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

  1. 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.
  2. 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}}

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

La soluzione ottima al problema è x_1=0,\ x_2=2 , cui corrisponde un valore di funzione obiettivo pari a 2.

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