Mathematical Engineering - Fondamenti di Ricerca Operativa

Full exam

Fondamenti di Ricerca OperativaAA 2016/2017 Esame del 24 Febbraio 2017 COGNOME NOME MATRICOLA SCRIVERE LE RISPOSTE NELLO SPAZIO SOTTO IL TESTO. Esercizio 1.Uno stabilimento che produce mattoncini per costruzioni deve pianificare la produzione per i prossimi mesi (insiemeM). In ogni mese la ditta pu`o decidere di produrre secondo due modalit`a: a 16 ore al giorno o a 24 ore al giorno. La modalit`a viene mantenuta per l’intero mese. A secondadella modalit`a scelta cambia il numero di tecnici per la manutenzione dei macchinari impiegati per ogni giornata lavorativa. Il costo dei tecnici rappresenta un costo di produzione indipendente dal numero di mattoncini prodotti e varia da mese a mese: nel mesei∈Mtale costo `e pari af16 ise l’impianto lavora 16 ore al giorno e a f24 ise l’impianto lavora 24 ore al giorno. Anche la massima capacit`a produttiva (in numero di mattoncini) e il costo di produzione di un mattoncino cambiano: nel mesei∈Msono pari aB16 ie c16 i , rispettivamente, se l’impianto lavora 16 ore al giorno e pari a B24 ie c24 i , rispettivamente, se lavora 24 ore al giorno.` E possibile decidere di immagazzinare i mattoncini prodotti per renderli disponibili sul mercato nei mesi successivi. Immagazzinare un mattoncino fino al mese successivo costag. Inoltre, `e necessario pagare un costo per la gestione del magazzino pari a Q indipendente dal numero di mattoncini immagazzinati. Per ogni mesei∈M`e nota la richiesta del mercator i. 1. Formulare in Programmazione Lineare Intera, il problema di soddisfare la domanda minimizzando i costi. 2. Come cambia il modello se, per motivi contrattuali, non `e possibile attivare la modalit`a di produzione di 24 ore per pi`u diγmesi consecutivi? 3. Scrivere secondo la sintassi di AMPL il modello relativo al punto 1. Esercizio 2.Si consideri il seguente problema di Programmazione Lineare max−4x 1+ 5 x 2 x1+ x 2≤ 8 −x 1+ x 2≤ 3 4x 1− 6x 2≤ 10 4x 1+ x 2≥ 3 x1≥ 0, x 2libera 1. Scrivere il duale del problema e tutte le condizioni di complementarit`a. 2. Sfruttando le condizioni di complementarit`a verificare se i seguenti punti sono ottimi: (a) (1,−1) (b) 5 2, 11 2 Esercizio 3.Si consideri il problema del flusso massimo. 1. Quale algoritmo si pu`o applicare per risolvere il problema? Quali accorgimenti sono necessari a garantire una complessit`a polinomiale? 2. Risolvere l’istanza riportata in figura a partire dal flusso dato: il flusso inizialex ije la capacit`a u ijsono riportati per ogni arco in quest’ordinex ij, u ij. Riportare i passaggi dell’algoritmo applicato. 1 2 3 4 5 6 5,9 5,5 0,12 6,6 0,6 1,7 0,10 4,7 6,13 0,9 4,4 . 3. Indicare un taglio di capacit`a minima. Esercizio 4.Risolvere il seguente problema di Programmazione Lineare Intera con il metodo del branch and bound, calcolando per via grafica l’ottimo del rilassamento continuo in ogni nodo. Riportare l’albero di branch and bound e le stime in ogni nodo. Eseguire prima il branch sulla variabilex 2. min−2x 1−7 2x 2 2x 1+ 2 x 2≤ 14 2x 1+ 4 x 2≤ 21 2x 2≤ 9 2x 1≤ 13 x1, x 2≥ 0,interi -1 0 1 2 3 4 5 6 7 8 -1 0 1 2 3 4 5 6 7 8 x 1 x 2 . Esercizio 5.Si consideri il problema dell’albero dei cammini minimi. 1. Descrivere le condizioni di ottimalit`a. 2. Si consideri l’esempio in figura, con radice 1, dove l’albero ottimo `eindicato in grassetto 1 3 2 5 4 7 6 5 4 -3 7 2 1 3 2 -6 2 4 3 (a) Per quali valori del costo dell’arco (3,5) la soluzione rimane ottima? Giustificare la risposta. (b) Per quali valori del costo dell’arco (5,6) la soluzione rimane ottima? Giustificare la risposta. Esercizio 6.1. Dare la definizione di diseguaglianza valida e di taglio per i problemi di Programmazione Lineare Intera. 2. Si consideri la regione ammissibile riportata in figura e il verticeA. Dire se le seguenti diseguaglianze sono diseguaglianze valide o tagli (relativi adA) giustificando le risposte. (a)x 1≤ 7 (b)x 1≤ 6 (c)x 2≤ 5 (d)x 1+ x 2≤ 10 -1 0 1 2 3 4 5 6 7 8 -1 0 1 2 3 4 5 6 7 8 A x1 x 2