Mathematical Engineering - Fondamenti di Ricerca Operativa

Full exam

Fondamenti di Ricerca OperativaAA 2016/2017 Esame del 24 Luglio 2017 COGNOME NOME MATRICOLA SCRIVERE LE RISPOSTE NELLO SPAZIO SOTTO IL TESTO O NELLA PAGINA PRECEDENTE. Esercizio 1.Un albergo deve gestire la pulizia della propria biancheria, asciugamanie lenzuoli, per il prossimo periodo, descritto dall’insieme di giorniT.` E un periodo di intensa attivit`a per l’albergo: per ogni giornot∈Tsono noti il numero di asciugamanira te il numero di lenzuoli rl tnecessari. All’inizio del periodo tutta la biancheria `e in uso in una stanza. Ogni giornoda t asciugamani e dl t lenzuoli vengono tolti dalle camere e devono essere lavati. Inoltre i lenzuoli devono essere stirati. La biancheria sporca deve venire lavata il giorno stesso in cui `e tolta dalle camere. Ogni giorno l’albergo deve decidere quanta biancheria lavare e stirare internamente e quanta inviare a una lavanderia esterna. Per ogni asciugamano inviato alla lavanderia esterna l’albergo paga un prezzog a, mentre paga un prezzo glper ogni lenzuolo. La biancheria inviata alla lavanderia `e pronta dopo 36 ore: se viene consegnata il giornoialla lavanderia `e riconsegnata nella mattina del giornoi+ 2 (e in quel giorno pu`o venire usata). Invece la biancheria lavata internamente `e pronta per essere usata il giorno successivo. Il costo di lavare un asciugamano nella lavanderia dell’albergo `ec a, il costo di lavare un lenzuolo `e c l. Inoltre i lenzuoli vanno stirati: l’albergo si affida a una stiratrice che pagafeuro per ogni mezza giornata, indipendentemente dal numero di lenzuoli stirati. La stiratrice pu`o lavorare per mezza giornata o per una giornata intera e stira fino aqlenzuoli in una mezza giornata. La biancheria pulita e stirata pu`o venire conservata in armadio se non viene usate immediatamente. 1. Formulare in Programmazione Lineare Intera il problema di gestire la pulizia della biancheria a costo minimo. 2.Variante:come cambia il modello se ogni giorno la lavanderia applica uno sconto disse la spesa del giorno `e di almenoK? 3. Scrivere secondo la sintassi di AMPL il modello relativo al punto 1. Esercizio 2.Si consideri il seguente problema in Programmazione Lineare: maxx 1− 2x 2 −5x 1+ x 2≤ 10 x2≤ 5 −x 1− x 2≤ 2 x1− x 2≤ 6 x1≤ 7 x1, x 2libere 1. Scrivere il duale del problema. 2. Enunciare tutte le condizioni di complementarit`a per il problema. 3. Applicando le condizioni di complementarit`a dire quale delle seguenti soluzioni `e ottima: (a) (−1,5) (b) (7,1) (c) (2,−4) Esercizio 3.Un grossista di prodotti farmaceutici deve rifornire 6 farmacie inuna zona montana. Il grossista effettua le consegne con un furgoncino, la cui capienza permette di portare il materiale per una sola farmacia. Ogni farmacia viene dunque rifornita in un giorno diverso della settimana. Poich`e le farmacie sono piuttosto distanti dal magazzino, il costo del carburante, proporzionale alla distanza da percorrere, `e rilevante e il grossista vuole decidere con che percorso rifornire ogni farmacia in modo da minimizzarlo. La rete stradale che collega farmacie e magazzino `e descritta dal grafo orientato in figura, dove il nodoMrappresenta il magazzino e i nodi 1, . . . ,6 rappresentano le farmacie. Per ogni strada, che pu`o essere percorsa in un solo senso, `e riportata la lunghezza. 3 M 5 4 2 1 6 20 23 10 60 15 30 26 7 19 35 6 1. Indicare di quale problema su grafo si tratta e qual `e l’algoritmopi`u efficiente per risolverlo. 2. Trovare i migliori percorsi per rifornire le farmacie, descrivendo i passi dell’algoritmo applicato. . 3. Viene aperta una nuova strada che collega il magazzino con la farmacia 6: discutere, applicando le opportune condizioni di ottimalit`a, per quali valori della lunghezzaαdella nuova strada la soluzione ottima attuale `e ancora ottima. Esercizio 4.Risolvere il seguente problema di Programmazione Lineare Intera con il branch and bound, risolvendo il rilassamento continuo in ogni nodo per via grafica e eseguendo prima il branch sulla variabilex 2. Riportare tutti i nodi dell’albero di branch and bound e motivare la chiusura dei nodi. max−x 1+ 4 x 2 −4x 1+ 2 x 2≤ 9 −2x 1− 2x 2≤ − 1 2x 1≤ 13 2x 1+ 4 x 2≤ 23 x1, x 2≥ 0 -1 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 7 x 1 x 2 Esercizio 5.Si consideri un problema di ottimizzazione nella forma decisionaleP. Quale delle seguenti affermazioni `e vera? Motivare la risposta. 1. SeP ∈PalloraP ∈N P. 2. SeP ∈PalloraP ∈N P-completi. 3. Se il problema dello zaino si pu`o ridurre aPalloraP`eN P-completo. 4. Se il problemaPsi pu`o ridurre al problema dello zaino alloraP`eN P-completo. N.B.: si ricorda che il problema dello zaino, nella sua forma decisionale, `e un problemaN P-completo. Esercizio 6.Enunciare il Teorema Fondamentale della Programmazione Lineare e discutere la sua rilevanza e l’impatto sul metodo del Simplesso.