Anno Accademico 2013-2014 19 febbario 2015
Corso 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 Fase II del metodo del simplesso pu`o ciclare e descrivere brevemente una possibile strategia che si pu`o adottare per evitare questo fenomeno.
b) (Punti 8) Enunciare e dimostrare il teorema che fornisce una caratterizzazione algebrica dei vertici di un poliedro in forma standard.
Parte 2
–Esercizi
1) (Punti 8) Una fabbrica produce 3 diversi tipi di cioccolata: al latte, fondente con nocciole, al latte con nocciole.
Per la produzione della cioccolata sono necessari quattro ingredienti: latte, cacao, nocciole e zucchero. Nella tabella vengono indicati i kg di nocciole, cacao e zucchero e i litri di latte necessari per ciascun kg di cioccolata, le quantit´a massime disponibili in kg e i costi unitari in euro al kg di questi ingredienti:
al latte fond. con nocciole al latte con nocciole quantit`a max costi unitari
latte 0.6 0.2 0.4 7500 1
cacao 0.5 0.7 0.5 10000 2
nocciole 0 0.1 0.1 4000 1.5
zucchero 0.3 0.2 0.3 5000 0.5
Ogni kg di cioccolata al latte viene venduto a 7 euro, ogni kg di cioccolata fondente con nocciole viene venduto a 10 euro, ogni kg di cioccolata al latte con nocciole viene venduto a 9 euro. Inoltre la produzione di cioccolata al latte, di cioccolata fondente con nocciole e di cioccolata al latte con nocciole non deve superare rispettivamente il 70%, il 40% e il 50% della produzione totale. Si vuole pianificare la produzione di questa industria, si vuole cio`e determinare le quantit`a di ciascun tipo di cioccolata da produrre sapendo che in totale devono essere prodotti almeno 6750 kg di cioccolata (indipendentemente dal tipo), in modo da massimizzare il profitto netto.
• 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− x2+ x3
x1− 4x2+ x3≥ 1 x1− x2− 2x3≥ 0 x ≥ 0
3) (Punti 6) Risolvere il seguente problema di knapsack binario usando il metodo del Branch and Bound:
max 4x1− x2+ x3+ 0.1x4+ 4.2x5+ 3x6+ x7
2x1+ x2+ 3x3+ x4+ 3x5+ 3x6+ 2x7≤ 7 x ∈ {0, 1}7
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: ...
