Mathematical Engineering - Fondamenti di Ricerca Operativa

Full exam

Fondamenti di Ricerca OperativaAA 2016/2017 Esame del 6 Febbraio 2017 COGNOME NOME MATRICOLA SCRIVERE LE RISPOSTE NELLO SPAZIO SOTTO IL TESTO ONELLA PAGINA PRECEDENTE. Esercizio 1.Un tour operator deve organizzare per San Valentino una cena in battello sulla Senna per alcuni gruppi di turisti.I`e l’insieme dei gruppi. Ogni gruppoi∈I`e composto dad icoppie di turisti e parla una lingua diversa da quella degli altri gruppi. Il tour operator deve prenotare i battelli e assegnare i turisti alle imbarcazioni. Un gruppo pu`o essere diviso su pi`u battelli (una coppia ovviamente no) ma sesu un battello sono imbarcati turisti del gruppoi deve essere presente sul battello anche una guida che parla la linguacorrispondente, che per`o non cena a bordo. Per ogni gruppoiil costo di una guida che parla la lingua corrispondente `e dib i. Il tour operator pu`o scegliere tra un insiemeJdi battelli. Per ogni battelloj∈Jsono il costo di noleggio del battelloc j, il prezzo di una cena per una coppiag j, e il numero di coperti che possono essere serviti sul battello p j. 1. Scrivere il modello del problema di minimizzare il costo complessivo della cena, che comprende anche la preno- tazione dei battelli e il costo delle guide, sapendo che il tour operator ha a disposizione un budgetBper pagare le guide. 2. Tradurre il modello nella sintassi di AMPL. 3.Variante 1:Come cambia il modello se prenotando almenoqbattelli il tour operator beneficia di uno sconto pari as? 4.Variante 2:Alcuni gruppi parlano la stessa lingua e possono essere accompagnati, se sullo stesso battello, da una sola guida. SiaKl’insieme delle lingue e siaa ikuna matrice che vale 1 se il gruppo i∈Iparla la lingua k∈Ke siab kil costo di una guida che parla la lingua k. Come varia il modello del problema? Esercizio 2.Risolvere il seguente problema in Programmazione Lineare con l’algoritmo del simplesso a partire dalla base (x 3, x 4): maxx 1+ 4 x 2− 3x 3 −x 1− x 2+ x 3+ x 4= 5 −2x 1+ 2 x 2− 2x 3+ 2 x 4= 4 x2, x 3, x 4≥ 0, x 1≤ 0 Esercizio 3.Il grafo in figura rappresenta una citt`a in cui sta per giocarsi un’importante partita di calcio. I nodi del grafo rappresentano punti importanti della citt`a:O`e lo stadio dove si svolge l’incontro,A`e l’aeroporto,S 1ed S 2 sono stazioni ferroviarie, mentreC 1, C 2, C 3sono stazioni dei pullman. Il costo degli archi rappresenta la lung hezza dei collegamenti tra i vari punti di interesse. S2 O C3 C2 S1 C1 A 12 6 2 3 2 14 2 7 1 1 14 12 13 Al termine della partita i tifosi della squadra avversaria devono raggiungere stazioni e aeroporto lungo strade presidiate da un cordone di polizia. Sapendo che il numero di agenti necessario a presidiare una via `e proporzionale alla lunghezza, indicare quali vie debbano essere presidiate in modo da garantire un collegamento presidiato tra stadio e stazioni e aeroporto usando il minor numero di agenti. Di che problema si tratta? Quale algoritmo si deve utilizzare per risolvere il problema? Descriverlo brevemente. Esercizio 4.Si consideri il seguente problema di programmazione lineare intera: max−2x 1− x 2 10x 1+ 18 x 2≤ 45 2x 1+ 6 x 2≥ 3 x1, x 2∈ Z+ 1. Calcolare la soluzione del rilassamento continuo per via grafica. 2. Verificare, calcolando i costi ridotti, l’ottimalit`a della soluzione trovata. 3. Calcolare tutti i tagli di Gomory associati alla soluzione trovata. 4. Riportare i tagli sul disegno. -1 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 7 x1 x 2 Esercizio 5.Si consideri un problema di flusso massimo su un grafoG= (N , A) con 6 nodi. Siau ijla capacit`a sull’arco (, ij). Il taglio di capacit`a minima `eN S= {2,3,5}eN T= {1,4,6}. Si consideri un flusso ammissibile ˉx. Quale delle seguenti affermazioni `e vera e quale falsa? Giustificare lerisposte. a) Se ˉx 15= u 15allora ˉ x`e ottima. b) Se ˉx 15= 0 allora ˉ x`e ottima. c) Se ˉx 24< u 24allora ˉ xnon `e ottima. d) Se ˉx`e ottima allora ˉx 36= u 36. e) Se ˉx`e ottima allora ˉx 35= 0. Esercizio 6.Si consideri l’albero parziale di branch and bound per un problema dimassimo mostrato in figura, dove per ogni nodo, tranne il nodo 6, sono dati l’upper boundU Be il lower boundLB. Il problemaP 5non `e ammissibile. P 0 [162 ,148] P 2 [155 ,151] P 1 [160 ,149] P 3 [159,150] P 4 [155,149] P 5 N.A. P6 1.` E possibile cheLB 6= 159? Motivare la risposta. 2. In che intervallo `e compreso l’ottimo? Si fornisca l’intervallo pi`u stringente. 3. Per quali valori diU B 6e LB 6`e possibile chiudere P 3? Motivare la risposta. 4. Per quali valori diU B 6e LB 6`e possibile chiudere tutti i nodi? Motivare la risposta.