Modello di rete (ricerca operativa)

Modelli di rete (nella ricerca operativa; ingl. Network models) — è una classe di modelli matematici che rappresentano un problema nella forma di un grafo (rete), dove i vertici (nodi) designano oggetti o stati, e gli archi (archi orientati) — le relazioni o i processi tra di essi. Nel contesto dell'ottimizzazione, per rete si intende spesso un grafo orientato, che nell'analisi operativa viene direttamente denominato «rete»; i vertici di tale rete sono chiamati nodi e gli archi sono chiamati archi orientati.

I modelli di rete sono uno strumento potente per l'analisi e l'ottimizzazione di sistemi complessi in settori quali la logistica, le telecomunicazioni, la gestione dei progetti e la finanza. La loro forza risiede nell'elevato livello di astrazione: un nodo può rappresentare una città, un router informatico o una fase di un progetto, mentre un arco può rappresentare una strada, un canale di comunicazione o un'operazione tecnologica.

Definizione e terminologia

La base dei modelli di rete è la teoria dei grafi. I concetti chiave sono:

• Rete di flusso (ingl. flow network): un grafo orientato in cui ogni arco ha una capacità (capacity) e un flusso (flow). Nel grafo sono individuati due vertici speciali: la sorgente (source), da cui il flusso ha origine, e il pozzo (sink), in cui esso confluisce.
• Legge di conservazione del flusso: Per qualsiasi vertice che non sia sorgente o pozzo, il flusso entrante totale deve essere uguale al flusso uscente totale. Questa condizione è l'analogo discreto delle leggi fisiche di conservazione.
• Pianificazione reticolare: Un modello che rappresenta un progetto come un insieme di operazioni interdipendenti (archi) ed eventi (nodi). Tali reti sono grafi orientati aciclici, che riflettono l'ordine di esecuzione delle attività.

Proprietà e teoremi fondamentali

I modelli di rete possiedono una serie di proprietà speciali che consentono l'applicazione di algoritmi ad alta efficienza per la loro risoluzione.

• Interezza delle soluzioni: Molti problemi di ottimizzazione su reti (ad esempio, il flusso massimo o il cammino minimo) godono della proprietà di totale unimodularità della matrice dei vincoli. Grazie a ciò, se i parametri del problema (capacità, lunghezze) sono interi, la soluzione ottimale trovata con i metodi della programmazione lineare sarà anch'essa intera, senza necessità di introdurre vincoli aggiuntivi.
• Teorema del flusso massimo e del taglio minimo: Risultato centrale della teoria dei flussi. Afferma che il valore massimo del flusso dalla sorgente al pozzo è uguale alla capacità minima tra tutti i tagli che separano la sorgente dal pozzo. Questo teorema stabilisce il criterio di ottimalità per il flusso e costituisce la base di molti algoritmi.
• Principio di ottimalità per i cammini minimi: Se il percorso dal punto A al punto C è il cammino minimo, allora qualsiasi sua sottoparte (ad esempio, dal punto intermedio B a C) è anch'essa il cammino minimo tra i vertici corrispondenti. Questa proprietà, alla base della programmazione dinamica, garantisce la correttezza di algoritmi come l'algoritmo di Dijkstra.
• Proprietà dell'albero ricoprente minimo (ARM):
• Proprietà del taglio: Per qualsiasi taglio del grafo, l'arco di peso minimo che attraversa il taglio appartiene ad almeno un ARM.
• Proprietà del ciclo: In qualsiasi ciclo del grafo, l'arco di peso massimo non appartiene ad alcun ARM.

Su queste proprietà si basa la correttezza degli algoritmi «greedy» di Prim e di Kruskal.

Principali problemi di ottimizzazione su reti

• Problema del cammino minimo: Trovare il percorso di lunghezza (peso) totale minima tra due nodi specificati. Viene risolto con l'algoritmo di Dijkstra (per pesi non negativi) o con l'algoritmo di Bellman-Ford (per pesi arbitrari).
• Problema del flusso massimo: Determinare il flusso massimo possibile dalla sorgente al pozzo date le capacità degli archi. Il metodo classico di risoluzione è l'algoritmo di Ford-Fulkerson.
• Problema dell'albero ricoprente minimo: Trovare il sottografo che connette tutti i vertici della rete e ha il costo totale degli archi minimo.
• Metodo del cammino critico (CPM): Nei modelli di pianificazione reticolare, determinare la sequenza più lunga di attività che stabilisce il tempo minimo possibile per il completamento dell'intero progetto. Le attività su questo percorso hanno un margine di tempo nullo.

Esempi

• Cammino minimo: Ricerca del percorso ottimale da parte di un sistema di navigazione tra due punti su una mappa urbana, dove le città sono nodi e le strade sono archi con pesi uguali alla lunghezza o al tempo di percorrenza.
• Flusso massimo: Determinazione della capacità massima di una rete di condotte, dove le stazioni di pompaggio sono nodi e le tubazioni sono archi con capacità limitata.
• Albero ricoprente minimo: Progettazione di una rete di comunicazione (ad esempio, posa di cavo in fibra ottica) per collegare diverse città con la lunghezza totale minima del cavo.
• Cammino critico: In un progetto di costruzione di una casa, dove le attività (gettata delle fondamenta, costruzione delle pareti, montaggio del tetto) hanno una durata definita e dipendenze tecnologiche, il cammino critico determina il tempo minimo di completamento della costruzione. Qualsiasi ritardo in un'attività su questo percorso provocherà un ritardo dell'intero progetto.

Vedi anche

• Ricerca operativa
• Teoria dei grafi
• Problema di trasporto
• Metodo del cammino critico
• PERT