L’ottimizzazione su reti è la parte della ricerca operativa che modella decisioni su grafi: percorsi, flussi, capacità, costi, tempi, precedenze e colli di bottiglia. È usata per rappresentare reti logistiche, infrastrutture di trasporto, reti di telecomunicazioni, sistemi produttivi, catene di fornitura, progetti con attività dipendenti e problemi di allocazione.
La ragione della sua importanza è duplice. Da un lato molti problemi reali sono naturalmente reticolari: nodi, archi e connessioni esistono già nel sistema fisico o organizzativo. Dall’altro lato, molti modelli di rete hanno una struttura matematica speciale che consente algoritmi più rapidi, soluzioni intere senza imporre esplicitamente l’integrità e interpretazioni operative più chiare rispetto a una programmazione lineare generica.
Grafo, nodi e archi
Una rete orientata si rappresenta come:
dove V è l’insieme dei nodi e A è l’insieme degli archi orientati. Un arco (i,j) può descrivere una strada, un collegamento dati, una tratta ferroviaria, una tubazione, una relazione di precedenza o una possibilità di assegnazione.
Su ogni arco possono essere definiti parametri diversi:
| Simbolo | Significato | Esempio operativo |
|---|---|---|
| c_{ij} | costo unitario | euro per unità spedita, penalità, distanza |
| t_{ij} | tempo | durata di attraversamento o lavorazione |
| u_{ij} | capacità superiore | portata massima, banda, risorsa disponibile |
| \ell_{ij} | capacità inferiore | flusso minimo, obbligo contrattuale |
| x_{ij} | variabile di flusso | quantità inviata sull’arco |
Il valore di una rete non sta solo nella forma del grafo, ma nel significato attribuito a questi parametri. Lo stesso grafo può produrre problemi diversi se gli archi rappresentano distanze, tempi, costi economici o rischi.
Modello generale di flusso
Una formulazione molto comune assegna a ogni arco una variabile x_{ij} e impone vincoli di capacità:
Nei nodi vale un bilancio. Indicando con b_k l’offerta netta del nodo k, si può scrivere:
Se b_k\gt0, il nodo immette flusso nella rete; se b_k\lt0, assorbe flusso; se b_k=0, è un nodo di transito e conserva ciò che riceve. L’obiettivo tipico di costo minimo è:
Questa forma unifica problemi apparentemente diversi: trasporti, assegnamento, distribuzione, instradamento, capacità produttiva e flussi a costo minimo.
Conservazione e capacità
Il vincolo di conservazione è la condizione che distingue un modello di rete da una semplice scelta di archi. In un nodo intermedio non si può creare flusso né farlo sparire:
I vincoli di capacità, invece, limitano localmente ciò che può attraversare un arco:
In logistica la capacità può essere il numero massimo di pallet, mezzi o tonnellate; in telecomunicazioni può essere banda; in produzione può essere tempo macchina; in energia può essere potenza trasferibile. Il modello resta formalmente simile, ma l’interpretazione delle unità e dei colli di bottiglia cambia.
Problemi classici
I problemi più ricorrenti sono:
| Problema | Domanda modellistica | Struttura tipica |
|---|---|---|
| Cammino minimo | Qual è il percorso a costo o tempo minimo? | etichette di distanza e rilassamento degli archi |
| Flusso massimo | Qual è la massima quantità trasferibile da sorgente a pozzo? | capacità, conservazione, tagli |
| flusso a costo minimo | Come inviare quantità date al costo minimo rispettando capacità? | bilanci ai nodi e costi sugli archi |
| Problema dei trasporti | Quanto spedire da origini a destinazioni? | grafo bipartito offerta-domanda |
| Problema di assegnamento | Come associare risorse e compiti uno a uno? | caso particolare dei trasporti |
| PERT/CPM | Quali attività determinano la durata minima di un progetto? | rete di precedenze e cammino critico |
La stessa terminologia “rete” non implica sempre flusso fisico. In PERT/CPM gli archi o i nodi descrivono attività e precedenze; nel cammino minimo si cerca un percorso; nel flusso massimo si distribuisce quantità su più percorsi contemporaneamente.
Cammini minimi
Nel cammino minimo si cerca la sequenza di archi con costo totale minimo da una sorgente s a una destinazione, oppure da s a tutti gli altri nodi. Una ricorrenza di ottimalità è:
Il concetto operativo è il rilassamento: se il passaggio da i a j riduce il costo noto per arrivare a j, l’etichetta viene aggiornata. Con costi non negativi si usa spesso Dijkstra; con costi anche negativi, ma senza cicli negativi, si usa Bellman-Ford; su grafi aciclici basta un ordinamento topologico.
Il modello è adatto quando si deve scegliere un solo percorso ottimo. Non va confuso con un problema di flusso, dove più percorsi possono essere usati simultaneamente e le capacità condivise sono parte del problema.
Flussi, tagli e reti residue
Nel flusso massimo si cerca la massima quantità inviabile da una sorgente s a un pozzo t. Il valore del flusso può essere scritto come:
Ogni flusso ammissibile è limitato da qualunque taglio che separi s da t. Il teorema max-flow min-cut afferma che il valore massimo del flusso coincide con la capacità minima di un taglio:
Gli algoritmi di incremento lavorano sulla rete residua. Se sull’arco (i,j) c’è flusso x_{ij} e capacità u_{ij}, la capacità residua in avanti è:
mentre l’arco inverso ha capacità residua:
Gli archi inversi permettono di correggere decisioni precedenti. Quando nella rete residua non esiste più un cammino da s a t, il flusso corrente è massimo e i nodi raggiungibili dalla sorgente individuano un taglio minimo.
Flusso a costo minimo
Il flusso a costo minimo combina costi, capacità e bilanci ai nodi. Una forma compatta è:
È il modello naturale quando non basta massimizzare una quantità, ma bisogna scegliere come distribuirla al costo minimo. Il problema dei trasporti è un caso speciale in cui la rete è bipartita: origini da un lato, destinazioni dall’altro, archi di spedizione tra i due insiemi.
Quando i dati sono interi e la matrice di incidenza della rete mantiene la struttura classica, le soluzioni estreme risultano intere. Questo spiega perché molti problemi di rete possono produrre decisioni discrete senza passare subito a un modello di programmazione intera. Se però compaiono costi fissi, vincoli logici, lotti minimi o attivazione di archi, l’integrità va modellata esplicitamente.
Algoritmi e complessità
La scelta dell’algoritmo dipende dalla struttura:
| Struttura | Metodo tipico | Nota |
|---|---|---|
| cammini con costi non negativi | Dijkstra | rapido e robusto su reti sparse |
| cammini con costi negativi | Bellman-Ford | rileva cicli negativi raggiungibili |
| flusso massimo | Ford-Fulkerson, Edmonds-Karp, Dinic | usa cammini aumentanti e rete residua |
| flusso a costo minimo | simplesso su reti, successive shortest path, cycle canceling | sfrutta conservazione e costi ridotti |
| reti di progetto | passaggio in avanti e all’indietro | calcola slack e cammino critico |
Il vantaggio dei metodi di rete è che sfruttano la topologia del problema. Usare un solutore lineare generale può essere corretto, ma spesso perde informazione strutturale utile: tagli, nodi critici, archi saturi, cammini alternativi e risorse residue sono parte della diagnosi operativa.
Dualità e interpretazione economica
Molti problemi di rete hanno una lettura duale molto concreta. Nel flusso massimo il duale assume la forma del taglio minimo; nel problema dei trasporti i potenziali associati a origini e destinazioni sono variabili duali; nei cammini minimi le etichette di distanza possono essere lette come potenziali.
Questa interpretazione collega l’ottimizzazione su reti ai prezzi ombra e alla dualità lineare. Un arco saturo può indicare una risorsa scarsa; un vincolo non attivo può avere valore marginale nullo; un taglio minimo mostra dove un aumento di capacità può migliorare davvero la prestazione complessiva.
La parte economicamente utile non è solo il valore ottimo. In un modello ben costruito si leggono anche archi saturi, flussi nulli, nodi sbilanciati, capacità residue, cammini critici e sensitività dei costi.
Modellazione pratica
Costruire una rete richiede alcune decisioni preliminari:
- scegliere cosa rappresentano i nodi: luoghi, attività, stati, risorse o eventi;
- scegliere cosa rappresentano gli archi: movimenti, precedenze, trasformazioni o assegnamenti;
- stabilire unità coerenti per costi, tempi e capacità;
- distinguere costi variabili, costi fissi e penalità;
- decidere se il flusso è continuo, intero, binario o multi-prodotto;
- verificare se esistono archi vietati, capacità minime, priorità o vincoli temporali.
Una rete troppo povera produce soluzioni matematicamente eleganti ma operative deboli. Una rete troppo dettagliata può diventare ingestibile o introdurre dati fittizi. Il buon modello mantiene solo la complessità che cambia davvero la decisione.
Errori comuni
Il primo errore è usare un problema di cammino minimo quando il sistema richiede capacità condivise: scegliere il percorso più breve non dice quanta domanda può attraversare la rete né dove si formeranno i colli di bottiglia.
Il secondo errore è sommare capacità locali senza rispettare la conservazione del flusso. Una rete non trasferisce più di quanto consentano i suoi tagli: aumentare un arco non critico può non produrre alcun miglioramento.
Un terzo errore è confondere costo minimo e flusso massimo. Il primo ottimizza una funzione economica dato un fabbisogno o un bilancio; il secondo massimizza la quantità trasferita. Sono problemi collegati, ma non equivalenti.
Infine, bisogna controllare le ipotesi di linearità e divisibilità. Se bisogna aprire o chiudere tratte, scegliere veicoli interi, attivare impianti o rispettare lotti minimi, il modello di rete continuo va esteso con variabili discrete.
Vedi anche: Programmazione lineare, Cammino minimo, Flusso massimo, Rete residua, Teorema max-flow min-cut, Problema dei trasporti, Problema di assegnamento, PERT/CPM e Formulario di ricerca operativa.