Antonio Sforza » 9.Ottimizzazione lineare: il metodo del Big M

Schema della lezione

In questa lezione si descrive il metodo del Big M, utilizzabile per la soluzione di un modello di P.L. che presenti vincoli del tipo = o ≥. Dopo una breve descrizione del metodo si riportano due esempi numerici svolti.

Il metodo del Big M

Il metodo del Big M è basato sulla modifica della funzione obiettivo z del problema originario. Si introducono in essa le variabili artificiali h_j con coefficienti di modulo elevato e segno opportuno, negativo se la funzione obiettivo z è a massimizzare, positivo se z è a minimizzare. In questo modo si favorisce l’annullamento delle variabili artificiali e quindi la loro uscita dalla base.

Si noti che l’aggiunta delle variabili artificiali alla funzione z fa perdere la forma canonica del sistema. Per poter innescare l’algoritmo è necessario rimettere il sistema in forma canonica rispetto alle variabili artificiali. A tale scopo bisogna effettuare preliminarmente una operazione di pivoting per ogni colonna di variabile artificiale, con pivot nell’elemento di valore 1.

L’algoritmo segue un percorso che parte da un vertice del dominio ampliato ed arriva ad un vertice di “confine” tra dominio ampliato e dominio originario, proseguendo poi fino alla soluzione ottima del dominio originario, senza eliminare dalla tabella le variabili artificiali.

Se l’algoritmo non riesce ad “espellere” le variabili artificiali dalla base il problema originario è inconsistente ed è stato reso consistente proprio con l’aggiunta delle variabili artificiali.
Nel seguito si riportano due esempi numerici.