Vai al contenuto

8.5 L'algoritmo del 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 ad albero ottima, oppure un ciclo che dimostra che il problema è illimitato
1Passo 0 (inizializzazione). Calcolare la soluzione ad albero \(\vet{x}\) dalle foglie,
2 e i potenziali \(\vet{\pi}\) dalla radice \(n\), con \(\pi_n=0\).
3Passo 1 (test di ottimalità). Calcolare 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}\) è ottima.
5Passo 2 (arco entrante). Scegliere l'arco ammissibile per l'ingresso \(e\) con il massimo \(|\bar{c}_{ij}|\).
6 Orientare il suo ciclo \(C\) come \(e\) se \(e \in L\), e contro \(e\) se \(e \in U\).
7Passo 3 (test dei rapporti). Calcolare \(\theta\), la minima capacità residua lungo \(C\).
8 Se \(\theta=+\infty\), STOP: il problema è illimitato.
9 Altrimenti l'arco uscente \(f\) è l'ultimo arco bloccante lungo \(C\) a partire dall'apice.
10Passo 4 (aggiornamento). Inviare \(\theta\) unità lungo \(C\), e porre \(T:=T \cup \{e\} \setminus \{f\}\).
11 L'arco \(f\) va in \(U\) o in \(L\).
12 Aggiornare i potenziali del sottoalbero staccato da \(f\), e andare al Passo 1.

Proposizione 8.15: terminazione senza pivot degeneri

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

Dimostrazione

Una struttura ad albero determina la sua soluzione ad albero, quindi il suo costo. Per la Proposizione 8.12 ogni pivot con \(\theta>0\) riduce il costo di \(\theta|\bar{c}_{kl}|>0\), quindi nessuna struttura ad albero si ripete. Le strutture ad albero sono in numero finito: al più \(\binom{m}{n-1}\) alberi, ciascuno con al più \(2^{m-n+1}\) stati dei limiti. □

8.5.1 L'algebra del pivot

  • Nel linguaggio del Capitolo 11 «Algoritmo del 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 con il cammino nell'albero da \(k\) a \(l\): per il Lemma «colonne di un ciclo» del Capitolo 1, \(d_a=+1\) sugli archi del cammino percorsi dalla coda alla testa, \(d_a=-1\) sugli altri, e \(d_a=0\) fuori dal cammino. Aumentare \(x_e\) di \(t\) cambia le variabili di base di \(-t\,\vet{d}\): è il flusso inviato lungo il ciclo fondamentale.

  • Il metodo dei potenziali per il problema di trasporto del Capitolo 7 «Trasporto e assegnamento» è l'algoritmo del simplesso su reti sul grafo bipartito delle origini e delle destinazioni: le celle di base formano un albero ricoprente, e i potenziali e i costi ridotti sono quelli di questo capitolo.

L'algoritmo del simplesso su reti passa da un albero all'altro: potenziali dalla radice, costi ridotti, arco entrante, ciclo, passo, arco uscente. Senza pivot degeneri il costo diminuisce a ogni pivot, e l'algoritmo si ferma.


Avanti: 8.6 Un esempio senza capacità