Lezione n°13

(1)

Lezione n

°

13

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

(2)

Teoria della Dualità

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

Problema Primale (P)

min c

₁

x

₁

₊

+ c

_n

x

_n

s.t.

a

₁₁

x

₁

+

+ a

_1n

x

_n

≥ b

₁



a

_m1

x

₁

+

+ a

_mn

x

_n

≥ b

_m

x ≥ 0

Problema Duale (D)

0 .

.

max

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

!

"

!

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

(3)

Teoria della Dualità

33

32

31

23

22

21

13

12

11 a

a

3

2

1 c

c

3

2

1 b

b

3

2

1 x

x

3

2

1 w

w

0 .

.

min

3

33

2

32

1

31

2

3

23

2

22

1

21

1

3

13

2

12

1

11

3

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

3

31

2

21

1

11 w

a

w

a

w

c

a

+

£

0 ,

0 ₂

₃

1

3

33

2

23

1

13

2

3

32

2

22

1

12 ³

³

£

+

£

+

w

c

w

a

w

a

w

a

c

w

a

w

a

w

a

(4)

In forma matriciale:

n

T

x

b

x

A

x

c

(P)

R

Î

³

0 min

m

T

w

c

w

A

w

b

D

R

Î

³

£

0 max

)

(

Problema Primale (P)

_{Problema Duale (D)}

min c

₁

x

₁

+

+ c

_n

x

_n

s.t.

a

₁₁

x

₁

+

+ a

_1n

x

_n

≥ b

₁



a

_m1

x

₁

++ a

_mn

x

_n

≥ b

_m

x ≥ 0

0 .

.

max

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

!

"

!

(5)

Teoria della Dualità

0

5

1

4

2

1

2

4

3

7

2

3

2

1 x

x

3

2

1 w

w

0 ,

7

5

1

2

4

3

2

1

2 .

.

4

3 min

2

1

2

1

2

1

2

1 ³

³

+

³

+

x

t

s

x

t

s

w

.

7

2

3 max

₁

+

₂

+

₃

3

5

1

4

2 w

₁

+

w

₂

+

w

₃

£

0 ,

0

4

2

1

3

2

1

2

1 ³

³

£

+

w

(6)

Duale del problema duale

(P) max b

T

w

A

T

w ≤ c

w ≥ 0

w ∈ R

m

−min - b

T

w

−A

T

w ≥ −c

w ≥ 0

w ∈ R

m

Il duale di questo

problema è:

−max -c

T

x

− Ax ≤ −b

x ≥ 0

x ∈ R

n

(D) min c

T

x

Ax ≥ b

x ≥ 0

x ∈ R

n

Il duale del problema duale è il problema primale.

-𝐴

!

-𝑏

T

-𝑐

w

(7)

n

T

R

x

b

x

A

x

c

(P)

Î

³

=

0 min

Trasformiamo i vincoli di uguaglianza in vincoli di

maggiore o uguale come segue:

b

x

A

=

equivale a

b

x

A

b

x

A

b

x

A

-³

-Þ

£

³

(8)

quindi si introducono

2m variabili duali, u e v

m

T

R

v

,

u

v

u

c

v

A

u

A

)

v

b

u

b

(

Î

³

£

-0

,

0 max

n

T

R

x

b

x

A

b

x

A

x

c

(P)

Î

³

-³

0 min

b

-A

A

-v

u

c

x

(9)

e sostituendo

w= u - v

si ottiene (D)

m

T

R

v

,

u

v

u

c

v

A

u

A

)

v

b

u

b

(

Î

³

£

-0

,

0 max

m

T

R

w

v

n

w

c

w

A

w

b

(D)

Î

£

.

max

n

T

R

x

b

x

A

x

c

(P)

Î

³

=

0 min

(10)

• Dato un generico problema di PL, sarebbe

possibile trasformarlo in uno equivalente in forma

canonica di min/max per calcolarne il duale

• In realtà, questo non è necessario, in quanto è

sempre possibile calcolare direttamente il duale

del problema dato

(11)

Teoria della Dualità

1

8

9

12

7

0

8

4

1

0

3

5

7

4

2

3

2

1 x

x

3

2

1 w

w

max

5x

₁

+ 3x

₂

s.t.

x

₁

+ 4x

₂

8x

₃

2 7x

₂

+ 12x

₃

_{ 4}

9x

₁

8x

₂

+ x

₃

= 7

x

₁

, x

₂

, x

₃

0 min

2w

₁

+ 4w

₂

+ 7w

₃

s.t.

w

₁

+ 9w

₃

5 4w

₁

+ 7w

₂

8w

₃

3 8w

₁

+ 12w

₂

+ w

₃

0 w

₁

_{ 0, w}

₂

0, w

₃

n.v.

(12)

min

max

c

T

c

b

T

A

T

≥

≥ 0

≤

≤ 0

=

n.v.

≥ 0

≤

≤ 0

≥

n.v.

₌

Coefficienti f.o.

Termini noti vincoli

Coefficienti vincoli

Dualità: regole di trasformazione generali

Coefficienti f.o.

Termini noti vincoli

Coefficienti vincoli

i-mo

vincolo

(i=1…m

)

i-ma

variabile

(i=1…m

)

j-ma

variabile

(j=1...n)

j-mo

vincolo

(j=1...n)

(13)

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, l’Algoritmo Primale-Duale, il Delayed

Column Generation alternativi al Simplesso (Primale) utili per

certe classi di problemi;

● può in certi casi essere conveniente risolvere D al posto di P

(14)

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

1. Teorema (debole) della dualità

Siano x e w soluzioni ammissibili rispettivamente per

(P) e (D), allora

w

b

x

(15)

Dimostrazione:

ˆ

x soluzione ammissibile di P

=

₎

Aˆ

x

b

(1)

Poich`e ˆ

w soluzione ammissibile di D

=

₎

c

T

w

ˆ

T

A

(3)

Dalle disequazioni (2) e (3), sapendo che ˆ

x

0 si ha: c

T

x

ˆ

w

ˆ

T

Aˆ

x

w

ˆ

T

b

0 min

³

x

b

x

A

x

c

(P)

T

0 max

)

(

³

£

w

c

w

A

w

b

D

T

(16)

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

T

_x=b

T

_{w 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

T

_{x*< c}

T

_{x. Ma poiché per ipotesi}

c

T

_x=b

T

_{w si ha che c}

T

_x*<b

T

_{w. Assurdo perchè va contro la tesi del teorema}

(17)

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

T

_x≥b

T

_{w per una qualsiasi soluzione ammissibile x di (P). Questo implica che}

(18)

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

(P)

Calcolare il duale di

(P)

e

risolvere entrambi i problemi

graficamente