8.5 L'algoritmo del simplesso di rete¶

Parte 4 · Il simplesso su reti · Capitolo 8 · Capitolo 8: Simplesso su reti · Dispensa, volume 4 (PDF) · Esercizi: Simplesso su reti

Algoritmo: Algoritmo del simplesso su reti

Input: una rete \(G=(N,A)\) con una struttura ad albero ammissibile \((T,L,U)\)

Output: una soluzione ottimale dell'albero, o un ciclo che dimostra che il problema non ha limiti

1Passaggio 0 (inizializzazione). Calcola la soluzione dell'albero \(\vet{x}\) dalle foglie,

2 e i potenziali \(\vet{\pi}\) dalla radice \(n\), con \(\pi_n=0\).

3Passaggio 1 (controllo dell'ottimalità). Calcola i costi ridotti \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\).

4 Se \(\bar{c}_{ij} \ge 0\) su \(L\) e \(\bar{c}_{ij} \le 0\) su \(U\), STOP: \(\vet{x}\) è ottimale.

5Passaggio 2 (inserimento dell'arco). Scegli l'arco idoneo \(e\) con il più grande \(|\bar{c}_{ij}|\).

6 Orienta il suo ciclo \(C\) come \(e\) se \(e \in L\), e contro \(e\) se \(e \in U\).

7Passaggio 3 (test del rapporto). Calcola \(\theta\), la capacità residua minima lungo \(C\).

8 Se \(\theta=+\infty\), STOP: il problema non è limitato.

9 Altrimenti l'arco in uscita \(f\) è l'ultimo arco bloccante lungo \(C\) dall'apice.

10Passaggio 4 (aggiornamento). Invia le unità \(\theta\) lungo \(C\) e imposta \(T:=T \cup \{e\} \setminus \{f\}\).

11 L'arco \(f\) va a \(U\) o a \(L\).

12 Aggiorna i potenziali del sottoalbero tagliato da \(f\) e vai al passo 1.

Nel Passaggio 2 risolviamo le parità scegliendo gli archi in ordine lessicografico. Nel Passaggio 0 calcoliamo la soluzione ad albero con la Proposizione 8.6; nel Passaggio 4 aggiorniamo flussi e albero con la Proposizione 8.12 e i potenziali con la Proposizione 8.13.
L'arresto al Passaggio 1 è corretto per il Teorema 8.10; l'arresto al Passaggio 3 è corretto per la Proposizione 8.14.
Ogni struttura incontrata è ammissibile per la Proposizione 8.12. Se i saldi e le capacità sono interi, tutti i flussi sono interi per il Corollario 8.4; se anche i costi sono interi, lo sono anche i potenziali.

Proposizione 8.15: terminazione senza pivot degenerati

Se ogni pivot dell'algoritmo ha \(\theta>0\), l'algoritmo si ferma dopo un numero finito di pivot.

Dimostrazione

Una struttura ad albero determina univocamente la soluzione ad albero e il relativo costo. Per la Proposizione 8.12, ogni pivot con \(\theta>0\) riduce il costo di \(\theta|\bar{c}_{kl}|>0\); quindi nessuna struttura può ripetersi. Le strutture sono in numero finito: ci sono al più \(\binom{m}{n-1}\) possibili alberi e, per ciascuno, al più \(2^{m-n+1}\) assegnazioni dei limiti. □

8.5.1 L'algebra del pivot¶

Nella terminologia del Capitolo 11 «Simplesso rivisto», i potenziali risolvono il primo sistema \(\vet{\pi}'\mat{M}_T=\vet{c}_T'\).
Il secondo sistema, \(\mat{M}_T\vet{d}=\mat{M}_e\), si risolve usando il cammino nell'albero da \(k\) a \(l\). Per il Lemma «Colonne di un ciclo» del Capitolo 1, poniamo \(d_a=+1\) sugli archi del cammino percorsi dalla coda alla testa, \(d_a=-1\) sugli altri archi del cammino e \(d_a=0\) fuori dal cammino. Se aumentiamo \(x_e\) di \(t\), le variabili di base cambiano di \(-t\,\vet{d}\): è l'aumento di flusso lungo il ciclo fondamentale.
Il metodo dei potenziali per il problema di trasporto del Capitolo 7 «Trasporto e assegnamento» è un algoritmo del simplesso su reti applicato al grafo bipartito di origini e destinazioni: le celle di base formano un albero ricoprente, i potenziali e i costi ridotti sono quelli definiti in questo capitolo.

L'algoritmo del simplesso su reti passa da un albero ricoprente al successivo: calcola i potenziali e i costi ridotti, sceglie l'arco entrante, determina il ciclo e il passo, quindi aggiorna l'albero. Se non si verificano pivot degeneri, il costo diminuisce a ogni iterazione e l'algoritmo termina.

Avanti: 8.6 Un esempio senza capacità