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 Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 6.Algoritmo del Simplesso Revisionato


Algoritmo del Simplesso Revisionato

Gran parte dello sforzo computazionale nell’implementazione del Metodo del Simplesso descritto è legata alla necessità di dover risolvere ad ogni iterazione i seguenti due sistemi di equazioni lineari.

\[ p'B=c_B; \quad Bu=A_j.\]

Se fosse disponibile un metodo efficiente con il quale ottenere la matrice B^{-1} all’inizio di ogni iterazione, allora i vettori

\[ c_B'B^{-1}\quad \mbox{e}\quad B^{-1}A_j \]

sarebbero immediatamente calcolabili tramite semplice moltiplicazione vettoriale.

L’implementazione alternativa descritta in questo paragrafo fornisce appunto tale metodo.

Metodo del Simplesso Revisionato, 2

Sia

\begin{displaymath} B = \left[ \begin{array}{cccccccc} A_{B(1)} & A_{B(2)} & \ldots & A_{B(l-1)} & A_{B(l-1) & A_{B(l+1)} & \ldots & A_{B(m)} \end{array} \right] \end{displaymath}

la matrice di base all’inizio dell’iterazione i e sia

\begin{displaymath} \bar B = \left[ \begin{array}{cccccccc} A_{B(1)} & A_{B(2)} & \ldots & A_{B(l-1)} & A_j & A_{B(l+1)} & \ldots & A_{B(m)} \end{array} \right] \end{displaymath}

la matrice di base all’inizio dell’iterazione successiva i+1.

Metodo del Simplesso Revisionato, 3

Come si può facilmente osservare le matrici B e \bar B differiscono per la sola colonna l.ma:

B contiene A_{B(l)} (colonna corrispondente alla variabile uscente dalla base);

\bar B contiene A_j (colonna corrispondente alla variabile entrante in base).

Dunque, è intuitivo pensare che anche le matrici B^{-1} e \bar B^{-1} siano simili.

Metodo del Simplesso Revisionato, 4

All’inizio della iterazione i+1 si dispone della matrice B^{-1}, a partire dalla quale si può ottenere la matrice \bar B^{-1} effettuando una serie di operazioni elementari sulle righe della matrice.

\[ \left[B^{-1}\vert u\right],\qquad \mbox{con}\ u=B^{-1}A_j. \]<br />

  • l indice della variabile uscente dalla base;
  • j indice della variabile entrante in base.

In particolare, data la matrice

\[ \left[B^{-1}\vert u\right], \]

occorre applicare ad essa una serie di operazioni elementari tese a trasformarne l’ultima colonna (quella contenente u) in una colonna contenente tutti 0 ed un solo 1 in corrispondenza della riga l.ma.

Metodo del Simplesso Revisionato, 5

Esempio

Supponiamo che

\[B^{-1}=\left[ \begin{array}{rrr}1&2&3\\-2&3&1\\4&-3&-2\end{array}\right];\\ \quad u=\left[\begin{array}{r}-4\\2\\2\end{array}\right].\]

e che l=3. Una volta costruita la matrice

\[\left[B^{-1}\vertu\right]=\left[\begin{array}{rrrr}1&2&3&-4\\-2&3&1&2\\4&-3&-2&2\end{array}\right],\]

bisogna operare su di essa in modo che la quarta colonna contenente u si trasformi nel vettore e_3=[0\ 0\ 1].

Metodo del Simplesso Revisionato, 6

Ad esempio, si potrebbe moltiplicare la terza riga per 2 ed aggiungerla alla prima riga, per poi sottrarre la terza dalla seconda e finalmente dividere la terza per 2, così ottenendo

\[\left[\bar B^{-1} \vert e_3\right]=\left[\begin{array}{rrrr}9&-4&-1&0\\-6&6&3&0\\2&-3/2&-1&1\end{array}\right],\]

le cui prime tre colonne contengono la matrice inversa desiderata.

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense ed Appunti del Corso.

  • 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