Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 11.Ottimizzazione lineare: Algoritmo del Simplesso revisionato


Schema della lezione

In questa lezione si illustra l’algoritmo del Simplesso Revisionato, così definito perché realizza una diversa implementazione dell’algoritmo del Simplesso, più efficace dal punto di vista computazionale, basata sulla constatazione che nel corso delle iterazioni l’algoritmo utilizza in effetti soltanto una parte di tutte le informazioni contenute nella tabella del sistema.

Si introducono le relazioni utilizzate dall’algoritmo, si descrive lo schema operativo di funzionamento e si riporta un esempio numerico.

Algoritmo del Simplesso Revisionato

L’algoritmo del Simplesso Revisionato (Revised Simplex) mantiene inalterata la struttura generale dell’algoritmo (1a s.b.a., test di ottimalità, stop o nuova s.b.a., ritorno al test di ottimalità e così via fino alla soluzione ottima), ma ne realizza una diversa implementazione, basata sulla constatazione che nel corso delle iterazioni l’algoritmo utilizza in effetti soltanto una parte di tutte le informazioni contenute nella tabella del sistema.

Si può notare infatti che per il test di ottimalità e per la determinazione della variabile entrante, viene utilizzato il vettore cjnb dei coefficienti della funzione obiettivo relativi alle variabili non basiche. Per determinare la variabile uscente, se s è il pedice della colonna pivot corrispondente alla variabile entrante, è necessario calcolare il minimo dei rapporti bi /ais, con i che varia da 1 a m. Per calcolare questi rapporti si utilizzano quindi altri due vettori: il vettore b della colonna dei termini noti ed il vettore ps dei coefficienti della colonna della variabile entrante.

L’algoritmo del Simplesso Revisionato realizza un’implementazione dell’algoritmo orientata a calcolare solo i tre vettori effettivamente necessari per passare da una tabella all’altra: cnb‘, b’, ps‘ .

Le espressioni di cnb‘, b’, ps

È possibile determinare con una procedura algebrica, descritta in dettaglio nel testo di riferimento, le espressioni di cnb‘, b’, ps relative ad ogni tabella dell’algoritmo in funzione di elementi noti o calcolabili nel corso della procedura:

  • cnb‘ = cnb – cb B-1NB ………. [cj' = cj cb B-1pj, ∀ j non basico]
  • b’ = B-1b, ps‘ = B-1 ps

L’espressione della funzione obiettivo è infine -z = – cb B-1b. Gli elementi noti di queste espressioni sono i seguenti:

  • cnb e cb coefficienti della funzione obiettivo della tabella iniziale relativi alle variabili non basiche e basiche al generico stadio k
  • NB matrice estratta dalla tabella iniziale costituita dalle colonne delle variabili non basiche allo stadio generico k
  • b vettore iniziale dei termini noti
  • ps colonna della matrice A iniziale relativa alla variabile entrante allo stadio k

La matrice B-1, inversa della matrice di base allo stadio k, deve invece essere calcolata ad ogni iterazione della procedura attraverso una operazione di pivoting limitata alle colonne della tabella k corrispondenti alle colonne in cui si trova la matrice identità della tabella iniziale.

Calcolo della matrice B-1

Si ricordi che un sistema Ax = b di dimensioni mxn (m<n) può essere messo in forma canonica rispetto a m variabili con una semplice operazione algebrica, premoltiplicando il sistema Ax = b per la matrice B-1, inversa della matrice B, detta matrice di base, costituita dalle colonne iniziali di A relative alle variabili rispetto alle quali si vuole il sistema in forma canonica.

Com’è noto, ogni tabella del simplesso contiene un sistema in forma canonica, necessario per identificare una soluzione basica ammissibile. Esso quindi può essere pensato come ottenuto da una trasformazione del sistema iniziale attraverso la pre-moltiplicazione per la matrice B-1, inversa della matrice B relativa all’insieme di variabili basiche di quella tabella.

Si noti ancora che il nostro sistema è in forma canonica sin dalla prima tabella (per l’aggiunta delle variabili slack e/o delle variabili artificiali). Il sistema quindi può essere scritto nella forma [A · I ] x = b. Se si effettua la pre-moltiplicazione per B-1 al fine di ottenere il sistema in forma canonica rispetto ad un prefissato insieme di variabili, si ottiene:  B-1 [A · I ] x = B-1b,  [B-1 A · B-1I ] x = B-1b, [D · B-1] x = B-1b.

Ciascuna tabella del Simplesso contiene quindi la matrice B-1, inversa della matrice di base associata alla soluzione relativa a quella tabella. Essa si trova nelle colonne corrispondenti alla matrice identità iniziale. Per ricavare B-1 ed applicare le espressioni dei tre vettori cnb‘, b’, ps è sufficiente quindi effettuare le operazioni di pivoting limitate a queste colonne della matrice.

Schema operativo del simplesso revisionato

Prima di svolgere esempi numerici è opportuno riassumere le operazioni del Simplesso Revisionato. In tabella sono riportate schematicamente le tabelle relative alla soluzione di un problema con 3 vincoli del tipo ≤ e 10 variabili originarie. La prima soluzione basica ammissibile è costituita quindi da 10 variabili originarie, non basiche, e 3 variabili slack, basiche, rispetto alle quali il sistema è in forma canonica.

Si supponga che dall’esame dei coefficienti della funzione obiettivo sia stata determinata come variabile entrante la variabile x8. Attraverso i rapporti bi /ai8 è possibile determinare la riga pivot e la variabile uscente (si supponga y2). L’elemento pivot è quindi a28. Con il Simplesso Standard si effettuerebbe l’operazione di pivoting estesa a tutta la tabella, generando una seconda tabella completa. Nel Simplesso Revisionato, invece, l’operazione di pivoting viene limitata alle colonne corrispondenti alla matrice identità della prima tabella, che contengono necessariamente la matrice B-1, inversa della matrice di base B. Calcolata in questo modo la matrice B-1 è possibile utilizzare l’espressione di c’nb, in funzione di B-1 e degli altri elementi noti, per calcolarne i relativi valori. Dall’esame di c’nb è possibile individuare la nuova variabile entrante (sia x4) e calcolare successivamente p’4, utilizzando l’espressione di p’s. Dopo aver calcolato b è possibile calcolare i rapporti bi /ai4. Ciò consente di determinare la variabile uscente (sia y1) ed individuare il nuovo elemento pivot a14. La procedura continua identicamente senza mai trasformare tutta la tavola, ma solo la parte relativa alla B-1, necessaria per calcolare i vettori cnb, pj e bi, rilevanti per lo sviluppo dell’algoritmo.

Simplesso revisionato


Esempio numerico

Si consideri il seguente problema:

\text{MAX  }z=\begin{array}{lrrr}x_1+2x_2-x_3+x_4+4x_5-2x_6\\ x_1+x_2+x_3+x_4+x_5+x_6\leq 6\\ 2x_1-x_2-2x_3+x_4 \leq 6 \\ 2x_1-x_2-2x_3+x_4\leq 4\\+x_3+x_4+2x_5+x_6\leq 4\end{array}

Bisogna aggiungere tre variabili slack nei tre vincoli di ≤. Per agevolare la numerazione delle colonne le variabili slack y1, y2 e y3 sono indicate con x7, x8 e x9.

La prima tabella del simplesso assume quindi la configurazione riportata in tabella.


Esempio numerico

Le variabili basiche sono x7, x8 e x9. Le variabili non basiche sono x1, x2, x3, x4, x5 e x6.

Si può quindi scrivere

c_b=[c_7\; c_8\;c_9]=[0,\;0,\;0]

c_{nb}=[c_1\;c_2\;c_3\_4\;c_5\;c_6]=[1,2,-1,1,4,-2]

La variabile entrante è la x5, la variabile uscente e la x9. Dunque nella tabella successiva le basiche saranno x7, x8 e x5. Le variabili non basiche saranno x1, x2, x3, x4, x6 e x9. Pertanto:

c_b=[c_7\; c_8\;c_9]=[0,\;0,\;4]

c_{nb}=[c_1\;c_2\;c_3\_4\;c_5\;c_6]=[1,2,-1,1,-2,0]

 

Esempio numerico

Si calcola B1 con il pivoting alle colonne della matrice I della prima tabella ottenendo:

B^{-1=}\left[\begin{array}{lll}10-\_\\01\;\;\;\;0\\00\;\;\;\;\_\end{array}\right]

Si avrà pertanto:

c_bB^{-1}=[0,0,4]\left[\begin{array}{lll}10-\_\\01\;\;\;\;0\\00\;\;\;\;\_\end{array}\right]=[0,0,2]

c_{nb}^{'}=c_{nb}-c_bB^{-1}NB=

=[1,2,-1,1,-2,0]-[0,0,2]\left[\begin{array}{llllll}1&1&1&1&1&0\\2&-1&-2&1&0&0\\0&0&1&1&1&1\end{array}\right]=

=[1,2,-3,-1,-4,-2]

-z=-c_bB^{-1}b=-[0,0,2]\left[\begin{array}{ccc}6\\4\\4\end{array}\right]=-8

Esempio numerico

Il test di ottimalità su cnb‘ mostra che la soluzione non è ottima perchè ci sono ancora coefficienti positivi.

La variabile entrante è la x2. Per determinare la variabile uscente è necessario calcolare le colonne p2‘ e b‘:

p_2'=B^{-1}p_2=\left[\begin{array}{lll}1&0&-1/2\\0&1&0\\0&0&1/2\end{array}\right]\left[\begin{array}{ccc}1\\-1\\0\end{array}\right]=\left[\begin{array}{ccc}1\\-1\\0\end{array}\right]

b'=B^{-1}b=\left[\begin{array}{lll}1&0&-1/2\\0&1&0\\0&0&1/2\end{array}\right]\left[\begin{array}{ccc}6\\4\\4\end{array}\right]=\left[\begin{array}{ccc}4\\4\\2\endarray}\right]

Con le matrici e i vettori calcolati [B-1,cnb', p2' e b'] si può costruire la nuova tabella parziale, riportata in figura.


Esempio numerico

Pioché il rapporto Min i {bi/ais}=Min i {4}=4, la variabile uscente è la x7 e quindi nella tabella successiva si avrà (si ricordi che i valori di cb e cnb vanno sempre presi nella prima tabella):

c_b=[c_2, c_8, c_5]=[2,0,4]

c_{nb}=[c_1,c_3,c_4,c_6,c_7,c_9]=[1,-1,1-2,0,0]

Per costruire la B’1 della tabella successiva si effettua l’operazione di pivoting limitata alle colonne della matrice identità della tabella iniziale:

B^{'1}=\left[\begin{array}{ccc}{1&0&-1/2\\1&1&-1/2\\0&0&1/2}\end{array}\right]

Esempio numerico

c_bB^{-1}=[2,0,4]\left[\begin{array}{ccc}1&0&-1/2\\1&1&-1/2\\0&0&1/2\end{array}\right]=[2,0,1]

-z=-c_bB^{-1}b=[-2,0,-1]\left[\begin{array}{ccc}6\\4\\4\end{array}\right]=-16

c_{nb}'=c_{nb}-c_bB^{-1}NB=

=[1,-1,1,-2,0,0]-[2,0,1]\left[\begin{array}{cccccc}1&1&1&1&1&0\\2&-2&1&0&0&0\\0&1&1&1&0&1\end{array}\right]

=[-1,-4,-2,-5,-2,-1]

In base al test di ottimalità su cnb’ la soluzione risulta ottima.

Si determini il vettore b’ per ottenere i valori delle variabili:

b'=B{-1}b=\left[\begin{array}{ccc}1&0&-1/2\\1&1&-1/2\\0&0&1/2\end{array}\right]\left[\begin{array}{ccc}6\\4\\4\end{array}\right]=\left[\begin{array}{ccc}4\\8\\2\end{array}\right]

L’ultima tabella assume pertanto la configurazione riportata in figura.

La soluzione ottima è la seguente:

x_2=4, x_8=8, x_5=2, x_1=x_3=x_4=x_6=x_7=x_9=0;\;\;\;z=16.

 


Esempio numerico in sintesi


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion