ESERCIZIO 1: Punto 1 - UnivAQ · 2018-10-26 · La seguente matrice è una matrice delle distanze...
Transcript of ESERCIZIO 1: Punto 1 - UnivAQ · 2018-10-26 · La seguente matrice è una matrice delle distanze...
La seguente matrice è una matrice delle distanze di un’istanza del
problema del Commesso Viaggiatore.
-2411127
2-313326
43-32415
113-3344
1323-123
13431-22
221422-1
7654321
Calcolare
1.Il valore del rilassamento che si ottiene determinando l’1-albero di costo minimo.
ESERCIZIO 1: Punto 1
Disegniamo il grafo G = (V, E) associato alla matrice delle
distanze.
1
3
45
6
72
2
24122
3
14
3
1
3
23
1
3
11
3
4
2
G
ESERCIZIO 1: Punto 1
Non consideriamo il nodo v = 1 e calcoliamo il minimo albero
ricoprente su G utilizzando l’algoritmo di Prim.
3
45
6
72
3
14
3
1
T = {2}; V–T = {3, 4, 5, 6, 7}
c*2i = min {c2i : i∈V–T} = c23 = c27 = 1
ESERCIZIO 1: Punto 1
Non consideriamo il nodo v = 1 e calcoliamo il minimo albero
ricoprente su G utilizzando l’algoritmo di Prim.
3
45
6
72
3
4
3
T = {2}; V–T = {3, 4, 5, 6, 7}
c*2i = min {c2i : i∈V–T}
1
1
= c27 = 1 T = {2, 7}; V–T = {3, 4, 5, 6}
7
1
14
2
ESERCIZIO 1: Punto 1
Non consideriamo il nodo v = 1 e calcoliamo il minimo albero
ricoprente su G utilizzando l’algoritmo di Prim.
3
45
6
72
3
4
3
T = {2, 7}; V–T = {3, 4, 5, 6}
c*2i = min {c2i : i∈V–T}
1
1
= c23 = 1
T = {2, 7,4};
V–T = {3, 5, 6}
7
c*7i = min {c7i : i∈V–T} = c73 =c74 = 1
4
21
1
4
3
3
1
= c74 = 1
ESERCIZIO 1: Punto 1
Non consideriamo il nodo v = 1 e calcoliamo il minimo albero
ricoprente su G utilizzando l’algoritmo di Prim.
3
45
6
72
3
4
3
T = {2, 7, 4}; V–T = {3, 5, 6}
c*2i = min {c2i : i∈V–T}
1
1
= c23 = 1
T = {2, 7, 4, 6};
V–T = {3, 5}
7
c*7i = min {c7i : i∈V–T} = c73 = 1
4
21
1
4
3
3
c*4i = min {c4i : i∈V–T} = c46 = 1
1
6
3
3
ESERCIZIO 1: Punto 1
Non consideriamo il nodo v = 1 e calcoliamo il minimo albero
ricoprente su G utilizzando l’algoritmo di Prim.
3
45
6
72
3
4
3
T = {2, 7, 4, 6}; V–T = {3, 5}
c*2i = min {c2i : i∈V–T}
1
1
= c23 = 1
T = {2, 7, 4, 6, 3};
V–T = {5}
7
c*7i = min {c7i : i∈V–T} = c73 = 1
4
21
1
4
3
3
c*4i = min {c4i : i∈V–T} = c43 = c45 = 3
1
6
3
c*6i = min {c6i : i∈V–T} = c63 = c65 = 3
3
23
ESERCIZIO 1: Punto 1
A questo punto, l’arco che dista meno dal nodo 5 è l’arco (3,5).
3
45
6
72
T = {2, 7, 4, 6, 3, 5}; V–T = ∅
17
1
4
1
6
3
4
3
1
4
21
3
3
3
3
3
2
Minimo albero ricoprente = {27, 74, 46, 73, 35}
5
ESERCIZIO 1: Punto 1
Per calcolare l’1-abero, re-introduciamo il nodo 1 e prendiamo i
due archi di costo minimo uscenti da tale nodo.
3
45
6
721
7
1
4
1
6
32
12
24122
1-albero = {15, 16, 27, 74, 46, 73, 35}
C(1-albero) = 9 = LOWER BOUND1
1
12
5
ESERCIZIO 1: Punto 1
La seguente matrice è una matrice delle distanze di un’istanza del
problema del Commesso Viaggiatore.
-2411127
2-313326
43-32415
113-3344
1323-123
13431-22
221422-1
7654321
Calcolare
3. Il valore di una soluzione euristica calcolata con l’algoritmo Double Tree.
ESERCIZIO 1: Punto 2
Calcoliamo il minimo albero ricoprente sul grafo di partenza G =
(V, E) utilizzando l’algoritmo di Prim.
1
3
45
6
72
2
24122
3
14
3
1
3
23
1
3
11
3
4
2
G
ESERCIZIO 1: Punto 2
1
3
45
6
72
2
2422
1
5
4
3
3
4
2
T = {1}; V–T = {2, 3, 4, 5, 6, 7}
c*1i = min {c1i : i∈V–T} = c15 = 1
T = {1, 5};
V–T = {2, 3, 4, 6, 7}
ESERCIZIO 1: Punto 2
1
3
45
6
72
41
5
4
3
3
4
c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2
T = {1, 5, 3};
V–T = {2, 4, 6, 7}
c*5i = min {c5i : i∈V–T} = c53 = 2
2
222
2
3
1
3
3
1
ESERCIZIO 1: Punto 2
1
3
45
6
72
41
5
4
4
c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2
T = {1, 5, 3, 2};
V–T = {4, 6, 7}
c*5i = min {c5i : i∈V–T} = c54 = c56 = 2
2
22
2
3
3
3
c*3i = min {c3i : i∈V–T} = c32 = c37 = 1
3
3
11
2
3
3
21
1
ESERCIZIO 1: Punto 2
1
3
45
6
72
41
5
44
c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2
T = {1, 5, 3, 2, 7};
V–T = {4, 6}
c*5i = min {c5i : i∈V–T} = c54 = c56 = 2
2
22
2
3
3
3
c*3i = min {c3i : i∈V–T} = c37 = 1
3
3
11
2
3
3
21
c*2i = min {c2i : i∈V–T} = c27 = 1
17
2
1
ESERCIZIO 1: Punto 2
1
3
45
6
72
41
5
44
c*1i = min {c1i : i∈V–T} = c12 = c13 = c16 = c17 = 2
T = {1, 5, 3, 2, 7, 4};
V–T = {6}
c*5i = min {c5i : i∈V–T} = c54 = c56 = 2
2
22
2
3
3
3
c*3i = min {c3i : i∈V–T} = c37 = 1
3
3
11
2
3
3
21
c*2i = min {c2i : i∈V–T} = c21 = 2
17
2
c*7i = min {c7i : i∈V–T} = c74 = 1
1
4
1
ESERCIZIO 1: Punto 2
A questo punto, l’arco che dista meno dal nodo 6 è l’arco (4,6).
T = {1, 5, 3, 2, 7, 4, 6}; V–T = ∅
Minimo albero ricoprente = {15, 53, 32, 27, 74, 46}
1
3
45
6
72
41
5
44
2
22
2
3
3
3
3
3
11
2
3
3
21
17
2
1
4
1
6
ESERCIZIO 1: Punto 2
Raddoppiamo gli archi dell’albero ricoprente
1
3
45
6
72
1
5
2
3
1
2
1
17
1
4
1
6
Il percorso euleriano sul multigrafo ottenuto è dato da:
PE = {1, 5, 3, 2, 7, 4, 6, 4, 7, 2, 3, 5, 1}
Ricaviamo il
cammino hamiltoniano
PH = {1, 5, 3, 2, 7, 4, 6, 1}
C(PH) = 9 = UPPER BOUND
2
ESERCIZIO 1: Punto 2
La seguente matrice è una matrice delle distanze di un’istanza del
problema del Commesso Viaggiatore.
-2411127
2-313326
43-32415
113-3344
1323-123
13431-22
221422-1
7654321
Calcolare
4. Il valore di una soluzione euristica calcolata con l’algoritmo di Christofides.
ESERCIZIO 1: Punto 3
Ereditiamo il minimo albero ricoprente dal punto precedente
1
3
45
6
72
5
2
3
1
2
1
17
1
4
1
6
Individuiamo i nodi di grado dispari:
Vd = {1, 6}
Sottografo
completo indotto
da Vd.
ESERCIZIO 1: Punto 3
2
Matching perfetto
sul sottografo
indotto: M = {16}
Consideriamoil grafo euleriano dato da M ∪ T
1
3
45
6
72
5
2
3
1
2
1
17
1
4
1
6
ESERCIZIO 1: Punto 3
2
Il percorso euleriano sul multigrafo ottenuto è dato da:
PE = {1, 5, 3, 2, 7, 4, 6, 1}
In questo caso PH = PE.
C(PH) = 9 = UPPER BOUND
ESERCIZIO 2
La tabella che segue contiene una lista di progetti che possono
essere attivati nel prossimo anno. Il budget totale a disposizione
è 170mila euro.
Ogni progetto ha un costo ai e un profitto (atteso) pi. Dopo aver formulato il problema di selezionare un sottoinsieme di progetti in
modo da massimizzare il profitto finale e rispettare il vincolo di
budget, determinare un upper bound per il profitto massimo
ottenibile.
240428216012017012596Profitto
2224414012301216Peso
87654321Progetto
ESERCIZIO 2
Il problema può essere formulato come segue:
Variabili di decisione:
xi = 1 se e solo se il progetto i-esimo è attivato.
z* = max (96x1 + 125x2 + 170x3 + 120x4 + 160x5 + 82x6 + 42x7 + 240x8)
16x1 + 12x2 + 30x3 + 12x4 + 40x5 + 41x6 + 24x7 + 22x8 < 170
x ∈ {0,1}8
ESERCIZIO 2
Consideriamo il rilassamento lineare del problema che
corrisponde ad un Knapsack continuo
z*RL = max (96x1 + 125x2 + 170x3 + 120x4 + 160x5 + 82x6 + 42x7 + 240x8)
16x1 + 12x2 + 30x3 + 12x4 + 40x5 + 41x6 + 24x7 + 22x8 < 170
x > 0
Riordiniamo i progetti in modo tale che
n
n
a
p
a
p
a
p≥≥≥ ...
2
2
1
1
ESERCIZIO 2p1/a1 = 96/16 = 6 ⇒ y4
p2/a2 = 125/12 = 10,41 ⇒ y2
p3/a3 = 170/30 = 5,6 ⇒ y5
p4/a4 = 120/12 = 10 ⇒ y3
p5/a5 = 160/40 = 4 ⇒ y6
p6/a6 = 82/41 = 2 ⇒ y7
p7/a7 = 42/24 = 1,75 ⇒ y8
p8/a8 = 240/22 = 10,9 ⇒ y1
z*RL = max (240y1 + 125y2 + 120y3 + 96y4 + 170y5 + 160y6 + 82y7 + 42y8)
22y1 + 12y2 + 12y3 + 16y4 + 30y5 + 40y6 + 41y7 + 24y8 < 170
y > 0
ESERCIZIO 2
Individuiamo il progetto h per cui ∑=
>h
j
j ba1
y1 = 1 ⇒ 170221
1
1 <=∑=j
a
y1 = y2 = 1 ⇒
y1 = y2 = y3 = 1 ⇒
y1 = y2 = y3 = y4 = 1 ⇒
y1 = y2 = y3 = y4 = y5 =1 ⇒
y1 = y2 = y3 = y4 = y5 = y6 = 1 ⇒
y1 = y2 = y3 = y4 = y5 = y6 = y7 = 1 ⇒ ⇒ h = 7
170342
1
<=∑=j
ja
170463
1
<=∑=j
ja
170624
1
<=∑=j
ja
170925
1
<=∑=j
ja
1701326
1
<=∑=j
ja
1701737
1
>=∑=j
ja
ESERCIZIO 2
Per il progetto h fissiamo la variabile yh:
92,041
38
41
132170
1
1
7 ==−
=
−
=
∑−
=
h
h
j
j
a
ab
y
La restante variabile y8 = 0.
Il valore della funzione obiettivo è pari a z*RL = 986,44 e
corrisponde ad un UPPER BOUND per il valore ottimo z* del
problema iniziale.
ESERCIZIO 3
Siano U, A1, ..., An insiemi finiti, e a1, ..., an � IR+. Sia
ℑ={X ⊆ U : |X ∩ Ak| < ak per ciascun k = 1, ..., n}.
Dire se la coppia (U,ℑ) individua o meno un matroide motivando la risposta.
A1
A2
A3U
X
a1
= 3
a2
= 1
a3
= 1
ESERCIZIO 3
Ricordiamo che la coppia (U,ℑ) è un matroide se valgono le seguenti condizioni:
1. ∅∈ℑ
2. Per ogni Y⊆ X, X∈ℑ ⇒Y∈ℑ.
3. Dati X, Y∈ℑ, con |X|<|Y|, esiste y∈Y tale che X ∪ {y} ∈ℑ.
Banalmente ∅∈ℑ.
Supponiamo che X∈ℑ. Allora |X ∩ Ak| < ak, per ciascun k = 1, ..., n.
Se Y⊆ X, allora |Y|<|X|. Pertanto|Y ∩ Ak| < |X ∩ Ak| < ak.
Possiamo quindi concludere che la coppia è subclusiva.
ESERCIZIO 3
Resta da verificare se la coppia (U,ℑ) soddisfa la proprietà di scambio.
Se pensiamo che tale proprietà sia soddisfatta dobbiamo
dimostrarlo in maniera formale.
Viceversa, se pensiamo che la proprietà di scambio non sia soddisfatta dobbiamo cercare un controesempio in cui essa non
vale.
ESERCIZIO 3
Consideriamo la seguente situazione:
A1
A2
A3U
a1
= 2
a2
= 1
a3
= 1
1
23
4 7
5 6
78
910
11
Siano: Y = {1, 4, 7, 11} e X = {1, 3, 8}. Entrambi gli insiemi
appartengono a ℑ. Infatti:
Y ∩ A1= {1, 4} ⇒|Y ∩ A
1|= 2 < a
1X ∩ A
1= {1, 3} ⇒|X ∩ A
1|= 2 < a
1
Y ∩ A2= {7} ⇒|Y ∩ A
2|= 1 < a
2X ∩ A
2= {8} ⇒|X ∩ A
2|= 1 < a
2
Y ∩ A3= {11} ⇒|Y ∩ A
3|= 1 < a
3X ∩ A
3= {8} ⇒|X ∩ A
3|= 1 < a
3
ESERCIZIO 3
Consideriamo la seguente situazione:
A1
A2
A3U
a1
= 2
a2
= 1
a3
= 1
1
23
4 7
5 6
78
910
11
Tuttavia è immediato osservare che, per ogni y ∈Y\X, l'insieme X ∪
{y} ∉ℑ.
Pertanto la proprietà di scambio non è verificata e la coppia (U,ℑ) non è un matroide.