Dualitá
Dualitá – p. 1/4
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
Dualitá – p. 2/4
In forma scalare
Primale:
max
Pn
j=1 cj xj
Pn
j=1 aij xj
= bi i = 1, . . . , m
xj ≥ 0
j = 1, . . . , n
Duale
min
Pm
i=1 ui bi
Pm
i=1 ui aij
≥ cj j = 1, . . . , n
Dualitá – p. 3/4
Variabili-vincoli
Esiste una stretta relazione tra
variabili del primale e vincoli del duale;
vincoli del primale e variabili del duale.
Dualitá – p. 4/4
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 xj nei vincoli del primale
il termine noto del j -esimo vincolo del duale coincide
con il coefficiente di xj nell’obiettivo del primale.
Dualitá – p. 5/4
Continua
Nel primale vi sono m vincoli esattamente come nel
duale vi sono m variabili;
i coefficienti dell’i-esima variabile ui del duale
coincidono con i coefficienti dell’i-esimo vincolo del
primale;
il coefficiente di ui nell’obiettivo del duale coincide con il
termine noto dell’i-esimo vincolo del primale.
Dualitá – p. 6/4
Esempio
Primale: max
Duale: min
x1 + x2
3x1 + 2x2 + x3 = 5 ↔ u1
4x1 + 5x2 + x4 = 4 ↔ u2
x2 + x5 = 2
↔ u3
x1 , x2 , x3 , x4 , x5 ≥ 0
5u1 + 4u2 + 2u3
3u1 + 4u2 ≥1
2u1 + 5u2 + u3 ≥1
u1 ≥0
u2 ≥0
u3 ≥0
↔
↔
↔
↔
↔
x1
x2
x3
x4
x5
Dualitá – p. 7/4
Relazioni primale-duale
Indichiamo con
Da = {u ∈ Rm : uA ≥ c}
la regione ammissibile del problema duale e con
Dott = {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
Dualitá – p. 8/4
Continua
OsservazionePer
ogni x0 ∈ Sa e per ogni u0 ∈ Da si ha che
cx0 ≤ u0 b.
x0 ∈ Sa ⇒ Ax0 = b ⇒ u0 b = u0 Ax0 = (u0 A)x0
x0 ∈ Sa ⇒ x0 ≥ 0
u0 ∈ Da ⇒ u0 A ≥ c |{z}
⇒ (u0 A)x0 ≥ cx0
x0 ≥0
Dualitá – p. 9/4
Continua
OsservazioneSe x∗ ∈ Sa
e u∗ ∈ Da ed inoltre
cx∗ = u∗ b
allora x∗ ∈ Sott e u∗ ∈ Dott .
Dall’osservazione precedente si ha che
∀ x ∈ Sa
cx ≤ u∗ b.
Ma essendo cx∗ = u∗ b si ha anche
∀ x ∈ Sa
cx ≤ cx∗
e quindi x∗ ∈ Sott .
Dualitá – p. 10/4
Continua
OsservazioneSe
uno dei due problemi ha obiettivo illimitato,
allora l’altro ha regione ammissibile vuota.
obiettivo primale illimitato
⇒
Da = ∅
Per assurdo sia Da 6= ∅ e sia u0 ∈ Da . In base alla prima
osservazione si ha:
∀ x ∈ Sa
cx ≤ u0 b
e quindi l’obiettivo del primale é limitato dal valore u0 b, il
che contraddice l’illimitatezza di tale obiettivo.
Dualitá – p. 11/4
Continua
Problema primale
↓
Problema duale
↓
Problema duale del duale≡ Problema primale
Il duale del problema duale coincide con il
problema primale.
Osservazione:
Dualitá – p. 12/4
Soluzioni di base per il duale
Base B → soluzione di base del primale:
xB = A−1
B b xN = 0.
Base B → soluzione di base del duale:
uB = cB A−1
B .
Dualitá – p. 13/4
Appartenenza a Da
Quando questa soluzione di base del duale é ammissibile
per il duale? Deve soddisfare i vincoli:
uB A ≥ c
o, equivalentemente:
uB AB ≥ cB
uB AN ≥ cN
Dualitá – p. 14/4
Continua
uB AB = cB A−1
B AB = cB ,
uB AN = cB A−1
B AN ,
Vincoli soddisfatti se:
cN − cB A−1
B AN ≤ 0
ovvero: ammissibile se tutti i coefficienti di costo ridotto
sono non positivi.
Dualitá – p. 15/4
Valore obiettivo
In particolare se
cN − cB A−1
B AN < 0
soluzione di base del duale uB ammissibile detta non
degenere, altrimenti verrá detta degenere.
B
cB xB = cB A−1
b
=
u
b,
B
ovvero:le due soluzioni di base rispettivamente del primale
e del duale associate alla base B hanno lo stesso valore
dell’obiettivo
Dualitá – p. 16/4
Quindi ...
... in base ad un’osservazione precedente, se entrambe
sono ammissibili per i rispettivi problemi, sono anche
soluzioni ottime degli stessi problemi.
Dualitá – p. 17/4
I teorema della dualitá
. TeoremaUno dei due problemi ha soluzioni ottime se e solo
se anche l’altro ha soluzioni ottime. Formalmente, Sott 6= ∅
se e solo se Dott 6= ∅. Inoltre, i valori ottimi dei due problemi
coincidono.
Sott 6= ∅ ⇒ Dott 6= ∅
Sia Sott 6= ∅ e sia B ∗ una base ottima per il problema
primale.Quindi:
xB ∗ = A−1
B∗ b
xN ∗ = 0,
é ammissibile per il primale ed inoltre soddisfa la
condizione di ottimalitá:
∗
cN ∗ − cB ∗ A−1
B ∗ AN ≤ 0.
Dualitá – p. 18/4
Continua
∗
B
u
Ma allora
= cB ∗ A−1
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.
Dott 6= ∅
⇒
Sott 6= ∅
conseguenza immediata della proprietá di simmetria tra
primale e duale.
Dualitá – p. 19/4
Relazioni primale-duale
Sott 6= ∅ ⇔ Dott 6= ∅
e i valori ottimi coincidono.
Se Sott = ∅ in quanto l’obiettivo primale é illimitato, allora
Da = ∅. Per la simmetria tra primale e duale, se Dott = ∅
in quanto l’obiettivo duale é illimitato, allora Sa = ∅.
Se Sa = ∅, allora Da = ∅ oppure l’obiettivo duale é
illimitato. Per la simmetria tra primale e duale espressa
nell’Osservazione, se Da = ∅, allora Sa = ∅ oppure
l’obiettivo primale é illimitato.
Dualitá – p. 20/4
Esempio
Primale (Sa = ∅)
max
2x1 − x2
x1 − x2 = 1
−x1 + x2 = −2
x1 , x2 ≥ 0
min
u1 − 2u2
u1 − u2 ≥ 2
−u1 + u2 ≥ −1
Duale (Da = ∅):
Dualitá – p. 21/4
II teorema della dualitá
. TeoremaSi ha che x∗ ∈ Sott e u∗ ∈ Dott se e solo se x∗ e u∗
appartengono rispettivamente a Sa e Da e soddisfano le
condizioni di complementaritá, cioé
(u∗ A − c)x∗ = 0.
o, in forma scalare:
n
X
j=1
m
X
i=1
u∗i aij − cj
!
x∗j = 0.
Dualitá – p. 22/4
Dimostrazione
(u∗ A − c)x∗ = 0
u∗ ∈ Da , x∗ ∈ Sa
(u∗ A − c)x∗ = 0
x∗ ∈ Sa
⇒
⇒
⇒
x∗ ∈ Sott , u∗ ∈ Dott
u∗ Ax∗ = cx∗ .
Ax∗ = b
Quindi:
u∗ b = u∗ Ax∗ = cx∗ ⇒
x∗ ∈ Sott , u∗ ∈ Dott
Dualitá – p. 23/4
Continua
x∗ ∈ Sott , u∗ ∈ Dott
⇒
(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
Dualitá – p. 24/4
Continua
(u∗ A − c)x∗ = 0
In forma scalare:
n
X
j=1
m
X
u∗i aij − cj
i=1
!
x∗j = 0.
u∗ ∈ Da e x∗ ∈ Sa implicano:
m
X
u∗i aij − cj ≥ 0,
x∗j ≥ 0 ∀ j = 1, . . . , n.
i=1
e quindi:
m
X
i=1
u∗i aij − cj
!
x∗j ≥ 0.
Dualitá – p. 25/4
Continua
Quindi:
n
X
j=1
m
X
u∗i aij − cj
i=1
!
x∗j = 0.
se e solo se:
m
X
i=1
u∗i aij − cj
!
x∗j = 0 ∀ j = 1, . . . , n.
Dualitá – p. 26/4
Di conseguenza ...
x∗j > 0
⇒
m
X
u∗i aij − cj = 0,
i=1
m
X
u∗i aij − cj > 0
⇒ x∗j = 0,
i=1
Dualitá – p. 27/4
Esempio
max
x1 − x2
x1 + 2x2 + x3 = 6
2x1 + x2 + x4 = 4
x1 , x2 , x3 , x4 ≥ 0.
Dualitá – p. 28/4
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).
Dualitá – p. 29/4
Continua
Riformulazione del problema primale rispetto alla base
B = {xi1 , . . . , xik , . . . , xim } ammissibile per il duale:
Pn−m
max
γ0 + j=1 γj xim+j
Pn−m
xi1 = β1 + j=1 α1j xim+j
···
Pn−m
xik = βk + j=1 αkj xim+j
···
Pn−m
xim = βm + j=1 αmj xim+j
x1 , . . . , xn ≥ 0
(1)
Ammissibilitá per la soluzione di base del duale:
γj ≤ 0 j = 1, . . . , n − m.
Dualitá – p. 30/4
Verifica di ottimalitá
Se
A−1
B b ≥ 0,
o, equivalentemente:
βi ≥ 0 i = 1, . . . , m
allora la base B é ottima, la soluzione di base del primale
xB = A−1
B b xN = 0
é ottima per il primale, mentre la soluzione di base
uB = cB A−1
B
é ottima per il duale.
Dualitá – p. 31/4
Verifica di illimitatezza del duale
Se esiste un r ∈ {1, . . . , m} tale che
βr < 0 αrj ≤ 0 j = 1, . . . , n − m,
allora si ha Sa = ∅. Infatti, dall’equazione:
xir = βr +
|{z}
<0
ovvero:
n−m
X
j=1
αrj xim+j < 0,
|{z} | {z }
≤0
≥0
xim+j ≥ 0, j = 1, . . . , n − m ⇒ xir < 0
⇒ Sa = ∅
Dualitá – p. 32/4
Quindi ...
... il duale ha obiettivo illimitato (Da = ∅ non si puó verificare
qui in quanto la soluzione di base del duale associata a B é
per ipotesi ammissibile e quindi Da non puó essere vuoto).
Dualitá – p. 33/4
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.
Dualitá – p. 34/4
Scelta della variabile uscente dalla base
Seleziona la variabile xik tale che
βk = min{βi } < 0
(per convenzione quella con indice piú piccolo se il minimo
é raggiunto da piú variabili).
Dualitá – p. 35/4
Scelta della variabile entrante in base
Scelta solo tra quelle con αkj > 0. In particolare:si sceglie la
variabile xim+h tale che
γj
γh
−
= min −
: αkj > 0 .
αkh
αkj
(nel caso il minimo sia raggiunto da piú variabili si sceglie,
per convenzione, quella con indice piú piccolo).
Dualitá – p. 36/4
L’algoritmo del simplesso duale
Inizializzazione
Sia B0 una base ammissibile per il duale
e k = 0.
Se soddisfatta la condizione di
ottimalitá: STOP . La soluzione di base associata a Bk
é una soluzione ottima del problema. Altrimenti si vada
al Passo 2.
Passo 1- verifica ottimalitá
Se é soddisfatta la
condizione di illimitatezza, allora: STOP, si ha Sa = ∅ e
Dott = ∅ in quanto il duale ha obiettivo illimitato.
Altrimenti si vada al Passo 3.
Passo 2 - verifica di illimitatezza
Si selezioni la
variabile xik che dovrá uscire dalla base attraverso la
regola vista.
Passo 3 - scelta variabile uscente dalla base
Dualitá – p. 37/4
Simplesso duale
Si selezioni la
che dovrá entrare in base attraverso la
Passo 4 - scelta variabile entrante in base
variabile xim+h
regola vista.
Si generi la nuova base
Bk+1 sostituendo in Bk la variabile xik con la variabile
xim+h e si esegua la corrispondente operazione di
cardine. Quindi, si ponga k = k + 1 e si ritorni al Passo
1.
Passo 5 - operazione di cardine
Dualitá – p. 38/4
Miglioramento dell’obiettivo
Il nuovo valore dell’obiettivo, esso é pari a:
<0
z}|{
βk
γ0 − γh
≤ γ0 ,
|{z} αkh
≤0 |{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.
Dualitá – p. 39/4
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 xj nei vincoli del primale;
il termine noto del j -esimo vincolo del duale coincide
con il coefficiente di xj nell’obiettivo del primale.
Dualitá – p. 40/4
Continua
nel primale vi sono m vincoli esattamente come nel
duale vi sono m variabili;
i coefficienti dell’i-esima variabile ui del duale
coincidono con i coefficienti dell’i-esimo vincolo del
primale;
il coefficiente di ui nell’obiettivo del duale coincide con il
termine noto dell’i-esimo vincolo del primale.
Dualitá – p. 41/4
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.
Table 1:
min
max
variabile ≥ 0
variabile ≤ 0
variabile libera
vincolo ≥
vincolo ≤
vincolo =
vincolo ≤
vincolo ≥
vincolo =
variabile ≥ 0
variabile ≤ 0
variabile libera
Dualitá – p. 42/4
Esempio
min
x1 + 2x2 + 3x3
x1 + x2 − x3 ≤ 1
↔ u1
x1 − 2x2 + x3 ≥ 2
↔ u2
x1 − x2 − x3 = 4
↔ u3
x1 ≥ 0, x2 ≤ 0, x3 libera
max
u1 + 2u2 + 4u3
u1 + u2 + u3 ≤1
↔ x1
u1 − 2u2 − u3 ≥2
↔ x2
−u1 + u2 − u3 =3
↔ x3
u1 ≤ 0, u2 ≥ 0, u3 libera
Dualitá – p. 43/4
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.
Dualitá – p. 44/4