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 , ma, a differenza del Metodo delle Due Fasi, esso minimizza una funzione obiettivo del tipo
dove M è un numero positivo molto grande e può essere interpretato come un fattore di penalità associato alle variabili artificiali.
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.
Esempio
Si consideri il seguente problema di PL in forma standard
Introduciamo nella formulazione m=3 variabili artificiali e sommiamo alla funzione obiettivo il termine di penalità proporzionato ad M.
Si noti che in questo caso occorrono solo 3 variabili artificiali, dato che l’ultimo vincolo è l’unico a contenere la variabile .
Dunque, si ottiene il seguente problema ausiliario:
Una soluzione di base ammissibile iniziale per il problema ausiliario è la soluzione , la cui corrispondente matrice di base è la matrice identità.
I tableau
Per M sufficientemente grande, il costo ridotto di è negativo, per cui decidiamo di portare in base, mentre quella uscente dalla base è .
II tableau
III tableau
IV tableau
V tableau
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.
1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
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.