n (5)Variabili-vincoli Esiste una stretta relazione tra variabili del primale e vincoli del duale

(1)

Dualitá

Dualit ´a – p. 1/44

(2)

Dualitá

Problema di PL in forma standard max cx

Ax = b x ≥ 0 Chiamato problema primale.

(3)

Dualitá

Problema di PL in forma standard max cx

Ax = b x ≥ 0

Chiamato problema primale.

A questo associato un altro problema di PL, detto problema duale:

min ub uA ≥ c

(4)

In forma scalare

Primale:

max Pn

j=1 c_jx_j Pn

j=1 a_ijx_j = b_i i = 1, . . . , m x_j ≥ 0 j = 1, . . . , n Duale

min Pm

i=1 u_ib_i Pm

i=1 u_ia_ij ≥ c_j j = 1, . . . , n

(5)

Variabili-vincoli

Esiste una stretta relazione tra

variabili del primale e vincoli del duale;

(6)

Variabili-vincoli

Esiste una stretta relazione tra

variabili del primale e vincoli del duale;

vincoli del primale e variabili del duale.

(7)

Continua

In particolare:

nel primale ci sono n variabili esattamente come nel duale vi sono n vincoli;

(8)

Continua

In particolare:

i coefficienti del j-esimo vincolo del duale coincidono con i coefficienti della variabile x_j nei vincoli del primale

(9)

Continua

In particolare:

i coefficienti del j-esimo vincolo del duale coincidono con i coefficienti della variabile x_j nei vincoli del primale il termine noto del j-esimo vincolo del duale coincide con il coefficiente di x_j nell’obiettivo del primale.

(10)

Continua

Nel primale vi sono m vincoli esattamente come nel duale vi sono m variabili;

(11)

Continua

i coefficienti dell’i-esima variabile u_i del duale

coincidono con i coefficienti dell’i-esimo vincolo del primale;

(12)

Continua

i coefficienti dell’i-esima variabile u_i del duale

coincidono con i coefficienti dell’i-esimo vincolo del primale;

il coefficiente di u_i nell’obiettivo del duale coincide con il termine noto dell’i-esimo vincolo del primale.

(13)

Esempio

Primale: max x1 + x2

3x1 + 2x2 + x3 = 5 4x¹ + 5x² + x⁴ = 4

x2 + x⁵ = 2

x1, x2, x3, x4, x5 ≥ 0

(14)

Esempio

3x1 + 2x2 + x3 = 5 ↔ u¹ 4x¹ + 5x² + x⁴ = 4 ↔ u² x2 + x⁵ = 2 ↔ u³ x1, x2, x3, x4, x5 ≥ 0

(15)

Esempio

Duale: min

↔ x1

↔ x2

↔ x³

↔ x⁴

↔ x⁵

(16)

Esempio

Duale: min

↔ x1

↔ x2

↔ x³

↔ x

(17)

Esempio

Duale: min

↔ x1

↔ x2

↔ x³

↔ x⁴

↔ x⁵

(18)

Esempio

Duale: min 5u¹ + 4u² + 2u³

↔ x1

↔ x2

↔ x³

↔ x

(19)

Esempio

3u1 + 4u2≥1 ↔ x1

↔ x2

↔ x³

↔ x⁴

↔ x⁵

(20)

Esempio

3u1 + 4u2≥1 ↔ x1

2u1 + 5u2 + u3≥1 ↔ x2

↔ x³

↔ x

(21)

Esempio

3u1 + 4u2≥1 ↔ x1

2u1 + 5u2 + u3≥1 ↔ x2

u1≥0 ↔ x³

↔ x⁴

↔ x⁵

(22)

Esempio

3u1 + 4u2≥1 ↔ x1

2u1 + 5u2 + u3≥1 ↔ x2

u1≥0 ↔ x³

u ≥0 ↔ x

(23)

Esempio

3u1 + 4u2≥1 ↔ x1

2u1 + 5u2 + u3≥1 ↔ x2

u1≥0 ↔ x³ u2≥0 ↔ x⁴ u3≥0 ↔ x⁵

(24)

Relazioni primale-duale

Indichiamo con

D_a = {u ∈ R^m : uA ≥ c}

la regione ammissibile del problema duale e con D_ott = {u^∗ ∈ D_a : u^∗b ≤ ub ∀ u ∈ D_a}

l’insieme delle sue soluzioni ottime.

Le soluzioni dei due problemi primale e duale sono fortemente legate tra loro

(25)

Continua

OsservazionePer ogni x0 ∈ S_a e per ogni u0 ∈ D_a si ha che cx0 ≤ u⁰b.

(26)

Continua

x0 ∈ S_a ⇒ Ax⁰ = b

(27)

Continua

x0 ∈ S_a ⇒ Ax⁰ = b ⇒ u⁰b = u⁰Ax0 = (u⁰A)x⁰

(28)

Continua

x0 ∈ S_a ⇒ Ax⁰ = b ⇒ u⁰b = u⁰Ax0 = (u⁰A)x⁰ x0 ∈ S_a ⇒ x⁰ ≥ 0

(29)

Continua

u0 ∈ D_a ⇒ u⁰A ≥ c

(30)

Continua

u0 ∈ D_a ⇒ u⁰A ≥ c ⇒

|{z}x0≥0

(u0A)x0 ≥ cx⁰

(31)

Continua

OsservazioneSe x^∗ ∈ S_a e u^∗ ∈ D_a ed inoltre cx^∗ = bu^∗

allora x^∗ ∈ S_ott e u^∗ ∈ D_ott.

(32)

Continua

Dall’osservazione precedente si ha che

∀ x ∈ S_a cx ≤ u^∗b.

(33)

Continua

∀ x ∈ S_a cx ≤ u^∗b.

Ma essendo cx^∗ = u^∗b si ha anche

(34)

Continua

∀ x ∈ S_a cx ≤ u^∗b.

Ma essendo cx^∗ = u^∗b si ha anche

∀ x ∈ S_a cx ≤ cx^∗ e quindi x^∗ ∈ S_ott.

(35)

Continua

OsservazioneSe uno dei due problemi ha obiettivo illimitato, allora l’altro ha regione ammissibile vuota.

(36)

Continua

obiettivo primale illimitato ⇒ D_a = ∅

(37)

Continua

Per assurdo sia D_a 6= ∅ e sia u0 ∈ D_a. In base alla prima osservazione si ha:

(38)

Continua

Per assurdo sia D_a 6= ∅ e sia u0 ∈ D_a. In base alla prima osservazione si ha:

∀ x ∈ S_a cx ≤ u⁰b

e quindi l’obiettivo del primale é limitato dal valore u0b, il che contraddice l’illimitatezza di tale obiettivo.

(39)

Continua

Problema primale

↓

Problema duale

(40)

Continua

Problema primale

↓

Problema duale

↓ Problema duale del duale

(41)

Continua

Problema primale

↓

Problema duale

↓

Problema duale del duale≡ Problema primale

(42)

Continua

Problema primale

↓

Problema duale

↓

Problema duale del duale≡ Problema primale

Osservazione: Il duale del problema duale coincide con il problema primale.

(43)

Soluzioni di base per il duale

Base B → soluzione di base del primale:

x_B = A⁻¹_B b x_N = 0.

(44)

Soluzioni di base per il duale

Base B → soluzione di base del primale:

x_B = A⁻¹_B b x_N = 0.

Base B → soluzione di base del duale:

u^B = c_BA⁻¹_B .

(45)

Appartenenza a D_a

Quando questa soluzione di base del duale é ammissibile per il duale? Deve soddisfare i vincoli:

u^BA ≥ c o, equivalentemente:

u^BA_B ≥ c_B u^BA_N ≥ c_N

(46)

Continua

u^BA_B = c_BA⁻¹_B A_B = c_B,

(47)

Continua

u^BA_N = c_BA⁻¹_B A_N,

(48)

Continua

u^BA_N = c_BA⁻¹_B A_N, Vincoli soddisfatti se:

c_N − c_BA⁻¹_B A_N ≤ 0 ovvero:

(49)

Continua

u^BA_N = c_BA⁻¹_B A_N, Vincoli soddisfatti se:

c_N − c_BA⁻¹_B A_N ≤ 0

ovvero: ammissibile se tutti i coefficienti di costo ridotto sono non positivi.

(50)

Valore obiettivo

In particolare se

c_N − c_BA⁻¹_B A_N < 0

soluzione di base del duale u^B ammissibile detta non degenere, altrimenti verrá detta degenere.

(51)

Valore obiettivo

In particolare se

c_N − c_BA⁻¹_B A_N < 0

soluzione di base del duale u^B ammissibile detta non degenere, altrimenti verrá detta degenere.

c_Bx_B = c_BA⁻¹_B b = u^Bb,

ovvero:le due soluzioni di base rispettivamente del primale e del duale associate alla base B hanno lo stesso valore dell’obiettivo

(52)

Quindi ...

... in base ad un’osservazione precedente, se entrambe sono ammissibili per i rispettivi problemi, sono anche

soluzioni ottime degli stessi problemi.

(53)

I teorema della dualitá

. ^TeoremaUno dei due problemi ha soluzioni ottime se e solo se anche l’altro ha soluzioni ottime. Formalmente, S_ott 6= ∅ se e solo se D_ott 6= ∅. Inoltre, i valori ottimi dei due problemi coincidono.

(54)

S_ott 6= ∅ ⇒ D_ott 6= ∅

(55)

S_ott 6= ∅ ⇒ D_ott 6= ∅

Sia S_ott 6= ∅ e sia B^∗ una base ottima per il problema primale.

(56)

S_ott 6= ∅ ⇒ D_ott 6= ∅

Sia S_ott 6= ∅ e sia B^∗ una base ottima per il problema primale.Quindi:

x_B^∗ = A⁻¹_B∗b x_N^∗ = 0,

é ammissibile per il primale ed inoltre soddisfa la condizione di ottimalitá:

c − c A⁻¹A ≤ 0.

(57)

Continua

Ma allora u^B^∗ = c_B^∗A⁻¹_B_∗ é ammissibile per il duale.

(58)

Continua

Ma allora u^B^∗ = c_B^∗A⁻¹_B_∗ é ammissibile per il duale. Le due soluzioni di base del primale e del duale associate a B^∗

hanno lo stesso valore dell’obiettivo ed essendo ammissibili rispettivamente per il primale e per il duale sono soluzioni ottime dei rispettivi problemi.

(59)

Continua

Ma allora u^B^∗ = c_B^∗A⁻¹_B_∗ é ammissibile per il duale. Le due soluzioni di base del primale e del duale associate a B^∗

hanno lo stesso valore dell’obiettivo ed essendo ammissibili rispettivamente per il primale e per il duale sono soluzioni ottime dei rispettivi problemi.

D_ott 6= ∅ ⇒ S_ott 6= ∅

conseguenza immediata della proprietá di simmetria tra primale e duale.

(60)

S_ott 6= ∅ ⇔ D_ott 6= ∅ e i valori ottimi coincidono.

(61)

Se S_ott = ∅ in quanto l’obiettivo primale é illimitato, allora D_a = ∅. Per la simmetria tra primale e duale, se D_ott = ∅ in quanto l’obiettivo duale é illimitato, allora S_a = ∅.

(62)

Se S_ott = ∅ in quanto l’obiettivo primale é illimitato, allora D_a = ∅. Per la simmetria tra primale e duale, se D_ott = ∅ in quanto l’obiettivo duale é illimitato, allora S_a = ∅.

Se S_a = ∅, allora D_a = ∅ oppure l’obiettivo duale é

illimitato. Per la simmetria tra primale e duale espressa nell’Osservazione, se D_a = ∅, allora S_a = ∅ oppure

l’obiettivo primale é illimitato.

(63)

Esempio

Primale (S_a = ∅)

max 2x¹ − x² x1 − x² = 1

−x1 + x2 = −2 x1, x2 ≥ 0

(64)

Esempio

Primale (S_a = ∅)

max 2x¹ − x² x1 − x² = 1

−x1 + x2 = −2 x1, x2 ≥ 0 Duale (D_a = ∅):

min u1 − 2u² u1 − u2 ≥ 2

−u1 + u2 ≥ −1

(65)

II teorema della dualitá

. ^TeoremaSi ha che x^∗ ∈ S_ott e u^∗ ∈ D_ott se e solo se x^∗ e u^∗ appartengono rispettivamente a S_a e D_a e soddisfano le condizioni di complementaritá, cioé

(u^∗A − c)x^∗ = 0.

o, in forma scalare:

Xn

j=1

Ã _m X

i=1

u^∗_i a_ij − c_j

!

x^∗_j = 0.

(66)

Dimostrazione

(u^∗A − c)x^∗ = 0 u^∗ ∈ D_a, x^∗ ∈ S_a ⇒ x^∗ ∈ S_ott, u^∗ ∈ D_ott

(67)

Dimostrazione

(u^∗A − c)x^∗ = 0 ⇒ u^∗Ax^∗ = cx^∗.

(68)

Dimostrazione

(u^∗A − c)x^∗ = 0 ⇒ u^∗Ax^∗ = cx^∗.

x^∗ ∈ S_a ⇒ Ax^∗ = b Quindi:

(69)

Dimostrazione

(u^∗A − c)x^∗ = 0 ⇒ u^∗Ax^∗ = cx^∗.

u^∗b = u^∗Ax^∗ = cx^∗

(70)

Dimostrazione

(u^∗A − c)x^∗ = 0 ⇒ u^∗Ax^∗ = cx^∗.

u^∗b = u^∗Ax^∗ = cx^∗ ⇒ x^∗ ∈ S_ott, u^∗ ∈ D_ott

(71)

Continua

x^∗ ∈ S_ott, u^∗ ∈ D_ott ⇒ (u^∗A − c)x^∗ = 0

(72)

Continua

x^∗ ∈ S_ott, u^∗ ∈ D_ott ⇒ (u^∗A − c)x^∗ = 0 Per il I teorema della dualitá:

u^∗b = cx^∗.

(73)

Continua

u^∗b = cx^∗.

x^∗ ∈ Sott ⇒ x^∗ ∈ Sa ⇒ Ax^∗ = b Quindi:

(74)

Continua

u^∗b = cx^∗.

x^∗ ∈ Sott ⇒ x^∗ ∈ Sa ⇒ Ax^∗ = b Quindi:

u^∗b = u^∗Ax^∗ = cx^∗ ⇒ u^∗Ax^∗−cx^∗ = 0 ⇒ (u^∗A−c)x^∗ = 0

(75)

Continua

(u^∗A − c)x^∗ = 0 In forma scalare:

Xn

j=1

Ã _m X

i=1

!

x^∗_j = 0.

(76)

Continua

Xn

j=1

Ã _m X

i=1

!

x^∗_j = 0.

u^∗ ∈ D_a e x^∗ ∈ S_a implicano:

Xm

i=1

u^∗_i a_ij − cj ≥ 0, x^∗_j ≥ 0 ∀ j = 1, . . . , n.

(77)

Continua

Xn

j=1

Ã _m X

i=1

!

x^∗_j = 0.

u^∗ ∈ D_a e x^∗ ∈ S_a implicano:

Xm

i=1

u^∗_i a_ij − cj ≥ 0, x^∗_j ≥ 0 ∀ j = 1, . . . , n.

e quindi:

Ã _m X

i=1

!

x^∗_j ≥ 0.

(78)

Continua

Quindi:

Xn

j=1

Ã _m X

i=1

!

x^∗_j = 0.

se e solo se:

Ã _m X

i=1

!

x^∗_j = 0 ∀ j = 1, . . . , n.

(79)

Di conseguenza ...

x^∗_j > 0 ⇒

Xm

i=1

u^∗_i a_ij − c_j = 0,

(80)

Di conseguenza ...

x^∗_j > 0 ⇒

Xm

i=1

u^∗_i a_ij − c_j = 0,

Xm

i=1

u^∗_i a_ij − c_j > 0 ⇒ x^∗_j = 0,

(81)

Esempio

max x1 − x2

x1 + 2x2 + x3 = 6 2x¹ + x² + x⁴ = 4 x1, x2, x3, x4 ≥ 0.

(82)

Il simplesso duale

Nel simplesso primale si genera una successione di basi ammissibili per il primale ma non per il duale fino a

raggiungere una base che sia anche ammissibile per il

duale (a patto che una tale base esista , a patto cioé che il primale ammetta soluzioni ottime e non abbia obiettivo

illimitato).

(83)

Il simplesso duale

Nel simplesso primale si genera una successione di basi ammissibili per il primale ma non per il duale fino a

duale (a patto che una tale base esista , a patto cioé che il primale ammetta soluzioni ottime e non abbia obiettivo

illimitato).

Nel simplesso duale si genera una successione di basi ammissibili per il duale ma non per il primale fino a

primale (a patto che una tale base esista , a patto cioé che il duale ammetta soluzioni ottime e non abbia obiettivo

illimitato).

(84)

Continua

Riformulazione del problema primale rispetto alla base B = {x_i₁, . . . , x_i_k, . . . , x_i_m} ammissibile per il duale:

max γ0 + Pn−m

j=1 γ_jx_i_m+j x_i₁ = β¹ + Pn−m

j=1 α1jx_i_m+j

· · · x_i_k = β_k + Pn−m

j=1 α_kjx_i_m+j ⁽¹⁾

· · ·

x_i_m = β_m + Pn−m

j=1 α_mjx_i_m+j x1, . . . , x_n ≥ 0

Ammissibilitá per la soluzione di base del duale:

(85)

Verifica di ottimalitá

Se

A⁻¹_B b ≥ 0, o, equivalentemente:

β_i ≥ 0 i = 1, . . . , m

allora la base B é ottima, la soluzione di base del primale x_B = A⁻¹_B b x_N = 0

é ottima per il primale, mentre la soluzione di base u^B = c_BA⁻¹_B

é ottima per il duale.

(86)

Verifica di illimitatezza del duale

Se esiste un r ∈ {1, . . . , m} tale che

β_r < 0 α_rj ≤ 0 j = 1, . . . , n − m, allora si ha S_a = ∅.