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 » 9.Metodo del Big-M


Il Metodo del Big-M

Il Metodo del Big-M è alternativo e perfettamente equivalente al Metodo delle Due Fasi, da cui differisce nel fatto che esso combina in un’unica fase tutte le operazioni desiderate.

Anche il metodo del Big-M introduce nella formulazione matematica originaria del problema al più m variabili artificiali y_1,y_2,\ldots,y_m , ma, a differenza del Metodo delle Due Fasi, esso minimizza una funzione obiettivo del tipo
$$\displaystyle{\sum_{j=1}^n c_jx_j + M\sum_{i=1}^m y_i},$$

dove M è un numero positivo molto grande e può essere interpretato come un fattore di penalità associato alle variabili artificiali.

Metodo del Big-M, 2

E’ immediato rendersi conto che se il problema originario ammette una soluzione ottima finita, allora nella soluzione ottima del problema ausiliario tutte le variabili artificiali hanno valore nullo.

Nell’applicare il Metodo del Big-M, non viene assegnato ad M un valore specifico, per cui durante le varie iterazioni del simplesso sia il valore della funzione obiettivo che i costi ridotti delle variabili sono dati in funzione di questo parametro e ogni qualvolta M viene confrontato con un altro numero al fine di stabilire se un certo costo ridotto sia negativo o meno, M dovrà sempre essere considerato il maggiore fra i due.

Metodo del Big-M, 3

Esempio
Si consideri il seguente problema di PL in forma standard

\[\begin{array}{rrrrrrrrrrr}\mbox{{\rm min}}&x_1&+&x_2&+&x_3&\\\mbox{{\rm s.a}}\\&x_1 &+&2x_2&+&3x_3&&&&=&3\\&-x_1&+&2x_2&+&6x_3&&&&=&2\\&&&4x_2&+&9x_3&&&&=&5\\&&&&&3x_3&+&x_4&&=&1\\&x&\geq&0\end{array}\]

Introduciamo nella formulazione m=3 variabili artificiali e sommiamo alla funzione obiettivo il termine di penalità proporzionato ad M.

Metodo del Big-M, 4

Si noti che in questo caso occorrono solo 3 variabili artificiali, dato che l’ultimo vincolo è l’unico a contenere la variabile x_4 .
Dunque, si ottiene il seguente problema ausiliario:

\[ \begin{array}{rrrrrrrrrrrrrrrrr} \mbox{{\rm min}} & x_1 & + & x_2 & + & x_3 & & & + & My_1 & + & My_2 & + & My_3 &\\ \mbox{{\rm s.a}} \\ & x_1 & + & 2x_2 & + & 3x_3 & & & + & y_1 & & & & & = & 3 \\ & -x_1 & + & 2x_2 & + & 6x_3 & & & & & + & y_2 & & & = & 2 \\ & & & 4x_2 & + & 9x_3 & & & & & & & + & y_3 & = & 5 \\ & & & & & 3x_3 & + & x_4 & & & & & & & = & 1 \\ & x,\ y& \geq & 0. \end{array} \]

Metodo del Big-M, 5

Una soluzione di base ammissibile iniziale per il problema ausiliario è la soluzione (y_1\ y_2\ y_3\ x_4)=b=(3\ 2\ 5\ 1) , la cui corrispondente matrice di base è la matrice identità.

I tableau

\centerline{ \begin{tabular}{|c|rrrrrrr|}\hline  &$x_1$&$x_2$&$x_3$&$x_4$&$y_1$&$y_2$&$y_3$ \\ \hline $-c'_Bx_B=-10M$ & $1$   & $-8M+1$  & $-18M+1$   & $0$ & $0$  &  $0$ & $0$ \\ \hline $y_1=3$& $1$ & $2$& $3$& $0$ & $1$  &  $0$ & $0$ \\ $y_2=2$ & $-1$  & $2$& $6$& $0$ & $0$  &  $1$ & $0$ \\ $y_3=5$& $0$& $4$& $9$ & $0$ & $0$  & $0$ & $1$ \\ $x_4=1$& $0$   & $0$ & $*3$& $1$ & $0$  &  $0$ & $0$ \\ \hline \end{tabular} }

Metodo del Big-M, 5 (segue)

Per M sufficientemente grande, il costo ridotto di x_3 è negativo, per cui decidiamo di portare x_3 in base, mentre quella uscente dalla base è x_4 .

II tableau

\centerline{ \begin{tabular}{|c|rrrrrrr|}\hline   &$x_1$&$x_2$&$x_3$&$x_4$&$y_1$&$y_2$&$y_3$ \\ \hline<br />
$-4M-1/3$       & $1$   & $-8M+1$  & $0$   & $6M-1/3$ & $0$  &  $0$ & $0$    \\ \hline<br />
$y_1=2$         & $1$   & $2$      & $0$      & $-1$  & $1$  &  $0$ & $0$    \\<br />
$y_2=0$         & $-1$  & $*2$     & $0$      & $-2$  & $0$  &  $1$ & $0$    \\<br />
$y_3=2$         & $0$   & $4$      & $0$      & $-3$  & $0$  &  $0$ & $1$    \\<br />
$x_3=1/3$       & $0$   & $0$      & $1$      & $1/3$ & $0$  &  $0$ & $0$    \\ \hline \end{tabular} }<br />

Metodo del Big-M, 6

III tableau

\centerline{\begin{tabular}{|c|rrrrrrr|}\hline &$x_1$&$x_2$&$x_3$&$x_4$&$y_1$&$y_2$&$y_3$\\\hline$-11/6$&$0$&$0$&$0$&$-1/12$&$2M-3/4$&$2M+1/4$&$0$\\\hline$x_1=1$&$1$&$0$&$0$&$1/2$&$1/2$&$-1/2$&$0$\\$x_2=1/2$&$0$&$1$&$0$&$-3/4$&$1/4$&$1/4$&$0$\\$y_3=0$&$0$&$0$&$0$&$0$&$-1$&$-1$&$1$\\$x_3=1/3$&$0$&$0$&$1$&$*1/3$&$0$&$0$&$0$\\\hline\end{tabular}}

IV tableau

\centerline{\begin{tabular}{|c|rrrrrrr|}\hline&$x_1$&$x_2$&$x_3$&$x_4$&$y_1$&$y_2$&$y_3$\\\hline$-11/6$&$0$&$0$&$0$&$-1/12$&$2M-3/4$&$2M+1/4$&$0$\\\hline$x_1=1$&$1$&$0$&$0$&$1/2$&$1/2$&$-1/2$&$0$\\$x_2=1/2$&$0$&$1$&$0$&$-3/4$&$1/4$&$1/4$&$0$\\$y_3=0$&$0$&$0$&$0$&$0$&$-1$&$-1$&$1$\\$x_3=1/3$&$0$&$0$&$1$&$*1/3$&$0$&$0$&$0$\\\hline\end{tabular}}

Metodo del Big-M, 6

V tableau

\centerline{\begin{tabular}{|c|rrrrrrr|}\hline &$x_1$&$x_2$&$x_3$&$x_4$&$y_1$&$y_2$&$y_3$\\\hline$-7/4$&$0$&$0$&$1/4$&$0$&$2M-3/4$&$2M+1/4$&$0$\\\hline$x_1=1/2$&$1$&$0$&$-3/2$&$0$&$1/2$&$-1/2$&$0$\\$x_2=5/4$&$0$&$1$&$9/4$&$0$&$1/4$&$1/4$&$0$\\$y_3=0$&$0$&$0$&$0$&$0$&$-1$&$-1$&$1$\\$x_4=1$&$0$&$0$&$3$&$1$&$0$&$0$&$0$\\\hline\end{tabular}}

Si noti che per M sufficientemente grande tutti i costi ridotti sono non negativi, per cui possiamo dire di aver trovato una soluzione ottima al problema ausiliario.

Inoltre, dal momento che il valore di tutte le variabili artificiali è nullo, la soluzione trovata è ottima anche per il problema originario.

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