Dualit` a forte

(1)

Dualit` a forte e condizioni di ottimalit` a

I

Dualit` a forte

I

Dualit` a debole

I

Condizioni di scarto complementare

BT 4.3

(2)

Dualit` a debole

Teorema

Data una soluzione ammissibile x del problema primale (in forma generica) ed una p del duale, risulta p

^T

b ≤ c

^T

x

Dimostrazione Definiamo le quantit` a

u

_i

= p

_i

(a

^T_i

x − b

_i

) v

_j

= (c

_j

− p

^T

A

_j

)x

_j

le regole di costruzione implicano che, in entrambi i casi, le due quantit` a moltiplicate hanno lo stesso segno, quindi, u

i

≥ 0, i = 1, . . . , m e v

j

≥ 0, j = 1, . . . , n. Risulta anche:

X

i

u

i

= p

^T

Ax − p

^T

b X

j

v

j

= c

^T

x − p

^T

Ax

da cui

0 ≤ X

i

u

i

+ X

j

v

j

= c

^T

x − p

^T

b

(3)

Conseguenze

Corollario

(a) se il primale ` e (inferiormente) illimitato, allora il duale ` e inammissibile

(b) se il duale ` e (superiormente) illimitato, allora il primale ` e inammissibile

Ottimo finito Illimitato Inammissibile

Ottimo finito NO

Illimitato NO NO SI

Inammissibile SI

(4)

Dualit` a forte

Teorema

Se un problema di PL ha una soluzione ottima anche il suo duale ce l’ha e i rispettivi valori coincidono

Dimostrazione (forma standard) Consideriamo un problema

min c

^T

x s.t. Ax = b x ≥ 0

Applicando il metodo del simplesso (con una regola anticiclaggio), si calcola una soluzione ottima x

^∗

associata alla base B. Alla terminazione Test Opt → true:

c

^T

− c

^T_B

B

⁻¹

A ≥ 0

^T

(5)

Dimostrazione (cont.)

Quindi, definendo p

^T

= c

^T_B

B

⁻¹

risulta p

^T

A ≤ c

^T

, cio` e, p ` e una soluzione ammissibile del problema duale

max p

^T

b s.t.

p

^T

A ≤ c

^T

ed inoltre si ha:

p

^T

b = c

^T_B

B

⁻¹

b = c

^T_B

x

^∗_B

= c

^T

x

^∗

cio` e, p ` e una soluzione ottima del problema duale e i due valori

ottimi coincidono

(6)

Conseguenze

Ottimo finito Illimitato Inammissibile

Ottimo finito SI NO NO

Illimitato NO NO SI

Inammissibile NO SI -

Infine, esistono problemi di PL per cui sia il primale che il duale sono inammissibili.

Esercizio Dato il problema primale:

min x

1

+ 2x

2

s.t.

x

1

+ x

2

= 1 2x

₁

+ 2x

₂

= 3

scrivere il suo duale e verificare che sono entrambi inammissibili

(7)

Condizioni di scarto complementare

Teorema

Siano x e p soluzioni ammissibili risp. per il problema primale e duale. Esse sono ottime se e solo se

p

_i

(a

^T_i

x − b

_i

) = 0, i = 1, . . . , m (1) (c

_j

− p

^T

A

_j

)x

_j

= 0, j = 1, . . . , n (2)

Dimostrazione Ricordiamo dalla dimostrazione della dualit` a debole che u

i

≥ 0, v

j

≥ 0 e che P

i

u

i

+ P

j

v

j

= c

^T

x − p

^T

b. Quindi, se x e p sono ottime, per il teorema della dualit` a forte si ha c

^T

x − p

^T

b = 0, cio` e u

_i

= v

_j

= 0, i = 1, . . . , m; j = 1, . . . , n.

Viceversa, se u

i

= v

j

= 0 per ogni i, j, si ha c

^T

x − p

^T

b = 0 che implica

x e p soluzioni ottime.

(8)

Interpretazione fisica

Una sfera solida giace in un poliedro descritto da disuguaglianze a

^T

x ≥ b

_i

.

Soggetta alla forza di gravit` a, la sfera raggiunge il punto di minima energia potenziale x

^∗

:

a₄

a₁ a₂

a₃ c

a₁

possiamo immaginare il punto di equilibrio come la soluzione

ottima del problema min c

^T

x : a

^T_i

x ≥ b

_i

, ∀i

(9)

Interpretazione fisica

all’equilibrio, la forza di gravit` a ` e bilanciata dalle spinte delle pareti, ortogonali alle stesse, cio` e allineate ai vettori a

_i

. Quindi, si ha

c = X

i

p

i

a

i

con p

i

moltiplicatori non negativi. Naturalmente, per le pareti che non toccano la sfera si ha p

_i

= 0, quindi risulta p

_i

(b

_i

− a

^T

x

^∗

), cio` e,

p

^T

b = X

i

p

i

b

i

= X

i

p

i

a

^T_i

x

^∗

= c

^T

x

^∗

In altri termini, il vettore p ` e la soluzione del problema duale max p

^T

b

p

^T

A = c

^T