Esame 2017 07 07

Page 1

Fondamenti di Ricerca Operativa AA 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 istr uzione. Alla gita partecipano alcune classi dell’istituto, descritte dall’insieme C: per ogni classe k ∈ C ` e noto il numero dei partecipanti pk. Per trasportare gli studenti si useranno dei bus messi a disposizion e da un’agenzia di viaggi. I bus disponibili sono descritti da un insieme V : per ogni bus j ∈ V ` e dato il numero di posti disponibili dj (escludendo i posti riservati ai docenti) e il costo di affitto del bus gj. Per fare assistenza alla gita si sono resi disponibili alcuni insegnan ti dell’istituto, descritti da un insieme I. Per ogni classe devono essere presenti almeno due insegnanti, s celti tra quelli che abitualmente insegnano nella classe stessa: un parametro mik ci dice se l’insegnante i abitualmente insegna nella classe k (mik = 1) o no ( mik = 0). il numero degli insegnanti deve essere almeno pari al numero dei bus di modo che ci possa essere almeno un insegnante su ogni b us. Per ogni insegnante presente alla gita la scuola deve affrontare un costo f , relativo alle spese di viaggio e soggiorno del docente stesso. Il pr eside deve decidere quali bus utilizzare e su quale bus debba essere trasp ortata ogni classe, sapendo che le classi non possono essere divise su pi` u veicoli. Inoltre deve decidere quali e q uanti insegnanti inviare in gita. L’obiettivo ` e minimizzare il costo complessivo della gita (trasporto e spese per i do centi). 1. Formulare in Programmazione Lineare Intera il problema descritt o. 2. V arianteCome cambia il modello se si vuole che almeno Q classi siano accompagnate da tre…