Anno Accademico 2013-2014
A
21 gennaio 2015Corso 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 il concetto di totale unimodularit`a `e di fondamentale importanza nella Programmazione Lineare Intera.
b) (Punti 8) Enunciare e dimostrare che un punto ¯x di un poliedro in Rn in forma generale `e vertice se e solo se in ¯x sono attivi n linearmente indipendenti.
Parte 2
–Esercizi
1) (Punti 8) Una fabbrica di calzature vuole produrre cinque nuovi modelli di scarpe: M1, M2, M3, M4 e M5.
Per la loro lavorazione si utilizzano pellami che vengono acquistati dall’esterno dei quali la fabbrica `e rifornita giornalmente. In particolare, per produrre una scarpa `e necessario l’utilizzo di un quantitativo di pellame che varia da modello a modello e che `e riportato nella tabella che segue (in cm2). Inoltre, la lavorazione di una scarpa si compone di tre fasi: il taglio del pellame, la cucitura e la lucidatura. Nella tabella che segue si riportano i tempi (in minuti) necessari per avere una scarpa finita pronta per la vendita e il prezzo di vendita unitario per ciascun modello (in Euro):
M1 M2 M3 M4 M5
pellame (cm2) 30 40 40 30 45
taglio (minuti ) 3 2 2.5 2.5 2
cucitura (minuti ) 3 2.5 3 4 3
lucidatura (minuti ) 1 1.5 1 1 1.5 prezzo (Euro) 110 130 115 140 125
Giornalmente arrivano alla fabbrica 4000 cm2di pellame il cui costo `e di 2.5 Euro per cm2. Per quanto riguarda le tre fasi di lavorazioni, la fabbrica dispone di un numero di operai pari 30 che lavorano 8 ore al giorno e vengono ripartiti nei tre reparti dove vengono effettuate le tre fasi di lavorazione. Al momento la ripartizione nei reparti `e di 10 operai per ciascuno dei reparti. Per motivi legati al mercato, la percentuale di ciascun modello fabbricato non deve superare il 35% del totale. Inoltre, giornalmente si vogliono fabbricare almeno 2 scarpe del modello M1, almeno 3 di ciascuno dei modelli M2, M3 e M4 e almeno 2 del modello M5. Si vuole determinare le quantit`a di ciascun modello di scarpe da fabbricare (e quindi vendere) giornalmente in modo da massimizzare il profitto netto complessivo (ricavo sottratto dei costi)
• 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 5x1− 2x2− x3
−2x1+ x2+ x3= 1 2x1− x2− 3x3= −1 x ≥ 0
3) (Punti 6) Risolvere il seguente problema di knapsack binario usando il metodo del Branch and Bound:
max x1+ 4x2− 3x3− 2x4+ 3x5+ 4x6+ x7
x1− x2+ 2x3+ x4+ 2x5+ 4x6+ 2x7≤ 5 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: ...
