2. ALGORITMO DEL SIMPLESSO -...

Politecnico di Torino Ricerca Operativa

R. Tadei 2. Simplesso1

2. ALGORITMO DELSIMPLESSO



Una piccola introduzione



SIMPLESSO

L’obiettivo del capitolo è quello di fornire un algoritmo,l’algoritmo del simplesso, che risolve qualsiasi problema diprogrammazione lineare.

Sono fondamentali le nozioni di pivot, di soluzione dibase, e in generale tutti i concetti che sono stati espressi nelcapitolo precedente sulla programmazione lineare.

Dovrebbe diventare chiaro che lo studio del problemain termini di tableau, pivot, coefficienti di costo relativo ecc., è ilcoronamento di tutto il discorso precedente.

Concludiamo il capitolo con la presentazione delmetodo del simplesso revisionato, ovvero un modo più veloceper trovare la soluzione del problema.



Il Metodo del Simplesso è un metodo iterativo che,esplorando l’insieme delle soluzioni basiche, raggiungel’ottimo, se esiste, in un numero finito di iterazioni.

Supponiamo che il P.L. sia di minimo, in forma standard.Per operare, il Metodo necessita di una forma canonicaequivalente.

Se il tableau corrispondente non è in forma canonicaallora bisogna cercare una soluzione ammissibile di base(slide 18), altrimenti si individua una s.a.b. iniziale ovvia esi procede con l’algoritmo del simplesso.



Algoritmo del simplessoIpotesiIpotesi : si parte da una S.A.B. e dal tableau Ax=b in formacanonica.

Si aggiunge una riga costituita dagli rj , j = 1, ... , n e da -z0 (valore,cambiato di segno, della f.o. nella s.a.b.)

TableauTableau del del simplesso simplesso

0

:

0

a1 a2 _ _ _ _ am am+1 am+2 _ _ _ _ _ _ _ _

_ _ _ _ _ _ _ _ _ _ _ _

_ _ _ _ _ _ _ _

_ _ _ _ _ _ _ _ _ _ _ _

1

1

1

0

0

0 0

0 0

::

:

:

:

:

y1,m+1 y1,m+2

ym,m+1 ym,m+2

rm+1 rm+2

aj an b

y1j y1n y10

ymj Ymn Ym0

rj rm -z0



≤≤+≤≤

=nim

miyx i

i 1 0

1 0

Soluzione di baseper ipotesi ammissibile,

yi0 ≥≥ 0 , i = 1 , ... , m



Giustificazione dell'ultima riga deltableau

Il tableau del simplesso è uguale a quello definito nel capitoloprecedente, con l’aggiunta dell’ultima riga degli rj ; vediamone l’utilità.

La f.o. z = cTx = c1x1 + c2x2 + ... + cnxn

può essere vista come un ulteriore vincolo del problema ; con l’aggiuntadella variabile (-z) otteniamo

c1x1 + c2x2 + ... + cnxn - z = 0

Aggiungiamo questa equazione come ultima riga nel tableau (1.9) dellaslide 38 - CAP.1

Se si fa un’operazione di pivot su a11=1, l’ultima riga diventa :

0 c2 ... cm (cm+1 - y1,m+1 c1) ... (cn - y1,n cn) (0 - c1 y10)

Stessa operazione su a22=1 :

0 0 c3 .. cm (cm+1 - y1,m+1 c1 - y2,m+1 c2 ) ... - c1 y10 - c2 y20



Si continua il procedimento per tutte le colonne delle var. dibase e si ottiene :

0 0 ... 0 (rm+1 ) ... (rn) -z0

dove

Con la base che si ha all’inizio, la f.o. vale z=z0 . Ma, come sivede dalla (1.25), se qualche rj è < di 0 conviene far entrare inbase la variabile corrispondente a quella colonna.

r c y c c z

z c y c y c y

m i m ii

m

m m

m m

= − = −

− = − − − −

+ +=

+ +∑1 11

1 1

0 1 10 2 20 0

,

...e



Volendo minimizzare z, si ha la possibilità di migliorarne illivello z0 , aumentando quelle variabili per cui rj < 0 ; ora si deveindividuare, se esiste, la variabile che esce dalla base :

=> se nella colonna della variabile candidata ad entrare tutti glielementi sono < di 0 , allora la var. non ha limiti superiori, percui (ottimo non limitato);

=> altrimenti esce la variabile della riga con il rapporto yio/yijminore (con yij >0) , che rappresenta il livello massimo a cui puòentrare la var. candidata.

xq entra e xp esce

La nuova z0 varrà :

z0’ = z0 + ( yp0 / ypq ) rq < z0 (2.1)

z → −∞



I passi dell'algoritmo

0. formare il tableau del simplesso

1. se rj ≥≥ 0 , ∀∀ j STOPSTOP ; la s.a.b. corrente è ottima

2. scegliere colonna q tale che rq < 0 per determinare la variabileda far entrare nella base (m+1 ≤≤ q ≤≤ n)

3. calcolare i rapporti yi0 / yiq, con yiq > 0 , i = 1 , ... , m.

SeSe yiq ≤≤0 , i = 1 , ... , m , STOPSTOP; problema illimitato, f. o. → − ∞→ − ∞.

AltrimentiAltrimenti, scegliere p = indice i corrispondente al rapportoyi0 / yiq minimo ( p è la variabile che esce dalla base )

4. (p,q) è il pivot. Aggiornare il tableau con le operazioni dipivot.

Ritornare al passo 1



Esempio

0,0,0

622

532

22

..

33 max

321

321

321

321

321

≥≥≥≤++≤++

≤++

++

xxx

xxx

xxx

xxx

ts

xxx



6,,1 , 0

622

532

22

..

33min

6321

5321

4321

321

K=≥=+++=+++

=+++

−−−

ix

xxxx

xxxx

xxxx

ts

xxx

i

Trasformazione del problema in forma standard con l’aggiunta delle variabili ausiliarie, x4 x5 x6 ,

in questo caso di slack:



Tableau iniziale

r c z

c c y cj

j j j

j i iji

m

= − =

= − ==∑

1

a1 a2 a3 a4 a5 a6 b

2 11 1

1 1

1 1

0 0

00

0 0

0 0 0 0

2

2

2 2

3 5

6

-3 -3-1

BASE

rrjj

N.B: con l’aggiunta delle variabili di slackotteniamo subito una soluzione di base (nonnecessariamente ammissibile);inoltre le zj sono uguali a zero perchè levariabili di base sono tutte fittizie (sono infattiquelle di slack) e quindi hanno costo ci nullo.Di conseguenza rj = cj



Abbiamo fatto entrare in base a2 , uscendo a4 , ma la soluzionenon è ancora ottima (come si può vedere dal seguente tableau);scegliamo allora di far entrare a3 : esce quindi a5

1 2 1 1

1

-1 1

0 0

0

0

0 0 0

2

-2

1

-3 0

0

1 -2

-2

1

2

-1 -2 1 2

Pivot su

f.o. (passata da 0 a -2)



f.o. = -4

1

1

0

0

1

0 2 0

1

-3 0

0

5

-2

-4

1

3

-7 0 -3 4

0 3 -1 1

1

-5 0

1Pivot su

La soluzione non è ancora ottima, entra x1 ed esce x2



r jj ≥ ∀0,

5Pivot su

1

0

0

0

7/5 3/5 0

1/5

0 3/5

1

2/5

-1

8/5

4

0 0 6/5 27/5

0 3/5 -1/5 1/5

-1/5

0 0

1

1

STOP, soluzione ottima

La soluzione ottima trovata vale:La soluzione ottima trovata vale:x1 = 1/5 ; x2 = 0; x3 = 8/5; x4 = 0; x5 = 0; x6 = 4

La funzione obiettivo vale: z = -27/5



2.1 RICERCA DI UNASOLUZIONE AMMISSIBILE

DI BASE INIZIALE



Problema (fase 1 del simplesso)Una soluzione ammissibile di base da cui partire con ilsimplesso non è sempre evidente, poichè non necessariamenteil tableau del sistema è in forma canonica.

Es: 2 2 4

3 3

0 0 0

1 2 3

1 2 3

1 2 3

x x x

x x x

x x x

+ + =+ + =

≥ ≥ ≥

3

, ,

Ax b

x

=≥ 0 (2.2)

trovare la s.a.b. x



m i n

. .

y

s t

y b

ii

m

=∑

+ =≥≥

1

0

0

A x

x

y

(2.3)

Introduciamo un nuovo problema, costruito su quellodi partenza, in modo che risulti in forma canonica e sul quale,da quanto visto, possiamo utilizzare l’algoritmo del simplesso.

Se facciamo le cose in modo opportuno, il risultato cheotteniamo è proprio una soluzione di base del problema dipartenza.

Si consideri il nuovo problema:

Se esiste s.a. alla (2.2) allora la (2.3) ha come soluzione yi=0 perqualsiasi i



a a b

a a b

a a z

r c z c y y a

n

m mn m

ii ini

j j j i iji

m

iji

m

iji

m

11 1 1

1

1 0

1 1 1

1 0

0 1

0 0

0

.. .. .. ..

.. .. .. .. .. .. .. .. ..

.. .. .. .. .. .. .. .. ..

.. .. .. ..

.. .. .. ..− − −

= − = − = − = −

∑ ∑

∑ ∑ ∑= = =

perchè :

Risolvo il problema ausiliario :



Esempio:

min

. .

, ,

4

2 2 4

3 3

0 0 0

1 2 3

1 2 3

1 2 3

1 2 3

x x x

s t

x x x

x x x

x x

+ +

+ + =+ + =

≥ ≥ ≥

3

x

Una soluzione di base non è immediatamente visibile;



min( )

. .

, , , , ;

y y

s t

x x x y

x x x y

x x y y

1 2

1 2 3 1

1 2 3 2

1 2 3 1 2

2 2 4

3 3

0

+

+ + + =+ + + =

≥

3

x

Studiamo il problema modificato:

In questo momento la soluzione di base è rappresentata da y1 =4 e y2=3;

Se il problema di partenza ha soluzione ammissibile di base riusciamo afar uscire dalla base del problema modificato y1 e y2 applicando ilsimplesso oppure il metodo del pivot.



Scelta ottima del vettore k da far entrarein base

>

ik

ik

yik yy

rik

0

0,maxmin

Esiste un modo per determinare quale sia il vettore ottimo dafar entrare in base:

Perchè MAX ?Avendo fissato k, devo scegliere il rapporto yio/yik piùpiccolo ( con yik>0 ) ma rk è minore di 0.

Perchè MIN ?Come si vede dalla (2.1) devo scegliere il minimo tra tutti imassimi trovati.



2.2 METODO DELSIMPLESSO REVISIONATO



Per un qualsiasi problema di p.l. si ha il sistema dei vincoliespresso nella forma :

Ax=b

La matrice A può essere vista come l’unione di due sottomatriciB e D (dove B è la matrice quadrata formata dalle colonne chehanno la variabile in base) :

A=[B|D]

Il sistema diventa:

[B|D] [ xB,,xD ]T = b

Esplicitando rispetto ad xB :

xB = B-1b - B-1DxD

Sostituendo in z:

z = cBT (B-1b - B-1DxD) + cD

T xD =

=cBT B-1b + (cD

T- cBT B-1D) xD

Osservazione introduttiva



Osservazione (cont.)

L’ultima espressione esprime il costo di ogni soluzione

nei termini xD.

Allora

rDT = cD T- cB

T B-1D

è il vettore dei costi relativi per le variabili non di base.

In base a tutto ciò, definiamo come vettore dei moltiplicatori delsimplesso, che avrà importanza fondamentale nello studio delsimplesso duale,

cioè il vettore λλT= = cBT B-1



Metodo del simplesso revisionatoSono dati :

B-1 inverso della base corrente

xB = y0 = B-1b soluzione di base corrente

Passo 1:Passo 1:

Calcolare i moltiplicatori del simplesso λλT:

λλT = cBT B-1

Calcolare i costi ridotti delle variabili fuori base:

rDT = cD

T- λλT D

Se rD ≥ ≥ 0 STOP , xB è ottima

Passo 2:Passo 2:

Altrimenti scegliere rj, ad esempio, più negativo; sia rq.

Il vettore aq entra in base.

Calcolare yq = B-1aq (è il vettore aq espresso nel termini

della base corrente).



Passo 3:Passo 3:

Se yiq≤≤ 0 , ∀∀ i STOP , PROBLEMA ILLIMITATO

Altrimenti trovare il vettore che lascia la basecalcolando i rapporti yi0 / yiq , con yiq > 0 e scegliendo ilminimo

Passo 4:Passo 4:

Sostituire in B il vettore che esce dalla base con ilvettore che entra:

Calcolare B-1 cioè la nuova matrice inversa di base

Calcolare xB = B-1b cioè la nuova soluzione di base

Tornare al passo 1;



Riassumendo



SIMPLESSO

Nel primo paragrafo di questo capitolo abbiamo trattatol’algoritmo del simplesso, per il quale risulta fondamentale laformazione del tableau, formato dalla matrice del sistema deivincoli scritta in forma canonica (slide 5-7), e lo abbiamoformalizzato (slide 10); è importante, però, andare oltrel’applicazione meccanica dei passi illustrati: infatti leggendoliattentamente non può sfuggire che ogni passo è conseguenzao di teoremi, o di osservazioni che sono state fatte nel capitoloprecedente; in questo senso il presente paragrafo rappresentail completamento e l’applicazione pratica di quantoprecedentemente affermato e dimostrato.

Le slide che vanno dalla numero 11 alla numero 16 nonsono altro che un esempio di applicazione praticadell’algoritmo.



Non è sicuramente sfuggito però che l’algoritmo del simplesso,richiedendo come ingresso un tableau in forma canonica, puòpartire solo se abbiamo trovato una soluzione ammissibile dibase, cosa che è immediata nel momento in cui il problema nonin forma standard lo diventa con l’aggiunta delle variabili dislack, ma che non è vera in generale; per risolvere questoproblema, cioè quello di trovare una soluzione ammissibile dibase dalla quale partire con il simplesso, abbiamo introdotto unproblema fittizio costruito su quello di partenza, risolvibile conl’algoritmo del simplesso, la cui soluzione, se esiste,rappresenta una possibile soluzione ammissibile di base per ilproblema dato; ovviamente da qui in avanti il problema èrisolvibile con il simplesso e si procede applicando i passidell’algoritmo (slide 17 -22).

Infine in chiusura di paragrafo suggeriamo un modoper decidere quale variabile far entrare in base: a questoproposito è il caso di sottolineare che il simplesso dice qualivariabili sono candidate ad entrare in base, ma non dice qualesia la scelta migliore tra tutte;



infatti se è vero che facendo entrare in base una determinatavariabile si migliora il valore della funzione obiettivo, non è veroche tutte le variabili che potrebbero entrare in base migliorinoallo stesso modo la funzione obiettivo; c’è un modo perscegliere quella localmente migliore (slide 23).

Il secondo paragrafo tratta il metodo del simplessorevisionato, che sostanzialmente realizza esattamente ciò chegià realizzava l’algoritmo standard del simplesso.

La differenza tra i due metodi non è nell’obiettivo, cheè comune, ma nel metodo, cioè mentre il primo sfruttapesantemente considerazioni teoriche, il secondo utilizza unapproccio più analitico.

Tutto questo ha un vantaggio, dal momento che nonsarà sicuramente sfuggito che il simplesso è molto oneroso inquanto richiede ogni volta di aggiornare tutto il tableau, fattoquesto che può diventare pesante se il problema in discussionepresenta molte variabili.



Il pregio di questo secondo metodo consiste nel fare inmodo che vengano utilizzati solo i dati che sono strettamentenecessari; unico onere è l’inversione ad ogni iterazione di unamatrice, che non deve però preoccupare più di tanto, poiché ,come verrà spiegato ad esercitazione, esiste un modo moltoveloce e sicuro per realizzarla.

Bisogna comunque tenere presente che questo metodonon è nato per essere applicato manualmente, quanto perrendere più facile la codifica da far eseguire al calcolatore, per ilquale l’inversione di una matrice, unica vera difficoltà, benchépossa essere onerosa, non è un’operazione particolarmenteimpegnativa (slide 24 - 28).

2. ALGORITMO DEL SIMPLESSO -...

Documents

Transcript of 2. ALGORITMO DEL SIMPLESSO -...