Corso di Ottimizzazione
Prova scritta del 28 Giugno 2017 Tempo a disposizione: ore 2:00.
Si ricorda che:
• Per quanto possibile, occorre scrivere in bella calligrafia (il testo illeggibile non verrà preso in considerazione).
• Su tutti i fogli che vi abbiamo consegnato occorre riportare cognome, nome e numero di matricola.
• Occorre riportare in modo chiaro tutti i passi che portano alla determinazione del risultato.
• Il numero dell’esercizio che si sta svolgendo va sempre riportato in modo chiaro.
• Non è consentita la consultazione di appunti, libri, etc.
• Non è consentito l’uso di calcolatrici, telefoni cellulari, etc.
• Non è concesso chiedere alcunché ai docenti e agli altri studenti.
• Occorre consegnare anche la brutta copia ai docenti.
Esercizio 1. (Punti 8)
Nel laboratorio informatico di una software house è necessario compilare n progetti tramite m macchine, dove m < n. La compilazione del progetto i richiede tij minuti se eseguita dalla macchina j. Scopo dell’azienda è, ovviamente, quello di minimizzare il tempo complessivo di compilazione, tenendo conto del fatto che le m macchine possono lavorare in parallelo tra loro, ma che ogni macchina può compilare in ogni istante al più un progetto. Si scriva un programma lineare che corrisponda a tale problema.
Esercizio 2. (Punti 4, la risposta occupi al massimo 15 righe)
Si enunci e si dimostri una condizione necessaria e sufficiente a che un vettore ξ sia direzione ammissibile per un puntox.
Esercizio 3. (Punti 8)
Si risolva, tramite l’algoritmo del simplesso primale, il seguente problema di programmazione lineare:
min x1+ 4x2
x1≤ 0 x1+ x2≤ 1
2x2− x1+ 4 ≥ 0 x1+ x2+ 5 ≥ 0
x2+ 3 ≥ 0 x1− x2+ 2 ≥ 0
x2≤ 0
Si parta dalla base ammissibile corrispondente ai vincoli della prima riga.
Esercizio 4. (Punti 8)
Si risolva il seguente problema MF con tramite l’algoritmo di Edmonds-Karp, determinando anche un taglio di capacità minima.
s
1 2 3
4 5 6
t
13
2 18
10
8 15
4 1
9 5
31
16
8 3 18
Esercizio 5. (Punti 4)
Nell’ambito dell’Esercizio 1, si consideri lo scenario seguente. Ogni macchina j ∈ {1, . . . , m}
consuma ej unità di energia elettrica ogni ora. L’azienda vuole fare in modo che le unità di energia elettrica complessivamente spese non superino un certo limite superioreu. Come è possibile catturare tale vincolo?.
