Programmazione Lineare Intera

Page 1

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 3x1 + x2 −x1 + 5x2≤ 20 4x1 + 2x2≤ 19 x1− x2≤ 1 x1, x2≥ 0, x1, x2∈ Z Calcolare la soluzione ottima applicando il metodo del branch and bound calcolando, ad ogni nodo, il valore del rilassamento continuo per via grafica. Si esegua il branch prima sulla variabile x1. Esercizio 2 Si consideri il seguente problema di programmazione lineare intera: max x1− 3x2 x1≥− 1 x2≥− 3 2 x1 + x2≤ 8 x1− x2≤ 6 x1, x2∈ Z Risolvere il problema applicando il metodo del branch and bound, eseguendo prima il branch sulla variabile x1. Calcolare la stima dell’ottimo ad ogni nodo per via grafica e riportare l’albero di branch and bound. Esercizio 3 Si consideri il seguente problema di programmazione lineare intera min−x1− 2x2 2x1 + 2x2≤ 7 2x1 + x2≥ 2 x1, x2≥ 0, x1, x2∈ Z Calcolare la soluzione del rilassamento continuo per via grafica. Verificare, calcolando i costi ridotti, l’ottimalit` a 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 4 Si consideri il seguente problema di programmazione lineare intera min x1− 2x2 2x2≤ 9 2x1 + x2≤ 7 x1, x2≥ 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 grafica. 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 16x1 + 9x2 + 12x3 + 2x4 8x1 + 6x2 + 7x3 + 2x4≤…