Post on 19-Feb-2019
Il metodo del simplesso
Il metodo del simplesso – p. 1/128
I problemi di PL in forma standard
I problemi di PL in forma standard hanno la seguenteformulazione:
max cx
aix = bi i = 1, . . . ,m
x ≥ 0
o, equivalentemente, in forma matriciale:
max cx
Ax = b
x ≥ 0
Il metodo del simplesso – p. 2/128
Un’osservazione
Osservazione
Ogni problema di PL in forma canonica può esseretrasformato in uno equivalente in forma standard.
Il metodo del simplesso – p. 3/128
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 alseguente:
max cx
aix + yi = bi i = 1, . . . ,m
x ≥ 0
yi ≥ 0 i = 1, . . . ,m
che è in forma standard. Il metodo del simplesso – p. 4/128
Continua
Ogni problema di PL può essere ricondotto ad unoequivalente in forma canonica.
Ogni problema in forma canonica può essere ricondotto aduno equivalente in forma standard.
Quindi: ogni problema di PL può essere ricondotto ad unoequivalente in forma standard.
NB: nella pratica si passa direttamente da un problema diPL in forma generica ad uno equivalente in forma standard,senza passare necessariamente attraverso un problema informa canonica.
Il metodo del simplesso – p. 5/128
Un esempio
Si trasformi il seguente problema di PL in forma generica inun 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/128
Ipotesi aggiuntiva
Si richiede che la matrice dei vincoli A ∈ Rm×n abbia rangopari a m, il numero delle sue righe, il che equivale arichiedere che:
non ci sono righe di A ottenibili come combinazionilineari di altre righe di A;
esistono m colonne della matrice A che formano unamatrice quadrata invertibile.
NB: Si può dimostrare che anche questa non è unacondizione restrittiva e che ci si può sempre ricondurre adessa.
Il metodo del simplesso – p. 7/128
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/128
Base di un problema di PL
Si definisce base di un problema di PL in forma standard unsottinsieme:
B = {xi1 , . . . , xim}
di m delle n variabili del problema di PL con la proprietà chela matrice AB ∈ Rm×m ottenuta considerando le solecolonne di A relative alle variabili xik , k = 1, . . . ,m, siainvertibile.
Le variabili dell’insieme B verranno dette variabili in base,quelle al di fuori di B verranno raggruppate nell’insieme:
N = {xim+1, . . . , xin}
e verranno dette variabili fuori base.
Il metodo del simplesso – p. 9/128
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/128
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} eB4 = {x4, x5} sono basi.
Il metodo del simplesso – p. 11/128
Riformulazione rispetto alla baseB
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 fuoribase
AN ∈ Rm×(n−m) la matrice ottenuta da A considerandole sole colonne relative alle variabili fuori base.
Il metodo del simplesso – p. 12/128
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
]
Il metodo del simplesso – p. 13/128
Riscrittura della riformulazione
Possiamo ora riscrivere il problema di PL in forma standardnella 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
Il metodo del simplesso – p. 14/128
Nell’esempio
max
cBxB︷ ︸︸ ︷
3x1 + 2x3 +
cNxN︷ ︸︸ ︷
4x2 + 2x4 + x5
ABxB︷ ︸︸ ︷
x1 + 2x3 +
ANxN︷ ︸︸ ︷
2x2 + x4 − x5 = 2
x1 + x3 + 2x2 + 4x4 − 2x5 = 2
x1, x3︸ ︷︷ ︸
xB
, x2, x4, x5︸ ︷︷ ︸
xN
≥ 0
Il metodo del simplesso – p. 15/128
E quindi ...
max
cBxB︷ ︸︸ ︷
3x1 + 2x3 +
cNxN︷ ︸︸ ︷
4x2 + 2x4 + x5
ABxB︷ ︸︸ ︷
x1 + 2x3 =
b−ANxN︷ ︸︸ ︷
2 − 2x2 − x4 + x5
x1 + x3 = 2 − 2x2 − 4x4 + 2x5
x1, x3︸ ︷︷ ︸
xB
, x2, x4, x5︸ ︷︷ ︸
xN
≥ 0
Il metodo del simplesso – p. 16/128
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 diuguaglianza considerando la variabili in base comeincognite del sistema e quelle fuori base come parametri.
Il metodo del simplesso – p. 17/128
Nell’esempio
max 3x1 + 2x3 + 4x2 + 2x4 + x5
x1 = 2 − 2x2 − 7x4 + 3x5
x3 = 0 + 3x4 − x5
x1, x3, x2, x4, x5 ≥ 0
Il metodo del simplesso – p. 18/128
Riformulazione rispetto alla base B
Infine, sostituendo xB nell’obiettivo:
cBxB + cNxN = cB
(A
−1B b − A
−1B ANxN
)+ cNxN
da cui:
max cBA−1B b + (cN − cBA
−1B AN )xN
xB = A−1B b − A
−1B ANxN
xB,xN ≥ 0
Questa riformulazione viene detta riformulazione delproblema di PL rispetto alla base B.
NB: tale riformulazione è del tutto equivalente al problemaoriginario di PL.
Il metodo del simplesso – p. 19/128
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
Il metodo del simplesso – p. 20/128
Soluzioni di base
Si definisce soluzione di base associata alla base B, laseguente soluzione del sistema di vincoli di uguaglianzaottenuta 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/128
Ammissibilità e non degenerazione
Se A−1B b ≥ 0 la soluzione di base si dice ammissibile.
Questo vuol dire che appartiene alla regione ammissibiledel problema di PL in quanto, oltre a soddisfare i vincoli diuguaglianza del problema, soddisfa anche quelli di nonnegatività 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/128
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.
Il metodo del simplesso – p. 23/128
Osservazione
Data una soluzione di base ammissibile e non degenereesiste un’unica base che la rappresenta, mentre unasoluzione di base ammissibile e degenere è rappresentatada più basi.
Si verifichi, ad esempio, che la base B5 = {x1, x4} ha comesoluzione di base associata:
x1 = 2 x4 = 0 x2 = x3 = x5 = 0,
che è la stessa associata alla base B2.
Il metodo del simplesso – p. 24/128
Ma ...
... cosa hanno a che fare le basi e le soluzioni di base con ilteorema fondamentale della PL?
La risposta ci viene dalla seguente osservazione.
Osservazione L’insieme dei vertici di Sa coincide con l’insiemedelle soluzioni di base ammissibili del problema di PL.
In pratica, vertici e di soluzioni di base ammissibili sono lastessa cosa vista da due punti di vista diversi: quellogeometrico (i vertici) e quello algebrico (le soluzioni di baseammissibili).
Il metodo del simplesso – p. 25/128
Basi adiacenti
Due basi B′ e B′′ si definiscono adiacenti se hanno m − 1variabili uguali e differiscono per una sola variabile.
Nell’esempio le basi B3 = {x3, x4} e B4 = {x4, x5} sonoadiacenti, mentre non lo sono B2 = {x1, x3} e B4.
Il metodo del simplesso – p. 26/128
Soluzioni di base adiacenti
Due soluzioni di base distinte si definiscono adiacenti seesistono due basi B′ e B′′ che le rappresentano e che sonotra loro adiacenti.
Si noti che due basi adiacenti non corrispondononecessariamente a due soluzioni di base adiacenti. Esseinfatti possono corrispondere alla stessa soluzione di basecome accade, ad esempio, con le basi B2 = {x1, x3} eB5 = {x1, x4}.
Il metodo del simplesso – p. 27/128
Riformulazione rispetto alla baseB
Sia data la base:
B = {xi1 , . . . , xim}.
conN = {xim+1
, . . . , xin}
l’insieme delle variabili fuori base. Abbiamo visto che, datala base B, la riformulazione del problema di PL rispetto allabase 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/128
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 dellamatrice −A
−1B AN
Il metodo del simplesso – p. 29/128
Continua
In forma scalare possiamo riscrivere la riformulazionerispetto alla base B nel seguente modo:
max γ0 +∑n−m
j=1 γjxim+j
xi1 = β1 +∑n−m
j=1 α1jxim+j
· · ·
xik = βk +∑n−m
j=1 αkjxim+j
· · ·
xim = βm +∑n−m
j=1 αmjxim+j
x1, . . . , xn ≥ 0
Il metodo del simplesso – p. 30/128
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
Il metodo del simplesso – p. 31/128
Passaggio ad una base adiacente
Supponiamo ora di voler passare dalla base B alla baseadiacente 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 deveavere che AB′ è invertibile.
Il metodo del simplesso – p. 32/128
Continua
Si ha che AB′ è invertibile e quindi B′ è una base se e solose nella riformulazione associata alla base B il coefficientedi xim+h
nell’equazione relativa a xik è diverso da 0, ovverose e solo se:
αkh 6= 0.
Nell’esempio:{x1, x2} non è una base{x1, x5} è una base
Il metodo del simplesso – p. 33/128
L’operazione di cardine
Tale operazione consente di passare dalla riformulazionerispetto alla base B a quella rispetto alla base adiacente B′.Per fare questo dovremo compiere le seguenti operazioni.
Ricavare xim+hdall’equazione relativa a xik , cioè:
xim+h= −
βk
αkh
+1
αkh
xik −n−m∑
j=1, j 6=h
αkj
αkh
xim+j.
sostituire ogni occorrenza della variabile xim+hnelle
restanti equazioni e nell’obiettivo con la parte destra ditale equazione
Il metodo del simplesso – p. 34/128
Esempio
Dalla riformulazione rispetto a B2 = {x1, x3} a quellarispetto a B6 = {x1, x5}
Ricavo x5 dall’equazione relativa a x3
x5 = 0 − x3 + 3x4
Sostituisco la parte destra dell’equazione nei restantivincoli 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
Il metodo del simplesso – p. 35/128
Riformulazione rispetto a B6 = {x1, x5}
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/128
Nota bene
Per poter recuperare dalle riformulazioni alcuneinformazioni (nel seguito vedremo, ad esempio, comesfruttare la riformulazione rispetto a una base B per poterottenere la matrice A
−1B ) è necessario mantenere un ordine
tra le variabili in una base. Quindi se nella base B′ lavariabile xim+h
sostituisce la variabile xik a cui corrispondela k-esima equazione della riformulazione rispetto a B,nella riformulazione rispetto a B′ l’equazione relativa allavariabile xim+h
dovrà ancora essere la k-esima, mentre laposizione delle equazioni relative a tutte le altre variabilideve rimanere invariata rispetto alla precedenteriformulazione.
Il metodo del simplesso – p. 37/128
Nell’esempio ...
... la variabile x5 ha preso il posto della x3 e l’equazionerelativa alla x5 è stata messa nella stessa posizione (laseconda) in cui si trovava quella della x3, mentre la restanteequazione ha mantenuto la posizione originaria.
Il metodo del simplesso – p. 38/128
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 restantivincoli 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/128
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
Il metodo del simplesso – p. 40/128
Nota bene
Le operazioni di cardine che abbiamo eseguito sugliesempi ci hanno consentito di passare da una base ad unaadiacente e, nel secondo esempio, anche da una soluzionedi base ad una adiacente. Tuttavia, nel secondo casosiamo passati da una soluzione di base ammissibile (quellaassociata a B6) ad una non ammissibile (quella associata aB4). Nell’algoritmo di risoluzione che ci apprestiamo adiscutere la scelta della base adiacente verso cui muoversinon verrà fatta a caso come abbiamo fatto nei precedentiesempi, ma sarà guidata da regole precise chefondamentalmente ci consentiranno di spostarsi tra verticidella regione ammissibile migliorando il valore dellafunzione obiettivo.
Il metodo del simplesso – p. 41/128
Ipotesi iniziale
Data la base B e la riformulazione rispetto ad essa:
max γ0 +∑n−m
j=1 γjxim+j
xi1 = β1 +∑n−m
j=1 α1jxim+j
· · ·
xik = βk +∑n−m
j=1 αkjxim+j
· · ·
xim = βm +∑n−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).
Il metodo del simplesso – p. 42/128
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 momentosupponiamo di avere già a disposizione una baseammissibile B.
Il metodo del simplesso – p. 43/128
Coefficienti di costo ridotto
I coefficienti γj delle variabili fuori base nell’obiettivo dellariformulazione rispetto alla base B vengono detti coefficientidi costo ridotto delle variabili fuori base.
Questi esprimono la variazione dell’obiettivo incorrispondenza dell’incremento di un’unità della variabilefuori base corrispondente.
Il metodo del simplesso – p. 44/128
Infatti ...
... se consideriamo l’obiettivo della riformulazione:
γ0 +n−m∑
j=1
γjxim+j,
e supponiamo di tenere a 0 il valore di tutte le variabili fuoribase tranne la variabile xim+h
il cui valore vieneincrementato a 1, otteniamo Il nuovo valore dell’obiettivoγ0 + γh con una variazione rispetto al valore γ0 (quello nellasoluzione di base associata a B) pari proprio al valore γh
del coefficiente di costo ridotto della variabile fuori basexim+h
.
Il metodo del simplesso – p. 45/128
Un esempio
Sia data la seguente riformulazione rispetto alla baseammissibile {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 dibase è la costante che appare nell’obiettivo (2).
Il metodo del simplesso – p. 46/128
Continua
Se teniamo a 0 il valore di x4 e portiamo a 1 quello di x3, ilvalore dell’obiettivo diventa 3, con una variazione pari alcoefficiente di costo ridotto (+1) di x3
Se teniamo a 0 il valore di x3 e portiamo a 1 quello di x4, ilvalore dell’obiettivo diventa 1, con una variazione pari alcoefficiente di costo ridotto (-1) di x4
Il metodo del simplesso – p. 47/128
Verifica di ottimalità
Alla base ammissibile B è associata una soluzione di baseammissibile (un vertice di Sa). Posso stabilire se questasoluzione appartiene a Sott?
Data una variabile fuori base, il cui valore è nullo nellasoluzione di base associata a B, quando "conviene" farcrescere 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 ilcoefficiente è nullo) o diminuisce (se è negativo).
Il metodo del simplesso – p. 48/128
Quindi ...
... se tutte le variabili fuori base hanno coefficiente di costoridotto minore o uguale a 0, ovvero
γj ≤ 0 j = 1, . . . , n − m.
la soluzione di base associata a B è soluzione ottima delproblema di PL.
Il metodo del simplesso – p. 49/128
Una dimostrazione formale
Il valore dell’obiettivo in corrispondenza della soluzione dibase 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−m∑
j=1
γj︸︷︷︸
≤0
xim+j︸ ︷︷ ︸
≥0
≤ γ0,
ovvero in Sa il valore dell’obiettivo non può mai superare ilvalore γ0. Essendo questo anche il valore dell’obiettivo perla nostra soluzione di base, tale soluzione di base è anchesoluzione ottima del nostro problema.
Il metodo del simplesso – p. 50/128
In forma vettoriale
Ricordando che γj sono le componenti del vettorecN − cBA
−1B AN (detto anche, per questa ragione, vettore
dei coefficienti di costo ridotto), in forma vettoriale lacondizione sufficiente di ottimalità si esprime nel modoseguente:
cN − cBA−1B AN ≤ 0.
Il metodo del simplesso – p. 51/128
La condizione non è necessaria!
Può succedere che la soluzione di base sia già unasoluzione ottima ma la condizione di ottimalità non siasoddisfatta. Ciò però può accadere solo nel caso di unasoluzione di base degenere.
Il metodo del simplesso – p. 52/128
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).
Il metodo del simplesso – p. 53/128
Continua
Passiamo ora, con l’operazione di cardine, alla baseadiacente {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 lasoluzione di base associata è ottima. Ma se osserviamo lasoluzione di base associata, questa coincide esattamentecon la precedente.
Il metodo del simplesso – p. 54/128
Osservazione
Si può dimostrare che data una soluzione di base ottimaesiste sempre almeno una base corrispondente per laquale la condizione di ottimalità è soddisfatta.
Nell’esempio abbiamo visto come la stessa soluzione dibase sia rappresentata sia dalla base {x3, x4} che dallabase {x1, x3}. La prima base non soddisfa la condizione,ma questa è soddisfatta dalla seconda base.
Il metodo del simplesso – p. 55/128
Verifica di illimitatezza
Supponiamo ora che la condizione di ottimalità non siasoddisfatta. Un’altra domanda che possiamo porci è laseguente: quando il problema ha valore dell’obiettivoillimitato?
Una condizione sufficiente perché questo si verifichi è laseguente:
∃ γh > 0 : αrh ≥ 0 r = 1, . . . ,m.
Il metodo del simplesso – p. 56/128
Infatti ...
... nella riformulazione rispetto alla base B poniamo a zerotutte 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 variabilexim+h
?
Il metodo del simplesso – p. 57/128
Continua
Per ogni r ∈ {1, . . . ,m}:
xir = βr︸︷︷︸
≥0
+ αrh︸︷︷︸
≥0
xim+h︸ ︷︷ ︸
≥0
≥ 0,
quindi per ogni possibile valore non negativo di xim+hle
variabili in base continuano ad avere valore non negativo equindi rimaniamo all’interno di Sa.
Ma vediamo ora cosa succede all’obiettivo:
γ0 + γh︸︷︷︸
>0
xim+h→
︸︷︷︸
xim+h→+∞
+∞,
da cui Sott = ∅ in quanto il valore dell’obiettivo è illimitato inSa.
Il metodo del simplesso – p. 58/128
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 negativisono anche i coefficienti di x3 nelle equazioni dei vincoli.
Il metodo del simplesso – p. 59/128
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’obiettivocresce a +∞ al crescere di t a +∞.
Il metodo del simplesso – p. 60/128
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 aduna 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 dellafunzione obiettivo non peggiore rispetto a quella attuale.
Il metodo del simplesso – p. 61/128
Variabile da far entrare in base
Scelgo la variabile fuori base da far entrare in basecercando di garantire un miglioramento del valoredell’obiettivo
Quali variabili fuori base (e quindi a valore nullo nellasoluzione di base) possono consentirmi di migliorare ilvalore dell’obiettivo?
Dovremo far crescere quelle con coefficiente di costoridotto γj positivo (facendo crescere le altre il valoredell’obiettivo diminuisce oppure non cambia). Quindidobbiamo restringere l’attenzione alle sole variabilixim+j
tali che γj > 0.
Il metodo del simplesso – p. 62/128
E...
... se c’è più di una variabile con coefficiente di costo ridottopositivo?
Qui adotteremo la regola di scelta tra queste variabili checonsiste 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’unicaregola possibile.
Nel caso il massimo sia raggiunto da più variabili adottiamo(come pura convenzione) la regola di selezionare lavariabile con indice più piccolo.
Il metodo del simplesso – p. 63/128
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 hannocoefficiente di costo ridotto positivo. Tra queste consideroquelle il cui coefficiente di costo ridotto è massimo (la x3 ela x4). Tra le due scelgo quella con indice minore e quindi lax3. Quindi scegliamo la variabile fuori base x3 come nuovavariabile da far entrare in base.
Il metodo del simplesso – p. 64/128
Variabile uscente dalla base
Una volta scelta la variabile xim+hche 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 daldesiderio di far crescere il valore dell’obiettivo, la sceltadella variabile uscente dalla base sarà motivata daldesiderio di non uscire dalla regione ammissibile.
Il metodo del simplesso – p. 65/128
Continua
Nella riformulazione rispetto alla base corrente fissiamo a 0tutte 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?
Il metodo del simplesso – p. 66/128
Continua
Abbiamo due casi:
Caso 1 Per tutti gli r ∈ {1, . . . ,m} tali che αrh ≥ 0vediamo che:
xir = βr + αrh︸︷︷︸
≥0
xim+h︸ ︷︷ ︸
≥0
≥ βr ≥ 0.
Quindi in questo caso non abbiamo alcuna restrizionesulla crescita di xim+h
.
Il metodo del simplesso – p. 67/128
Continua
Caso 2 Per gli r tali che αrh < 0, allora vediamo che ilvalore di xim+h
può crescere al massimo fino a:
−βr
αrh
e oltre questo valore la variabile xir assume valorinegativi (si esce quindi dalla regione ammissibile Sa).
Il metodo del simplesso – p. 68/128
Quindi ...
... se vogliamo rimanere in Sa, ci dobbiamo arrestare nonappena una variabile xir con αrh < 0 si annulla al cresceredi xim+h
. Questa sarà la variabile xik tale che
αkh < 0 e −βk
αkh
= minr : αrh<0
{
−βr
αrh
}
.
(Criterio dei minimi rapporti).Nel caso il minimo sia raggiunto da più variabili la sceltaricade, per convenzione, su quella con indice più piccolo.La variabile xik sarà quella che uscirà dalla base.
Il metodo del simplesso – p. 69/128
Nell’esempio
Abbiamo precedentemente scelto x3 come variabileentrante in base. Quale variabile dovrà uscire dalla base?Sia la x1 che la x2 sono candidate (per entrambe ilcoefficiente di x3 nelle rispettive equazioni è negativo).Qual è la prima che si annulla al crescere di x3?
Il metodo del simplesso – p. 70/128
Continua
Fissando a 0 tutte le variabili fuori base tranne la x3 siottiene:
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è permantenere non negative le variabili in base x1 e x2)possiamo far crescere x3 al massimo fino al valore 1. Incorrispondenza di tale valore si annulla la variabile x1 e talevariabile sarà quella che dovrà uscire di base.
Il metodo del simplesso – p. 71/128
Continua
Equivalentemente, utilizzando il criterio dei minimi rapporti:
x1 → −1
−1= 1 x2 → −
2
−1= 2.
Il minimo dei rapporti (pari a 1) è raggiunto incorrispondenza della variabile x1 e quindi questa sarà lavariabile che dovrà uscire dalla base.
Il metodo del simplesso – p. 72/128
E infine ...
... una volta selezionata la variabile entrante in base (laxim+h
) e quella uscente di base (la xik) con le regole viste,non resta che compiere l’operazione di cardine nel modogià descritto in precedenza ottenendo la riformulazionerispetto alla nuova base B′.
Il metodo del simplesso – p. 73/128
Nell’esempio
Entra x3 ed esce x1.
L’operazione di cardine porta alla seguente riformulazionerispetto alla nuova base B′ = {x2, x3}:
max 4 − 2x1 + 4x4 + 3x5
x3 = 1 − x1 + x4 + x5
x2 = 3 + x1 − 2x4 − 2x5
x1, x2, x3, x4, x5 ≥ 0
Il metodo del simplesso – p. 74/128
Ed ora...
... non facciamo altro che iterare sulla nuova base B′
quanto fatto sulla base precedente B.
Il metodo del simplesso – p. 75/128
L’algoritmo del simplesso
Inizializzazione Sia B0 una base ammissibile e k = 0.
Passo 1- verifica ottimalit a Se soddisfatta la condizione diottimalità: STOP . La soluzione di base associata a Bk
è una soluzione ottima del problema. Altrimenti si vadaal Passo 2.
Passo 2 - verifica di illimitatezza Se è soddisfatta lacondizione di illimitatezza, allora: STOP, si ha Sott = ∅ inquanto l’obiettivo del problema è illimitato. Altrimenti sivada al Passo 3.
Passo 3 - scelta variabile entrante in base Si selezioni lavariabile xim+h
che dovrà entrare in base attraverso laregola vista.
Il metodo del simplesso – p. 76/128
Il metodo del simplesso
Passo 4 - scelta variabile uscente dalla base Si selezioni lavariabile xik che dovrà uscire dalla base attraverso laregola vista.
Passo 5 - operazione di cardine Si generi la nuova baseBk+1 sostituendo in Bk la variabile xik con la variabilexim+h
e si esegua la corrispondente operazione dicardine. Quindi, si ponga k = k + 1 e si ritorni al Passo1.
Il metodo del simplesso – p. 77/128
Nell’esempio
Condizione di ottimalità? NOCondizione di illimitatezza? NOVariabile entrante in base: x4
Variabile uscente dalla base: x2
Operazione di cardine:
max 10 − 2x2 − x5
x3 = 5/2 − 1/2x1 − 1/2x2
x4 = 3/2 + 1/2x1 − 1/2x2 − x5
x1, x2, x3, x4, x5 ≥ 0
Il metodo del simplesso – p. 78/128
Continua
Condizione di ottimalità? SI!Soluzione ottima: soluzione di base associata alla base{x3, x4}:
x1 = x2 = x5 = 0 x3 = 5/2 x4 = 3/2
Valore ottimo: γ0 = 10
Il metodo del simplesso – p. 79/128
Puntualizzazione
L’algoritmo del simplesso e i suoi derivati (di cui vedremo unesempio più avanti) non sono gli unici algoritmi dirisoluzione per problemi di PL.
Altri metodi di risoluzione per i problemi di PL sono icosidetti algoritmi del punto interno.
Il metodo del simplesso – p. 80/128
E non dimentichiamo ...
... che abbiamo ipotizzato di avere già a disposizione unabase ammissibile B0 ma non abbiamo ancora visto come sipuò stabilire se esiste e, nel caso esista, come trovarla.
Il metodo del simplesso – p. 81/128
Miglioramento valore obiettivo
Il valore dell’obiettivo nella nuova soluzione di base ottenutasostituendo xik nella base con xim+h
è
γ0 − γh
βk
αkh
.
con:
βk ≥ 0 per l’ammissibilità della soluzione di baseassociata a B.
γh > 0 per la regola di scelta della variabile entrante inbase.
αkh < 0 per la regola di scelta della variabile uscentedalla base.
Il metodo del simplesso – p. 82/128
Quindi ...
γ0 − γh︸︷︷︸
>0
≥0︷︸︸︷
βk
αkh︸︷︷︸
<0
≥ γ0.
ovvero: il valore dell’obiettivo nella nuova soluzione di baseassociata a B′ è non peggiore rispetto al valore γ0 nellasoluzione di base associata a B.
Il metodo del simplesso – p. 83/128
Inoltre ...
...se βk > 0, il che si verifica sempre nel caso di soluzioni dibase non degeneri, il nuovo valore dell’obiettivo èstrettamente migliore rispetto al precedente.
Nel caso degenere può succedere che i due valori sianouguali. In questo caso si può dimostrare che le due basi Be B′ rappresentano la stessa soluzione di base.
Il metodo del simplesso – p. 84/128
Finitezza del simplesso
Se tutte le soluzioni di base ammissibili in un problema diPL sono non degeneri, allora il metodo del simplessotermina in un numero finito di iterazioni.
Il metodo del simplesso – p. 85/128
Infatti ...
... ad ogni iterazione la nuova soluzione di baseammissibile (o vertice) ha un valore strettamente migliorerispetto alla precedente e quindi è diversa da tutte quelleche la hanno preceduta.
Essendo il numero di soluzioni di base ammissibili finito ( ivertici sono in numero finito), il metodo dovrà arrestarsidopo un numero finito di iterazioni o restituendo unasoluzione ottima oppure stabilendo che il problema haobiettivo illimitato.
Il metodo del simplesso – p. 86/128
E nel caso degenere?
Si può verificare la situazione di ciclaggio.
Trovandosi in un vertice degenere, l’algoritmo del simplessopuò generare la seguente sequenza di basi cherappresentano tutte questo stesso vertice degenere:
Bt→ Bt+1→ · · · → Bt+r−1→ Bt+r = Bt.
Una volta tornato nella base Bt si ripete tutto il ciclo: siamoentrati in un loop!
Il metodo del simplesso – p. 87/128
Ma ...
... la situazione di ciclaggio si verifica molto raramente nellapratica ed esistono anche regole particolari per la sceltadelle variabili da far entrare e uscire di base, dette regoleanticiclaggio (che non vedremo), che consentonoall’algoritmo di terminare in un numero finito di iterazioni.
Il metodo del simplesso – p. 88/128
Soluzioni ottime uniche e multiple
Una volta trovata una soluzione ottima del problema (unpunto in Sott) ci possiamo chiedere se ce ne sono altre.
Seγj < 0 j = 1, . . . ,m,
allora: soluzione ottima unica
Il metodo del simplesso – p. 89/128
Infatti ...
... in Sa si avrà:
γ0 +n−m∑
j=1
γj︸︷︷︸
<0
xim+j︸ ︷︷ ︸
≥0
≤ γ0,
Inoltre:
xim+j> 0 ⇒ γ0 +
n−m∑
j=1
γjxim+j< γ0
Quindi il valore ottimo γ0 si ottiene solo con xim+j= 0 ∀ j,
ovvero nella soluzione di base attuale.
Il metodo del simplesso – p. 90/128
Esempio
max 4 − x1 − x2
x3 = 2 + x1 − x2
x4 = 1 − 2x2
x1, x2, x3, x4 ≥ 0
Il metodo del simplesso – p. 91/128
E se esiste un qualcheγh = 0?
Esistono in tal caso più soluzioni ottime?
Non è detto. Sono possibili diversi casi.
Il metodo del simplesso – p. 92/128
Riformulazione ristretta
Riscriviamo la riformulazione rispetto alla base B tenendo a0 tutte le variabili fuori base tranne la xim+h
con γh = 0.Avremo:
max γ0
xi1 = β1 + α1hxim+h
· · ·
xim = βm + αmhxim+h
x1, . . . , xn ≥ 0
Il metodo del simplesso – p. 93/128
Caso 1
Esiste h tale che γh = 0 e
αrh ≥ 0 r = 1, . . . ,m,
Esiste certamente un insieme illimitato di soluzioni ottime.
Il metodo del simplesso – p. 94/128
Esempio
max 4 − x2
x3 = 2 + x1 − x2
x4 = 1 − 2x2
x1, x2, x3, x4 ≥ 0
Per tutti i t ≥ 0, i punti
x1 = t x2 = 0 x3 = 2 + t x4 = 1
sono soluzioni ottime.
Il metodo del simplesso – p. 95/128
Caso 2
Esiste h tale che γh = 0 e
∀ r : αrh < 0 si ha che βr > 0,
Esiste certamente un insieme limitato di soluzioni ottime: ilsegmento che congiunge la soluzione di base attuale conquella (distinta) ottenuta attraverso un’operazione dicardine che fa entrare in base xim+h
e sceglie secondo laregola già vista la variabile da far uscire di base.
Il metodo del simplesso – p. 96/128
Esempio
max 4 − x2
x3 = 2 + x1 − x2
x4 = 1 − x1 + 2x2
x1, x2, x3, x4 ≥ 0
Per tutti i t ∈ [0, 1], i punti
x1 = t x2 = 0 x3 = 2 + t x4 = 1 − t
sono soluzioni ottime.
Il metodo del simplesso – p. 97/128
Caso 3
Per ogni h tale che γh = 0 si ha che:
∃ r : αrh < 0 e βr = 0,
In tal caso non possiamo dire se esiste un’unica soluzioneottima o se vi sono soluzioni ottime multiple.
Il metodo del simplesso – p. 98/128
Esempio 1
max 4 − x2
x3 = 2 + x1 − x2
x4 = −x1 − x2
x1, x2, x3, x4 ≥ 0
Esiste una sola soluzione ottima.
Il metodo del simplesso – p. 99/128
Esempio 2
max 2 − x3
x4 = x1 − x2 − x3
x5 = −x1 + x2 + x3
x1, x2, x3, x4, x5 ≥ 0
Tutte le soluzioni:
x3 = x4 = x5 = 0 x1 = x2 = α ∀ α ≥ 0,
sono ammissibili e ottime (il caso α = 0 coincide con lasoluzione di base associata alla base {x4, x5}).
Il metodo del simplesso – p. 100/128
Come calcolareA−1B
Come vedremo è importante conoscere, data una base B ela relativa matrice AB, l’inversa A
−1B di tale matrice. Non è
però sempre necessario calcolare da zero tale inversa. Inalcuni casi la riformulazione rispetto alla base B ci forniscegià la matrice A
−1B . Quali sono questi casi?
Quelli in cui alcune colonne della matrice A formano lamatrice identica I, ovvero esistono m variabili [xt1 , . . . , xtm
]le cui corrispondenti colonne nella matrice A formano lamatrice identica di ordine m × m.
Il metodo del simplesso – p. 101/128
Esempio
max x1 − x3 − 2x4 − 2x5
x1 + x2 + x4 = 8
x1 − x2 + x3 = 4
x1 + 2x2 + x5 = 12
x1, x2, x3, x4, x5 ≥ 0
Prendiamo le m = 3 variabili [x4, x3, x5]
x4 →
1
0
0
x3 →
0
1
0
x5 →
0
0
1
Il metodo del simplesso – p. 102/128
Riformulazione modificata
max cBA−1B b + (cN − cBA
−1B AN )xN
xB = A−1B b − A
−1B ANxN
xB,xN ≥ 0
Riscriviamo questa portando tutte le variabili fuori basenella parte sinistra delle equazioni dei vincoli, ovvero:
max cBA−1B b + (cN − cBA
−1B AN )xN
xB + A−1B ANxN = A
−1B b
xB,xN ≥ 0
Il metodo del simplesso – p. 103/128
Lettura dell’inversa
La prima colonna di A−1B è la colonna relativa a xt1 nella
riformulazione modificata , la seconda colonna di A−1B è la
colonna relativa a xt2 nella riformulazione modificata,eccetera fino alla m-esima colonna di A−1
B che è la colonnarelativa a xtm
nella riformulazione modificata.
NB: l’ordine delle variabili xtr, r = 1, . . . ,m, è essenziale.
Il metodo del simplesso – p. 104/128
Sull’esempio
Base B0 = {x4, x3, x5}. La riformulazione rispetto a questabase è la seguente:
max −44 + 6x1 + 3x2
x4 = 8 − x1 − x2
x3 = 4 − x1 + x2
x5 = 12 − x1 − 2x2
x1, x2, x3, x4, x5 ≥ 0
Con una prima operazione di cardine scambiamo x1 e x3
nella base.
Il metodo del simplesso – p. 105/128
Continua
Base B1 = {x4, x1, x5}
max −24 − 6x3 + 9x2
x4 = 4 + x3 − 2x2
x1 = 4 − x3 + x2
x5 = 8 + x3 − 3x2
x1, x2, x3, x4, x5 ≥ 0
Poi, con una seconda operazione di cardine scambiamo x2
e x4 nella base.
Il metodo del simplesso – p. 106/128
Continua
Base B2 = {x2, x1, x5}
max −6 − 3/2x3 − 9/2x4
x2 = 2 + 1/2x3 − 1/2x4
x1 = 6 − 1/2x3 − 1/2x4
x5 = 2 − 1/2x3 + 3/2x4
x1, x2, x3, x4, x5 ≥ 0
Il metodo del simplesso – p. 107/128
Continua
A questo punto ci chiediamo: data la base B2 = {x2, x1, x5}con la relativa matrice di base:
AB2=
1 1 0
−1 1 0
2 1 1
qual è l’inversa di tale matrice?
Il metodo del simplesso – p. 108/128
Continua
Riformulazione modificata
max −6 − 3/2x3 − 9/2x4
x2 − 1/2x3 + 1/2x4 = 2
x1 + 1/2x3 + 1/2x4 = 6
x5 + 1/2x3 − 3/2x4 = 2
x1, x2, x3, x4, x5 ≥ 0
Il metodo del simplesso – p. 109/128
Continua
Prima colonna di A−1B2
è la colonna della variabile x4 nellariformulazione modificata
1/2
1/2
−3/2
Seconda colonna: i coefficienti di x3:
−1/2
1/2
1/2
Il metodo del simplesso – p. 110/128
Continua
Terza colonna: i coefficienti di x5:
0
0
1
Quindi:
A−1B2
=
1/2 −1/2 0
1/2 1/2 0
−3/2 1/2 1
Il metodo del simplesso – p. 111/128
Il metodo due fasi
Descriveremo ora un metodo, detto metodo due fasi, che,dato un problema di PL:
o ci consente di stabilire se Sa = ∅
o, in caso contrario, ci restituisce una base ammissibiledel problema.
Il metodo del simplesso – p. 112/128
Le due fasi
Problema di PL in forma standard:
max cx
aix = bi i = 1, . . . ,m
xj ≥ 0 j = 1, . . . , n
Chiameremo questo problema problema di II fase. Ad essoassociamo il seguente problema, detto problema di I fase:
ξ∗ = max −∑m
i=1 si
aix + si = bi i ∈ {1, . . . ,m} : bi ≥ 0
aix − si = bi i ∈ {1, . . . ,m} : bi < 0
xj ≥ 0 j = 1, . . . , n
si ≥ 0 i = 1, . . . ,m
Il metodo del simplesso – p. 113/128
Limitatezza obiettivo I fase
Per prima cosa notiamo che si ≥ 0, i = 1, . . . ,m, implica che
−m∑
i=1
si ≤ 0
e quindi l’obiettivo del problema di I fase non può essereillimitato.
Il metodo del simplesso – p. 114/128
Ammissibilità problema I fase
Riformulazione del problema di I fase rispetto alla base{s1, . . . , sm}:
ξ∗ = max −∑
i: bi≥0(bi − aix) −∑
i: bi<0(−bi + aix)
si = bi − aix i ∈ {1, . . . ,m
si = −bi + aix i ∈ {1, . . . ,m
xj ≥ 0 j = 1, . . . , n
si ≥ 0 i = 1, . . . ,m
La soluzione di base:
si = bi i : bi ≥ 0, si = −bi i : bi < 0, xj = 0 j = 1, . . . , n,
è ammissibile.
Il metodo del simplesso – p. 115/128
Quindi ...
... il problema di I fase ha regione ammissibile non vuota eobiettivo non illimitato. Ne consegue che esso ammettesoluzione ottima.
Osservazione Il problema di I fase ha valore ottimo ξ∗ pari a 0se e solo se il problema di II fase ha regione ammissibile Sa
non vuota.
Il metodo del simplesso – p. 116/128
Dimostrazione
Supponiamo dapprima che ξ∗ = 0 e dimostriamo cheSa 6= ∅.ξ∗ = 0 vuol dire che esiste una soluzione del problema di Ifase che indichiamo con (s,x) con tutte le variabili si = 0,cioè s = 0.
Il metodo del simplesso – p. 117/128
Continua
Se sostituiamo questa soluzione nei vincoli del problema diI fase otteniamo:
aix + si = bi i ∈ {1, . . . ,m} : bi ≥ 0
aix − si = bi i ∈ {1, . . . ,m} : bi < 0
xj ≥ 0 j = 1, . . . , n
si = 0 i = 1, . . . ,m
Equivalentemente:
aix = bi i = 1, . . . ,m x ≥ 0,
da cui si ricava che x ∈ Sa.
Il metodo del simplesso – p. 118/128
Viceversa ...
... supponiamo ora che Sa 6= ∅ e dimostriamo che questoimplica che ξ∗ = 0.Dato x ∈ Sa, ovvero
aix = bi i = 1, . . . ,m x ≥ 0,
si verifica facilmente che la soluzione (s,x) con
si = 0 i = 1, . . . ,m,
è ammissibile per il problema di I fase in quanto
aix + si = bi i ∈ {1, . . . ,m} : bi ≥ 0
aix − si = bi i ∈ {1, . . . ,m} : bi < 0
xj ≥ 0 j = 1, . . . , n
si = 0 i = 1, . . . ,mIl metodo del simplesso – p. 119/128
Continua
Tale soluzione ha come valore dell’obiettivo:
−m∑
i=1
si = 0.
Poiché, come già osservato, il valore dell’obiettivo delproblema di I fase non può essere superiore a 0, questasoluzione ammissibile è anche ottima per il problema di Ifase e il valore ottimo ξ∗ è pari a 0.
Il metodo del simplesso – p. 120/128
Quindi ...
... se risolviamo ora il problema di I fase utilizzando ilmetodo del simplesso a partire dalla base ammissibile{s1, . . . , sm} arriveremo ad un valore ottimo ξ∗ del problemadi I fase e:
ξ∗ < 0 ⇒ Sa = ∅
ξ∗ = 0 ⇒ Sa 6= ∅
Il metodo del simplesso – p. 121/128
Ma ...
... se sono nel secondo caso come faccio a trovare unabase ammissibile per il problema di II fase con la relativariformulazione? Abbiamo due casi possibili:
Caso 1 tutte le variabili si sono al di fuori della base ottimadel problema di I fase. In tal caso la base ottima delproblema di I fase è già una base ammissibile del problemadi II fase. La riformulazione del problema di II fase rispetto aquesta base si può ottenere semplicemente dallariformulazione del problema di I fase rispetto a questa base
Il metodo del simplesso – p. 122/128
Continua
Caso 2 Alcune variabili si sono nella base ottima delproblema di I fase.In tal caso si operano, fino a quando è possibile, delleoperazioni di cardine per far uscire di base le variabili si
attualmente in base facendo entrare al loro posto solovariabili xj.Se si riesce a far uscire dalla base tutte le variabili si ci siritrova infine nella stessa situazione del Caso 1 e siprocede nello stesso modo.Se non ci si riesce vuol dire che ci sono vincoli ridondantida eliminare nel problema.
Il metodo del simplesso – p. 123/128
Una semplificazione
Se una variabile xi del problema di II fase compare in unosolo dei vincoli di uguaglianza e in tale vincolo hacoefficiente dello stesso segno del corrispondente terminenoto, allora possiamo evitare di introdurre una variabile s inquel vincolo nel problema di I fase. In tal caso una baseammissibile iniziale per il problema di I fase comprenderà lavariabile xi.
Il metodo del simplesso – p. 124/128
Esempio
max x1 + 2x2
−x1 − x2 + x3 = −1
x1 + x2 + x4 = 2
x1, x2, x3, x4 ≥ 0
Il metodo del simplesso – p. 125/128
Esempio
max 2x1 + x2 + 1/2x3
x1 + x2 + x3 = 3
x1 − x2 + x3 = 1
x1 + x3 = 2
x1, x2, x3 ≥ 0
Il metodo del simplesso – p. 126/128
Esempio
max x1 + x2
x1 + x2 = 3
x1 + x3 = 1
x2 + x4 = 1
x1, x2, x3, x4 ≥ 0
Il metodo del simplesso – p. 127/128
Esempio
max −2s1 − 3s2 − x5
x1 = 3 − s1 − 2x4 − x5
x2 = 4 − 2s1 − 3s2 + x3 − x4 − x5
s3 = s1 + 2s2 + x5
x1, x2, x3, x4, x5, s1, s2, s3 ≥ 0
Faccio entrare in base x5 e faccio uscire dalla base s3
Il metodo del simplesso – p. 128/128