Lezionidi RicercaOperativa Lezionen 14 °

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. 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.

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

𝑐

𝑇

𝑥

∗

= 𝑐

"#

𝑥

"∗

= 𝑐

"#

𝐴

"$%

𝑏

• Ammissibilità (𝑤

∗#

= 𝑐

_"#

𝐴

$%_"

):

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

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

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 𝑤∗" è:

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

• Ottimalità:

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:

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)

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

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, … , 𝑚

𝑣

_'

𝑥

_'

= 𝑐

_'

− 𝑎

_'#

𝑤 𝑥

_'

= 0

𝑖 = 1, … 𝑛

condizioni di ortogonalità

• Per ogni vincolo non soddisfatto all’uguaglianza dalla soluzione

ottima di (P) (𝑎'𝑥 > 𝑏_'), la variabile duale 𝑤_' associata a questo

vincolo DEVE essere uguale a zero nella soluzione ottima di (D).

• Per ogni variabile 𝑥₍ non nulla nella soluzione ottima di (P), il

corrispondente vincolo in (D) DEVE essere soddisfatto

all’uguaglianza (𝑐₍ = 𝑎₍"𝑤) dalla soluzione ottima di (D).

Conseguenze dell condizioni di ortogonalità

𝑠_'𝑤_' = 𝑎'𝑥 − 𝑏_' 𝑤_' = 0 𝑗 = 1, … , 𝑚

𝑣₍𝑥₍ = 𝑐₍ − 𝑎₍"𝑤 𝑥₍ = 0 𝑖 = 1, … 𝑛

condizioni di ortogonalità

Relazioni analoga si ricava partendo dalla soluzione ottima del duale. Queste relazioni saranno utili per l’interpretazione economica delle variabili duali.

Sia (P) un problema di PL in forma standard e sia 𝑥∗ una soluzione di

base ammissibile ottima (non degenere) di (P). A partire da 𝑥∗ le

condizioni degli scarti complementari individuano un’unica soluzione ottima del duale.

Calcolo della soluzione ottima duale

𝑃 𝑚𝑖𝑛 − 𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ − 𝑥₃ = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0 𝐷 𝑚𝑎𝑥 𝑤₁ + 4𝑤₂ 𝑤₁ + 𝑤₂ ≤ −1 𝑤₁ + 2𝑤₂ ≤ −2 -𝑤₁ ≤ 0 𝑤₂ ≤ 0 𝑤 𝑛. 𝑣. Esempio 𝑥_#∗ = 𝑥)∗ 𝑥_*∗ = 𝐴$%# 𝑏 = 0 %⁄ ) −1 %⁄ ) 1 4 = 21 Base ottima B={2,3}.

Calcolo della soluzione ottima duale

𝑃 𝑚𝑖𝑛 − 𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ − 𝑥₃ = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0 𝐷 𝑚𝑎𝑥 𝑤₁ + 4𝑤₂ 𝑤₁ + 𝑤₂ ≤ −1 𝑤₁ + 2𝑤₂ ≤ −2 -𝑤₁ ≤ 0 𝑤₂ ≤ 0 𝑤 𝑛. 𝑣. Scarti complementari 𝑤₁(𝑥₁ + 𝑥₂ − 1) = 0 𝑤₂(4 − 𝑥₁ − 2𝑥₂) = 0 −1 − 𝑤₁ − 𝑤₂ 𝑥₁ = 0 −2 − 𝑤₁ − 2𝑤₂ 𝑥₂ = 0 𝑥∗ = 0 2 1 0 𝑤₁(0 + 2 − 1) = 0 𝑤₂(4 − 0 − 4) = 0 −1 − 𝑤₁ − 𝑤₂ 0 = 0 −2 − 𝑤₁ − 2𝑤₂ 2 = 0 𝑤₁ = 0 𝑤₂ = −1

Sia (P) un problema di PL in forma standard e sia 𝑥∗ una soluzione di

base ammissibile ottima (non degenere) di (P). A partire da 𝑥∗ le

condizioni degli scarti complementari individuano un’unica soluzione ottima del duale.

Calcolo della soluzione ottima duale

𝑠_'𝑤_' = 𝑎'𝑥 − 𝑏_' 𝑤_' = 0 𝑗 = 1, … , 𝑚 (1)

𝑣₍𝑥₍ = 𝑐₍ − 𝑎₍"𝑤 𝑥₍ = 0 𝑖 = 1, … 𝑛 (2)

Se (P) è in forma standard il sistema (1) è sempre soddisfatto. Perche?

Poiché 𝑥∗ una soluzione di base ammissibile ottima (non degenere) il

sistema (2) si riduce a:

𝑐₍ − 𝑎₍"𝑤 = 0 𝑖 ∈ 𝐵 ⟹ 𝑐_𝐵 − 𝐴_#"𝑤 = 0 ⟹ 𝐴_#"𝑤 = 𝑐_𝐵

Data la non singolarità della matrice 𝐴_# il precedente sistema ammette

un’unica soluzione ossia: 𝑤𝑇 _{= 𝑐}

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

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

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

𝑃 𝑚𝑎𝑥 𝑧 = −𝑥_! + 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

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