Home

Federica EU

1/15

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

A=(0, 0, 0) con costo 0;
B=(0, 0, 10) con costo -120;
C=(0, 10, 0) con costo -120;
D=(10, 0, 0) con costo -100;
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

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.