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

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

Esempio 1. Big M


Esempio 1. Big M (segue)


Esempio 1. Big M (segue)


Esempio 1. Big M (segue)


Esempio 1. Big M (segue)


Esempio 1. Big M (segue)


Percorso dell’algoritmo del Simplesso nel dominio esteso


Esempio 2. Big M


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Esempio 2. Big M (segue)


Percorso dell’algoritmo del Simplesso nel dominio originario


  • 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