Progetto e Ottimizzazione di Reti 06/07 Homework 3
Esercizio 1
Gli archi di maggiore spessore sono un matching perfetto sul grafo di figura. Dimostrare se questo matching è il matching perfetto di peso minimo.
3 6 5 8 3
4 10 1 2
8 Esercizio 2
Un’azienda dolciaria artigianale deve pianificare la produzione di panettoni per la settimana che precede il Natale. Per garantire un panettone sempre fragrante l’azienda o consegna il panettone prodotto in giornata, oppure lo conserva in un apposito magazzino riscaldato per al massimo tre giorni dalla data di produzione. La tabella seguente esprime la richiesta giornaliera di panettoni
Lunedì Martedì Mercoledì Giovedì Venerdi Sabato 110 130 135 135 175 205
Sapendo che:
1. L’azienda ha una capacità massima giornaliera di produzione come da tabella, con associato il costo di produzione giornaliero per panettone
Lunedì Martedì Mercoledì Giovedì Venerdi Sabato Capacità 180 170 165 155 130 90
Costo (€cent/panettone)
35 40 40 55 65 70
2. Il magazzino ha capacità sufficientemente grande e che immagazzinare un panettone ha un costo di 30 €cent al giorno.
Formulare il problema di minizzare i costi di produzione soddisfacendo completamente la domanda come problema di flusso a costo minimo e calcolare la soluzione ottima.
*
Progetto e Ottimizzazione di Reti 06/07 Homework 3
Esercizio 3
Risolvere, con l’algoritmo del simplesso su reti, il seguente problema di Programmazione Lineare:
min 28 x1 + 32 x2 + 14 x3 + 18 x4 + 21 x5
s.t.
x1 + x2 > 4 x1 + x2 + x3 > 12 x2 + x3 + x4 > 15 x1 + x2 + x3 > 10 x > 0
Esercizio 4
Calcolare il flusso di costo minimo sul seguente grafo (sugli archi sono riportati i valori cij, uij)
-2 3, 6 +5
7, 8 4, 6
1, 4 5, 9
4, 5 +3 -2
+5
8, 6 3, 4
1, 3
2, 5 2, 7
-6 -3
*
