vincoli del primale e variabili del duale

Dualità

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

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

Variabili-vincoli

Esiste una stretta relazione tra

variabili del primale e vincoli del duale;

vincoli del primale e variabili del duale.

Continua

In particolare:

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

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.

Continua

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

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.

Esempio

Primale: max x1 + x2

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

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

3u1 + 4u2≥1 ↔ x1

2u1 + 5u2 + u3≥1 ↔ x2

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

Relazioni primale-duale

Indichiamo con

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

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

l’insieme delle sue soluzioni ottime.

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

Continua

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

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

u₀ ∈ D_a ⇒ u⁰A ≥ c ⇒

|{z}

x⁰≥0

(u0A)x0 ≥ cx⁰

Continua

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

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

Dall’osservazione precedente si ha che

∀ x ∈ S_a cx ≤ u^∗b. Ma essendo ^cx∗ = u^∗b si ha anche

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

Continua

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

obiettivo primale illimitato ⇒ D_a = ∅

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.

Continua

Problema primale

↓

Problema duale

↓

Problema duale del duale≡ Problema primale

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

Dimostrazione

Trasformiamo il duale in forma standard:

− max −(u^′ − u^′′)b

−(u^′ − u^′′)A + Iy = −c u^′,u^′′,y ≥ 0

Il duale di questo problema risulta essere:

− min −cz

−Az ≥ −b Az ≥ b

z ≥ 0

che risulta equivalente al problema primale:

max cz Az = b

z ≥ 0

Simmetria

Questa osservazione ci mostra la totale simmetria esistente tra problema primale e duale.

Si noti in particolare che si è dimostrata un’implicazione del tipo:

Il primale ha la proprietà P ⇒ il duale ha la proprietà P^′ si è automaticamente dimostrato anche che

Il duale ha la proprietà P ⇒ il duale del duale ha la proprietà P^′ o, equivalentemente

Il duale ha la proprietà P ⇒ il primale ha la proprietà P^′

Esempio di simmetria

Abbiamo dimostrato che se il primale ha la proprietà P ≡ obiettivo illimitato, allora il duale ha la proprietà P^′ ≡

regione ammissibile vuota.

Con questo abbiamo anche automaticamente dimostrato che se il duale ha la proprietà P ≡ obiettivo illimitato, allora il primale ha la proprietà P^′ ≡ regione ammissibile vuota.

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 .

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

Continua

u^BA_B = c_BA⁻¹

B A_B = c_B,

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.

Valore obiettivo

In particolare se

c_N − c_BA⁻¹

B A_N < 0

soluzione di base del duale ^uB 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

Quindi ...

... in base a un’osservazione precedente, se entrambe sono ammissibili per i rispettivi problemi, sono anche soluzioni ottime degli stessi problemi.

I teorema della dualità

Teorema Uno 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.

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_N∗ − c_B∗A⁻¹_B∗A_N∗ ≤ 0.

Continua

Ma allora ^uB∗ = 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.

Relazioni primale-duale

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

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, se D_a = ∅, allora S_a = ∅ oppure l’obiettivo primale è illimitato.

Esempio

Primale (S_a = ∅)

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

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

min u1 − 2u² u1 − u2 ≥ 2

−u1 + u2 ≥ −1

II teorema della dualità

Teorema Si 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

Xm

i=1

u^∗_i a_ij − c_j

!

x^∗_j = 0.

Dimostrazione

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

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

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

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

Continua

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

u^∗b = cx^∗.

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

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

Continua

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

Xn

j=1

Xm

i=1

u^∗_i a_ij − c_j

!

x^∗_j = 0.

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

Xm

i=1

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

e quindi:

m !

Continua

Quindi:

Xn

j=1

Xm

i=1

u^∗_i a_ij − c_j

!

x^∗_j = 0.

se e solo se:

Xm

i=1

u^∗_i a_ij − c_j

!

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

Di conseguenza ...

x^∗_j > 0 ⇒

Xm

i=1

u^∗_i a_ij − c_j = 0,

Xm

i=1

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

Esempio

max x1 − x2

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

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

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

raggiungere una base che sia anche ammissibile per il

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

illimitato).

Continua

Riformulazione del problema primale rispetto alla base B = {x_i1, . . . , x_ik, . . . , x_im} ammissibile per il duale:

max γ0 + Pn−m

j=1 γ_jx_im+j x_i1 = β¹ + Pn−m

j=1 α1jx_im+j

· · · x_ik = β_k + Pn−m

j=1 α_kjx_im+j ⁽¹⁾

· · ·

x_im = β_m + Pn−m

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

Ammissibilità per la soluzione di base del duale:

γ_j ≤ 0 j = 1, . . . , n − m.

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

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 = ∅. Infatti, dall’equazione:

x_ir = β_r

|{z}

<0

+

n−mX

j=1

α_rj

|{z}

≤0

x_im+j

| {z }

≥0

< 0,

ovvero:

x_im+j ≥ 0, j = 1, . . . , n − m ⇒ xi_r < 0 ⇒ Sa = ∅

Quindi ...

... il duale ha obiettivo illimitato (D_a = ∅ non si può verificare qui in quanto la soluzione di base del duale associata a B è per ipotesi ammissibile e quindi D_a non può essere vuoto).

Cambio di base

Se le condizioni di ottimalità e illimitatezza non sono

soddisfatte, si effettua un cambio di base tenendo conto che si vuole:

mantenere l’ammissibilità duale;

migliorare (ridurre) o quantomeno non peggiorare il valore dell’obiettivo duale.

Scelta della variabile uscente dalla base

Seleziona la variabile x_ik tale che

β_k = min{β_i} < 0

(per convenzione quella con indice più piccolo se il minimo è raggiunto da più variabili).

Scelta della variabile entrante in base

Scelta solo tra quelle con α_kj > 0.

In particolare: si sceglie la variabile x_im+h tale che

− γ_h

α_kh = min



− γ_j

α_kj : α_kj > 0

 .

(nel caso il minimo sia raggiunto da più variabili si sceglie, per convenzione, quella con indice più piccolo).

L’algoritmo del simplesso duale

Inizializzazione Sia B0 una base ammissibile per il duale e k = 0.

Passo 1- verifica ottimalit `a Se soddisfatta la condizione di ottimalità: STOP . La soluzione di base associata a B_k è una soluzione ottima del problema. Altrimenti si vada al Passo 2.

Passo 2 - verifica di illimitatezza Se è soddisfatta la

condizione di illimitatezza, allora: STOP, si ha S_a = ∅ e D_ott = ∅ in quanto il duale ha obiettivo illimitato.

Altrimenti si vada al Passo 3.

Passo 3 - scelta variabile uscente dalla base Si selezioni la variabile x_ik che dovrà uscire dalla base attraverso la regola vista.

Simplesso duale

Passo 4 - scelta variabile entrante in base Si selezioni la variabile x_im+h che dovrà entrare in base attraverso la regola vista.

Passo 5 - operazione di cardine Si generi la nuova base B_k+1 sostituendo in B_k la variabile x_ik con la variabile x_im+h e si esegua la corrispondente operazione di

cardine. Quindi, si ponga k = k + 1 e si ritorni al Passo 1.

Miglioramento dell’obiettivo

Il nuovo valore dell’obiettivo, esso è pari a:

γ0 − γ_h

|{z}

≤0

<0

z}|{β_k α_kh

|{z}>0

≤ γ⁰,

e quindi il valore dell’obiettivo per la nuova soluzione di base è migliore o quantomeno non peggiore rispetto alla precedente.

Se γ_h < 0 (cosa certamente vera nel caso non degenere) possiamo anche garantire che il nuovo valore dell’obiettivo sia strettamente minore rispetto al precedente.

Duale di un problema di PL generico

Come per i problemi in forma standard, vi sarà una stretta relazione tra le variabili di un problema ed i vincoli dell’altro.

Più precisamente avremo, come per la forma standard, che:

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

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.

Continua

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

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.

La tabella

Rispetto alla forma standard quello che può cambiare sono i versi delle disequazioni ed i segni delle variabili. Per

stabilire questi ci si può rifare allo specchietto nella seguente tabella.

min max

variabile ≥ 0 vincolo ≤ variabile ≤ 0 vincolo ≥ variabile libera vincolo =

vincolo ≥ variabile ≥ 0 vincolo ≤ variabile ≤ 0 vincolo = variabile libera

Esempio

min x1 + 2x2 + 3x3

x1 + x² − x³ ≤ 1 ↔ u¹ x1 − 2x² + x³ ≥ 2 ↔ u² x1 − x² − x³ = 4 ↔ u³ x1 ≥ 0, x2 ≤ 0, x3 libera

max u1 + 2u² + 4u³

u1 + u2 + u3≤1 ↔ x1

u1 − 2u2 − u3≥2 ↔ x2

−u¹ + u2 − u³=3 ↔ x³ u ≤ 0, u ≥ 0, u libera

Continua

Le relazioni tra primale e duale (osservazioni varie, I e II teorema della dualità, simmetria tra i due problemi)

possono essere estesi anche a problemi di PL in forma più generale e ai loro duali.