Metodo delle Due Fasi

Quando si applica?

Il metodo delle due fasi si applica a problemi di PL con vincoli misti () nei quali non è possibile trovare come base la matrice identità.

Se non c’è la matrice identità, è impossibile avviare il simplesso infatti.

Consiste, appunto, di due fasi:

1. Determina una soluzione di base ammissibile e la forma canonica;
2. Risolvi il problema di PL.

Nella fase 1 si risolve un problema detto Artificiale.

Consideriamo un problema di PL in Forma Standard che non ha la sottomatrice identità:

Aggiungiamo ad ogni vincolo una variabile detta artificiale.

Nella fase si risolve il problema artificiale:

Una soluzione del problema artificiale è del tipo:

Se è soluzione di Base ammissibile del problema iniziale!

Supponiamo di aver risolto il problema della fase, per andare avanti con la teoria. 

Otterremmo:

=valore ottimo=

A questo punto ci sono due casi:

1. vuol dire che qualche allora si conclude che il problema iniziale non ha soluzione ammissibile. La regione ammissibile del problema è dunque vuota.
2. La soluzione finale della fase è tale che è una soluzione di base ammissibile per il problema iniziale.

Quando si passa alla fase si usa la tabella finale della fase e si ricalcolano i costi ridotti, perché si riprende la funzione obiettivo del problema iniziale.

Ci sono 2 ulteriori sottocasi:

1. Non ci sono variabili artificiali in base. Si cancellano nella tabella le colonne delle variabili artificiali, e si risolve il problema.
2. Ci sono variabili artificiali in base. Restano in base anche nella fase 2, e si cerca di farle uscire dalla base con il metodo del simplesso. Se non si riesce, vuol dire che il vincolo associato alle variabili artificiali in base è ridondante, e si può eliminare.

Esempio

Fase 1

Consideriamo un problema con soli vincoli di uguaglianza, ma senza matrice identità.

(direttamente in forma standard perché mi secco a ricopiare)

Applichiamo la fase: creiamo un problema artificiale sostituendo la funzione obiettivo, e aggiungendo le variabili artificiali (che si comportano come variabili scarto):

Otteniamo la matrice:

Nota Bene

Se si usano le variabili artificiali in ogni riga i costi ridotti delle variabili fuori base sono dati dall’OPPOSTO della somma per colonna.

Calcoliamo i costi ridotti con la formula , che tradotto dal matematichese significa:

• Costo Ridotto = Coeff. Variabili nella f.o. - coeff. variabili base f.o. colonna corrente.

 

Per cui il valore corrente della f.o. è: -vettore coeff. variabili base nella f.o. colonna termini noti:

  Entra in base , esce .

Dopo alcune iterazioni, otteniamo la tabella finale:

Dato che , si può passare alla fase.

Notiamo che la soluzione di base trovata in questo caso è: , ed il vettore è una SAB ammissibile per il problema iniziale.

Nota Bene

La prima fase si conclude in uno dei due sottocasi:

1. Problema iniziale inammissibile
2. Fornisce una SAB Ammissibile per il problema iniziale (forma canonica per avviare la risoluzione del problema)

Fase 2

Questa fase risolve il problema iniziale partendo dalla soluzione di base ammissibile trovata alla fine della prima fase: 

Notiamo che non sono in base, e si può eliminare pure in quanto vincolo ridondante (sia colonna che riga) (è ridondante perché l’equazione che rappresenta la riga equivale a 0) 

Ottenuta questa tabella si riprende la funzione obiettivo originale:

I valori dei costi ridotti e della funzione obiettivo sono a questo punto:

Vettore

• 0
• 0

Dopo altri svariati calcoli e un’altra iterazione, arriviamo alla SAB ottima: , con valore ottimo

Fin 💖