Il metodo del simplesso
Il metodo del simplesso – p. 1/127
I problemi di PL in forma standard
I problemi di PL in forma standard hanno la seguente formulazione:
max cx
aix = bi i = 1, . . . , m x ≥ 0
o, equivalentemente, in forma matriciale:
max cx Ax = b
x ≥ 0
Un’osservazione
Osservazione 1 Ogni problema di PL in forma canonica puó essere trasformato in uno equivalente in forma
standard.
Il metodo del simplesso – p. 3/127
Dimostrazione
Problema di PL in forma canonica
max cx
aix ≤ bi i = 1, . . . , m x ≥ 0
aix ≤ bi ⇔ aix + yi = bi, yi ≥ 0.
Quindi, il problema di PL in forma canonica é equivalente al seguente:
max cx
aix + yi = bi i = 1, . . . , m x ≥ 0
Continua
Ogni problema di PL puó essere ricondotto ad uno equivalente in forma canonica.
Il metodo del simplesso – p. 5/127
Continua
Ogni problema di PL puó essere ricondotto ad uno equivalente in forma canonica.
Ogni problema in forma canonica puó essere ricondotto ad uno equivalente in forma standard.
Continua
Ogni problema di PL puó essere ricondotto ad uno equivalente in forma canonica.
Ogni problema in forma canonica puó essere ricondotto ad uno equivalente in forma standard.
Quindi: ogni problema di PL puó essere ricondotto ad uno equivalente in forma standard.
Il metodo del simplesso – p. 5/127
Continua
Ogni problema di PL puó essere ricondotto ad uno equivalente in forma canonica.
Ogni problema in forma canonica puó essere ricondotto ad uno equivalente in forma standard.
Quindi: ogni problema di PL puó essere ricondotto ad uno equivalente in forma standard.
NB: nella pratica si passa direttamente da un problema di PL in forma generica ad uno equivalente in forma standard, senza passare necessariamente attraverso un problema in forma canonica.
Un esempio
Si trasformi il seguente problema di PL in forma generica in un problema di PL in forma standard
min x1 + x2 + x3 x1 + 2x2 − x3 ≤ 3 x1 + 4x2 + 5x3 = 5
x1 − 2x2 + x3 ≥ 3 x1 ≥ 0
x2 ≤ 0
x3 libera in segno
Il metodo del simplesso – p. 6/127
Ipotesi aggiuntiva
Si richiede che la matrice dei vincoli A ∈ Rm×n abbia rango pari a m, il numero delle sue righe, il che equivale a
richiedere equivalentemente che:
non ci sono righe di A ottenibili come combinazioni lineari di altre righe di A;
esistono m colonne della matrice A che formano una matrice quadrata invertibile.
NB: Si puó dimostrare che anche questa non é una
condizione restrittiva e che ci si puó sempre ricondurre ad essa.
Esempi
A1 =
1 2 1 3 2 1 3 4 3 0 5 5
Rango di A1 < m = 3
A2 =
"
1 2 2 1 −1 3 7 1 3 1
#
Rango di A2 = m = 2
Il metodo del simplesso – p. 8/127
Base di un problema di PL
Si definisce base di un problema di PL in forma standard un sottinsieme:
B = {xi1, . . . , xim}
di m delle n variabili del problema di PL con la proprietá che la matrice AB ∈ Rm×m ottenuta considerando le sole
colonne di A relative alle variabili xik, k = 1, . . . , m, sia invertibile.
Le variabili dell’insieme B verranno dette variabili in base, quelle al di fuori di B verranno raggruppate nell’insieme:
N = {xim+1, . . . , xin}
Un esempio
Dato
max 3x1 + 4x2 + 2x3 + 2x4 + x5 x1 + 2x2 + 2x3 + x4 − x5 = 2 x1 + 2x2 + x3 + 4x4 − 2x5 = 2
x1, x2, x3, x4, x5 ≥ 0 Matrice dei vincoli
A =
"
1 2 2 1 −1 1 2 1 4 −2
#
Il metodo del simplesso – p. 10/127
Continua
B1 = {x1, x2} → non é una base. Infatti
AB1 =
"
1 2 1 2
#
non é invertibile
Invece, B2 = {x1, x3} é una base in quanto:
AB2 =
"
1 2 1 1
#
é invertibile
Allo stesso modo si verifichi che B3 = {x3, x4} e B4 = {x4, x5} sono basi.
Soluzioni di base
Data una base B, indichiamo con:
xB ∈ Rm il vettore delle variabili in base
Il metodo del simplesso – p. 12/127
Soluzioni di base
Data una base B, indichiamo con:
xB ∈ Rm il vettore delle variabili in base
xN ∈ Rn−m il vettore delle variabili fuori base
Soluzioni di base
Data una base B, indichiamo con:
xB ∈ Rm il vettore delle variabili in base
xN ∈ Rn−m il vettore delle variabili fuori base
cB ∈ Rm il vettore dei costi relativi alle variabili in base
Il metodo del simplesso – p. 12/127
Soluzioni di base
Data una base B, indichiamo con:
xB ∈ Rm il vettore delle variabili in base
xN ∈ Rn−m il vettore delle variabili fuori base
cB ∈ Rm il vettore dei costi relativi alle variabili in base cN ∈ Rn−m il vettore dei costi relativi alle variabili fuori base
Soluzioni di base
Data una base B, indichiamo con:
xB ∈ Rm il vettore delle variabili in base
xN ∈ Rn−m il vettore delle variabili fuori base
cB ∈ Rm il vettore dei costi relativi alle variabili in base cN ∈ Rn−m il vettore dei costi relativi alle variabili fuori base
AN ∈ Rm×(n−m) la matrice ottenuta da A considerando le sole colonne relative alle variabili fuori base.
Il metodo del simplesso – p. 12/127
Nell’esempio
Con la base B = {x1, x3} abbiamo:
xB = (x1 x3)
Nell’esempio
Con la base B = {x1, x3} abbiamo:
xB = (x1 x3)
xN = (x2 x4 x5)
Il metodo del simplesso – p. 13/127
Nell’esempio
Con la base B = {x1, x3} abbiamo:
xB = (x1 x3)
xN = (x2 x4 x5) cB = (3 2)
Nell’esempio
Con la base B = {x1, x3} abbiamo:
xB = (x1 x3)
xN = (x2 x4 x5) cB = (3 2)
cN = (4 2 1)
Il metodo del simplesso – p. 13/127
Nell’esempio
Con la base B = {x1, x3} abbiamo:
xB = (x1 x3)
xN = (x2 x4 x5) cB = (3 2)
cN = (4 2 1)
AN =
"
2 1 −1 2 4 −2
#
Riscrittura della riformulazione
Possiamo ora riscrivere il problema di PL in forma standard nella seguente forma equivalente:
max cBxB + cNxN ABxB + ANxN = b
xB, xN ≥ 0 e quindi anche in questo modo:
Il metodo del simplesso – p. 14/127
Riscrittura della riformulazione
Possiamo ora riscrivere il problema di PL in forma standard nella seguente forma equivalente:
max cBxB + cNxN ABxB + ANxN = b
xB, xN ≥ 0 e quindi anche in questo modo:
max cBxB + cNxN ABxB = b − ANxN
xB, xN ≥ 0
Nell’esempio
max
cBxB
z }| { 3x1 + 2x3 +
cNxN
z }| {
4x2 + 2x4 + x5
ABxB
z }| { x1 + 2x3 +
ANxN
z }| {
2x2 + x4 − x5 = 2 x1 + x3 + 2x2 + 4x4 − 2x5 = 2
x1, x3
| {z }
xB
, x2, x4, x5
| {z }
xN
≥ 0
Il metodo del simplesso – p. 15/127
E quindi ...
max
cBxB
z }| { 3x1 + 2x3 +
cNxN
z }| {
4x2 + 2x4 + x5
ABxB
z }| { x1 + 2x3 =
b−ANxN
z }| {
2 − 2x2 − x4 + x5 x1 + x3 = 2 − 2x2 − 4x4 + 2x5
x1, x3
| {z }
xB
, x2, x4, x5
| {z }
xN
≥ 0
Continua
Moltiplichiamo ora i vincoli di uguaglianza per A−1B : max cBxB + cNxN
A−1B ABxB = A−1B b − A−1B ANxN xB, xN ≥ 0
e quindi da A−1B ABxB = IxB = xB
max cBxB + cNxN
xB = A−1B b − A−1B ANxN xB, xN ≥ 0
Questo equivale a risolvere il sistema dato dai vincoli di uguaglianza considerando la variabili in base come
incognite del sistema e quelle fuori base come parametri.
Il metodo del simplesso – p. 17/127
Nell’esempio
max 3x1 + 2x3 + 4x2 + 2x4 + x5 x1 = 2 − 2x2 − 7x4 + 3x5
x3 = 0 + 3x4 − x5 x1, x3, x2, x4, x5 ≥ 0
Riformulazione rispetto alla base B
Infine, sostituendo xB nell’obiettivo:
max cBA−1B b + (cN − cBA−1B AN)xN xB = A−1B b − A−1B ANxN
xB, xN ≥ 0
Questa riformulazione viene detta riformulazione del problema di PL rispetto alla base B.
NB: tale riformulazione é del tutto equivalente al problema originario di PL.
Il metodo del simplesso – p. 19/127
Nell’esempio
Riformulazione rispetto alla base B = {x1, x3}: max 6 − 2x2 − 13x4 + 8x5
x1 = 2 − 2x2 − 7x4 + 3x5 x3 = 0 + 3x4 − x5
x1, x3, x2, x4, x5 ≥ 0
Soluzioni di base
Si definisce soluzione di base associata alla base B, la seguente soluzione del sistema di vincoli di uguaglianza ottenuta ponendo xN = 0:
xB = A−1B b xN = 0.
Nell’esempio:
x1 = 2 x3 = 0 x2 = x4 = x5 = 0
Il metodo del simplesso – p. 21/127
Ammissibilitá e non degenerazione
Se A−1B b ≥ 0 la soluzione di base si dice ammissibile.
Questo vuol dire che appartiene alla regione ammissibile del problema di PL in quanto, oltre a soddisfare i vincoli di uguaglianza del problema, soddisfa anche quelli di non negativitá delle variabili.
Ammissibilitá e non degenerazione
Se A−1B b ≥ 0 la soluzione di base si dice ammissibile.
Questo vuol dire che appartiene alla regione ammissibile del problema di PL in quanto, oltre a soddisfare i vincoli di uguaglianza del problema, soddisfa anche quelli di non negativitá delle variabili.
Se inoltre si ha A−1B b > 0 si parla di soluzione di base non degenere, altrimenti si parla di soluzione di base degenere.
Il metodo del simplesso – p. 22/127
Nell’esempio
B2 = {x1, x3} → soluzione di base ammissibile e degenere B3 = {x3, x4}: la soluzione di base é
x3 = 6/7 x4 = 2/7 x1 = x2 = x5 = 0, che é ammissibile e non degenere
B4 = {x4, x5}: la soluzione di base é
x4 = −1 x5 = −3 x1 = x2 = x3 = 0, che é non ammissibile.
Osservazione
Data una soluzione di base ammissibile e non degenere esiste un’unica base che la rappresenta, mentre una
soluzione di base ammissibile e degenere é rappresentata da piú basi.
Si verifichi, ad esempio, che la base B5 = {x1, x4} ha come soluzione di base associata:
x1 = 2 x4 = 0 x2 = x3 = x5 = 0, che é la stessa associata alla base B2.
Il metodo del simplesso – p. 24/127
Ma ...
... cosa hanno a che fare le basi e le soluzioni di base con il teorema fondamentale della PL?
Ma ...
... cosa hanno a che fare le basi e le soluzioni di base con il teorema fondamentale della PL?
La risposta ci viene dalla seguente osservazione.
Osservazione 3 L’insieme dei vertici di Sa coincide con
l’insieme delle soluzioni di base ammissibili del problema di PL.
In pratica, vertici e di soluzioni di base ammissibili sono la stessa cosa vista da due punti di vista diversi: quello
geometrico (i vertici) e quello algebrico (le soluzioni di base ammissibili).
Il metodo del simplesso – p. 25/127
Basi adiacenti
Due basi B′ e B′′ si definiscono adiacenti se hanno m − 1 variabili uguali e differiscono per una sola variabile.
Nell’esempio le basi B3 = {x3, x4} e B4 = {x4, x5} sono adiacenti, mentre non lo sono B2 = {x1, x3} e B4.
Soluzioni di base adiacenti
Due soluzioni di base distinte si definiscono adiacenti se
esistono due basi B′ e B′′ che le rappresentano e che sono tra loro adiacenti.
Il metodo del simplesso – p. 27/127
Soluzioni di base adiacenti
Due soluzioni di base distinte si definiscono adiacenti se
esistono due basi B′ e B′′ che le rappresentano e che sono tra loro adiacenti.
Si noti che due basi adiacenti non corrispondono
necessariamente a due soluzioni di base adiacenti. Esse infatti possono corrispondere alla stessa soluzione di base come accade, ad esempio, con le basi B2 = {x1, x3} e
B5 = {x1, x4}.
Riformulazione rispetto alla base B
Sia data la base:
B = {xi1, . . . , xim}.
con
N = {xim+1, . . . , xin}
l’insieme delle variabili fuori base. Abbiamo visto che, data la base B, la riformulazione del problema di PL rispetto alla base B é data da
max cBA−1B b + (cN − cBA−1B AN)xN xB = A−1B b − A−1B ANxN
xB, xN ≥ 0
Il metodo del simplesso – p. 28/127
Continua
Indichiamo con:
γ0 il valore cBA−1B b;
γj, j = 1, . . . , n − m, le componenti del vettore cN − cBA−1B AN;
βr, r = 1, . . . , m, le componenti del vettore A−1B b;
αrj, r = 1, . . . , m, j = 1, . . . , n − m, le componenti della matrice −A−1B AN
Continua
In forma scalare possiamo riscrivere la riformulazione rispetto alla base B nel seguente modo:
max γ0 + Pn−m
j=1 γjxim+j xi1 = β1 + Pn−m
j=1 α1jxim+j
· · · xik = βk + Pn−m
j=1 αkjxim+j
· · ·
xim = βm + Pn−m
j=1 αmjxim+j x1, . . . , xn ≥ 0
Il metodo del simplesso – p. 30/127
Nell’esempio
Riformulazione rispetto alla base B2 = {x1, x3}: max 6 − 2x2 − 13x4 + 8x5
x1 = 2 − 2x2 − 7x4 + 3x5 x3 = 0 + 3x4 − x5
x1, x3, x2, x4, x5 ≥ 0
Passaggio ad una base adiacente
Supponiamo ora di voler passare dalla base B alla base adiacente B′ ottenuta rimuovendo da B la variabile xik,
1 ≤ k ≤ m, e sostituendola con la variabile fuori base xim+h, 1 ≤ h ≤ n − m, ovvero:
B′ = {xi1, . . . , xik−1, xim+h, xik+1, . . . , xim}.
La prima domanda che ci dobbiamo porre é :
Il metodo del simplesso – p. 32/127
Passaggio ad una base adiacente
Supponiamo ora di voler passare dalla base B alla base adiacente B′ ottenuta rimuovendo da B la variabile xik,
1 ≤ k ≤ m, e sostituendola con la variabile fuori base xim+h, 1 ≤ h ≤ n − m, ovvero:
B′ = {xi1, . . . , xik−1, xim+h, xik+1, . . . , xim}.
La prima domanda che ci dobbiamo porre é :
quando B′ é effettivamente una base. Perché lo sia si deve avere che AB′ é invertibile.
Continua
Si ha che AB′ é invertibile e quindi B′ é una base se e solo
se nella riformulazione associata alla base B il coefficiente di xim+h nell’equazione relativa a xik é diverso da 0, ovvero se e solo se:
αkh 6= 0.
Nell’esempio:
{x1, x2}
Il metodo del simplesso – p. 33/127
Continua
Si ha che AB′ é invertibile e quindi B′ é una base se e solo
se nella riformulazione associata alla base B il coefficiente di xim+h nell’equazione relativa a xik é diverso da 0, ovvero se e solo se:
αkh 6= 0.
Nell’esempio:
{x1, x2} non é una base {x1, x5}
Continua
Si ha che AB′ é invertibile e quindi B′ é una base se e solo
se nella riformulazione associata alla base B il coefficiente di xim+h nell’equazione relativa a xik é diverso da 0, ovvero se e solo se:
αkh 6= 0.
Nell’esempio:
{x1, x2} non é una base {x1, x5} é una base
Il metodo del simplesso – p. 33/127
L’operazione di cardine
Tale operazione consente di passare dalla riformulazione rispetto alla base B a quella rispetto alla base adiacente B′. Per fare questo dovremo compiere le seguenti operazioni.
Ricavare xim+h dall’equazione relativa a xik, cioé:
xim+h = − βk
αkh + 1
αkhxik −
n−mX
j=1, j6=h
αkj
αkhxim+j. sostituire ogni occorrenza della variabile xim+h nelle
restanti equazioni e nell’obiettivo con la parte destra di tale equazione
Esempio
Dalla riformulazione rispetto a B2 = {x1, x3} a quella rispetto a B6 = {x1, x5}
Ricavo x5 dall’equazione relativa a x3 x5 = 0 − x3 + 3x4
Il metodo del simplesso – p. 35/127
Esempio
Dalla riformulazione rispetto a B2 = {x1, x3} a quella rispetto a B6 = {x1, x5}
Ricavo x5 dall’equazione relativa a x3 x5 = 0 − x3 + 3x4
Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo
max 6 − 2x2 − 13x4 + 8(0 − x3 + 3x4) x1 = 2 − 2x2 − 7x4 + 3(0 − x3 + 3x4)
x5 = 0 − x3 + 3x4 x1, x3, x2, x4, x5 ≥ 0
Riformulazione rispetto a B 6 = {x 1 , x 5 }
max 6 − 2x2 − 8x3 + 11x4 x1 = 2 − 2x2 + 2x4 − 3x3
x5 = 0 − x3 + 3x4 x1, x3, x2, x4, x5 ≥ 0
Il metodo del simplesso – p. 36/127
Nota bene
Per poter recuperare dalle riformulazioni alcune
informazioni (nel seguito vedremo, ad esempio, come
sfruttare la riformulazione rispetto a una base B per poter ottenere la matrice A−1B ) é necessario mantenere un ordine tra le variabili in una base. Quindi se nella base B′ la
variabile xim+h sostituisce la variabile xik a cui corrisponde la k-esima equazione della riformulazione rispetto a B,
nella riformulazione rispetto a B′ l’equazione relativa alla variabile xim+h dovrá ancora essere la k-esima, mentre la posizione delle equazioni relative a tutte le altre variabili deve rimanere invariata rispetto alla precedente
riformulazione.
Nell’esempio ...
... la variabile x5 ha preso il posto della x3 e l’equazione relativa alla x5 é stata messa nella stessa posizione (la
seconda) in cui si trovava quella della x3, mentre la restante equazione ha mantenuto la posizione originaria.
Il metodo del simplesso – p. 38/127
Un altro esempio
Passaggio da B6 = {x1, x5} a B4 = {x4, x5} Ricavo x4 dall’equazione relativa a x1
x4 = −1 + 1/2x1 + x2 + 3/2x3
Un altro esempio
Passaggio da B6 = {x1, x5} a B4 = {x4, x5} Ricavo x4 dall’equazione relativa a x1
x4 = −1 + 1/2x1 + x2 + 3/2x3
Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo
max 6 − 2x2 − 8x3 + 11(−1 + 1/2x1 + x2 + 3/2x3) x4 = −1 + 1/2x1 + x2 + 3/2x3
x5 = 0 − x3 + 3(−1 + 1/2x1 + x2 + 3/2x3) x1, x3, x2, x4, x5 ≥ 0
Il metodo del simplesso – p. 39/127
Continua
Riformulazione rispetto a B4 = {x4, x5}:
max −5 + 11/2x1 + 9x2 + 17/2x3 x4 = −1 + 1/2x1 + x2 + 3/2x3 x5 = −3 + 3/2x1 + 3x2 + 7/2x3
x1, x3, x2, x4, x5 ≥ 0
Nota bene
Le operazioni di cardine che abbiamo eseguito sugli
esempi ci hanno consentito di passare da una base ad una adiacente e, nel secondo esempio, anche da una soluzione di base ad una adiacente. Tuttavia, nel secondo caso
siamo passati da una soluzione di base ammissibile (quella associata a B6) ad una non ammissibile (quella associata a B4). Nell’algoritmo di risoluzione che ci apprestiamo a
discutere la scelta della base adiacente verso cui muoversi non verrá fatta a caso come abbiamo fatto nei precedenti esempi, ma sará guidata da regole precise che
fondamentalmente ci consentiranno di spostarsi tra vertici della regione ammissibile migliorando il valore della
funzione obiettivo.
Il metodo del simplesso – p. 41/127
Ipotesi iniziale
Data la base B e la riformulazione rispetto ad essa:
max γ0 + Pn−m
j=1 γjxim+j xi1 = β1 + Pn−m
j=1 α1jxim+j
· · · xik = βk + Pn−m
j=1 αkjxim+j
· · ·
xim = βm + Pn−m
j=1 αmjxim+j x1, . . . , xn ≥ 0
supponiamo che βk ≥ 0, k = 1, . . . , m, ovvero la base B é ammissibile (la soluzione di base associata é ammissibile).
Nota bene
Due problemi non banali sono:
stabilire se esiste una base ammissibile (o, equivalentemente, stabilire se Sa 6= ∅)
nel caso esista, determinarne una.
Questi problemi li affronteremo in seguito. Per il momento supponiamo di avere giá a disposizione una base
ammissibile B.
Il metodo del simplesso – p. 43/127
Coefficienti di costo ridotto
I coefficienti γj delle variabili fuori base nell’obiettivo della riformulazione rispetto alla base B vengono detti coefficienti di costo ridotto delle variabili fuori base.
Questi esprimono la variazione dell’obiettivo in
corrispondenza dell’incremento di un’unitá della variabile fuori base corrispondente.
Infatti ...
... se consideriamo l’obiettivo della riformulazione:
γ0 +
n−mX
j=1
γjxim+j,
e supponiamo di tenere a 0 il valore di tutte le variabili fuori base tranne la variabile xim+h il cui valore viene
incrementato a 1, otteniamo Il nuovo valore dell’obiettivo γ0 + γh con una variazione rispetto al valore γ0 (quello nella soluzione di base associata a B) pari proprio al valore γh del coefficiente di costo ridotto della variabile fuori base xim+h.
Il metodo del simplesso – p. 45/127
Un esempio
Sia data la seguente riformulazione rispetto alla base ammissibile {x1, x2} di un problema di PL:
max 2 + x3 − x4 x1 = 2 + x3 + x4 x2 = 1 + 2x3 + x4
x1, x2, x3, x4 ≥ 0
Il valore dell’obiettivo nella corrispondente soluzione di base é la costante che appare nell’obiettivo (2).
Continua
Se teniamo a 0 il valore di x4 e portiamo a 1 quello di x3, il valore dell’obiettivo diventa 3, con una variazione pari al coefficiente di costo ridotto (+1) di x3
Se teniamo a 0 il valore di x3 e portiamo a 1 quello di x4, il valore dell’obiettivo diventa 1, con una variazione pari al coefficiente di costo ridotto (-1) di x4
Il metodo del simplesso – p. 47/127
Verifica di ottimalitá
Alla base ammissibile B é associata una soluzione di base ammissibile (un vertice di Sa). Posso stabilire se questa
soluzione appartiene a Sott?
Verifica di ottimalitá
Alla base ammissibile B é associata una soluzione di base ammissibile (un vertice di Sa). Posso stabilire se questa
soluzione appartiene a Sott?
Data una variabile fuori base, il cui valore é nullo nella soluzione di base associata a B, quando "conviene" far crescere da 0 il valore di tale variabile?
Il metodo del simplesso – p. 48/127
Verifica di ottimalitá
Alla base ammissibile B é associata una soluzione di base ammissibile (un vertice di Sa). Posso stabilire se questa
soluzione appartiene a Sott?
Data una variabile fuori base, il cui valore é nullo nella soluzione di base associata a B, quando "conviene" far crescere da 0 il valore di tale variabile?
Solo quando il suo coefficiente di costo ridotto é positivo, altrimenti il valore dell’obiettivo o rimane invariato (se il coefficiente é nullo) o diminuisce (se é negativo).
Quindi ...
... se tutte le variabili fuori base hanno coefficiente di costo ridotto minore o uguale a 0, ovvero
γj ≤ 0 j = 1, . . . , n − m.
la soluzione di base associata a B é soluzione ottima del problema di PL.
Il metodo del simplesso – p. 49/127
Una dimostrazione formale
Il valore dell’obiettivo in corrispondenza della soluzione di base associata a B é γ0.
Una dimostrazione formale
Il valore dell’obiettivo in corrispondenza della soluzione di base associata a B é γ0.
Inoltre in Sa si ha xim+j ≥ 0, j = 1, . . . , n − m.
Il metodo del simplesso – p. 50/127
Una dimostrazione formale
Il valore dell’obiettivo in corrispondenza della soluzione di base associata a B é γ0.
Inoltre in Sa si ha xim+j ≥ 0, j = 1, . . . , n − m. Quindi per il valore dell’obiettivo in Sa si avrá:
γ0 +
n−mX
j=1
γj
|{z}≤0
xim+j
| {z }
≥0
≤ γ0,
Una dimostrazione formale
Il valore dell’obiettivo in corrispondenza della soluzione di base associata a B é γ0.
Inoltre in Sa si ha xim+j ≥ 0, j = 1, . . . , n − m. Quindi per il valore dell’obiettivo in Sa si avrá:
γ0 +
n−mX
j=1
γj
|{z}≤0
xim+j
| {z }
≥0
≤ γ0,
ovvero in Sa il valore dell’obiettivo non puó mai superare il valore γ0. Essendo questo anche il valore dell’obiettivo per la nostra soluzione di base, tale soluzione di base é anche soluzione ottima del nostro problema.
Il metodo del simplesso – p. 50/127
In forma vettoriale
Ricordando che γj sono le componenti del vettore
cN − cBA−1B AN (detto anche, per questa ragione, vettore dei coefficienti di costo ridotto), in forma vettoriale la condizione sufficiente di ottimalitá si esprime nel modo seguente:
cN − cBA−1B AN ≤ 0.
La condizione non é necessaria!
Puó succedere che la soluzione di base sia giá una soluzione ottima ma la condizione di ottimalitá non sia soddisfatta. Ció peró puó accadere solo nel caso di una soluzione di base degenere.
Il metodo del simplesso – p. 52/127
Un esempio
Sia data la seguente riformulazione rispetto alla base {x3, x4} di un problema di PL:
max x1
x3 = 1 − x2 x4 = −x1
x1, x2, x3, x4 ≥ 0 La soluzione di base corrispondente é:
x3 = 1 x4 = 0 x1 = x2 = 0.
Si noti che é degenere. La condizione di ottimalitá non é soddisfatta (il coefficiente di x1 nell’obiettivo é pari a 1).
Continua
Passiamo ora, con l’operazione di cardine, alla base
adiacente {x1, x3}. La riformulazione rispetto a questa base é la seguente:
max −x4
x3 = 1 − x2 x1 = −x4
x1, x2, x3, x4 ≥ 0
Ora la condizione di ottimalitá é soddisfatta e quindi la
soluzione di base associata é ottima. Ma se osserviamo la soluzione di base associata, questa coincide esattamente con la precedente.
Il metodo del simplesso – p. 54/127
Osservazione
Si puó dimostrare che data una soluzione di base ottima esiste sempre almeno una base corrispondente per la quale la condizione di ottimalitá é soddisfatta.
Nell’esempio abbiamo visto come la stessa soluzione di base sia rappresentata sia dalla base {x3, x4} che dalla base {x1, x3}. La prima base non soddisfa la condizione, ma questa é soddisfatta dalla seconda base.
Verifica di illimitatezza
Supponiamo ora che la condizione di ottimalitá non sia soddisfatta. Un’altra domanda che possiamo porci é la seguente: quando il problema ha valore dell’obiettivo illimitato?
Il metodo del simplesso – p. 56/127
Verifica di illimitatezza
Supponiamo ora che la condizione di ottimalitá non sia soddisfatta. Un’altra domanda che possiamo porci é la seguente: quando il problema ha valore dell’obiettivo illimitato?
Una condizione sufficiente perché questo si verifichi é la seguente:
∃ γh > 0 : αrh ≥ 0 r = 1, . . . , m.
Infatti ...
... nella riformulazione rispetto alla base B poniamo a zero tutte le variabili fuori base tranne la variabile xim+h con
γh > 0. Ció che rimane é:
max γ0 + γhxim+h
xi1 = β1 + α1hxim+h
· · ·
xim = βm + αmhxim+h x1, . . . , xn ≥ 0
Cosa succede se faccio crescere il valore della variabile xim+h?
Il metodo del simplesso – p. 57/127
Continua
Per ogni r ∈ {1, . . . , m}: xir = βr
|{z}≥0
+ αrh
|{z}≥0
xim+h
| {z }
≥0
≥ 0,
quindi per ogni possibile valore non negativo di xim+h le
variabili in base continuano ad avere valore non negativo e quindi rimaniamo all’interno di Sa.
Ma vediamo ora cosa succede all’obiettivo:
Continua
Per ogni r ∈ {1, . . . , m}: xir = βr
|{z}≥0
+ αrh
|{z}≥0
xim+h
| {z }
≥0
≥ 0,
quindi per ogni possibile valore non negativo di xim+h le
variabili in base continuano ad avere valore non negativo e quindi rimaniamo all’interno di Sa.
Ma vediamo ora cosa succede all’obiettivo:
γ0 + γh
|{z}>0
xim+h →
xim+h|{z}→+∞
+∞,
da cui Sott = ∅ in quanto il valore dell’obiettivo é illimitato in Sa.
Il metodo del simplesso – p. 58/127
Un esempio
Sia data la seguente riformulazione rispetto alla base {x1, x2} di un problema di PL:
max 2 + x3 − x4 x1 = 2 + x3 + x4 x2 = 1 + 2x3 + x4
x1, x2, x3, x4 ≥ 0
Il coefficiente di x3 nell’obiettivo é positivo e non negativi sono anche i coefficienti di x3 nelle equazioni dei vincoli.
Continua
Se poniamo x4 = 0 e x3 = t ≥ 0 il problema diventa:
max 2 + t
x1 = 2 + t x2 = 1 + 2t x1, x2, x3, x4 ≥ 0 da cui si nota che i punti
x1 = 2 + t x2 = 1 + 2t x3 = t x4 = 0
sono tutti in Sa per ogni t ≥ 0, mentre il valore dell’obiettivo cresce a +∞ al crescere di t a +∞.
Il metodo del simplesso – p. 60/127
Cambio di base
Cosa succede se nessuna delle due condizioni di arresto (ottimalitá e illimitatezza) é soddisfatta?
Cambio di base
Cosa succede se nessuna delle due condizioni di arresto (ottimalitá e illimitatezza) é soddisfatta?
Effettuo un cambio di base passando da quella attuale ad una adiacente.
Ma come scelgo la base adiacente verso cui spostarmi?
Il metodo del simplesso – p. 61/127
Cambio di base
Cosa succede se nessuna delle due condizioni di arresto (ottimalitá e illimitatezza) é soddisfatta?
Effettuo un cambio di base passando da quella attuale ad una adiacente.
Ma come scelgo la base adiacente verso cui spostarmi?
Voglio cercare di spostarmi in una base adiacente che:
sia ancora ammissibile
la soluzione di base corrispondente abbia valore della funzione obiettivo non peggiore rispetto a quella attuale.
Variabile da far entrare in base
Scelgo la variabile fuori base da far entrare in base cercando di garantire un miglioramento del valore dell’obiettivo
Quali variabili fuori base (e quindi a valore nullo nella soluzione di base) possono consentirmi di migliorare il valore dell’obiettivo?
Il metodo del simplesso – p. 62/127
Variabile da far entrare in base
Scelgo la variabile fuori base da far entrare in base cercando di garantire un miglioramento del valore dell’obiettivo
Quali variabili fuori base (e quindi a valore nullo nella soluzione di base) possono consentirmi di migliorare il valore dell’obiettivo?
Dovremo far crescere quelle con coefficiente di costo ridotto γj positivo (facendo crescere le altre il valore dell’obiettivo diminuisce oppure non cambia). Quindi dobbiamo restringere l’attenzione alle sole variabili xim+j tali che γj > 0.
E...
... se c’é piú di una variabile con coefficiente di costo ridotto positivo?
Qui adotteremo la regola di scelta tra queste variabili che consiste nel scegliere quella che fa crescere piú
rapidamente il valore dell’obiettivo e cioé la variabile xim+h tale che:
γh = max
j=1,...,n−m γj,
tenendo comunque presente che questa non é l’unica regola possibile.
Nel caso il massimo sia raggiunto da piú variabili adottiamo (come pura convenzione) la regola di selezionare la
variabile con indice piú piccolo.
Il metodo del simplesso – p. 63/127
Nell’esempio
Data la seguente riformulazione rispetto alla base {x1, x2} di un problema di PL:
max 2 + 2x3 + 2x4 + x5 x1 = 1 − x3 + x4 + x5 x2 = 2 − x3 − x4 − x5
x1, x2, x3, x4, x5 ≥ 0
Nell’esempio
Data la seguente riformulazione rispetto alla base {x1, x2} di un problema di PL:
max 2 + 2x3 + 2x4 + x5 x1 = 1 − x3 + x4 + x5 x2 = 2 − x3 − x4 − x5
x1, x2, x3, x4, x5 ≥ 0
In questo caso tutte le variabili fuori base hanno
coefficiente di costo ridotto positivo. Tra queste considero quelle il cui coefficiente di costo ridotto é massimo (la x3 e la x4). Tra le due scelgo quella con indice minore e quindi la x3. Quindi scegliamo la variabile fuori base x3 come nuova variabile da far entrare in base.
Il metodo del simplesso – p. 64/127
Variabile uscente dalla base
Una volta scelta la variabile xim+h che dovrá entrare in base, quale variabile in base dovrá farle posto, ovvero quale sará la variabile in base xik che dovrá uscire dalla base?
Variabile uscente dalla base
Una volta scelta la variabile xim+h che dovrá entrare in base, quale variabile in base dovrá farle posto, ovvero quale sará la variabile in base xik che dovrá uscire dalla base?
Se la scelta della variabile che entra in base é guidata dal desiderio di far crescere il valore dell’obiettivo, la scelta della variabile uscente dalla base sará motivata dal
desiderio di non uscire dalla regione ammissibile.
Il metodo del simplesso – p. 65/127
Continua
Nella riformulazione rispetto alla base corrente fissiamo a 0 tutte le variabili fuori base tranne la xim+h. Si avrá dunque:
max γ0 + γhxim+h
xi1 = β1 + α1hxim+h
· · ·
xim = βm + αmhxim+h x1, . . . , xn ≥ 0
Fino a quando possiamo far crescere il valore di xim+h senza uscire dalla regione ammissibile?
Continua
Abbiamo due casi:
Caso 1 Per tutti gli r ∈ {1, . . . , m} tali che αrh ≥ 0 vediamo che:
xir = βr + αrh
|{z}≥0
xim+h
| {z }
≥0
≥ βr ≥ 0.
Quindi in questo caso non abbiamo alcuna restrizione sulla crescita di xim+h.
Il metodo del simplesso – p. 67/127
Continua
Caso 2 Per gli r tali che αrh < 0, allora vediamo che il valore di xim+h puó crescere al massimo fino a:
− βr αrh
e oltre questo valore la variabile xir assume valori
negativi (si esce quindi dalla regione ammissibile Sa).
Quindi ...
... se vogliamo rimanere in Sa, ci dobbiamo arrestare non appena una variabile xir con αrh < 0 si annulla al crescere di xim+h. Questa sará la variabile xik tale che
αkh < 0 e − βk
αkh = min
r : αrh<0
½
− βr αrh
¾ .
(Criterio dei minimi rapporti).
Nel caso il minimo sia raggiunto da piú variabili la scelta ricade, per convenzione, su quella con indice piú piccolo.
La variabile xik sará quella che uscirá dalla base.
Il metodo del simplesso – p. 69/127
Nell’esempio
Abbiamo precedentemente scelto x3 come variabile
entrante in base. Quale variabile dovrá uscire dalla base?
Nell’esempio
Abbiamo precedentemente scelto x3 come variabile
entrante in base. Quale variabile dovrá uscire dalla base?
Sia la x1 che la x2 sono candidate (per entrambe il
coefficiente di x3 nelle rispettive equazioni é negativo).
Qual é la prima che si annulla al crescere di x3?
Il metodo del simplesso – p. 70/127
Continua
Fissando a 0 tutte le variabili fuori base tranne la x3 si ottiene:
max 2 + 2x3 x1 = 1 − x3 x2 = 2 − x3
x1, x2, x3, x4, x5 ≥ 0
e si puó vedere che per mantenersi in Sa (cioé per mantenere non negative le variabili in base x1 e x2)
possiamo far crescere x3 al massimo fino al valore 1. In
corrispondenza di tale valore si annulla la variabile x1 e tale variabile sará quella che dovrá uscire di base.
Continua
Equivalentemente, utilizzando il criterio dei minimi rapporti:
x1 → − 1
−1 = 1 x2 → − 2
−1 = 2.
Il minimo dei rapporti (pari a 1) é raggiunto in
corrispondenza della variabile x1 e quindi questa sará la variabile che dovrá uscire dalla base.
Il metodo del simplesso – p. 72/127
E infine ...
... una volta selezionata la variabile entrante in base (la xim+h) e quella uscente di base (la xik) con le regole viste, non resta che compiere l’operazione di cardine nel modo giá descritto in precedenza ottenendo la riformulazione rispetto alla nuova base B′.
