Mathematical Engineering - Fondamenti di Ricerca Operativa

Programmazione Lineare Intera

Divided by topic

Fondamenti di Ricerca Operativa Esercizi proposti Programmazione Lineare Intera AA. 2019/2020 Fondamenti di Ricerca Operativa pagina 1 Esercizio 1 Si consideri il seguente problema di programmazione lineare intera: max 3x 1+ x 2 x 1+ 5 x 2 20 4x 1+ 2 x 2 19 x1 x 2 1 x1; x 2 0; x 1; x 22 Z Calcolare la soluzione ottima applicando il metodo del branch and bound calcolando, ad ogni nodo, il valore del rilassamento continuo per via gra ca. Si esegua il branch prima sulla variabile x1. Esercizio 2Si consideri il seguente problema di programmazione lineare intera: maxx 1 3x 2 x1 1 x2 32 x1+ x 2 8 x1 x 2 6 x1; x 22 Z Risolvere il problema applicando il metodo del branch and bound, eseguendo prima il branch sulla variabilex 1. Calcolare la stima dell'ottimo ad ogni nodo per via gra ca e riportare l'albero di branch and bound. Esercizio 3Si consideri il seguente problema di programmazione lineare intera minx 1 2x 2 2x 1+ 2 x 2 7 2x 1+ x 2 2 x1; x 2 0; x 1; x 22 Z Calcolare la soluzione del rilassamento continuo per via gra ca. Veri care, calcolando i costi ridotti, l'ottimalita della soluzione trovata. Calcolare i tagli di Gomory associati alla soluzione trovata. Riportare i tagli sul disegno e calcolare la nuova soluzione del rilassamento continuo. Esercizio 4Si consideri il seguente problema di programmazione lineare intera minx 1 2x 2 2x 2 9 2x 1+ x 2 7 x1; x 2 0;intere Calcolare la soluzione ottima intera applicando il metodo dei piani di taglio e usando i tagli di Gomory. Ad ogni iterazione calcolare la soluzione continua per via gra ca.Programmazione Lineare Intera Giuliana Carello Fondamenti di Ricerca Operativa pagina 2 Esercizio 5 Si consideri il seguente problema di programmazione lineare a variabili binarie: max 16x 1+ 9 x 2+ 12 x 3+ 2 x 4 8x 1+ 6 x 2+ 7 x 3+ 2 x 4 13 x1; x 2; x 3; x 42 f 0;1g Calcolare la soluzione la soluzione ottima con il metodo del branch and bound, riportando l'albero di branch and bound.Programmazione Lineare Intera Giuliana Carello