PL Simplesso FRODE 06 07

E. Amaldi -- Fondamenti di R. O. -- Politecnico di Milano 1

4.5 Metodo del simplesso

min z = cTxs.v.

Ax = bx 0

PL in forma standard

Esamina una sequenza di soluzioni di base ammissibilicon valori non crescenti della funzione obiettivo fino araggiungerne una ottima o a determinare che il PL illimitato (Dantzig 1947).

Si passa da una soluzione di base ammissibile ad una vicina


cammino lungo gli spigolidel poliedro delle soluzioni ammissibili fino a un vertice ottimo

vertici adiacentiGeometricamente:

NB: Nel caso peggiore il metodo pu esaminare tutte le soluzioni di base ammissibili ma mediamente risulta molto efficiente.


Bisogna sapere come:

determinare una soluzione di base ammissibile iniziale (o stabilire che il PL inammissibile)

applicando il metodo ad un altro PL

verificare lottimalit della soluzione di base ammissibile corrente

passare dalla soluzione di base ammissibile correntead una soluzione di base ammissibile vicina migliore(o stabilire che il PL illimitato).


Costi ridotti

Dati un PL min{ cTx : Ax = b, x 0 }

e una base ammissibile B, Ax = b si pu riscrivere come

B xB + N xN = b xB = B-1b - B-1N xNcon B-1b 0.Soluzione di base ammissibile: xB = B-1b, xN = 0


Sostituendo nella funzione obiettivo:

espressa in funzione solo delle variabili fuori base

z0 = costo soluzione di base ammissibilexB = B-1b, xN = 0

costi ridotticTN

B-1b B-1NxNxN

xBxN

cTx = (cTB cTN) = (cTB cTN)

cTx = cTB B-1b cTB B-1NxN + cTN xN= cTB B-1b + ( cTN cTB B-1N ) xN


cj = variazione della funzione obiettivo se xj fuori base aumentasse di 1 unit e le altre variabili fuori base rimanessero uguali a 0

vettore dei costi ridotti rispetto alla base B

= 0T cTN

= IcT cT cTB B-1A = [cTB cTB B-1B, cTN cTB B-1N]

Def.:


Test di ottimalit

Dato un PL di min (max) e una base ammissibile B, setutti i costi ridotti (delle variabili fuori base) sono nonnegativi (non positivi) la soluzione di base ammissibile xB = B-1b 0, xN = 0 di costo cTB B-1b ottima.Infatti cT 0T implica

cTx = cTB B-1b + cTN xN cTB B-1b x 0, A x = bNB: Questa condizione di ottimalit sufficiente ma

in generale non necessaria.


Cambiamento di base (min)Sia una base ammissibile B e xj fuori base (xN) con costo ridotto cj < 0.

Aumentare xj il pi possibile (entra in base) mantenendo le altre variabili fuori base uguali a 0.

La variabile xi in base (xB) tale che xi 0 impone il limite alla crescita di xj pi stringente si annulla (esce dalla base).

La nuova base ha una colonna diversa (vertici adiacenti)


Forma canonicaAd ogni iterazione bisogna porre il sistema

mibxan

jijij ,...,1

1==

=BxB + NxN = bin forma canonica

xi xj miban

mjiij ,...,1

1==+

+=

che mette in evidenza le variabili in base in funzione di quelle fuori base.

I xB + N xN = b

xB = b - N xN


La forma canonica associata ad una base B si ottiene

calcolano aij e bi in funzione di B-1

B-1B xB + B-1N xN = B-1b

eseguendo una sequenza di operazione di pivoting

I bN

I xB + N xN = b mette in evidenza la soluzione di base xB = b e xN = 0 !


Operazione di pivoting

1. Scegliere un coefficiente ars 0 (il pivot)2. Dividere per ars la r-esima riga3. Per ogni riga i r, sottrarre la r-esima riga

moltiplicata per ais

NB: Stesse operazioni (che lasciano invariato linsieme delle soluzioni) usate nel metodo di eliminazione di Gauss per risolvere i sistemi di equazioni lineari.


5-43/2

0130212-30-20- 1

523

0130210-1400-1121

Esempio: min z = x1 + x2 + x3x1 +2x2 + x3 x4 = 3

4x2 x3 + x5 = 22x1 +3x3 + x4 = 5

xi 0 i = 1,,5pivot

r

s

A b

5/2 1

03/201130000--10

colonne variabili in base


Operazioni di pivoting permettono di:

mettere un PL in forma canonica rispetto ad una base B passare da una forma canonica ad unaltra, ovvero

cambiare base.

Vantaggio: B-1 della nuova base B non viene calcolatada zero ma in modo incrementale applicando allinversa della base precedente (con ununica colonna diversa) ununica operazione di pivoting!


1) Variabile da fare entrare nella base

con costo ridotto cj < 0 (NB: decremento zdipende anche dal limite alla crescita di xj !)

che produce z massimo rispetto a z = cBTB-1b regola di Bland: s = min{ j : cj < 0}

scelta colonna s pivot

Scegliere la base ammissibile vicina (vertice adiacente) in modo tale da:

migliorare il valore della funzione obiettivo

mantenere lammissibilit

Per problemi di max: cj > 0


la funzione obiettivo illimitata!

NB: Se cj< 0 con aij 0 i, nessun elemento della colonna pu fare da pivot

limite alla crescita di xs pi stringente

altrimenti nessun limite!

scelta riga r pivot

2) Variabile da fare uscire dalla base

indice i con minimo = * tra quelle con ais>0

regola di Bland: r = min{ i : = *, ais>0 } a caso

is

i

ab

is

i

ab


Rappresentazione sotto forma di tabella(tableau)

z = cTxsistema

Ax = b

Tableau iniziale:- termine noto funz. obiettivo

termini noti

m righe

funz. obiettivo

Ab

cT0x1 xn

con vincoli di non negativit impliciti


N

cTN

Bb

cTB0

x1 xm xm+1 xn

00

-1z

Considerando una base B e partizionando A = [B N]

0 = cTx z

con operazioni di pivoting (o pre-moltiplicando per B-1) si porta il tableau in forma canonica rispetto a B:

N

cTN

Ib

0 0-z0

x1 xm xm+1 xn

variabili in base

-zxB[1]xB[m] b = B-1b

z = cTB B-1b + cTN xNz0


Esempio:

Tableau rispetto alla base con colonne 3, 4:

min z = - x1 - x26x1 +4x2 +x3 = 243x1 2x2 + x4 = 6

xi 0 i =1,, 4

x4

x3

-z

10-23601462400-1-10x4x3x2x1

pivot

I2x2Pivot su 3 equivale a ricavare x1 dalla riga pivot e sostituirla nelle rimanenti righe

x1 entra nella base e x4 esce dalla base

r

s

base


Tableau rispetto alla nuova base:

x1

x3

-z

1/30-2/312-2180121/30-5/302x4x3x2x1

base

soluzione di base ammissibile:

x1 = 2, x3 = 12, x2 = x4 = 0

con z = -2

1306

x1x1

costi ridotti


x2 unica variabile fuori base da fare entrare (c2 = -5/3 < 0)x3 unica variabile in base che pu uscire (ars = 8 > 0)

x1

x3

-z

1/30-2/312-2180121/30-5/302x4x3x2x1

r

s

x1

x2

-z

1/61/12013-1/41/8103/2-1/125/24009/2

x4x3x2x1

s

r

x4

x2

-z

10618013/2 6006x4x3x2x1

Tutti i costi rodotti 0 sol. di base (ammissibile) ottima:x*1 = 0, x*2 = 6, x*3 = 0, x*4 = 18

con z* = -6


Algoritmo del simplesso (PL di min)

],[]0,[

siaia

Procedura pivot(r,s)?

BEGINSiano B[1],,B[m] gli indici delle colonne di una base ammissibile iniziale B;Costruire il tableau iniziale A = {a[i,j]: 0im, 0jn} in forma canonica rispetto a B;illimitato:=false; ottimo:=false;WHILE (ottimo = false) AND (illimitato = false) THEN

IF a[0,j] 0 j=1,,m THEN ottimo := true; /* per PL di min */ELSE

Scegliere una xs fuori base con a[0,s] < 0;IF a[i,s] 0 i=1,,m THEN illimitato := true;ELSE

Determina indice r che minimizzacon 1 i m e a[i,s] > 0;pivot(r,s) /* aggiornamento tableau */B[r] := s;

END-IFEND-IF

END

costi ridotti


Degenerazione e convergenza

Def. Una soluzione di base ammissibile x degenere secontiene almeno una variabile di base = 0.

x con pi di n-m zeri corrisponde a pi basi distinte!

Stesso vertice:

pi di n vincoli ( gli m di Ax = b e pi di n-mtra gli n di x 0 ) sono soddisfatti con segno di uguaglianza.

x


Si pu percorrere ciclicamente (all) una sequenza di basi degeneri associate allo stesso vertice.

In presenza di soluzioni di base (ammissibili) degeneriil cambiamento di base pu non diminuire il valore della funzione obiettivo:

Se la sol. di base corrente degenere, * pu essere = 0 e quindi la nuova sol. di base identica a quella precedente.

Anche se * > 0, pi variabili in base possono annullarsi quando xs viene aumentata a *. La nuova sol. di base quindi degenere.


Esistono varie regole anticiclo per la scelta delle variabili che entrano ed escono dalla base (indici r, s)

# finito di pivot

nm

Proposizione: Lalgoritmo del simplesso con la regola di Bland termina dopo iterazioni.

Regola di Bland: tra le variabili candidate ad entrare/uscire dalla base (xs e xr) scegliere sempre quella con indice minore.


Campagne sperimentali:

Il numero di iterazioni cresce linearmente rispetto a m(m . 3m) e molto lentamente ( logaritmicamente) rispetto a n !

In casi patologici (Klee & Minty 72) il numero di iterazioni pu essere esponenziale in n e/o m,ma lalgoritmo mediamente molto efficiente.


Metodo del simplesso a due fasi

Fase 1: Determinazione di una soluzione di base ammissibile iniziale

min z = x1 +x3x1 +2x2 5

x2 +2x3 = 6

x1, x2, x3 0

Esempio: x1 + 2x2 + x4 = 5

x4 0 una sottomatrice I2x2 di A!

min z = cTxAx = b

x 0Ipotesi: b 0Sia (P)


Problema ausiliario con variabili artificiali yi, 1 i m

1

minm

iiyv

==

A x + I y = b

x 0, y 0 una soluzione di base ammissibile iniziale ovviay = b 0

(PA)

1) Se v* > 0, (P) inammissibile

2) Se v* = 0, chiaramente y* = 0 e x* una soluzione di base ammissibile di (P)


Per 2) si verificano i sottocasi:

Se yi fuori basei, 1 i m, eliminando quelle colonne si ottiene un tableau in forma canonica rispetto a una base; la riga di z va determinata mediante sostituzione.

cf. esempio

Se yi in base (soluzione degenere), si pu effettuare un pivot su un coefficiente 0 della riga yie scambiare yi con una variabile xj fuori base.


y2

y1

-v

22-4

10-61-201410002-22y2y1x3x2x1

Esempio: min z = x1+ x2+10 x3x2 + 4x3 = 2

-2x1 + x2 - 6x3 = 2

x1, x2, x3 0

Mettere v = y1+y2 in formacanonica sostituendo le espressioni di y1, y2 in funzione di x1, x2 e x3

(PA)

min v = y1+ y2x2+ 4x3+ y1 = 2

-2x1+ x2 - 6x3+ y2 = 2

x1, x2, x3 , y1, y2 0

(P)


y2

y1

-v

22-4

10-61-201410002-22y2y1x3x2x1

y2

x2

-v

020

1-1-100-201410021002y2y1x3x2x1

ottimo v* = 0


scegliendo come pivot il coefficiente 2 della riga di y2 si ottiene:

base ottima equivalente

soluzioni di base ottima per (PA) x1= 0, x2= 2, x3= 0

di base ammissibile per (P)

x1

x2

-v

020

-5010141011000y2y1x3x2x1

trasferito la colonna di I nella zona delle variabili originali

01


z = x1+x2+10 x3 forma canonicavariabile fuori base

Sostituendo:

x2 = 2 - 4x3x1 = -5x3

z = 2 + x3

tableau corrispondente alla soluzione di base ammissibili iniziale per (P)

La soluzione di base ammissibile gia ottima quindi niente seconda fase !

x1

x2

-z

02-2

501410100x3x2x1

PL Simplesso FRODE 06 07

Documents

Transcript of PL Simplesso FRODE 06 07