Home

Federica EU

1/8

Paola Festa » 8.Metodo delle Due Fasi

Come individuare una soluzione ammissibile di base iniziale?

Il metodo del simplesso prende in input una soluzione di base iniziale ammissibile.
Ma come trovare una soluzione ammissibile di base iniziale?
In alcuni casi è semplice individuare una siffatta soluzione.
Supponiamo, ad esempio, di dover risolvere un problema di programmazione lineare definito da un insieme di vincoli del tipo
$Ax\leq b,\ \mbox{con}\ b\geq 0.$

In tal caso, introducendo un vettore di variabili di slack nonnegative s, è possibile riscrivere l’insieme di vincoli come

$Ax+s=b$

e il vettore

$(x,s),\ \mbox{con}\ x=0\ \mbox{e}\ s=b$

costituisce una soluzione di base ammissibile cui corrisponde una matrice di base pari alla matrice identità.
Tuttavia, in generale individuare una soluzione di base ammissibile iniziale non è semplice, in quanto, come vedremo tra breve, spesso richiede la soluzione di un problema di programmazione lineare ausiliario.

Metodo delle Due Fasi, 1

Si consideri un generico problema di PL informa standard:
$\begin{array}{rrrr} \mbox{{\rm min}} & c'x & \\ \mbox{{\rm s.a}} \\ & Ax & = & b \\ & x & \geq & 0. \end{array}$

Introducendo un vettore di variabili ausiliarie $y\in {\mathbb R}^m$ , applichiamo il Metodo del Simplesso per risolvere il seguente problema ausiliario:

$\begin{array}{rrrrrrrr} \mbox{{\rm min}} & y_1 & + & y_2 & + & \ldots & + &y_m \\ \mbox{{\rm s.a}} \\ & Ax & + & y & = & b \\ & x & & & \geq & 0 \\ & & & y & \geq & 0. \end{array}$

Nel caso del problema ausiliario una soluzione di base iniziale ammissibile è immediatamente individuabile ponendo $x=0,\ y=b$ ; soluzione questa cui è associata come matrice di base la matrice identità.

A questo punto, disponendo di una soluzione di base ammissibile iniziale, si applica il Metodo del Simplesso per trovare la soluzione ottima $(x^*,y^*)$ al problema ausiliario.

Metodo delle Due Fasi, 2

Sia $(x^*,y^*)$ la soluzione ottima al problema ausiliario.

Caso A: $y^*_i>0,\ \mbox{per qualche}\ i=1,\ldots,m.$

In tal caso, non esiste soluzione ammissibile per il problema originario;

Caso B: $y^*_i=0,\ \forall\ i=1,\ldots,m.$

In questo caso, il problema originario ammette almeno una soluzione ammissibile.

Sono possibili i seguenti due scenari.

nessuna delle variabili artificiali è in base: $x^*$ costituisce una soluzione di base ammissibile per il problema originario, per cui può essere fornita in input al Metodo del Simplesso per risolvere il problema originario.
almeno una delle variabili artificiali è in base: per ottenere una soluzione di base ammissibile per il problema originario da fornire in input al Metodo del Simplesso, occorre fare uscire dalla base tutte le variabili artificiali “scambiandole” con variabili del problema originario e che sono al momento fuori base.

Il procedimento appena esposto consente di risolvere tramite Metodo del Simplesso un qualunque problema di PL in forma standard.

Esso in letteratura è noto come Metodo delle Due Fasi.

Metodo delle Due Fasi, 3

Esempio
Si consideri il seguente problema di PL
$\begin{array}{rrrrrrrr} \mbox{{\rm min}} & x_1 & + & x_2 & + & 10x_3 \\ \mbox{{\rm s.a}} \\ & & & x_2 & + & 4x_3 & = & 2 \\ & -2x_1 & + & x_2 & - & 6x_3 & = & 2 \\ & & & x & \geq & 0 \end{array}$

Per ottenere una soluzione di base ammissibile per il problema originario e poi risolvere quest’ultimo occorre ricorrere al Metodo delle Due Fasi.

Metodo delle Due Fasi, 3 (segue)

I Fase: Si introducono due variabili artificiali $y_1, y_2\geq 0$ e viene costruito il seguente problema ausiliario.
$\begin{array}{rrrrrrrrrrrr} \mbox{{\rm min}} & y_1 & + & y_2 \\\mbox{{\rm s.a}} \\ & & & x_2 & + & 4x_3 & + & y_1 & & = & 2 \\ & -2x_1 & + &x_2 & - &6x_3 & & + & y_2& = 2\\ & & & x, & y\geq & 0 \end{array}$

Occorre risolvere il problema ausiliario a partire dalla soluzione ammissibile di base iniziale immediatamente individuabile data da $x=(0,0,0)$ fuori base e $y=(2,2)$ in base.

In quanto segue, il problema ausiliario viene risolto all’ottimo tramite il Metodo del Simplesso Tabellare.

Metodo delle Due Fasi, 4

I tableau
$\centerline{ \begin{tabular}{|c|rrrrr|}\hline &$x_1$&$x_2$&$x_3$&$y_1$&$y_2$ \\ \hline $-4$ & $2$ & $-2$ & $2$ & $0$ & $0$ \\ \hline $y_1=2$ & $0$ & $*1$ & $4$ & $1$ & $0$ \\ $y_2=2$ & $-2$ & $1$ & $-6$ & $0$ & $1$\\ \hline \end{tabular} }$

La variabile $x_2$ è l’unica candidata ad entrare in base, mentre $y_1,\ y_2$ sono possibili candidate ad uscire dalla base e si sceglie di far uscire dalla base $y_1$ (Regola di Bland).

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

Le variabili della nuova base sono $x_2,\ y_2$ .

Metodo delle Due Fasi, 5

II tableau

$\centerline{\begin{tabular}{|c|rrrrr|}\hline&$x_1$&$x_2$&$x_3$&$y_1$&$y_2$\\\hline$0$&$2$&$0$&$10$&$2$&$0$\\\hline$x_2=2$&$0$&$1$&$4$&$1$&$0$\\$y_2=0$&$*-2$&$0$&$-10$&$-1$&$1$\\\hline\end{tabular}}$

I costi ridotti sono nonnegativi, per cui siamo in presenza di una soluzione ottima per il problema ausiliario.

Il valore di funzione obiettivo è nullo. Infatti, $y_1=y_2=0$ . Dunque, possiamo concludere che il problema originario ammette soluzioni, anche se $y_2$ è in base.

Per risolvere il problema, eseguiamo un’operazione di pivot su uno qualunque degli elementi $u_{21},\ u_{22},\ u_{23}$ , purchè non nullo. Supponiamo di scegliere $u_{21}$ come elemento di pivot.

Metodo delle Due Fasi, 6

III tableau

$\centerline{\begin{tabular}{|c|rrrrr|}\hline&$x_1$&$x_2$&$x_3$&$y_1$&$y_2$\\\hline$0$&$0$&$0$&$0$&$1$&$1$\\\hline$x_2=2$&$0$&$1$&$4$&$1$&$0$\\$x_1=0$&$1$&$0$&$5$&$\frac{1}{2}$&$-\frac{1}{2}$\\\hline\end{tabular}}<br />$

Si è così ottenuta la soluzione $x=(2,0)$ , ammissibile per il problema originario.

Procediamo alla II Fase, dedicata alla risoluzione del problema originario tramite il Metodo del Simplesso Tabellare.

II Fase:

I tableau

$\centerline{\begin{tabular}{|c|rrr|}\hline&$x_1$&$x_2$&$x_3$\\\hline$-2$&$0$&$0$&$1$\\\hline$x_2=2$&$0$&$1$&$4$\\$x_1=0$&$1$&$0$&$5$\\\hline\end{tabular}}$