Home

Federica EU

1/6

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],$