Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 13: 27-28 Aprile 2009
Teoria della dualità:
- Teorema forte della dualità
- Teorema degli scarti complementari
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
2. Teorema (forte) della dualità
Se (P) e (D) ammettono soluzione ottima finita, allora
per ogni ottimo x* per (P) esiste una soluzione ottima
w* per (D) tale che
c x b w
T
*
T
*
La dimostrazione del Teorema della dualità forte
evidenzia che il valore della soluzione ottima di (D)
corrispondente alla soluzione ottima di (P) x *B  AB1 b
vale
*T
T 1
B B
w c A
Dim. Sia B la base associata a x*
*
1




A
x
*
B b
B
x  * 

x N   0 
Se c x  b w
T
*
T
quindi
*
T
B
1
B
Dimostriamo che w
*T
*T
T
*
*
T
B
1
B
T
B
1
B
c A Ac  0
T
B
*T
T
T
B
1
B
T
T

 

c A AB | AN   c | c  c  c | c A AN  c 

1
B
T
B

T
N
 0 | c A AN  c  0
T
B
T
N
T
B
T
B
T
B
1
B
1
B
c A
T
B
è ammissibile per (D):
A w c  w Ac  c A Ac
T
*
B
allora c A b  b w e w
T
B
*
1
B
c x c x c A b
T
T
N
Poichè c TB AB1 AN  c TN  0 è la condizione di ottimalità
per (P) (problema di minimizzazione), è verificata
l’ammissibilità.
Per la dualità debole
b wc x c x
T
T
*
 w ammissibil e
T
cT x* è estremo superiore per (D),
quindi la soluzione
w
*T
 c B AB1
T
ammissibile per cui c x  b w
T
*
T
*
è ottima per (D).
La base B è ottima per (P) e per (D). Siano infatti X e W
rispettivamente gli insiemi delle soluzioni ammissibili
per (P) e (D)
c x b w
T
*
A  AB | AN 
*
T
max b w
min c x B  c x N
T
B
T
T
N
w AB  c B
T
AB x B  AN x N  b
xB  0
 x B   AB1 b
x 

x N   0 
w AN  c N
T
xN  0
una sol. di base per (P)
T
T
w var .libere
la corrispondente per (D)
1
B
w c A
T
T
B
c x b w
T
*
l’ammissibilità per (P)
T
*
l’ammissibilità per (D)
 a)
T
w W  
b)
1
B
xX  A b0
(c B AB1 ) AB  c B
T 1
T
(c B AB ) AN  c N
T
(vera sempre)
a)
cB  cB
b)
c B AB1 AN  c N  0
T
T
T
T
c B AB1 a j  c j  0
T
T
jN
sono le (n-m)
condizioni di ottimalità
(costi ridotti) di (P)
c x b w
T
*
T
*
La base B è ottima se x e wT sono rispettivamente
ammissibili per (P) e (D).


Solo in corrispondenza dell’ottimo dalla base B
ammissibile per (P) si ottiene una soluzione
ammissibile per (D) (che in particolare è anche
ottima).
Ad una generica iterazione del simplesso dalla base
T
T 1


c
corrente per (P) si può costruire un vettore
B AB
che non è soluzione di (D).

Tale vettore è detto dei MOLTIPLICATORI DEL
SIMPLESSO e compare nel calcolo dei coefficienti
di costo ridotto (problema di min):
c
T
B
1
B
A
A
N
c
T
N

Il Teorema dello “scarto complementare”
(Complementary Slackness Theorem)
Consideriamo la coppia di problemi (P) e (D) in
forma canonica e trasformiamoli in forma standard
(P)
min c T x
Ax  b
x0
( D)
T
max b w
A wc
w0
T
Ax  I s  b
x  0 n var .
s  0 m var . di surplus
AT w  I v  c
w  0 m var .
v  0 n var . di slack
Ad ogni variabile di (P) è associato un vincolo di (D) e
quindi la corrispondente variabile di slack e viceversa.
3. Teorema della slackness complementare
Data la coppia di soluzioni x e w rispettivamente
ammissibili per (P) e (D), x e w sono ottime per (P) e
(D) se e solo se
s j w j  (a x  b j ) w j  0
j  1, , m
vi xi  (ci  a w) xi  0
i  1, , n
j
T
i
dove aj è il vettore riga j-esima di A
ai è il vettore colonna i-esima di A