Anno Accademico 2013-2014
A
2 luglio 2014Corso di Laurea in Ingegneria Informatica e Automatica
Prova di esame di Ricerca Operativa (9 cfu)
Cognome: Nome: matricola:
Quesito A Quesito B Totale Esercizio 1 Esercizio 2 Esercizio 3 Totale PUNTEGGIO
teoria esercizi TOTALE
Parte 1
–Quesiti teorici
a) (Punti 2) Spiegare perch`e la corrispondenza tra Soluzioni di Base Ammissibili e Basi, in generale, non `e biunivoca.
b) (Punti 8) Enunciare e dimostrare il Teorema Fondamentale della Programmazione Lineare (Riportare senza dimostrazione l’enunciato del Lemma utilizzato nella dimostrazione stessa).
Parte 2
–Esercizi
1) (Punti 8) Un’industria acquista materie grezze e le lavora ottenendo un prodotto finale. Le materie grezze che possono essere acquistate sono quattro: M1, M2, M3, M4. I contenuti percentuali di zinco, rame e carbonio delle materie grezze sono riportati nella seguente tabella insieme ai costi unitari (in Euro al quintale) e alla disponibilit`a massima (in quintali)
zinco rame carbonio Costi unitari disponibilit`a max
M1 3.5 5 2.5 40 10000
M2 6.3 4.2 3.7 52 8000
M3 2.8 7 5.2 51 9000
M4 4.1 6 5.2 47 9500
Il prodotto finale deve avere un contenuto di almeno il 5% di zinco, di almeno il 3% di rame e di almeno il 2% di carbonio. Si vuole pianificare la produzione di questa industria, si vuole cio`e determinare le quantit´a di ciascuna materia grezza da usare per ottenere il prodotto finale sapendo che devono essere prodotti almeno 12500 quintali di prodotto finale, in modo da minimizzare il costo complessivo. Si tenga inoltre conto della limitazione commerciale che consiste nell’imporre che se `e utilizzata la materia M1 allora non pu`o essere utilizzata la materia M2.
• Costruire un modello lineare (formulazione algebrica) per questo problema.
• Scrivere in forma parametrica i file .mod, .dat che realizzano un’implementazione in AMPL di questo problema.
2) (Punti 8) Usando il metodo del simplesso risolvere il seguente problema di Programmazione Lineare:
min x1+ 2x2+ 3x3 x1+ 2x2+ x3= 4
−2x1+ x2−2x3= −2 x≥0
3) (Punti 6) Utilizzando l’algoritmo di Dijkstra calcolare il cammino minimo dal nodo 1 al nodo 9 del grafo rappresentato in figura. Rappresentare anche l’albero dei cammini minimi.
Autorizzo la pubblicazione su sito internet del risultato della prova ai sensi del Decreto Legislativo n. 196 del 30/6/2003 (Codice in materia di protezione dei dati personali)
Firma: ...
