Modelli di flusso su reti¶
Parte 3 · Flussi · Capitolo 4 · Dispensa, volume 3 (PDF) · Esercizi: Modelli di flusso
-
4.1 Reti e flussi
-
4.2 Il modello di flusso di costo minimo
-
4.3 Feasibility conditions
-
4.4 Rimozione dei limiti inferiori
-
4.5 Istanze non bilanciate
-
4.6 Totale unimodularità e integralità
-
4.7 Il modello duale e i costi ridotti
-
4.8 Casi speciali
-
4.9 Un'istanza di traslato
Il certificato di ottimalità
Prerequisiti
-
Da questo modulo, Capitolo 1 «Grafi»: grafi orientati, matrice di incidenza nodo-arco, alberi di copertura e rango della matrice di incidenza.
-
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità» e Capitolo 15 «La geometria di Programmazione lineare»: duale di un LP, dualità debole e forte, vertici di un poliedro.
-
Determinanti: lo sviluppo di Laplace lungo una colonna e la regola di Cramer.
Obiettivi
Alla fine di questo capitolo sarai in grado di:
-
descrivono una rete con saldi, limiti inferiori, capacità e costi e scrivono il modello di flusso di costo minimo, anche in forma matriciale con la matrice di incidenza;
-
verificare le condizioni necessarie per l'esistenza di un flusso ammissibile e costruire controesempi;
-
rimuove i limiti inferiori mediante una sostituzione e bilancia un'istanza con un nodo fittizio;
-
dimostrare che la matrice di incidenza è totalmente unimodulare e dedurre che il modello ha ottimo intero soluzioni quando i dati sono interi;
-
scrivere il duale con i potenziali \(\pi_i\), calcolare i costi ridotti e certificare l'ottimalità di un flusso;
-
riconosce il percorso più breve, il flusso massimo, i problemi di trasporto e di assegnazione come costo minimo modelli di flusso.
Avanti: 4.1 Reti e flussi
Esercizi su questo capitolo: Modelli di flusso