Antonio Sforza » 10.Ottimizzazione lineare: il metodo delle due fasi

Schema della lezione

In questa lezione si descrive il metodo delle 2 fasi, utilizzabile per la soluzione di un modello di P.L. che presenti vincoli del tipo = o ≥. Dopo una breve descrizione del metodo si riporta un esempio numerico svolto.

Il metodo delle due fasi

Il metodo delle due fasi opera diversamente dal metodo del Big M. Per eliminare le variabili artificiali dalla soluzione del problema e determinare una soluzione ottima appartenente al dominio originario, esso costruisce una nuova funzione obiettivo ausiliaria w, definita come somma delle variabili artificiali: w = ∑_i=_1,k h_i, se k è il numero di variabili artificiali del sistema.

Questa funzione obiettivo w deve essere minimizzata. Infatti, poiché le variabili artificiali sono non negative, anche la loro somma sarà non negativa. Il minimo della funzione w è dunque pari a 0 e corrisponde all’annullamento di tutte le variabili artificiali.

Si noti che l’aggiunta della riga della w, espressa in funzione delle h_i, fa perdere la forma canonica del sistema di equazioni esteso con le funzioni obiettivo z e w.

È necessario pertanto esprimere la w in funzione delle variabili originarie. In questo modo il sistema resta in forma canonica rispetto alle variabili artificiali.

Si riporta nel seguito un esempio numerico.