12
Problemi strutturati
12.1 IL PROBLEMA DEL CAMMINO MINIMO: L’ALGORITMO DI DIJKSTRA Esercizio 12.1.1 Dato il grafo di Figura 12.1.1, trovare il peso dei cammini minimi dal nodo 1 a tutti gli altri nodi del grafo (il peso associato a ciascun arco
`e mostrato in figura in prossimit`a dell’arco stesso).
3 6 2 5
4
1 7
5
1
7 2 3 1
2
4 5
Fig. 12.1.1 Esercizio 12.1.1
Soluzione.
I passi dell’algoritmo sono i seguenti (l’evoluzione di T `e omessa essendo sem- plicemente T = V − S):
• Iterazione 0.
(a) Inizializzazione.
S = {1}. π(1) = 0. π(2) = 7. π(3) = 1. π(4) = +∞. π(5) = +∞.
π(6) = +∞.
• Iterazione 1.
(b) j = 3. S = {1, 3}.
(c) N+(j) ∩ T = {2, 5, 6}. π(2) = min(7, 1 + 5) = 6.
π(5) = min(+∞, 1 + 2) = 3. π(6) = min(+∞, 1 + 7) = 8.
• Iterazione 2.
(b) j = 5. S = {1, 3, 5}.
(c) N+(j) ∩ T = {2, 4}. π(2) = min(6, 2 + 3) = 5. π(4) = min(+∞, 3 + 5) = 8.
• Iterazione 3.
(b) j = 2. S = {1, 2, 3, 5}.
(c) N+(j) ∩ T = {4, 6}. π(4) = min(8, 5 + 4) = 8. π(6) = min(8, 5 + 1) = 6.
• Iterazione 4.
(b) j = 6. S = {1, 2, 3, 5, 6}.
(c) N+(j) ∩ T = ∅.
• Iterazione 5.
(b) j = 4. S = {1, 2, 3, 4, 5, 6}. STOP.
I pesi dei cammini minimi saranno quindi: π∗(1) = 0. π∗(2) = 5. π∗(3) = 1.
π∗(4) = 8. π∗(5) = 3. π∗(6) = 6.
Una comoda rappresentazione delle varie iterazioni dell’algoritmo `e data dalla seguente forma tabellare:
iter. 2 3 4 5 6
0 7 1 +∞ +∞ +∞
1 6 +∞ 3 8
2 5 8 8
3 8 6
4 8
ove le righe rappresentano iterazioni mentre le colonne sono in corrispondenza ai nodi. L’elemento i, j rappresenta il valore della variabile π(j) all’iterazione i- esima. L’elemento selezionato all’iterazione i-esima `e rappresentato in grassetto (talvolta pu`o essere circolettato) e, nelle iterazioni successive, il valore della vari- abile corrispondente non viene pi`u riportato. La riga corrispondente all’ultima iterazione `e omessa.
Esempio 12.1.2 Dato il grafo di figura 12.1.2, determinare per quali valori di x esiste un cammino minimo finito dal nodo 1 al nodo 6.
-8
7
2 4
1 4
6 3
x2
5 -4x
6 x
4
Fig. 12.1.2 Esercizio 12.1.2
Soluzione.
Affinch´e esista una soluzione finita del problema, non devono esistere nel grafo cicli orientati di peso negativo. Esistono nel grafo dato due cicli orientati: C1 = {2, (2, 6), 6, (6, 4), 4, (4, 2)} e C2 = {3, (3, 6), 6, (6, 5), 5, (5, 3)}. Il primo ciclo ha peso non-negativo se e solo se x + 7 − 8 ≥ 0, e cio`e x ≥ 1. Il secondo ciclo ha peso negativo se e solo se x2− 4x + 4 ≥ 0, che `e sempre verificata. Quindi, si avr`a un cammino minimo finito da 1 a 6 se e solo se x ≥ 1.
Esercizio 12.1.3 Dato il grafo di Figura 12.1.3, determinare per quali valori di x non esista un cammino minimo dal nodo s al nodo t che passi per il nodo 4.
s
1
2
3
4
5
6
7
8
3 1
4
1 2
3
1 1 1
8 5
3 2
1
2
2
x
7
3 6
3 t
Fig. 12.1.3 Esercizio 12.1.3
Soluzione.
Osservare innanzitutto che ogni cammino da s a t passante per il nodo 4, passer`a necessariamente anche per l’arco (4, 8). Affinch´e il cammino minimo fino a t non passi per l’arco (4, 8) deve esistere un cammino minimo dal nodo s al nodo 8 di peso inferiore al peso di un cammino minimo da s a 4 aumentato del peso dell’arco (4, 8). Quindi bisogna innanzi tutto calcolare il peso di un cammino minimo fino al nodo 8 che non utilizzi l’arco (4, 8) (ad esempio considerando x molto grande, o rimuovendo l’arco) e calcolare il peso di un cammino minimo fino al nodo 4. A tal scopo si pu`o utilmente sfruttare l’algoritmo di Dijkstra, con la semplificazione che una volta ottenuti i pesi cercati (e cio`e π∗(4) e π∗(8)) possiamo concludere le iterazioni dell’algoritmo.
I passi dell’algoritmo sono i seguenti (l’evoluzione di T `e omessa essendo sem- plicemente T = V − S):
• Iterazione 0.
(a) Inizializzazione.
S = {1}. π(s) = 0. π(1) = 4. π(2) = 1. π(3) = 3. π(4) = +∞.
π(5) = +∞. π(6) = +∞. π(7) = +∞. π(8) = +∞. π(t) = +∞.
• Iterazione 1.
(b) j = 2. S = {s, 2}.
(c) N+(j)∩ T = {1, 3, 6, 7}. π(1) = min(4, 1+ 2) = 3. π(3) = min(3, 1+ 1) = 2.
π(6) = min(+∞, 1 + 8) = 9. π(7) = min(+∞, 1 + 5) = 6.
• Iterazione 2.
(b) j = 3. S = {s, 2, 3}.
(c) N+(j) ∩ T = {6, 7}. π(6) = min(9, 2 + 3) = 5. π(7) = min(6, 2 + 2) = 4.
• Iterazione 3.
(b) j = 1. S = {s, 1, 2, 3}.
(c) N+(j) ∩ T = {4, 5}. π(4) = min(+∞, 3 + 3) = 6. π(5) = min(+∞, 3 + 1) = 4.
• Iterazione 4.
(b) j = 5. S = {s, 1, 2, 3, 5}.
(c) N+(j) ∩ T = {4, 6, 8}. π(4) = min(6, 4 + 1) = 5. π(6) = min(5, 4 + 2) = 5.
π(8) = min(+∞, 4 + 7) = 11.
• Iterazione 5.
(b) j = 7. S = {s, 1, 2, 3, 5, 7}.
(c) N+(j) ∩ T = {6, 8}. π(6) = min(5, 4 + 2) = 5. π(8) = min(11, 4 + 6) = 10.
• Iterazione 6.
(b) j = 4. S = {s, 1, 2, 3, 4, 5, 7}.
(c) N+(j) ∩ T = ∅.
• Iterazione 7.
(b) j = 6. S = {s, 1, 2, 3, 4, 5, 6, 7}.
(c) N+(j) ∩ T = {8}. π(8) = min(10, 5 + 3) = 8.
• Iterazione 8.
(b) j = 8. S = {s, 1, 2, 3, 4, 5, 6, 7, 8}.
(c) N+(j) ∩ T = {t}. π(t) = min(+∞, 8 + 3) = 11. STOP.
Notare che al passo (c) dell’iterazione 6, l’intersezione fra l’intorno positivo del nodo 4 e l’insieme T `e considerato vuota, concordemente all’assunzione che l’arco (4, 8) sia stato rimosso.
Le iterazioni dell’algoritmo possono essere rappresentate in forma tabellare:
iter. 1 2 3 4 5 6 7 8 t
0 4 1 3 +∞ +∞ +∞ +∞ +∞ +∞
1 3 2 +∞ +∞ 9 6 +∞ +∞
2 3 +∞ +∞ 5 4 +∞ +∞
3 6 4 5 4 +∞ +∞
4 5 5 4 11 +∞
5 5 5 10 +∞
6 5 10 +∞
7 8 +∞
8 11
I pesi dei cammini minimi cercati saranno quindi: π∗(4) = 5. π∗(8) = 8. Quindi, affinch´e l’arco (4, 8) non sia contenuto in nessun cammino minimo, dovr`a essere π∗(4) + x > π∗(8), ovvero x > 3.
Sommario
1 Introduzione 1
2 La Programmazione Matematica 3
2.1 Problemi di Programmazione Matematica 3
3 Modelli di Programmazione Lineare 5
3.1 Modelli di allocazione ottima di risorse 5
3.2 Modelli di miscelazione 14
3.3 Modelli di trasporto 19
4 Il linguaggio di modellizzazione algebrica AMPL 25 4.1 Esercizi di formulazioni mediante il linguaggioAMPL 25
5 La Programmazione Lineare 31
5.1 Interpretazione geometrica di un Problema di Programmazione
Lineare 31
6 Teoria della Programmazione Lineare 43
6.1 Vertici di un poliedro 43
7 Il metodo del simplesso 45
7.1 La forma standard 45
7.2 Vertici e Soluzioni di Base 46
7.3 Il criterio di ottimalit`a e il criterio di illimitatezza 49
7.4 Il metodo del simplesso 54
8 La dualit`a nella Programmazione Lineare 73
8.1 Teoria della dualit`a 73
9 Modelli di Programmazione Lineare Intera 85 9.1 Modelli di Programmazione Lineare Intera 85 10 Teoria della Programmazione Lineare Intera 95
11 Soluzione di problemi di Programmazione Lineare Intera 97 11.1 Esercizi sulla soluzione di problemi di Programmazione
Lineare Intera 97
12 Problemi strutturati 109
12.1 Il problema del cammino minimo: l’algoritmo di Dijkstra 109
