Il simplesso su reti¶

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

Prerequisiti

Da questo modulo, Capitolo 1 «Grafi»: alberi di copertura, foglie, cicli fondamentali e rango della matrice di incidenza nodo-arco.
Da questo modulo, Capitolo 4 «Modelli di flusso su reti»: il modello di flusso di costo minimo, la rimozione dei limiti inferiori, i potenziali, i costi ridotti e l'istanza di trasbordo sulla rete di riferimento.
Dal modulo Programmazione lineare, Capitolo 6 «Algoritmo del simplesso», Capitolo 7 «Condizioni di ottimalità e regole pivot», Capitolo 8 «Fase 0 dell'algoritmo del simplesso» e Capitolo 11 «Simplesso rivisto»: basi, soluzioni di base, costi ridotti, pivot, degenerazione e Fase 0.

Obiettivi

Alla fine di questo capitolo sarai in grado di:

dimostrare che le basi del modello di flusso di costo minimo corrispondono agli alberi ricoprenti e calcolare una soluzione associata a un albero eliminando le foglie;
calcolare i potenziali di un albero ricoprente e i costi ridotti, e verificare l'ottimalità di una soluzione ad albero con archi ai limiti inferiori o superiori;
eseguire un pivot, individuando l'arco entrante, il ciclo orientato, il passo e l'arco uscente, e aggiornare flussi, albero e potenziali;
riconoscere un pivot degenere, verificare la forte ammissibilità di una struttura ad albero e applicare la regola dell'arco uscente che la preserva e impedisce cicli;
trovare una struttura ad albero iniziale con la Fase 0 sulla rete ausiliaria oppure dimostrare che non esistono flussi ammissibili.

Avanti: 8.1 L'algoritmo del simplesso sul modello del flusso di costo minimo

Esercizi su questo capitolo: Simplesso su reti