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
 
 
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