L’ALGORITMO DEL SIMPLESSO REVISIONATO improta/simplesso... · G. Improta - Trasparenti del Corso...

G. Improta - Trasparenti del Corso di Ricerca Operativa A.A. 2001/2002 - Vietata la riproduzione senza l'espresso assenso dell'autore. - L'Algoritmo del Simplesso Revisionato

L’ALGORITMO DEL SIMPLESSO REVISIONATO

L'algoritmo del simplesso revisionato costituisce una diversa implementazione dell’algoritmo standard tesa a ridurre, sotto certe condizioni, il tempo di calcolo e l'occupazione di memoria richiesti. Anch'esso, dunque, partendo da una prima soluzione di base ammissibile si sposta verso la soluzione ottima con l'applicazione, ad ogni iterazione, del test di ottimalità ed il passaggio, qualora l’ultima soluzione esaminata non sia ottima, ad una soluzione di base ammissibile migliore ed i criteri utilizzati sono quelli stessi di cui si serve il simplesso standard. Ciò che è rivisto nel simplesso revisionato è la procedura mediante la quale si perviene alle informazioni necessarie per effettuare il test di ottimalità e lo scambio tra variabile entrante e variabile uscente.


Le informazioni necessarie per effettuare tali operazioni sono: Ø i coefficienti di costo modificati delle variabili

non basiche per realizzare il test di ottimalità ed individuare la variabile entrante; Ø la colonna dei tassi di assorbimento modificati

della variabile entrante; Ø la colonna dei termini noti modificati per

individuare la variabile uscente.

Per giungere alla conoscenza di questi tre vettori è necessario con la tecnica utilizzata nel simplesso standard modificare con una operazione di pivot, ad ogni iterazione, tutta la matrice A dei tassi di assorbimento. L'obiettivo del simplesso revisionato è quello di contenere, quando sia possibile, tale inconveniente.


PROCEDURA MATRICIALE PER LA TRASFORMAZIONE DI UN SISTEMA DI EQUAZIONI LINEARI IN FORMA CANONICA Sia Ax = b, un sistema di m relazioni in n variabili (n>m) a rango massimo. In tale ipotesi la matrice A conterrà almeno una matrice di base B e si supponga, per semplicità di notazione, che essa sia costituita dalle ultime m colonne della matrice A del sistema.

Si partizioni la matrice A nelle singole colonne pj (j=1,2, ...,n) dei coefficienti:

A = [p1,p2,…,pn]

e si ponga:

B = [pn-m+1,pn-m+2,…,pn]

Indicando con C la matrice residua composta dalle prime (n - m) colonne di A:

C = [p1,p2,…,pn-m]


si può scrivere:

A = [C ¦ B]

Premoltiplicando per l'inversa B-1 di B si ha:

B-1A = [B-1C ¦ B-1B]

Essendo B-1B = Im e indicando con R il prodotto B-1C, si ottiene:

B-1A = [R ¦ Im]

che costituisce la trasformazione, in forma canonica, della matrice A rispetto alla base B.


CALCOLO DELL'INVERSA CON IL METODO DEL PIVOT Si consideri una matrice quadrata A di ordine m e si voglia calcolarne l'inversa A-1. Si indichi con D una matrice con m righe e 2m colonne, costituita da due partizioni, la prima rappresentata dalla matrice A, la seconda dalla matrice identità Im di ordine m:

D = [A ¦ Im]

Si trasformi, con il metodo del pivot, la matrice A in una matrice identità Im di ordine m:

D’ = [Im¦ W]

Poiché nelle prime m colonne di D’ vi è la matrice identità, l'operazione effettuata equivale a:

A-1D = A-1[A ¦ Im] = [A-1A ¦ A-1Im]

dunque: W = A-1

e quindi: D' = [Im¦ A-1]


Si voglia ricercare l'inversa della matrice:

=

34

21A

La si riscriva completandola con la matrice identità di ordine due:

10

01

34

21

Con una operazione di pivot su a11 si ottiene:

−− 14

01

50

21

Con una operazione di pivot su a22 si ottiene:

−

−5/15/4

5/25/3

10

01

da cui si ricava:

−

−=−

5/15/4

5/25/31A


LA TABELLA DEL SIMPLESSO IN FORMA MATRICIALE Un problema p.l. con m vincoli ed n variabili può essere espresso attraverso un sistema di (m+1) relazioni in (n+1) variabili:

A+x+ = b+ in cui: Ø x+ è il vettore colonna delle variabili del

problema, comprensivo della variabile (-z):

−−=+

z

x

x

Ø b+ è il vettore colonna dei termini noti aumentato di un'ultima componente, nulla, che rappresenta il valore iniziale della (-z):

−=+

0

b

b

Ø A+ è la matrice costituita dalla matrice dei tassi di assorbimento A aumentata del vettore dei coefficienti di costo e del vettore colonna relativo alla variabile (-z):


−−−=+

1|

|

Tc

0A

A

Si partizioni il vettore x suddividendolo in :

Ø xNB (vettore delle variabili non basiche);

Ø xB (vettore delle variabili basiche (con la –z);

e si partizionino, corrispondentemente, la matrice A ed il vettore cT:

−−==

B

NB

x

x

x; cT = [cT

NB | cTB]; A=[NB | B]

La relazione:

A+x+ = b+

può essere allora scritta:


−−−−−1||

||

TB

TNB cc

0BNB

−−

B

NB

x

x

=

−0

b

Ponendo:

−=+

TNBc

NB

NB

−−−=+

1|

|

TBc

0B

B

La:

−−−−−1||

||

TB

TNB cc

0BNB

−−

B

NB

x

x

=

−0

b


può essere scritta:

[NB+| B+]

−−

B

NB

x

x

=

−0

b

e dunque:

NB+xNB + B+xB = b+

Per portare il sistema in forma canonica rispetto alle variabili di base, si premoltiplichi per (B+)-1:

(B+)-1NB+xNB + (B+)-1B+xB = (B+)-1b+ (*) e si sostituisca l'espressione esplicita della (B+)-1:


CALCOLO DELLA (B+)-1

Assegnata la matrice B+:

1

0cB

B

si vuole trovare una matrice X tale che sia:

B+X = Im+1

ovvero:

1

0cB

B

22X12

21

11 XXX

=

1

00

Im

Effettuando il prodotto righe per colonne al primo membro ed eguagliando agli elementi del secondo membro si ottiene:

BX11 + X21 = Im BX12 + X22 = 0


cBX11 + X21 = 0 cBX12 + X22 = 1

da cui si ricava:

X11 = B-1 X12 = 0 X21 = -cBB-1 X22 = 1

e dunque si ottiene:

(B+)-1 =

− −

−

1

0Bc

B1

B

1


È possibile, utilizzando l'espressione esplicita della (B+)-1, ottenere le espressioni dei diversi termini che costituiscono la (*).

Il primo termine:

−−−−−−−−=

−

−

+−+

1|

|

1TB

1

1

Bc

0B

NB)(B ==

−−TNBc

NB

−−−−−−−−−−−−−−−−−−−−

−−

−−

NBBcc

NBB

1TB

TNB

1

fornisce la matrice dei tassi di assorbimento ed il vettore dei coefficienti di costo delle variabili non basiche, modificati rispetto alla base B.

Il secondo termine:

(B+)-1B+ = Im+1

è la matrice identità corrispondente alle variabili di base.


Il terzo termine:

−−−−−−−−=

−

−

+−+

1|

|

1TB

1

1

Bc

0B

b)(B =

−0

b

−−−−−−−−−−−−−−

−−

−−

bBc

bB

1TB

1

è il vettore dei termini noti modificati, cioè i valori che delle variabili in base ed il valore della (-z).

Ad una generica iterazione k, la tabella del simplesso contiene dunque il seguente insieme di informazioni:

==++

−−−−−−−−−−−−−−−−−−−− ++

−−ΝΒΝΒ

−−

B1mNB xIx

NBBcc

NBB

1B

1

−−−−−−−−−−−−−−

−−

−−

bBc

bB

1TB

1

e ponendo: cBB-1= ππT, si ottiene:

==++

−−−−−−−−−−−−−−−−−−−− ++

ΝΒΝΒ

−−

B1mNB xIx

ðNBc

NBB 1

−−−−−−−−−−−−−−

−−

bð

bB

T

1

Il vettore ππ viene indicato in letteratura come vettore dei moltiplicatori del simplesso.


PASSAGGIO DA SIMPLESSO STANDARD A REVISIONATO

Si riesaminino le informazioni necessarie nel simplesso per effettuare il test di ottimalità ed il passaggio ad una eventuale soluzione di base ammissibile migliore.

Coefficienti di costo modificati delle variabili non basiche:

c'TNB = cTNB - cT

BB-1NB = cTNB - ππTNB

i coefficienti di costo modificati possono essere ottenuti a partire dalle informazioni iniziali cT

NB, cT

B, NB purché sia nota la B-1, o anche dalle sole cT

NB ed NB purché siano noti B-1 e ππ.

Vettore dei tassi di assorbimento modificati della variabile entrante:

NB' = B-1 NB

il vettore dei tassi di assorbimento modificati della variabile entrante, può essere ottenuto con la espressione:


p's = B-1ps Dunque p's può essere ottenuta, a partire dal vettore iniziale ps, purché sia nota la B-1 .

Vettore dei termini noti modificati:

b' = B-1b

può essere ottenuto a partire dal vettore iniziale b, conoscendo la B-1.

Il valore della funzione obiettivo:

z = -cBTB-1b = -ππTb

può essere ottenuto a partire dalle informazioni iniziali cB

T e b conoscendo la B-1 oppure a partire dal solo vettore b, purché sia noto ππ.

Dunque, una volta nota la B-1 e il vettore ππT = TBc B-1

(vettore dei moltiplicatori del simplesso associato alla base B) si possono generare tutte le informazioni necessarie per la conduzione dell'algoritmo del simplesso. È da notare che B-1, ed il vettore ππ sono entrambi


contenuti nella (B+)-1.

Si potrebbe, allora, pensare che, volendo ricavare, ad ogni iterazione, le informazioni strettamente necessarie per la conduzione dell'algoritmo del simplesso, si dovrebbe calcolare ad ogni iterazione la (B+)-1 corrente. In realtà ciò non è necessario.

Infatti la tabella iniziale dell'algoritmo del simplesso contiene sempre, per la presenza delle slack e/o delle artificiali, una matrice identità di ordine m.

Alla generica iterazione k dell'algoritmo il sistema sarà in forma canonica rispetto ad un gruppo di m variabili diverso da quello iniziale, ed alla (-z).

Poiché la matrice iniziale è del tipo [NB+ | Im+1] ne deriva che le colonne che inizialmente costituivano la matrice identità conterranno l'inversa della matrice di base alla kesima iterazione.

D'altra parte anche nella tabella iniziale le ultime (m+1) colonne contengono la (B+)-1. Infatti essendo B+1 = Im+1 sarà ancora (B+1)-1 = Im+1.


IL SIMPLESSO REVISIONATO I dati del problema si suppongono riuniti in una tabella iniziale. Da tale tabella vengono prelevate, durante lo sviluppo dell'algoritmo, le informazioni man mano che esse si rendono necessarie. Alla prima iterazione risulta:

(B+1)-1 = Im+1 ed il vettore dei termini noti è quello iniziale.

All'inizio di ciascuna iterazione k sono disponibili la 1

k)( −+B e la colonna dei termini noti modificati.

Per effettuare il test di ottimalità si calcola il vettore cT'NB:

c'TNB = cTNB - cT

BB-1NB = cTNB - ππTNB

Qualora il test fornisca esito negativo viene individuata la variabile entrante xs. Viene quindi calcolata la colonna pivot modificata p's

p's = B-1ps


che, unitamente al vettore b'k, consente la determinazione della variabile uscente, ovvero della riga pivot e dunque del perno a'rs. Si effettua una operazione di pivot sul perno a'rs limitata alla (B+)-1 ed al vettore dei termini noti. In tal modo la colonna p's viene trasformata nel vettore ur, vettore unitario ad (m+1) componenti avente l'elemento unitario nella posizione resima.

La 1k)( −−++B e la b'k vengono trasformati

rispettivamente nella 11k)( −−

++++B e la b'k+1.

Si è ripristinato, in questo modo, un insieme di informazioni corrispondente a quello disponibile all'inizio dell'iterazione che consente dunque di ripetere il procedimento.


ESEMPIO

z= 2x1 - x2 + x3 Max! s.a 3x1 + x2 + x3 ≤≤ 60 x1 - x2 + 2x3 ≤≤ 10 x1 + x2 - x3 ≤≤ 20 x1 x2 x3 ≥≥ 0

Aggiungendo ai vincoli le variabili slack, si ottiene

la tabella iniziale.

1 2 3 4 5 6 x1 x2 x3 y1 y2 y3 -z b 3 1 1 1 60 1 -1 2 1 10 1 1 -1 1 20 2 -1 1 1 0

Tabella iniziale

Da questa tabella vengono prelevati, nel corso dell’algoritmo, i dati necessari.


Prima iterazione. Risulta:

1 0 0 0 (B+)1-1 = 0 1 0 0 0 0 1 0 0 0 0 1

1 0 0 (B)1-1 = 0 1 0 0 0 1

ππ1 = [0, 0, 0]

Siano vNB e vB due vettori le cui componenti forniscono gli indici delle variabili che, a ciascuna iterazione, sono non basiche e basiche rispettivamente.

Risulta: vNB

1 = [1, 2, 3,]; vB1 = [4, 5, 6]



c1NB = cNB - ππ1NB =

3 1 1 [ 2, -1, 1] – [0, 0, 0] 1 -1 2 1 1 -1

= [2, -1, 1]

vNB = [ 1 2 3] la soluzione non è massima e la colonna pivot è quella relativa alla variabile x1. Colonna pivot modificata:

1 0 0 3 3 p1

1 = 0 1 0 . 1 = 1 0 0 1 1 1

Riunendo le informazioni ricavate si ottiene la

tabella ristretta, su cui agisce il simplesso


revisionato:

x1 y1 y2 y3 -z b

y1 3 1 0 0 0 60

y2 1 0 1 0 0 10

y3 1 0 0 1 0 20

-z 2 0 0 0 1 0

Tabella ristretta 1. Var. entr. x1, uscente y2

Si effettua una operazione pivot sulla tabella ristretta alla (B+)-1 orlata col vettore dei termini noti, ottenendo le informazioni necessarie per condurre la seconda iterazione.

Seconda iterazione.

x1 y1 y2 y3 -z b

y1 0 1 -3 0 0 30

x1 1 0 1 0 0 10

y3 0 0 -1 1 0 10

-z 0 0 -2 0 1 20


Tabella ristretta 1 dopo il pivot

Risulta: 1 -3 0 0 (B+)1-1 = 0 1 0 0 0 -1 1 0 0 -2 0 1

1 -3 0 (B)1-1 = 0 1 0 0 -1 1

ππ1 = [0, 2, 0]

vNB2 = [5, 2, 3,]; vB

2 = [4, 1, 6]



0 1 1 [ 0, -1, 1] – [0, 2, 0] 1 -1 2


0 1 -1

= [-2, 1, -3] vNB = [ 5 2 3]

la soluzione non è massima e la colonna pivot è quella relativa alla variabile x2. Colonna pivot modificata:

1 -3 0 1 4 p2

2 = 0 1 0 . -1 = -1 0 -1 1 1 2

Riunendo le informazioni ricavate si ottiene la

seconda tabella ristretta:

x2 y1 y2 y3 -z b

y1 4 1 -3 0 0 30

x1 -1 0 1 0 0 10

y3 2 0 -1 1 0 10

-z 1 0 -2 0 1 20

Tabella ristretta 2. Var. entr. x2, uscente y3

Si effettua l’operazione di pivot ristretta,


ottenendo le informazioni necessarie per condurre la terza iterazione: Terza iterazione.

x2 y1 y2 y3 -z b

y1 0 1 -1 -2 0 10

x1 0 0 0.5 0.5 0 15

x2 1 0 -0.5 0.5 0 5

-z 0 0 -1.5 -0.5 1 25

Tabella ristretta 2 dopo il pivot


vNB = [ 5 6 3]


0 0 1 [ 0, 0, -1] – [0, 1.5, 0.5] 1 0 2 0 1 -1


= [-1.5, -0.5, -1.5] vNB = [ 5 6 3]

L'analisi dei coefficienti di costo mostra che si è trovata la soluzione massima essendo tutti i coefficienti di costo delle variabili non basiche non positivi. La soluzione ottima risulta allora:

y2 = y3 = x3 = 0 ; x1 = 15 ; x2 = 5 ; z = 25

L’ALGORITMO DEL SIMPLESSO REVISIONATO improta/simplesso... · G. Improta - Trasparenti del Corso...

Documents

Transcript of L’ALGORITMO DEL SIMPLESSO REVISIONATO improta/simplesso... · G. Improta - Trasparenti del Corso...