Ricerca operativa - esercizi

Prof. Gennaro Improta - Prova d'esame del 17 giugno 2008

In occasione della Giornata Mondiale dei Rifugiati del 20 giugno 2008, l’agenzia per i rifugiati delle Nazioni Unite (UNHRA) deve predisporre un piano per la realizzazione di piccoli alloggi in legno ed elementi prefabbricati da collocare in un nuovo campo di accoglienza, destinato ad accogliere almeno 1200 rifugiati.

Attraverso una ricerca di mercato, è stata individuata una ditta che propone due tipi di alloggio adatti allo scopo: il modello Dafne (in grado di ospitare 2 persone) ed il modello Silene (in grado di ospitarne 3).

La ditta metterà a disposizione i progetti e le istruzioni per l’assemblaggio delle diverse parti, e fornirá i principali materiali consistenti, per un alloggio del tipo Dafne, in 8 quintali di elementi prefabbricati per la realizzazione del basamento e delle strutture portanti, e 60 m² di parti in legno impregnato.

Ogni alloggio del tipo Silene richiede, invece, per la sua costruzione, 10 quintali di elementi prefabbricati e 200 m² di parti in legno impregnato.

La ditta è in grado di assicurare, in tempo utile, al più 8000 quintali di elementi prefabbricati e 120000 m² di parti in legno impregnato.

Sapendo che il costo di realizzazione per un alloggio di tipo Dafne è pari a 10.000 euro, mentre quello degli alloggi di tipo Silene risulta pari a 13.000 euro, l’ufficio tecnico dell’UNHRA è chiamato dalla direzione a calcolare quanti alloggi dei due tipi convenga realizzare per minimizzare il costo complessivo.

Da un sondaggio effettuato tra gli utilizzatori, risulta che agli alloggi di tipo Dafne è associato un indice di gradimento pari a 10, mentre agli alloggi di tipo Silene è associato un indice di gradimento pari a 15.

Per lo stesso progetto è da ognuno degli alloggi di tipo Dafne.

L’ufficio tecnico è dunque chiamato a fornire anche un secondo piano di realizzazione dell’intervento, che indichi quanti alloggi di ciascun tipo realizzare per massimizzare un indicatore di accoglienza complessivo, pari alla somma del numero di alloggi realizzati per ciascun tipo, moltiplicati per i rispettivi indici di gradimento.

Quesito 1

• Si formuli il modello di programmazione lineare associato ai due problemi di ottimizzazione;
• Si disegni il dominio di ammissibilità;
• Si disegnino sul grafico le funzioni obiettivo e le direzioni dei rispettivi gradienti;
• Si risolva graficamente il modello, individuando i vertici corrispondenti alle soluzioni ottime ed i corrispondenti vincoli saturi;
• Si indichino gli eventuali vertici corrispondenti a soluzioni degenerate, specificando anche se sono ammissibili o meno;
• Si indichino tutte le soluzioni di base (ammissibili e non ammissibili) individuabili sul grafico o sul diagramma di esso, specificando la composizione delle basi;
• Si calcoli analiticamente la prima soluzione ottima, utilizzando uno ed uno solo dei metodi di simplesso noti;
• Si indichino gli archi successivamente esclusi dai vertici (non ammissibili ed ammissibili) esplorati dall’algoritmo del simplesso durante la ricerca delle soluzioni ottime;

Quesito 2

Con riferimento al problema relativo al quesito 1, ed al caso di massimizzazione dell’indice di accoglienza:

• Si effettui, in modo analitico e grafico, l’analisi di stabilità per variazioni del termine noto relativo al vincolo sulla disponibilità di Silene;

Quesito 3

Si consideri il problema del P di massimizzare due espressioni:

• Si individui il problema duale;
• Si spieghino le operazioni effettuate per ottenerlo;
• Si fornisca una interpretazione del significato delle variabili del problema duale;
• Si determini il valore delle variabili del problema duale all’ottimo.

Quesito 4

La direzione strategica dell’UNHRA, preso atto delle proposte di intervento a minimo costo e massima accoglienza, ritiene opportuno adottare quest’ultimo criterio.

Tuttavia sottopone all’attenzione dell’ufficio tecnico la presenza di un vincolo di budget stringente per il completamento dell’operazione, che impone una disponibilità massima per l’operazione pari a 6,5 milioni di euro.

Si calcoli analiticamente la nuova soluzione ottima in grado di massimizzare l’indice di accoglienza, tenendo conto di questo ulteriore vincolo.

Quesito 5

Con riferimento al grafo riportato in figura con i relativi pesi sugli archi:

• Si determini l’arborescenza dei minimi percorsi relativo al nodo origine (con etichetta 1) utilizzando l’algoritmo di Dijkstra;
• Si illustrino i passi teorici della procedura utilizzata;
• Si ipotizzi che il grafo considerato rappresenti il reticolo delle attività di un progetto e che i costi sugli archi siano le durate delle attività, si determini e si illustri il relativo percorso critico e si costruisca il relativo diagramma di Gantt.

Tempo massimo a disposizione 3 ore.

Rispondere ai quesiti (ed ai sottoquesiti) nel medesimo ordine in cui sono posti.

Scrivendo in modo chiaro.

Utilizzare fogli a quadretti, numerando i fogli e segnando cognome nome e matricola in alto a destra.