In questa lezione si descrive il metodo Branch and Bound per l’ottimizzazione intera.
Si propongono esempi di problemi risolti con il metodo Branch and Bound: un problema di programmazione lineare con variabili intere e un problema con variabili intere binarie, il problema dello zaino, cioè del caricamento ottimo di un contenitore.
Per la soluzione di problemi di programmazione intera di dimensioni reali non è praticabile un approccio di enumerazione totale o esplicita. Si rivela molto utile invece un approccio definito di “enumerazione parziale” o “implicita”. Esso è basato fondamentalmente sulla suddivisione di un problema in due o più sottoproblemi. Ciò significa che l’insieme delle soluzioni ammissibili viene partizionato in due o più sottoinsiemi la cui intersezione è nulla e la cui unione costituisce l’insieme di partenza. Si stabilisce quindi una corrispondenza tra sottoproblema e sottoinsieme di soluzioni. Ciascuno di questi sottoinsiemi può contenere la soluzione ottima del problema originario. Essi costituiscono quindi la lista dei sottoinsiemi “candidati”. In un generico stadio della procedura si individua con un opportuno criterio un sottoinsieme della lista e si calcola un limite per il valore di funzione obiettivo relativo alle soluzioni in esso contenute. Si sviluppa quindi un’analisi volta a decidere se il sottoinsieme in questione deve essere ulteriormente partizionato ed esaminato per determinare soluzioni ammissibili del problema, oppure può essere eliminato da ulteriori considerazioni.
Quest’ultima condizione si può verificare in quattro casi:
Se si verifica una di queste quattro condizioni è inutile continuare ad esplorare il sottoinsieme e quindi lo si elimina. Se non si verifica nessuna di queste condizioni il sottoinsieme (sottoproblema) esaminato viene a sua volta partizionato in due o più sottoinsiemi (sottoproblemi), che vengono aggiunti alla lista degli insiemi (problemi) candidati, e si ripete la scelta di un insieme (problema) candidato da esplorare. La procedura si itera fino a quando non ci sono più sottoinsiemi (sottoproblemi) da esplorare. La migliore soluzione ammissibile trovata costituisce la soluzione ottima del problema originario.
In ultima analisi le componenti fondamentali del metodo Branch and Bound, sono sostanzialmente quattro:
Questo approccio metodologico per la soluzione di problemi di ottimizzazione intera si definisce, con terminologia anglosassone, metodo Branch and Bound, perché basato su un meccanismo di partizione e ramificazione (branch) degli insiemi di soluzioni, e sul calcolo di un valore limite (bound) della funzione obiettivo.
s.a.
Il valore di diventa il limite inferiore della f.o. del problema intero originario.
E’ necessario caricare uno zaino che può sopportare un peso massimo b con prodotti di cui si conosce il valore ed il peso unitario. Determinare quali prodotti caricare, e in quali quantità, per massimizzare il valore caricato rispettando il vincolo di peso massimo.
Siano
Sia x il vettore delle variabili xj , j = 1,…, n
Max z = ∑ j = 1, n vj xj
s.a
∑ j = 1, n pj xj ≤ b
xj ≤ nj j = 1,…, n
xj ≤ 0 intero … j = 1,…, n
Per ciascun prodotto è disponibile una sola unità.
E’ necessario utilizzare variabili binarie.
Il modello si semplifica
Max z = ∑ j = 1, n vj xj
s.a
∑ j = 1, n pj xj ≤ b
xj ≤ {0, 1}j = 1,…, n
Il modello dello Zaino binario:
Max z = ∑ j = 1, n vj xj
s.a
∑ j = 1, n pj xj ≤ b
xj ≤ {0, 1}j = 1,…, n
Il modello:
Max z = 32xA + 36xB +15xC +20xD + 5xE
s.a
16xA + 9xB + 5xC + 8xD + 5xE ≤ 32
xA, xB, xC, xD, xE = 0/1
2. Ottimizzazione non lineare monodimensionale
3. Ottimizzazione non lineare multidimensionale non vincolata
4. Ottimizzazione non lineare multidimensionale vincolata
5. Ottimizzazione lineare: formulazione di modelli
6. Ottimizzazione lineare: Algoritmo del Simplesso
7. Ottimizzazione lineare: Algoritmo del Simplesso - II parte
8. Ottimizzazione lineare: Algoritmo del Simplesso - III parte
9. Ottimizzazione lineare: il metodo del Big M
10. Ottimizzazione lineare: il metodo delle due fasi
11. Ottimizzazione lineare: Algoritmo del Simplesso revisionato
12. Ottimizzazione lineare: Analisi post-ottimale
13. Ottimizzazione lineare: il modello duale
15. Ottimizzazione intera: il metodo del piano di taglio
16. Ottimizzazione intera: il metodo Branch and Bound
17. Ottimizzazione su rete: Introduzione alla Teoria dei Grafi
18. Ottimizzazione su rete: Problemi di percorso
19. Ottimizzazione su rete: Problemi di flusso
20. Ottimizzazione su rete: Problemi di progetto, circuito e locali...