Mathematical Engineering - Fondamenti di Ricerca Operativa

Full exam

Fondamenti di Ricerca OperativaAA 2016/2017 Esame del 7 Luglio 2017 COGNOME NOME MATRICOLA SCRIVERE LE RISPOSTE NELLO SPAZIO SOTTO IL TESTO O NELLA PAGINA PRECEDENTE. Esercizio 1.Il preside di una scuola superiore deve organizzare una gita di istruzione. Alla gita partecipano alcune classi dell’istituto, descritte dall’insiemeC: per ogni classek∈C`e noto il numero dei partecipantip k. Per trasportare gli studenti si useranno dei bus messi a disposizione da un’agenzia di viaggi. I bus disponibili sono descritti da un insiemeV: per ogni busj∈V`e dato il numero di posti disponibilid j(escludendo i posti riservati ai docenti) e il costo di affitto del busg j. Per fare assistenza alla gita si sono resi disponibili alcuni insegnan ti dell’istituto, descritti da un insiemeI. Per ogni classe devono essere presenti almeno due insegnanti, scelti tra quelli che abitualmente insegnano nella classe stessa: un parametrom ikci dice se l’insegnante iabitualmente insegna nella classek(m ik= 1) o no ( m ik= 0). il numero degli insegnanti deve essere almeno pari al numero dei bus di modo che ci possa essere almeno un insegnante su ogni bus. Per ogni insegnante presente alla gita la scuola deve affrontare un costof, relativo alle spese di viaggio e soggiorno del docente stesso. Il preside deve decidere quali bus utilizzare e su quale bus debba essere trasportata ogni classe, sapendo che le classi non possono essere divise su pi`u veicoli. Inoltre deve decidere quali e quanti insegnanti inviare in gita. L’obiettivo `e minimizzare il costo complessivo della gita (trasporto e spese per i docenti). 1. Formulare in Programmazione Lineare Intera il problema descritto. 2.VarianteCome cambia il modello se si vuole che almenoQclassi siano accompagnate da tre insegnanti che le conoscono? 3. Scrivere secondo la sintassi di AMPL il modello relativo al punto 1. Esercizio 2.Risovere il seguente problema di Programmazione Lineare: max 3x 1+ 4 x 2− x 3− 5x 4 x1+ 2 x 2+ x 3+ 2 x 4≤ 5 3x 1− x 2+ 5 x 3+ x 4≤ 1 xi≥ 0,∀i= 1, . . . ,4 Esercizio 3.Un’azienda di trasporti deve attivare delle tratte per collegare 7 citt`a nella provincia in cui opera. Le citt`a sono rappresentate come nodi di un grafo e le tratte disponibili come lati di un grafo. Il grafo `e riportato in figura. Ogni tratta `e percorsa in entrambi i sensi. Ad ogni tratta `e associato un costo, dovuto al costo di carburante necessario a precorrere la tratta e all’autista. Il costo `e riportato sul lato corrispondente. L’azienda vuole selezionare le tratte da attivare in modo da garantire che da ogni citt`a si possa raggiungere ogni altra citt`a della regione e vuole minimizzare il costo complessivo delle tratte attivate. D A F G B C E 13 12 9 12 12 10 8 7 20 15 11 •Si che problema si tratta? •Calcolare la soluzione ottima, descrivendo l’algoritmo applicato. •Si vuole aggiungere un’ulteriore citt`a,H, che pu`o essere collegata aBcon costo 10, aCcon costo 12 e aFcon costo 9. Senza ricalcolare l’intera soluzione, come si pu`o collegareHin modo ottimo? Motivare la risposta. •Si rende disponibile una nuova tratta, che collegaAaGcon costo 8: la soluzione ottima cambia? Motivare la risposta. Esercizio 4.Risolvere il seguente problema di zaino binario con il branch and bound, calcolando un lower bound solo al nodo radice: max 8x 1+ 12 x 2+ 24 x 3+ 19 x 4 2x 1+ 4 x 2+ 5 x 3+ 3 x 4≤ 7 xi∈ { 0,1},∀i= 1, . . . ,4 Esercizio 5.Quale delle seguenti affermazioni `e vera? Motivare la risposta: •Un problema di programmazione lineare la cui regione ammissibile `e un politopo ha sempre una soluzione ottima finita. •Se un problema di programmazione lineare `e ammissibile allora ha sempre una soluzione ottima di base. •Un problema in programmazione lineare pu`o avere una soluzione ottima di base e infinite soluzioni ottime non di base. Esercizio 6.Scrivere il modello in programmazione lineare del problema del flusso massimo e del suo duale e commentare il significato dei due modelli e le relazioni tra i due problemi.