Mathematical Engineering - Fondamenti di Ricerca Operativa

Full exam

Fondamenti di Ricerca OperativaAA 2016/2017 Esame del 21 Settembre 2017 COGNOME NOME MATRICOLA SCRIVERE LE RISPOSTE NELLO SPAZIO SOTTO IL TESTO ONELLA PAGINA PRECEDENTE. Esercizio 1.Il gestore di alcuni stabilimenti balneari deve decidere come allestire i suoi stabilimenti (descritti dal- l’insiemeJ) per il prossimo anno. In ogni stabilimentoj∈Jc’`e spazio perb jfile di postazioni. Le postazioni possono essere allestite o in modo normale (due sdraio e un ombrellone) o in versione lusso (un ombrellone, due lettini e una sdraio) e in ogni fila dello stabilimentoj∈Jc’`e posto pern jpostazioni normali e per l jpostazioni di lusso. Postazioni normali e di lusso non vengono mescolate nella stessa fila. Ad ogni postazione di lusso deve essere garantita una cabina: per ogni stabilimentoj`e noto il numero di cabine disponibiliC j. In magazzino il gestore ha a disposizione Ssdraio, Llettini eOombrelloni, che possono essere usati in ogni stabilimento. Se ci fosse bisogno di altri ombrelloni, lettini o di altre sdraio, il gestore potr`a acquistarle: il costo di un ombrellone `eg O, il costo di un lettino `e g Lmentre il costo di una sdraio `eg S. Per la manutenzione degli stabilimenti il gestore deve assumere un a persona ognikfile di ombrelloni e pagare uno stipendiof. Un dipendente non pu`o lavorare per pi`u di uno stabilimento. Il prezzo di affitto per la stagione di una postazione nello stabilimentoj∈J`epl j e pn j per una postazione di lusso e normale, rispettivamente. Il gestore si aspetta il tutto esaurito per la stagione e deve decidere come allestire gli stabilimenti con l’obiettivo massimizzare il profitto (differenza tra ricavo e spese). 1. Formulare in Programmazione Lineare Intera il problema. 2.Variante:come cambia il modello se il gestore pu`o usufruire di uno sconto diqper l’acquisto di sdraio, lettini e ombrelloni se la spesa complessiva supera la cifraQ? 3. Scrivere secondo la sintassi di AMPL il modello relativo al punto 1. Esercizio 2.Risolvere il seguente problema in programmazione lineare: maxx 1+ 3 x 2− x 3+ x 4 x1+ x 2− 3x 3+ x 4≤ 5 −2x 1+ x 2+ x 3− 3x 4≤ 3 x1, x 2, x 3, x 4≥ 0 Esercizio 3.1. Risolvere il seguente problema di flusso massimo, dove per ogni arco sono indicati il flusso iniziale e la capacit`a, descrivendo i passi dell’algoritmo applicato: 1 2 3 5 6 4 7 6,10 2,3 1,2 5,7 0,3 2,2 0,5 1,6 6,6 2,5 . 2. Trovare un taglio di capacit`a minima illustrando il metodo con cui viene trovato. Esercizio 4.Si consideri il seguente problema di programmazione lineare intera: max−5x 1− x 2 2x 1+ 2 x 2≤ 17 26x 1+ 6 x 2≥ 39 x1, x 2≥ 0,intere 1. Calcolare la soluzione del rilassamento continuo per via grafica. -1 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 7 x1 x 2 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. Esercizio 5.Si consideri l’albero parziale di branch and bound per un problema diminimo mostrato in figura, dove per ogni nodo, tranne il nodo 6, sono dati l’upper boundU Be il lower boundLB. Il problemaP 4non `e ammissibile. P 0 [205 ,183.5] P 2 [201 ,191.6] P 1 [202 ,186.7] P 3 [203,188.3] P 4 N.A. P5 200, 192.5 P6 1.` E possibile cheU B 6= 190? E che U B 6= 199? 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 5? Motivare la risposta. 4. Per quali valori diU B 6e LB 6`e possibile chiudere tutti i nodi? Motivare la risposta. Esercizio 6.1. Descrivere le condizioni di ottimalit`a per il problema dell’albero di copertura di costo minimo. 2. Si consideri il grafo in figura, in cui per ogni lato `e riportato il peso. In grassetto `e riportato un albero di copertura per il grafo: 1 2 4 5 3 7 6 8 2 6 1 3 2 7 w78 8 12 5 w16 10 w67 7 8 (a) Per quali valori diw 78l’albero `e ottimo? Motivare la risposta. . (b) Per quali valori diw 67l’albero `e ottimo? Motivare la risposta. (c) Per quali valori diw 16l’albero `e ottimo? Motivare la risposta.