Lezione n° 14

Lezione n° 14

Teoria della dualità:

-  Coppia di Problemi Primale/Duale -  Regole di Trasformazione

-  Teorema debole della dualità

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica Università degli Studi di Salerno

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

Teoria della Dualità

Ad ogni problema di PL (Primale) è associato un problema Duale

Problema Primale (P)

min c₁x₁ ++ c_nx_n s.t.

a₁₁x₁ ++ a_1nx_n ≥ b₁



a_m1x₁ ++ a_mnx_n ≥ b_m x ≥ 0

Problema Duale (D)

0 . . max

1 1

1 1

1 11

1 1

≥

≤ +

+

≤ +

+

+ +

w

c w

a w

a

c w

a w

a t s

w b w

b

n m

mn n

m m

m m









(n variabili, m vincoli) (m variabili, n vincoli)

Il problema D ha tante variabili quanti sono i vincoli di P e tanti vincoli quante sono le variabili di P.

Teoria della Dualità

33 32

31

23 22

21

13 12

11

a a

a

a a

a

a a

a

3 2

1 c c c

3 2 1

b b b

3 2

1 x x x

3 2 1

w w w

0 . .

min

3 3

33 2

32 1

31

2 3

23 2

22 1

21

1 3

13 2

12 1

11

3 3 2

2 1

1

≥

≥ +

+

≥ +

+

≥ +

+

+ +

x

b x

a x

a x

a

b x

a x

a x

a

b x

a x

a x

a t s

x c x

c x

c

t s

w b w

b w

.

b

max _{1 1} + _{2 2} + _{3 3}

1 3

31 2

21 1

11w a w a w c

a + + ≤

0 ,

0 ,

0 _{2 3}

1

3 3

33 2

23 1

13

2 3

32 2

22 1

12

≥

≥

≥

≤ +

+

≤ +

+

w w

w

c w

a w

a w

a

c w

a w

a w

a

In forma matriciale:

n T

x x

b x

A x c (P)

∈ R

≥

≥ 0

min

m T

T

w w

c w

A w b

D

∈R

≥

≤ 0

max )

(

Problema Primale (P) Problema Duale (D)

min c₁x₁ ++ c_nx_n s.t.

a₁₁x₁ ++ a_1nx_n ≥ b₁



a_m1x₁ ++ a_mnx_n ≥ b_m

x ≥ 0 0

. . max

1 1

1 1

1 11

1 1

≥

≤ +

+

≤ +

+

+ +

w

c w

a w

a

c w

a w

a t s

w b w

b

n m

mn n

m m

m m









Teoria della Dualità

0 5

1

1 4

2 1 2

4 3

7 2 3

2 1 x x

3 2 1

w w w

0 ,

7 5

1

2 4

3 2

1 2

. .

4 3

min

2 1

1 2 1

2 1

2 1

≥

≥

≥ +

≥ +

+

x x

x x x

x x

t s

x x

t s

w w

w .

7 2

3

max ₁ + ₂ + ₃

3 5

1 4

2w₁ + w₂ + w₃ ≤

0 ,

0 ,

0

4 2

1

3 2

1

2 1

≥

≥

≥

≤ +

w w

w

w w

Duale di un Primale con vincoli di uguaglianza:

n T

R x

x

b x

A x c (P)

∈

≥

= 0

min

Trasformiamo i vincoli di uguaglianza in vincoli di maggiore o uguale come segue:

b

A =x equivale a

b x

A b

x A

b x

A

−

≥

−

⇒

≤

≥

quindi si introducono 2m variabili duali, u e v

m T T

T T

R v

, u

v u

c v

A u

A

) v b u

b (

∈

≥

≥

≤

−

−

0 ,

0 max

n T

R x

x

b x

A

b x

A x c (P)

∈

≥

−

≥

−

≥ 0

min

b b A −

A v −

u

c x

e sostituendo w= u - v si ottiene (D)

m T T

T T

R v

, u

v u

c v

A u

A

) v b u

b (

∈

≥

≥

≤

−

−

0 ,

0 max

m T

T

R w

v n w

c w

A w b

(D)

∈

≤ . . max

n T

R x

x

b x

A x c (P)

∈

≥

= 0

min

Dualità: regole di trasformazione generali

i i

i

i i

i

i i

i

i i

i

i i

i

i i

i

c A

w x

c A

w x

c A

w x

w b

x A

w b

x A

w b

x A

c b

b c

=

≥

≤

≤

≥

=

≤

≤

≥

≥

ata non vincol

0 0

ata non vincol

0 0 max min

Teoria della Dualità

1 8

- 9

12 7

0

8 - 4

1

0 3

5

7 4 2

3 2

1 x x x

3 2 1

w w w

0 ,

,

7 8

9

4 12

7

2 8

4 . .

3 5

min

3 2 1

3 2

1

3 2

3 2

1

2 1

≥

= +

−

≤ +

≥

− +

+

x x x

x x

x

x x

x x

x t s

x x

. .

7 4

2

max _{1 2 3}

t s

w w

w + +

. . ,

0 ,

0

0 12

8

3 8

7 4

5 9

3 2

1

3 2

1

3 2

1

3 1

v n w w

w

w w

w

w w

w

w w

≤

≥

≤ +

+

−

≤

− +

≤ +

La teoria della Dualità è importante perchè:

  le soluzioni di (P) e (D) sono legate tra loro;

  la soluzione ottima del duale è un bound sulla soluzione ottima del primale.

  le soluzioni duali hanno un’interpretazione economica utile per l’analisi di sensitività (post-ottimalità);

  sulla teoria della dualità sono basati algoritmi, quali il Simplesso Duale e l’Algoritmo Primale-Duale, alternativi al Simplesso (Primale) utili per certe classi di problemi;

  può in certi casi essere conveniente risolvere D al posto di P (conviene risolvere il problema con il minor numero di vincoli)

Risultati fondamentali della Teoria della Dualità

Siano dati i problemi

0

min

≥

≥ x

b x

A x c

(P) ^T

0

max )

(

≥

≤ w

c w

A w b D

T T

1. Teorema (debole) della dualità

Siano x e w soluzioni ammissibili rispettivamente per (P) e (D), allora

w b

x

c^T ≥ ^T

Dimostrazione:

⇒

≥

⇒

≥

≥

⇒

) ˆ ( ˆ

ˆ ˆ 0

Poichè

ˆ soluzione ˆ

b w x

A w

w

b x

A x

T T

c x w

A x x

c w

A w

T T T T

ˆ ˆ

ˆ

ˆ 0 Poichè

ˆ soluzione ˆ

≤

⇒

≥

≤

⇒

xˆ^Tc = c^T x ≥ ˆˆ x^T A^T wˆ

Poichè x y = y^T x^T

Poichè

(x y)^T = y^T x^T

(A ˆx)^T w ≥ bˆ ^T w ⇒ ˆxˆ ^TA^T w ≥ bˆ ^T w ˆ

≥ b^T wˆ Quindi:

Risultati fondamentali della Teoria della Dualità

Corollario 1

Se x è una soluzione ammissibile per (P) e w una soluzione

ammissibile per (D) tali che c^Tx=b^Tw allora x e w sono soluzioni ottime dei rispettivi problemi.

Dimostrazione.

Supponiamo per assurdo che x non sia ottimo per (P). Quindi esiste un’altra soluzione ammissibile x* di (P) tale che c^Tx*< c^Tx. Ma poiché per ipotesi

c^Tx=b^Tw si ha che c^Tx*<b^Tw. Assurdo perchè va contro la tesi del teorema debole della dualità.

Risultati fondamentali della Teoria della Dualità

Corollario 2

Se il problema primale (P) è illimitato inferiormente allora il duale (D) è inammissibile. Viceversa se il duale (D) è illimitato

superiormente il primale (P) è inammissibile.

Dimostrazione.

Supponiamo che il valore ottimo del primale (P) sia -∞ e che il problema duale ammetta una soluzione w. Dal teorema della dualità debole si ha che c^Tx≥b^Tw per una qualsiasi soluzione ammissibile x di (P). Questo implica che b^Tw ≤ -∞. Assurdo.

Risultati fondamentali della Teoria della Dualità

Il corollario 2 stabilisce che l’illimitatezza di un problema implica l’inammissibilità del suo duale. Tuttavia questa non è una

proprietà simmetrica ossia se un problema è inammissibile non è detto che il suo duale sia illimitato. Per esempio:

0 1

1

min

2 1

2 1

2 1

2 1

≥

≥

−

≥ +

−

−

−

,x x

x x

x x

x x

(P) Calcolare il duale di (P) e

risolvere entrambi i problemi graficamente