Ottimizzazione nella gestione dei progetti
Studente: …………………………………
Prova scritta del 16/04/2005 COMPITO B
Matricola: …………………………………
ESERCIZIO 1
2
2
(5 punti)
0
Dati il grafo dei vincoli e il
costo relativo ad ogni
1
possibile istante di inizio delle
attività:
4
1
2
5
1
0
1
3
7
1
3
t0
t1
t2
t3
a2
1
2
3
4
a3
3
1
3
t4
t5
a4
4
2
4
1
a5
2
3
1
2
2
1
a6
1
6
(2 punti) Disegnare il grafo associato al problema di taglio minimo per la minimizzazione dei costi.
(3 punti) Date le soluzioni S1={(2,0) (3,2) (4,2) (5,3) (6,2)} S2={(2,0) (3,0) (4,0) (5,2) (6,2)},
determinarne l’ammissibilità utilizzando i corrispondenti tagli e, se ammissibili, determinarne il
costo.
ESERCIZIO 2
(6 punti)
SFmax(7)
FSmin(0)
FSmin(0)
2
FSmin(0)
4
SFmin(4)
Att
1
2
3
4
5
6
7
d
0
9
3
1
1
2
0
SSmin(3)
7
FSmin(1)
6
FFmax(5)
1.
2.
3
SSmin(1)
SFmin(3)
1
Dato il seguente grafo delle precedenze:
5
SSmin(0)
(2 punti) effettuare la trasformazione nel grafo dei vincoli
(4 punti) calcolare l’ ESS (Earliest Start Schedule)
ESERCIZIO 3
(12 punti)
Sia dato il seguente grafo di precedenze semplici, ove i due
interi associati a ogni nodo rappresentano, rispettivamente,
la durata (in alto) e la quantità di risorsa utlizzata (in basso)
della corrispondente attività (1 e 9 sono le attività fittizie di
inizio e fine progetto). La quantità di risorsa disponibile in
ogni periodo è 4.
0
1
1
1
3
1
6
1
0
3
2
3
2
4
2
4
5
2
5
7
2
0
9
0
3
8
1
1. (Punti 2). Dare la definizione generale di chiusura transitiva e di insiemi ammissibili secondo
Mingozzi. Applicare le definizioni al grafo in figura.
2. (Punti 4). Scegliendo una coppia di attività opportuna, calcolare il lower bound “Critical Path
Rafforzato” relativamente alla coppia scelta.
3. (Punti 6). Calcolare il lower bound “Vertex Packing” (insieme stabile), utilizzando per il calcolo
euristico dell’insieme stabile l’algoritmo greedy.
ESERCIZIO 4
(Punti 8).
(Punti 4). Enunciare e dimostrare il lemma di validità delle disequazioni prodotte per round
down.
(Punti 3). Definire i tagli di Gomory e dimostrarne la validità.
(Punti 1). Mostrare come la disequazione clique x + y + z  1 può essere ottenuta dai vincoli
x + y  1, y + z  1, x + z  1
ESERCIZIO 3
Cammino critico (in rosso) (LBP = 12)
0
1
1
1
3
1
6
1
2
4
2
0
5
7
2
9
0
4
5
2
3
2
3
0
3
8
1
Se oriento l’arco da 2 a 5, il cammino
critico ha ancora peso 12.
0
1
1
1
3
1
6
1
0
3
2
3
2
4
2
4
5
2
5
7
2
0
9
0
3
8
1
L’attività 2 e l’attività 5 non possono essere
svolte simultaneamente (3+2= 5 > 4).
Aggiungo un arco alternativo di estremi 2 e 5.
Se oriento l’arco da 5 a 2, e calcolo il
nuovo cammino critico ottengo LB = 13
0
1
1
1
3
1
6
1
0
2
4
2
3
2
3
4
5
2
5
7
2
0
9
0
3
8
1
Quindi LBP rafforzato (con un singolo arco) = max{12, min {12,13}} = 12
Si potevano scegliere anche altre coppie (es. 2 e 4, 5 e 8).
ESERCIZIO 3
(12 punti)
1
Chiusura transitiva esclusi nodi fittizi.
0
1
1
1
3
1
6
1
0
2
4
2
5
7
2
3
3
9
0
4
5
2
3
2
3
0
1
6
2
2
5
7
4
4
5
3
8
Insiemi ammissibili
{2, 3}, {2,6}, {3,8},
{4,6}, {4,8}, {4,6,8},
{5,6}, {5,8}, {5,6,8},
{6,8}, {7,8}
Grafo delle coppie ammissibili
3
8
1
attività 2
3
4
5
6
7
8
Peso
3
1
2
4
1
5
3
Grado 2
2
2
2
4
1
5
Ratio 1.5 0.5 1.0 2.0 0.3 5.0 0.6
Rapporti Peso/Grado
Ordinamento non crescente di rapporti Peso/grado (possibili
anche altri ordinamenti):  = {7, 5, 2, 4, 8, 3, 6,}
1
1
6
3
Scelgo 7.
3
1
Scelgo 5.
3
Rimuovo 5 e
il suo intorno
Rimuovo 7 e
il suo intorno
2
2
Scelgo 2.
Rimuovo 2 e il
suo intorno.
4
4
5
S = {2,4,5,7}
3
2
2
4
Il bound vale p(S) = 3 + 2 + 4 + 5 = 14
Scelgo 4.
2
4