4.8 Casi speciali¶
Parte 3 · Flussi · Capitolo 4 · Capitolo 4: Modelli di flusso · Dispensa, volume 3 (PDF) · Esercizi: Modelli di flusso
- Diversi problemi classici sono modelli \(\mathrm{MCF}\) con dati speciali; tutti i limiti inferiori sono zero.
| problema e modello \(\mathrm{MCF}\) | |
|---|---|
| Percorso più breve | \(b_s=1\), \(b_t=-1\), \(b_i=0\) altrimenti; \(u_{ij}=+\infty\), \(c_{ij}\) la lunghezza del arco: l'unità di flusso viaggia da \(s\) a \(t\). |
| Flusso massimo e \(b_i=0\) e \(c_{ij}=0\) per ogni arco, più l'arco \((t,s)\) con \(c_{ts}=-1\) e \(u_{ts}=+\infty\): il flusso su \((t,s)\) è il valore inviato da \(s\) a \(t\). | |
| Trasporti e \(N=P \cup D\) con archi dalle origini \(P\) alle destinazioni \(D\); \(b_i\) la fornitura di \(i \in P\), \(-b_j\) la domanda di \(j \in D\), \(u_{ij}=+\infty\). | |
| Assegnazione e un modello di trasporto con \(|P|=|D|\), \(b_i=1\) per \(i \in P\) e \(b_j=-1\) per \(j \in D\). |
- Nei quattro modelli i saldi e i limiti sono interi, quindi i vertici interi di Teorema 4.15 sono percorsi, flussi interi e assegnazioni.
Percorso più breve, flusso massimo, trasporto e assegnazione sono modelli di flusso a costo minimo con saldi speciali, capacità e costi.
Avanti: 4.9 Un'istanza di traslato