Il flusso massimo è un problema di ottimizzazione su reti: data una rete orientata con capacità sugli archi, si cerca la massima quantità trasferibile da una sorgente s a un pozzo t rispettando vincoli di capacità e conservazione del flusso.
Modello matematico
La rete è un grafo orientato:
dove V è l’insieme dei nodi e A quello degli archi. Per ogni arco (i,j) si definiscono una capacità u_{ij} e una variabile di flusso x_{ij}.
Il vincolo di capacità è:
Per ogni nodo intermedio k\in V\setminus\{s,t\} vale la conservazione:
Il valore del flusso inviato dalla sorgente è:
L’obiettivo è massimizzare v. In una rete standard senza archi entranti in s la seconda somma è nulla, ma la forma generale evita ambiguità nei modelli trasformati.
Lettura dei vincoli
| Elemento | Formula | Significato operativo |
|---|---|---|
| Capacità dell’arco | \displaystyle 0\le x_{ij}\le u_{ij} | Nessun arco può trasportare più della propria capacità. |
| Conservazione | \displaystyle \sum_i x_{ik}=\sum_j x_{kj} | Un nodo intermedio non crea né assorbe flusso. |
| Valore del flusso | \displaystyle v=\sum_j x_{sj}-\sum_i x_{is} | Misura quanto flusso netto parte dalla sorgente. |
| Capacità di un taglio | \displaystyle u(S,T)=\sum_{i\in S,\ j\in T}u_{ij} | Limite superiore imposto dagli archi che separano sorgente e pozzo. |
Un flusso ammissibile è quindi un’assegnazione sugli archi che rispetta simultaneamente limiti locali e bilanci ai nodi. Il problema non è scegliere un singolo cammino, ma coordinare più cammini concorrenti che condividono capacità.
Tagli e ottimalità
Un taglio s-t separa i nodi in due insiemi S e T, con s\in S e t\in T. La capacità del taglio somma le capacità degli archi che vanno da S a T. Ogni flusso ammissibile è limitato superiormente da qualunque taglio:
Il teorema max-flow min-cut afferma che il valore massimo del flusso coincide con la capacità minima di un taglio. Per questo, quando si trova un flusso di valore v e un taglio di capacità v, si ha contemporaneamente una soluzione ammissibile e un certificato di ottimalità.
Algoritmi e rete residua
Gli algoritmi classici aumentano il flusso lungo cammini disponibili nella rete residua. Per un arco (i,j) con capacità u_{ij} e flusso x_{ij}, la capacità residua in avanti è:
e la possibilità di ridurre un flusso già inviato compare come capacità residua all’indietro. L’algoritmo termina quando non esiste più un cammino residuo da s a t: in quel momento gli archi saturi individuano un taglio minimo.
| Metodo | Idea | Uso tipico |
|---|---|---|
| Ford-Fulkerson | aumenta lungo un cammino residuo qualunque | Schema concettuale di base. |
| Edmonds-Karp | sceglie cammini residui minimi in numero di archi | Variante polinomiale semplice da implementare. |
| Dinic | usa livelli e flussi bloccanti | Più efficiente su reti grandi. |
Applicazioni
Il modello di flusso massimo compare in logistica, reti di trasporto, assegnazione di capacità, instradamento dati, scheduling con risorse condivise e segmentazione di immagini. In ambito gestionale è utile perché traduce vincoli fisici o organizzativi in un certificato quantitativo: se il flusso massimo è inferiore alla domanda, il taglio minimo indica il collo di bottiglia strutturale.
Errori comuni
- Confondere il flusso massimo con il cammino minimo: il primo combina più archi e più cammini, il secondo sceglie un percorso ottimo.
- Sommare tutte le capacità uscenti dalla sorgente senza considerare i colli di bottiglia a valle.
- Dimenticare la conservazione nei nodi intermedi, ottenendo flussi che non sono fisicamente realizzabili.
- Interpretare il taglio minimo come un singolo arco: spesso è un insieme di archi che, insieme, separano sorgente e pozzo.
Vedi anche: Teorema max-flow min-cut, Rete residua, Ottimizzazione su reti, Cammino minimo, Formulario di ricerca operativa.