Lezione n° 15

Lezione n° 15

Teoria della dualità:

-  Teorema forte della dualità

-  Teorema degli scarti complementari

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica Università di Salerno

Prof. Cerulli – Dott.ssa Gentili – Dott. Carrabs

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.

*

* b w

x

c^T = ^T

0

min

≥

= x

b x

A

x c

(P)

n.v.

w

c w

A

w b

(D)

T T

max

≤

Dim.: Sia x^* la soluzione ottima del primale e sia B la base ad esso associata.

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

= ⎡

−

0

1

*

* * A b

x

x x ^B

N

B quindi

c

x

= c

x

= c

A

b

Sia w^*T = c_B^TA_B^-1 , vogliamo dimostrare che questo

vettore è una soluzione ammissibile ed ottima per (D).

0

min

≥

= x

b x

A

x c

(P)

n.v.

w

c w

A

w b

(D)

T T

max

≤

•  Ammissibilità (w^*T = c_B^TA_B^-1 ):

[ ^c

^{− c}

^{| c}

^A

^A

^{− c}

] [ ^{= 0 | c}

^A

^A

^{− c}

] ^{≤ 0}

=

c w

A

≤ ⇔ ^w

^A _≤ ^c

⇒ ^c

^A

^A ≤ ^c

T T

B T

B

A A c

c

− ≤ 0

[ ] ⁻ [ ] [ ⁼

] [ ⁻ ] ⁼

− T

N T

N B B

T B T

B T

N T

N B B

B T

B

A A A c c c c A A c c

c

| | |

|

⇔

Poichè è la condizione di ottimalità per (P) (problema di minimizzazione), è verificata l’ammissibilità.

T T

N N

B T

BA A c

c ⁻¹ − ≤ 0

Il valore della funzione obiettivo duale in w^*T è:

w^*Tb= c_B^TA_B^-1b = c_B^Tx^*_B = c^Tx^*

Dal Corollario 1 del teorema della dualità debole sappiamo che, essendo c^Tx^*= w^*Tb, anche w^*T è ottima.

•  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: w^*T = c^T_BA_B^-1

Riassumendo

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

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

Se (P) inammissibile ⇒ (D) illimitato o inammissibile

*

* b w

x

c^T = ^T

[ ]

0 0

min

|

≥

≥

= +

+

=

N B

N N

B B

N T

N B

T B

N B

x x

b x

A x

A

x c

x c

A A

A

libere w

c A

w

c A

w w b

T N N

T

T B B

T T

. var max

≤

≤

una sol. di base (che soddisfa le cond. di ottimalità) per (P)

⎥ ⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

= ⎡

−

0

1

b A

x

x x

N B

la corrispondente per (D)

−1

=

T

c A

w

l’ammissibilità per (P)

1

0

≥

⇒

∈ X A

b

x

l’ammissibilità per (D)

⎩⎨

⎧

≤

⇒ ≤

∈ ₋

−

T N N

B T

B

T B B

B T T B

c A

A c

b

c A

A c

W a

w ) ( )

) (

)

1 1

0 )

)

1 − ≤

≤

− T

N N

B T

B

T B T

B

c A

A c

b

c c

a (vera sempre)

N j

c a

A

c^T_{B B}⁻¹ _j − _j ≤ 0 ∈ sono le (n-m)

condizioni di ottimalità (costi ridotti) di (P)

*

* b w

x

c^T = ^T

  Solo in corrispondenza dell’ottimo dalla base B ammissibile per (P) si ottiene una soluzione ammissibile per (D) (che in particolare è anche ottima).

−1

= ^T_{B B}

T c A π

  Ad una generica iterazione del simplesso dalla base corrente per (P) si può costruire un vettore

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

^A

^A

^{− c}

)

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 x A x b x

T

≥

≥ 0

surplus di

m s

n x

b s

I x

A

x c^T

. var 0

. var 0

min

≥

≥

=

−

0 max

) (

≥

≤ w

c w

A w b D

T T

slack di

n v

m w

c v

I w

A

w b

T

T

. var 0

. var 0

max

≥

≥

= +

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

dove a^j è la j-esima riga di A

a_i è la i-esima colonna di A

n i

x w a

c x

v

m j

w b

x a w

s

i T

i i

i i

j j

j j

j

, ,

1 0

) (

, ,

1 0

) (

…

…

=

=

−

=

=

=

−

=

0

0 2 5 1

4 2 3

max

2 1

2 1

2 1

2 1

≥

≥

≤ +

−

≤ +

−

+

−

x x

x x

x x

x x

Esercizio

0

0 2 5 1

4

2 z 3

max

2 1

2 1

2 1

2 1

≥

≥

≤ +

−

≤ +

−

+

−

=

x x

x x

x x

x x

Esercizio

0

0

2 3

2 1 1

5 4

g min

2 1

2 1

2 1

2 1

≥

≥

≥ +

−

≥

−

−

+

=

w w

w w

w w

w w

(P) (D)

5 ,

4

, 1 ₂

1 = x = z =

x ^z ₌ ⁵ _≤¹⁰ ₌ ^g w₁ = 0, w₂ = 2 ,g =10

7 ,

6

,

2 ₂

1 = x = z =

x _{, 1 , 7}

2 1

2

1 = w = g =

w

0

0 2 5 1

4

2 z 3

max

2 1

2 1

2 1

2 1

≥

≥

≤ +

−

≤ +

−

+

−

=

x x

x x

x x

x

x Esercizio

0

0

2 3

2 1 1

5 4

g min

2 1

2 1

2 1

2 1

≥

≥

≥ +

−

≥

−

−

+

=

w w

w w

w w

w w

(P) (D)

0

, 0

5 2

1

4

2 z 3

max

2 2

1

1 2

1

2 1

≥

≥

= +

+

−

= +

+

−

+

−

=

s x

s x

x

s x

x

x x

0

, 0

2 - 3

1

2 1

5 4

g min

2 2

1

1 2

1

2 1

≥

≥

= +

−

=

−

−

−

+

=

v w

v w

w

v w

w

w w

Esercizio

(P) (D)

0

, 0

5 2

1

4

2 z 3

max

2 2

1

1 2

1

2 1

≥

≥

= +

+

−

= +

+

−

+

−

=

s x

s x

x

s x

x

x x

0

, 0

2 - 3

1

2 1

5 4

g min

2 2

1

1 2 1

2 1

≥

≥

= +

−

=

−

−

−

+

=

v w

v w

w

v w w

w w

0 ,

0 6

,

2 _{2 1 2}

1 = x = ⇒ s = s =

x ^{, 1 0 0}

2 1

2 1

2

1 = w = ⇒ v = ,v =

w 2 0 0 1

2 ) 1 6 2

4 ( )

4

( _{1 2 1}

1

=

∗

=

∗

− +

=

∗

−

+ x x w

s 





0 1

0 1

) 6 1 5 ( 2 )

5 1

( _{1 2 2}

2

=

∗

=

∗

− +

=

∗

−

+ x x w

s  



 



0 2

0 2

) 2 1

1 2

( 1 )

2 1

( ₁ 1 _{2 1}

1

=

∗

=

∗ +

−

−

=

∗ +

−

−w w x

v  



 



0 6

0 6

2) 1 3

2 (1 2)

( _{1 2} 3 ₂

2

=

∗

=

∗

− +

=

∗

−

+ w x

w

v 







0 )

(

0 )

(

=

−

=

=

−

=

i T

i i i

i

j j

j j

j

x w a c

x v

w b

x a w

s