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 » 7.Algoritmo del Simplesso Tabellare


Metodo del Simplesso Tabellare, 1

Un’ulteriore implementazione del Metodo del Simplesso è nota come Metodo del Simplesso Tabellare.

Pur essendo meno efficiente in termini di complessità computazionale rispetto al Simplesso Revisionato, il Simplesso Tabellare presenta il vantaggio di riportare in forma compatta tutti i dati necessari alla computazione

in un’unica tabella, detta anche tableau.

A differenza del Simplesso Revisionato in cui viene aggiornata ad ogni iterazione la matrice inversa B^{-1} , il Simplesso Tabellare aggiorna ad ogni iterazione la seguente matrice

\[B^{-1}[b \vert A]\in {\mathbb R}^{m\times (n+1)},\]

le cui colonne sono gli n+1 vettori

\[B^{-1}b,\ B^{-1}A_1,\ B^{-1}A_2,\ \ldots,\ B^{-1}A_n.\]

Metodo del Simplesso Tabellare, 2

Sia B(l) l’indice della variabile candidata ad uscire dalla base e sia j l’indice della variabile candidata ad entrare in base:

la colonna B^{-1}b è detta colonna zero e contiene i valori assunti dalle variabili correntemente in base;

la j.ma colonna B^{-1}A_j è detta colonna di pivot;

la riga l.ma è detta riga di pivot;

l’elemento u_l all’incrocio della colonna e della riga di pivot è detto elemento di pivot.

Nota: l’elemento di pivot u_l è sempre positivo.

Infatti, se u\leq 0 , ciò comporterebbe la terminazione dell’algoritmo con valore ottimo della funzione obiettivo pari a -\infty .

Metodo del Simplesso Tabellare, 3

Le informazioni contenute nelle righe del tableau hanno la seguente interpretazione.

Dati i vincoli del problema b=Ax e data la matrice corrente di base B, i vincoli possono anche essere equivalentemente espressi come

\[ B^{-1}b=B^{-1}Ax, \]

che è esattamente l’informazione contenuta nelle righe del tableau.
Per quanto riguarda la determinazione del valore di \theta^* e della variabile x_{B(l)} candidata ad uscire dalla base, ci si rende immediatamente conto che basta controllare i valori

\[ \frac{x_{B(i)}}{u_i} \]

dati dal rapporto fra l’ i.ma entrata della colonna zero e l’ i.ma entrata della colonna di pivot, tali che u_i sia positivo: il più piccolo di tali rapporti fornisce il valore da assegnare a \theta^* e determina anche la variabile

x_{B(l)} .

Metodo del Simplesso Tabellare, 4

Alla fine di ogni iterazione del Simplesso Tabellare è necessario aggiornare il tableau

\[ B^{-1}[b\vert A],\]

per ottenere il tableau

\[\bar B^{-1}[b\vert A],\]

dove \bar B è la nuova matrice di base.

Siffatto aggiornamento è realizzato applicando al tableau

\[ B^{-1}[b\vert A],\]

una serie di operazioni di riga elementari atte a trasformare la colonna j.ma del tableau nel vettore unitario e_l .

Metodo del Simplesso Tabellare, 5

Al tableau tipicamente è aggiunta anche una riga zero, il cui primo elemento situato nell’angolo in alto a sinistra
corrisponde a

\[ -c_B'B^{-1}b,\]

cioè al valore cambiato di segno che la funzione obiettivo assume in corrispondenza della corrente soluzione ammissibile di base x_B,\ x_N .
I restanti n elementi della riga zero corrispondono al vettore dei costi ridotti

\[ c'-c_B'B^{-1}A.\]

Dunque, il tableau presenta la seguente struttura:

\begin{tabular}{|c|c|}\hline $-c_B'B^{-1}b$&$c'-c_B'B^{-1}A$ \\\hline $B^{-1}b$&$B^{-1}A$\\\hline\end{tabular}

\begin{table}[h]\centerline{\begin{tabular}{|c|c|}\hline$-c_B'B^{-1}b$&$c'-c_B'B^{-1}A$\\\hline$B^{-1}b$&$B^{-1}A$\\\hline\end{tabular}}\end{table}

Metodo del Simplesso Tabellare, 6

Più in dettaglio, il tableau presenta la seguente struttura:

Guardando i costi ridotti contenuti nella riga zero,

→ o si verifica la validità delle condizioni di ottimalità della soluzione corrente;

→ oppure si individua l’indice j della variabile entrante in base e una volta determinato j, eventualmente anche la riga zero subisce le opportune trasformazioni affinché \bar c_j sia reso nullo.

Metodo del simplesso tabellare

Metodo del simplesso tabellare


Metodo del Simplesso Tabellare, 7

Esempio
Si consideri il seguente problema di PL:

\[ \begin{array}{rrrrrrrr} \mbox{{\rm min}} & -10x_1 & - & 12x_2 & - & 12x_3   &  \\ \mbox{{\rm s.a}} \\  & x_1  & + & 2x_2 & + & 2x_3 & \leq & 20 \\ & 2x_1 & + &  x_2 & + & 2x_3 & \leq & 20 \\  & 2x_1 & + &  x_2 & + &  x_3 & \leq & 20 \\ & x    & \geq & 0 \end{array} \]

la cui regione ammissibile P è rappresentata in Figura.
Si noti che il problema ammette 5 soluzioni ammissibili di base:

  1. A=(0, 0, 0) con costo 0;
  2. B=(0, 0, 10) con costo -120;
  3. C=(0, 10, 0) con costo -120;
  4. D=(10, 0, 0) con costo -100;
  5. E=(4, 4, 4) con costo -136.

E è l’unica soluzione ottima.

Regione ammissibile del problema. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont – Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Regione ammissibile del problema. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa


Metodo del Simplesso Tabellare, 8

Per formulare il problema in forma standard, occorre introdurre tre variabili di slack:

\[ \begin{array}{rrrrrrrrrrrrr} \mbox{{\rm min}} & -10x_1 & - & 12x_2 & - & 12x_3   &  \\ \mbox{{\rm s.a}} \\  & x_1  & + & 2x_2 & + & 2x_3 & + & x_4 &     &     &  & = & 20 \\ & 2x_1 & + &  x_2 & + & 2x_3 &   &   & + & x_5 &   & = & 20 \\   & 2x_1 & + &  x_2 & + &  x_3 &  &  &   & + & x_6 & = & 20 \\  & x & \geq & 0 \end{array} \]

La soluzione

\[ x=(x_1, x_2, x_3, x_4, x_5, x_6)=(0, 0, 0, 20, 20, 20)\ \mbox{ (corrispondente al punto A nello spazio}\  (x_1,x_2,x_3) ), \]

secondo la quale le variabili di base sono x_4,\ x_5,\ x_6 , cioè B(1)=4, B(2)=5 e B(3)=6, è una soluzione ammissibile e può dunque essere usata come soluzione iniziale per il simplesso.

La matrice di base corrispondente ad essa è

\[ B=[A(4)\ A(5)\ A(6)]=\left[ \begin{array}{rrrr} 1&0&0\\ 0&1&0\\ 0&0&1 \end{array} \right] . \]

Metodo del Simplesso Tabellare, 9

Supponiamo di voler risolvere il problema applicando il Metodo del Simplesso Tabellare.

Per ottenere la riga zero, basta osservare che

\[ c_B=0 \Longrightarrow c_Bx_B=0,\ \mbox{e}\ \bar c=c. \]

Dunque, il tableau iniziale è

\centerline{ \begin{tabular}{|c|rrrrrr|}\hline &$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$x_6$ \\ \hline $-c'_Bx_B=0$ & $-10$ & $-12$ & $-12$ & $0$ & $0$ & $0$ \\ \hline $x_4=20$     & $1$   & $2$   & $2$   & $1$ & $0$ & $0$      \\ $x_5=20$     & $*2$  & $1$   & $2$   & $0$ & $1$ & $0$      \\ $x_6=20$     & $2$   & $2$   & $1$   & $0$ & $0$ & $1$      \\ \hline \end{tabular} }

Metodo del Simplesso Tabellare, 10

I iterazione:
Scegliamo di far entrare in base x_1, avendo costo ridotto negativo. Dunque, la colonna pivot è la colonna

$$u=\left(\begin{array}{c}1\\2\\2\end{array}\right).$$

E’ necessario, ora, stabilire quale sia la variabile uscente dalla base. A tale scopo, calcoliamo i rapporti

\[\frac{x_i}{u_i},\ i=4,5,6\]

e la variabile uscente sarà quella cui corrisponde il minimo rapporto.

Sia x_5 che x_6 sono possibili candidate e si sceglie di far uscire dalla base x_5 (Regola di Bland).

L’elemento di pivot è, dunque, l’elemento in tabella contrassegnato da un asterisco.

Le variabili della nuova base sono x_4,\ x_1,\  x_6 , cioè \bar B(1)=4,\ \bar B(2)=1,\  \bar B(3)=6 .

Metodo del Simplesso Tabellare, 11

Applicando opportune operazioni elementari alle righe del tableau orientate a trasformare la colonna di pivot nel vettore colonna

$$e_2=\left(\begin{array}{c}0\\ 1\\0\end{array}\right),$$

si ottiene il seguente tableau:

\begin{tabular}{|c|rrrrrr|}\hline&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$x_6$\\\hline$-c'_Bx_B=100$&$0$&$-7$&$-2$&$0$&$5$&$0$\\\hline$x_4=10$&$0$&$3/2$&$*1$&$1$&$-1/2$&$0$\\$x_1=10$&$1$&$1/2$&$1$&$0$&$1/2$&$0$\\$x_6=0$&$0$&$1$&$-1$&$0$&$-1$&$1$\\\hline\end{tabular}

La nuova soluzione di base nello spazio (x_1\ x_2\ x_3) corrisponde al punto D=(10, 0, 0).

Essa è una soluzione degenere, dato che il valore della variabile di base x_6 è nullo (infatti, D attiva quattro vincoli).

Metodo del Simplesso Tabellare, 12

II iterazione:
Sia x_2 che x_3 sono variabili potenzialmente candidate ad entrare in base, dato che entrambe hanno un costo ridotto negativo.

Supponiamo che sia x_3 ad entrare in base. Dunque, la colonna pivot u è

$$u=\left(\begin{array}{r}1\\1\\-1\end{array}\right).$$

Al fine di stabilire quale sia la variabile uscente dalla base, calcoliamo i rapporti

\[\frac{x_i}{u_i},\i=4,1.\]

Sia
x_4 che x_1 sono possibili candidate e si sceglie di far uscire dalla base x_4 .

L’elemento di pivot è, dunque, l’elemento in tabella contrassegnato da un asterisco.

Le variabili della nuova base sono x_3,\ x_1,\  x_6 , cioè \bar B(1)=3,\ \bar B(2)=1,\  \bar B(3)=6 .

Metodo del Simplesso Tabellare, 13

Applicando opportune operazioni elementari alle righe del tableau orientate a trasformare la colonna di pivot nel

vettore colonna

$$e_1=\left(\begin{array}{c}1\\0\\0\end{array}\right),$$

si ottiene il seguente tableau:

\begin{tabular}{|c|rrrrrr|}\hline&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$x_6$\\\hline$-c'_Bx_B=120$&$0$&$-4$&$0$&$2$&$4$&$0$\\\hline$x_3=10$&$0$&$3/2$&$1$&$1$&$-1/2$&$0$\\$x_1=0$&$1$&$-1$&$0$&$-1$&$1$&$0$\\$x_6=10$&$0$&$*5/2$&$0$&$1$&$-1/2$&$1$\\\hline\end{tabular}

La nuova soluzione di base nello spazio (x_1\ x_2\ x_3) corrisponde al punto B=(0, 0, 10).

Metodo del Simplesso Tabellare, 14

III iterazione:
x_2 è l’unica candidata ad entrare in base e la colonna pivot u è

$$u=\left(\begin{array}{r}\frac{3}{2}\\-1\\\frac{5}{2}\end{array}\right).$$

Al fine di stabilire quale sia la variabile uscente dalla base, calcoliamo i rapporti

\[\frac{x_i}{u_i},\ i=3,6\]

e si individua in x_6 la variabile uscente. L’elemento di pivot è, dunque, l’elemento in tabella contrassegnato da un asterisco.

Le variabili della nuova base sono x_3,\ x_1,\ x_2 , cioè \bar B(1)=3,\ \bar B(2)=1,\ \bar B(3)=2 .

Metodo del Simplesso Tabellare, 15

Applicando opportune operazioni elementari alle righe del tableau orientate a trasformare la colonna di pivot nel

vettore colonna

$$e_3=\left(\begin{array}{c}0\\0\\ 1\end{array}\right),$$

si ottiene il seguente tableau:

\begin{tabular}{|c|rrrrrr|}\hline&$x_1$&$x_2$&$x_3$&$x_4$&$x_5$&$x_6$\\\hline$-c'_Bx_B=136$&$0$&$0$&$0$&$18/5$&$8/5$&$8/5$\\\hline$x_3=4$&$0$&$0$&$1$&$2/5$&$2/5$&$-3/5$\\$x_1=4$&$1$&$0$&$0$&$-3/5$&$2/5$&$2/5$\\$x_2=4$&$0$&$1$&$0$&$2/5$&$-3/5$&$2/5$\\\hline\end{tabular}

A questo punto, l’algoritmo termina restituendo come soluzione ottima la soluzione corrispondente al punto E, cioè
x_1=4, x_2=4,\  x_3=4 , con valore della funzione obiettivo pari a -136.

Si noti che il Metodo del Simplesso si è spostato da un vertice (soluzione ammissibile di base) ad uno adiacente

secondo il percorso A-D-B-E.

Facendo scelte diverse circa le variabili entranti e quelle uscenti, l’algoritmo avrebbe potuto scegliere un percorso diverso.

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 del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • 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