1 se e ∈ A(P)
0 altrimenti. (6.4)
6.3. CAMMINI MINIMI E PROGRAMMAZIONE LINEARE 71 Ogni cammino P da s a t contiene esattamente un arco di δ+(s) e nessun arco di δ−(s), mentre contiene esattamente un arco di δ−(t) e nessun arco di δ+(t); inoltre, per ogni vertice v ∈ V(P)∖{s,t}, P contiene esattamente un arco di δ+(v) e un arco di δ−(v); infine, per ogni v ∈ V ∖ V(P), P non contiene archi n´e di δ+(v) n´e di δ−(v). Allora, affinch´e x ∈ RA sia un vettore corrispondente ad un cammino da s a t, dovranno essere soddisfatti i vincoli
∑
∑e∈Acexe. Consideriamo dunque il seguente programma lineare:
min ∑ per ogni v ∈ V ∖{s,t}. La discussione precedente implica la seguente osservazione.
Osservazione 6.10 Sia P un cammino da s a t in D e sia x il corrispondente vettore definito come in (6.4). Allora x `e una soluzione ammissibile per il programma lineare (6.6)–(6.8) e ha costo c(P).
Il viceversa non `e vero: ci sono soluzioni ammissibili di (6.6)–(6.8) le cui componenti sono diverse da 0 e 1 e che dunque non sono associate ad alcun cammino. Vedremo, tuttavia, che il valore ottimo del programma lineare (6.6)–(6.8) `e esattamente il costo di un cammino minimo da s a t quando il grafo non contiene cicli di costo negativo.
Scriviamo il duale di (6.6)–(6.8). Poich´e c’`e una variabile per ogni arco ed un vincolo per ogni nodo del grafo, il duale avr`a un vincolo per ogni arco e una variabile yv per ogni nodo v ∈ V . Per ogni arco (u,v) ∈ A, la variabile xuv ha coefficiente +1 nel vincolo (6.7) corrispondente al nodo v e coefficiente −1 nel vincolo corrispondente al nodo u, mentre ha coefficiente 0 in tutti gli altri vincoli (6.7). Pertanto, il duale `e il seguente:
max yt− ys (6.9)
s.a yv− yu ≤cuv, (u,v) ∈ A. (6.10) Si noti che i vincoli del problema duale dipendono unicamente da D e da c, ma non dalla scelta dei nodi s e t. Una soluzione ammissibile y del duale `e chiamata un potenziale ammissibile per(D,c).
Teorema 6.11 Sia D =(V,A) un grafo orientato con costi (ce)e∈A sugli archi. Esiste un potenziale ammissibile per (D,c) se e solo se D non contiene alcun ciclo di costo negativo rispetto a c.
Dimostrazione. Per il Lemma di Farkas (Teorema 4.13), esiste un potenziale ammissibile per
Basta dunque dimostrare che D contiene un ciclo di costo negativo se e solo il sistema (6.11)–
(6.13) ha una soluzione.
Supponiamo che D contenga un ciclo di costo negativo C e sia ¯x il vettore definito da
¯ xe=⎧⎪⎪
⎨⎪⎪⎩
1 se e ∈ A(C)
0 altrimenti. (6.14)
Allora ¯x`e una soluzione del sistema (6.11)–(6.13).
Viceversa, supponiamo che il sistema abbia una soluzione ¯x e scegliamo ¯x col numero minimo di componenti positive. Definiamo S ={e ∈ A ∶ ¯xe>0}. Si noti che S ≠ ∅, altrimenti
¯
x non soddisferebbe la disequazione (6.11). Allora esiste un arco (v0, v1) ∈ S. Siccome
∑e∈δ−(v1)x¯e>0, per la (6.12) esiste (v1, v2) ∈ S. Procedendo in questo modo, costruiamo una sequenza di archi (v0, v1),(v1, v2),(v2, v3),... tutti in S. Poich´e il numero di nodi `e finito, prima o poi troveremo un nodo vk gi`a visitato, cio`e chiuderemo un ciclo C tale che A(C) ⊆ S.
Sia ε = min{¯xe∶ e ∈ A(C)}. Se definiamo un vettore x′ ponendo
si verifica facilmente che x′soddisfa le condizioni (6.12)–(6.13). Se c(C) < 0, abbiamo trovato il ciclo che cercavamo; dunque assumiamo c(C) ≥ 0. Allora
∑
dunque x′ soddisfa tutte le condizioni (6.11)–(6.13). Per come `e stato definito ε, x′ ha meno componenti positive di ¯x, il che contraddice la scelta di ¯x. ◻ Il Teorema 6.13, enunciato pi`u sotto, mostra che in assenza di cicli di costo negativo il programma lineare (6.6)–(6.8) permette di determinare il costo di un cammino minimo da s a t. Prima per`o dobbiamo dimostrare un lemma preliminare.
Lemma 6.12 Sia D =(V,A) un grafo orientato con costi (ce)e∈A sugli archi e siano s, t ∈ V due nodi fissati. Sia R l’insieme dei nodi raggiungibili da s e supponiamo che t ∈ R.
Se il programma lineare (6.6)–(6.8) associato a D ha una soluzione ottima, allora anche il programma lineare (6.6)–(6.8) associato al sottografo di D indotto da R ha una soluzione ottima; inoltre, i valori ottimi coincidono.
Dimostrazione. Indichiamo con D′ il sottografo di D indotto da R e con A′ l’insieme degli archi di D′; dunque D′ = (R,A′). Chiamiamo PL(D) e PL(D′) i programmi lineari della
6.3. CAMMINI MINIMI E PROGRAMMAZIONE LINEARE 73 forma (6.6)–(6.8) associati rispettivamente a D e D′. PL(D′) si ottiene da PL(D) ponendo a zero le variabili xe con e ∈ A ∖ A′. Dunque PL(D′) `e pi`u vincolato di PL(D). Allora sar`a sufficiente dimostrare che ogni soluzione ammissibile PL(D) (in particolare la soluzione ottima) `e ammissibile anche per PL(D′).
Sia ¯x ∈ RAuna soluzione ammissibile PL(D). Definiamo
δ+(R) = {(u,v) ∈ A ∶ u ∈ R, v ∉ R}, δ−(R) = {(u,v) ∈ A ∶ u ∉ R, v ∈ R}.
Consideriamo la somma delle equazioni (6.7) di PL(D) corrispondenti ai nodi v ∈ R. Se e `e un arco con entrambi gli estremi in R, la variabile xe appare una volta con coefficiente +1 e una volta con coefficiente −1; dunque queste variabili non appaiono nella somma. Otteniamo allora con u ∈ R e v ∉ R, allora, poich´e u `e raggiungibile da s, anche v lo sarebbe, contraddicendo il fatto che v ∉ R. Allora, per la (6.16), ∑e∈δ−(R)x¯e =0, da cui, poich´e ¯x ≥0, si deduce che
(i) il programma lineare (6.6)–(6.8) `e inammissibile se e solo se non esiste alcun cammino da s a t in D;
(ii) se il programma lineare (6.6)–(6.8) `e illimitato, D ha un ciclo di costo negativo;
(iii) se il programma lineare (6.6)–(6.8) ha soluzione ottima, il valore ottimo `e il costo di un cammino minimo da s a t in D.
Dimostrazione. Mostriamo prima la (i). Supponiamo che (6.6)–(6.8) abbia una soluzione ammissibile ¯x e scegliamo ¯x col numero minimo di componenti positive. Sia S ={e ∈ A ∶ ¯xe>
0}. Supponiamo prima che S contenga un ciclo C e sia ε = min{¯xe∶ e ∈ A(C)}. Il vettore x′ definito come in (6.15) `e ammissibile e ha meno componenti positive di ¯x, una contraddizione.
Dunque S non contiene cicli. Ora, l’equazione (6.12) per v = s garantisce l’esistenza di un arco (s,v1) ∈ S. Se v1 ≠ t, l’equazione (6.12) per v = v1 garantisce l’esistenza di un arco (v1, v2) ∈ S. Poich´e S non contiene cicli, v2 ≠ s. Se v2 ≠t, troviamo (v2, v3) ∈ S e cos`ı via.
Siccome S non contiene cicli, il processo termina solo quando si trova un nodo vk = t: ma allora abbiamo individuato un cammino da s a t in S, e dunque in D. Questo mostra che se (6.6)–(6.8) ha soluzioni ammissibili allora esiste un cammino da s a t in D. Il viceversa segue dall’Osservazione 6.10.
Per dimostrare la (ii), ricordiamo che se (6.6)–(6.8) `e illimitato allora il suo duale (6.9)–
(6.10) `e inammissibile. Questo significa che non ci sono potenziali ammissibili in(D,c). Per il Teorema 6.11, D ha un ciclo di costo negativo.
Dimostriamo ora la (iii). Sia ¯x una soluzione ottima del programma lineare. Per il Lem-ma 6.12, possiamo restringerci al sottografo indotto da R; per non appesantire la notazione,
assumiamo senza perdita di generalit`a che R = V , dunque lavoriamo direttamente sul pro-gramma lineare originale. Poich´e R = V , per ogni v ∈ V il costo di un cammino minimo da s a v`e un valore ℓ(v) < +∞. Definiamo ¯yv =ℓ(v). Poich´e valgono le condizioni di Bellman (6.3),
¯
y`e una soluzione ammissibile del problema duale (6.9)–(6.10). Inoltre, poich´e ¯ys=ℓ(s) = 0, il costo di ¯y`e pari a ℓ(t). Allora, per il Teorema di Dualit`a Debole, il costo di ¯x `e almeno ℓ(t), cio`e il valore ottimo del programma lineare `e almeno ℓ(t). D’altro canto, detto P un cammi-no minimo da s a t (dunque c(P) = ℓ(t)), sappiamo dall’Osservazione 6.10 che il programma lineare ha una soluzione ammissibile di costo ℓ(t). Dunque il valore ottimo del programma
lineare `e proprio ℓ(t). ◻
In particolare, se D non ha cicli di costo negativo, allora il programma lineare (6.6)–(6.8) permette di determinare il costo di un cammino minimo da s a t. Si noti per`o che conoscere il costo di un cammino minimo non significa conoscere anche un cammino minimo. Tuttavia,
`e possibile dimostrare (ma non lo facciamo), che se x∗ `e una soluzione ottima di base, allora tutte le componenti di x∗ sono 0 o 1, dunque x∗ corrisponde ad un cammino minimo P secondo la relazione (6.4). Poich´e il metodo del simplesso restituisce sempre una soluzione ottima di base (quando il problema ammette ottimo), tale metodo pu`o essere usato per trovare un cammino di costo minimo (in assenza di cicli di costo negativo).
Osserviamo anche che nella parte (iii) abbiamo dimsotrato che il vettore (ℓ(v))v∈V costi-tuisce una soluzione ottima del programma lineare duale.
Notiamo infine che l’inversa della proposizione (ii) del Teorema 6.13 non vale: infatti, `e facile costruire un grafo orientato D che abbia cicli di costo negativo ma che sia privo di cammini da s a t; in tal caso, il programma lineare `e inammissibile.