Il metodo del simplesso - di.unito.itlocatell/didattica/ro1/simplesso-sl-bf.pdf · I problemi di PL...

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


Un’osservazione

Osservazione

Ogni problema di PL in forma canonica può esseretrasformato in uno equivalente in forma standard.


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.


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


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.


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


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.


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

]


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.


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.


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


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


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


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.


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:

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.


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, 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


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.


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


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


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.


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


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


−1B AN )xN

xB = A−1B b − A

−1B ANxN

xB,xN ≥ 0


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


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


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


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


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


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


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


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.


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.


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


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


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


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.


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.


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

.


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


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


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


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.


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.


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.


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.


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


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.


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.


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

?


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.


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.


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 +∞.


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.


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.


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.


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.


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.


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


· · ·


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 ≥ 0vediamo che:

xir = βr + αrh︸︷︷︸

≥0

xim+h︸︷︷︸

≥0

≥ βr ≥ 0.

Quindi in questo caso non abbiamo alcuna restrizionesulla crescita di xim+h

.


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


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.


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?


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.


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.


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


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


Ed ora...

... non facciamo altro che iterare sulla nuova base B′

quanto fatto sulla base precedente B.


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

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.


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


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


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.


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.


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.


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.


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.


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.


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.


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!


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.


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


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.


Esempio

max 4 − x1 − x2

x3 = 2 + x1 − x2

x4 = 1 − 2x2

x1, x2, x3, x4 ≥ 0


E se esiste un qualcheγh = 0?

Esistono in tal caso più soluzioni ottime?

Non è detto. Sono possibili diversi casi.


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


· · ·


x1, . . . , xn ≥ 0


Caso 1

Esiste h tale che γh = 0 e

αrh ≥ 0 r = 1, . . . ,m,

Esiste certamente un insieme illimitato di soluzioni ottime.


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.


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.


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.


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.


Esempio 1

max 4 − x2

x3 = 2 + x1 − x2

x4 = −x1 − x2

x1, x2, x3, x4 ≥ 0

Esiste una sola soluzione ottima.


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


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.


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


Riformulazione modificata


−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:


−1B AN )xN

xB + A−1B ANxN = A

−1B b

xB,xN ≥ 0


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.


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.


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.


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


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?


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


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


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


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


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.


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.


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.


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.


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.


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.


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= ∅


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


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.


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.


Esempio

max x1 + 2x2

−x1 − x2 + x3 = −1

x1 + x2 + x4 = 2

x1, x2, x3, x4 ≥ 0


Esempio

max 2x1 + x2 + 1/2x3

x1 + x2 + x3 = 3

x1 − x2 + x3 = 1

x1 + x3 = 2

x1, x2, x3 ≥ 0


Esempio

max x1 + x2

x1 + x2 = 3

x1 + x3 = 1

x2 + x4 = 1

x1, x2, x3, x4 ≥ 0


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 - di.unito.itlocatell/didattica/ro1/simplesso-sl-bf.pdf · I problemi di PL...

Documents

Transcript of Il metodo del simplesso - di.unito.itlocatell/didattica/ro1/simplesso-sl-bf.pdf · I problemi di PL...