Lezionidi RicercaOperativa Lezionen 14 °

(1)

Lezione n

°

14

Teoria della dualità:

- Teorema forte della dualità

- Teorema degli scarti complementari - Relazioni tra il primale e il duale

R. Cerulli

–

F. Carrabs

Lezioni di Ricerca Operativa

(2)

2. Teorema forte della dualità

Data una coppia di problemi primale duale, (P) e (D), se uno dei due problemi ammette una soluzione ottima finita, allora anche l’altro problema ammette una soluzione ottima finita ed i valori ottimi delle funzioni obiettivo coincidono, i.e.

(3)

Dim.: Sia 𝑥∗ la soluzione ottima del primale e sia B la base ad esso associata.

quindi

Sia 𝑤∗" = 𝑐_#"𝐴_#$%. Vogliamo dimostrare che questo vettore è una

soluzione ammissibile ed ottima per (D).

𝑃 𝑚𝑖𝑛 𝑐"𝑥 A𝑥 = 𝑏 𝑥 ≥ 0 𝐷 𝑚𝑎𝑥 𝑏"𝑤 AT_{𝑤 ≤ 𝑐} 𝑤 𝑛. 𝑣. 𝑥∗ = 𝑥# ∗ 𝑥_&∗ = 𝐴$%_# 𝑏 0

𝑐

𝑇

𝑥

∗

= 𝑐

"#

𝑥

"∗

= 𝑐

"#

𝐴

"$%

𝑏

(4)

• Ammissibilità (𝑤

∗#

= 𝑐

_"#

𝐴

$%_"

):

𝑃 𝑚𝑖𝑛 𝑐"𝑥 A𝑥 = 𝑏 𝑥 ≥ 0 𝐷 𝑚𝑎𝑥 𝑏"𝑤 AT_{𝑤 ≤ 𝑐} 𝑤 𝑛. 𝑣. 𝐴𝑇_𝑤∗ _{≤ 𝑐 ⟹ 𝑤}∗"_{𝐴 ≤ 𝑐}" _{⟹ 𝑐} #"𝐴#$%𝐴 ≤ 𝑐" ⟹ 𝑐#"𝐴$%# 𝐴 − 𝑐" ≤ 0

𝑐_#"𝐴_#$% 𝐴_# | 𝐴_& − 𝑐_#" | 𝑐_&" = 𝑐_#"𝐴$%_# 𝐴_# |𝑐_#"𝐴$%_# 𝐴_& − 𝑐_#" | 𝑐_&" =

(5)

Dal Corollario 1 del teorema debole della dualità, poichè 𝑤∗"𝑏 =

𝑐𝑇_𝑥∗ _{allora w}*T _{è ottima per (D).}

Poichè 𝑐_#"𝐴_#$%𝐴_& − 𝑐_&" ≤ 0" è la condizione di ottimalità per (P)

(problema di minimizzazione), l’ammissibilità è verificata.

Il valore della funzione obiettivo duale in 𝑤∗" è:

𝑤∗"𝑏 = 𝑐_#"𝐴$%_# 𝑏 = 𝑐_#"𝑥_#∗ = 𝑐𝑇_𝑥∗

(6)

Dal teorema della dualità forte ricaviamo che, data la base ottima B del primale, è possibile calcolare velocemente la soluzione ottima del duale (D) tramite l’equazione:

(7)

Riassumendo

Se (P) è illimitato ⟹ (D) non è ammissibile

(P) ha soluzione ottima finita ⟺ (D) ha soluzione ottima finita

(ed i valori delle loro f.o. coincidono)

(8)

Il Teorema dello “scarto complementare”

(Complementary Slackness Theorem)

Consideriamo la coppia di problemi (P) e (D) in forma canonica e trasformiamoli in forma standard

𝑃 𝑚𝑖𝑛 𝑐"𝑥 A𝑥 ≥ 𝑏 𝑥 ≥ 0 𝐷 𝑚𝑎𝑥 𝑏"𝑤 AT_{𝑤 ≤ 𝑐} 𝑤 ≥ 0 𝑚𝑖𝑛 𝑐"𝑥 A𝑥 − 𝐼𝑠 = 𝑏 𝑥 ≥ 0 𝑛 var. 𝑠 ≥ 0 𝑚 var. di surplus 𝑚𝑎𝑥 𝑏"𝑤 AT_{𝑤 + 𝐼𝑣 = 𝑐} 𝑤 ≥ 0 𝑚 var. 𝑣 ≥ 0 𝑛 var. di slack

(9)

Ad ogni variabile di (P) è associato un vincolo di (D) e quindi la corrispondente variabile di slack/surplus 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

dove aj _{è la j-esima riga di A}

a_i è la i-esima colonna di A

𝑠

_&

𝑤

_&

= 𝑎

&

𝑥 − 𝑏

_&

𝑤

_&

= 0

𝑗 = 1, … , 𝑚

(10)

Esercizio

1. Scrivere il duale del problema e determinare una coppia di soluzioni primale-duale

ammissibile.

2. Verificare che le soluzioni trovare soddisfano il teorema debole della dualità.

3. Verificare se le soluzioni trovate sono ottime per i rispettivi problemi.

4. Risolvere graficamente il primale ed individuare il punto di ottimo e la base B.

5. Calcolare la soluzione ottima del duale a partire dalla base ottima B.

6. Verificare utilizzando gli scarti complementari che le soluzioni trovate nei due punti

precedenti siano effettivamente ottime.

𝑚𝑎𝑥 − 𝑥_% + 3 2 𝑥' −𝑥_% + 𝑥_' ≤ 4 − 1 2 𝑥% + 𝑥' ≤ 5 𝑥_% ≥ 0, 𝑥_' ≥ 0

(11)

Esercizio 𝑃 𝑚𝑎𝑥 𝑧 = −𝑥_! + 3 2 𝑥" −𝑥_! + 𝑥_" ≤ 4 −1 2 𝑥! + 𝑥" ≤ 5 𝑥_! ≥ 0, 𝑥_" ≥ 0 𝐷 𝑚𝑖𝑛 𝑔 = 4𝑤_! + 5𝑤_" −𝑤_! − 1 2 𝑤" ≥ −1 𝑤_! + 𝑤_" ≥ 3 2 𝑤_! ≥ 0, 𝑤_" ≥ 0 𝑥_% = 1, 𝑥_' = 4 ⟹ 𝑧 = 5 𝑤_% = 0, 𝑤_' = 2 ⟹ 𝑔 = 10

𝑧 = 5 ≤ 10 = 𝑔 Il Teorema debole è verificato?

Sol. Ammissibile per (P) Sol. Ammissibile per (D)

𝑥_% = 2, 𝑥_' = 6 ⟹ 𝑧 = 7 𝑤% =

1

2 , 𝑤' = 1 ⟹ 𝑔 = 7

(12)

X

-4 4 (2) (1) -10 5 Punto di ottimo x = (2,6) Base ottima B = {1,2} 𝑤∗ = 𝑐_$𝐴_$%! = −1 3 2 −2 2 −1 2 = [ 1 2 1] 𝑚𝑎𝑥 𝑧 = −𝑥_! + 3 2 𝑥" −𝑥_! + 𝑥_" ≤ 4 −1 2 𝑥! + 𝑥" ≤ 5 𝑥_! ≥ 0, 𝑥_" ≥ 0

(13)

𝑃 𝑚𝑎𝑥 𝑧 = −𝑥_! + 3 2 𝑥" −𝑥_! + 𝑥_" ≤ 4 −1 2 𝑥! + 𝑥" ≤ 5 𝑥_! ≥ 0, 𝑥_" ≥ 0 𝐷 𝑚𝑖𝑛 𝑔 = 4𝑤_! + 5𝑤_" −𝑤_! − 1 2 𝑤" ≥ −1 𝑤_! + 𝑤_" ≥ 3 2 𝑤_! ≥ 0, 𝑤_" ≥ 0 Esercizio 𝑃 𝑚𝑎𝑥 𝑧 = −𝑥_! + 3 2 𝑥" −𝑥_! + 𝑥_" + 𝑠_! = 4 −1 2 𝑥! + 𝑥" + 𝑠" = 5 𝑥 ≥ 0, 𝑠 ≥ 0 𝐷 𝑚𝑖𝑛 𝑔 = 4𝑤_! + 5𝑤_" −𝑤_! − 1 2 𝑤" − 𝑣! ≥ −1 𝑤_! + 𝑤_" − 𝑣_" ≥ 3 2 𝑤 ≥ 0, 𝑣 ≥ 0

(14)

Esercizio 𝑃 𝑚𝑎𝑥 𝑧 = −𝑥_! + 3 2𝑥" −𝑥_! + 𝑥_" + 𝑠_! = 4 −1 2𝑥! + 𝑥" + 𝑠" = 5 𝑥 ≥ 0, 𝑠 ≥ 0 𝐷 𝑚𝑖𝑛 𝑔 = 4𝑤_! + 5𝑤_" −𝑤_! − 1 2𝑤" − 𝑣! ≥ −1 𝑤_! + 𝑤_" − 𝑣_" ≥ 3 2 𝑤 ≥ 0, 𝑣 ≥ 0 𝑥_! = 2, 𝑥_" = 6 𝑤_! = 1 2, 𝑤" = 1

Sol. Ammissibile per (P)

Sol. Ammissibile per (D)

(4 + 𝑥_! − 𝑥_")𝑤_! &_! = 4 + 2 − 6 1 2 = 0 ∗ 1 2 = 0 (5 + 1 2 𝑥! − 𝑥")𝑤" &_" = 5 + 1 − 6 ∗ 1 = 0 ∗ 1 = 0 (−𝑤_! − 1 2 𝑤" + 1)𝑥! '_! = − 1 2 − 1 2 + 1 ∗ 2 = 0 ∗ 2 = 0 (𝑤_! + 𝑤_" − 3 2)𝑥" '_" = 1 2 + 1 − 3 2 ∗ 6 = 0 ∗ 6 = 0

Condizioni degli scarti complementari: 𝑠_𝑣#𝑤# = 0