Dualit`a forte e condizioni di ottimalit`a

Dualità forte e condizioni di ottimalità
I
Dualità forte
I
Dualità debole
I
Condizioni di scarto complementare
BT 4.3
Dualità debole
Teorema
Data una soluzione ammissibile x del problema primale (in forma
generica) ed una p del duale, risulta pT b ≤ cT x
Dimostrazione Definiamo le quantità
ui = pi (aTi x − bi )
vj = (cj − pT Aj )xj
Quindi:
X
ui = pT Ax − pT b;
i
X
vj = cT x − pT Ax
j
da cui:
X
i
ui +
X
j
vj = cT x − pT b
Dimostrazione (cont.)
ricordando le regole di costruzione:
primale
aTi x ≥ bi ,
aTi x ≤ bi ,
aTi x = bi ,
xj ≥ 0, j
xj ≤ 0, j
xj libero,
i ∈ M1
i ∈ M2
i ∈ M3
∈ N1
∈ N2
j ∈ N3
duale
pi ≥ 0, i ∈ M1
pi ≤ 0, i ∈ M2
pi libero, i ∈ M3
pT Aj ≤ cj , j ∈ N1
pT Aj ≥ cj , j ∈ N2
pT Aj = cj , j ∈ N3
si ha che:
ui ≥ 0, i = 1, . . . , m;
vj ≥ 0, j = 1, . . . , n.
da cui
0≤
X
i
ui +
X
j
v j = c T x − pT b
Conseguenze
Corollario
(a) se il primale è (inferiormente) illimitato, allora il duale è
inammissibile
(b) se il duale è (superiormente) illimitato, allora il primale è
inammissibile
Ottimo finito
Ottimo finito
Illimitato
Inammissibile
NO
Illimitato
NO
NO
SI
Inammissibile
SI
Dualità forte
Teorema
Se un problema di PL ha una soluzione ottima anche il suo duale
ce l’ha e i rispettivi valori coincidono
Dimostrazione (forma standard)
Consideriamo un problema
min cT x
s.t. Ax = b
x≥0
Applicando il metodo del simplesso (con una regola anticiclaggio), si
calcola una soluzione ottima x∗ associata alla base B. Alla terminazione
Test Opt → true:
cT − cTB B−1 A ≥ 0T
Dimostrazione (cont.)
Quindi, definendo pT = cTB B−1 risulta pT A ≤ cT , cioè, p è una
soluzione ammissibile del problema duale
max pT b
s.t.
pT A ≤ c T
ed inoltre si ha:
pT b = cTB B−1 b = cTB x∗B = cT x∗
cioè, p è una soluzione ottima del problema duale e i due valori
ottimi coincidono
Conseguenze
Ottimo finito
Illimitato
Inammissibile
Ottimo finito
SI
NO
NO
Illimitato
NO
NO
SI
Inammissibile
NO
SI
-
Infine, esistono problemi di PL per cui sia il primale che il duale
sono inammissibili.
Esercizio Dato il problema primale:
min x1 + 2x2
x1 + x2 = 1
2x1 + 2x2 = 3
x1 ≥ 0
x2 ≤ 0
scrivere il suo duale e verificare che sono entrambi inammissibili
Condizioni di scarto complementare
Teorema
Siano x e p soluzioni ammissibili risp. per il problema primale e
duale. Esse sono ottime se e solo se
pi (aTi x − bi ) = 0,
T
(cj − p Aj )xj = 0,
i = 1, . . . , m
(1)
j = 1, . . . , n
(2)
Dimostrazione Ricordiamo
dalla
P
P dimostrazione della dualità debole che
ui ≥ 0, vj ≥ 0 e che i ui + j vj = cT x − pT b. Quindi, se x e p
sono ottime, per il teorema della dualità forte si ha cT x − pT b = 0, cioè
ui = vj = 0, i = 1, . . . , m; j = 1, . . . , n.
Viceversa, se ui = vj = 0 per ogni i, j, si ha cT x − pT b = 0 che implica
x e p soluzioni ottime.
Interpretazione fisica
Una sfera solida giace in un poliedro descritto da disuguaglianze
aT x ≥ bi .
Soggetta alla forza di gravità, la sfera raggiunge il punto di minima
energia potenziale x∗ :
a4
a3
c
a1
a2
possiamo immaginare il punto di equilibrio come la soluzione
ottima del problema min cT x : aTi x ≥ bi , ∀i
Interpretazione fisica
all’equilibrio, la forza di gravità è bilanciata dalle spinte delle pareti,
ortogonali alle stesse, cioè allineate ai vettori ai . Quindi, si ha
c=
X
pi ai
i
con pi moltiplicatori non negativi.
In altre parole p è soluzione ammissibile del problema duale
max pT b
pT A = c T
p≥0
Interpretazione fisica
Inoltre:
I
per le pareti che non toccano la sfera si ha pi = 0
I
per le pareti che toccano la sfera si ha aTi x = bi
e quindi
pi (bi − aTi x∗ ) = 0
Di conseguenza, vale la relazione
pT b =
X
i
pi bi =
X
pi aTi x∗ = cT x∗
i
In altri termini, il vettore p è una soluzione ottima del problema
duale