Schema Generale:
- Si risolve il (RL), se
è intera - Si genera un taglio (nuovo vincolo!)
- Tale che
- Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
- Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo
Procedimento ed Efficienza
È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.
A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.
Link to original
Metodo di Gomory
Genera il taglio sfruttando la tabella finale del Simplesso del Rilassamento Lineare (RL).
In particolare, usa la riga della tabella associata ad una componente frazionaria della soluzione ottima del (RL).
Sia data la tabella finale della risoluzione del RL:
— WIP
è frazionario.
Procedimento
Scriviamo la riga
e consideriamo i floor dei coefficienti:
Questo è il taglio di Gomory in forma intera.
Il taglio va aggiunto al rilassamento lineare dopo averlo reso standard. Si aggiunge il vincolo standard:
Come precedentemente detto, la convergenza è lenta. I primi tagli risultano più efficaci, ma lo sono meno continuando ad iterare l’algoritmo.
Se si opera un taglio alla volta e ci sono più valori frazionari si sceglie sempre la riga con indice minore, oppure quella con termine noto che ha la parte frazionaria maggiore.
Esempio (Grafico, lungo)
EH, VOLEVI! wip.