8.5 L'algoritmo del simplesso su reti¶
Parte 4 · Il simplesso su reti · Capitolo 8 · Capitolo 8: Simplesso su reti · Dispensa, volume 4 (PDF) · Slide · Esercizi: Simplesso su reti · App: Il simplesso su reti, pivot per pivot
Algoritmo: Algoritmo del simplesso su reti
STOP: \(\vet{x}\) è ottima.STOP: il problema è illimitato.-
Le parità nel Passo 2 si risolvono con l'ordine lessicografico degli archi. Il Passo 0 usa la procedura della Proposizione 8.6, il Passo 4 gli aggiornamenti della Proposizione 8.12 e della Proposizione 8.13.
-
L'arresto nel Passo 1 è corretto per il Teorema 8.10, l'arresto nel Passo 3 per la Proposizione 8.14.
-
Ogni struttura incontrata è ammissibile per la Proposizione 8.12. Con bilanci e capacità interi tutti i flussi sono interi (Corollario 8.4), e con costi interi tutti i potenziali sono interi.
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à