Problema di Flusso a Costo Minimo: Definizione¶
Il problema viene riformulato su un grafo orientato $G=(V, A)$.
- Nodi ($V$): Rappresentano i centri dell'azienda (magazzini, centri di produzione, centri di distribuzione). Ad ogni nodo $i$ è associato un valore $b_i$: 0 per i magazzini, $> 0$ (quantità prodotta) per i centri di produzione, e $< 0$ (quantità rivenduta, $|b_i|$) per i centri di distribuzione. È necessario che tutto ciò che viene realizzato sia rivenduto ($\sum_i b_i = 0$).
- Archi ($A$): Rappresentano i collegamenti di trasporto. Ogni arco $(i, j)$ ha un costo di trasporto per unità di prodotto ($c_{ij}$) e una capacità massima ($d_{ij}$).
- Flusso ($x_{ij}$): La quantità di prodotto che viaggia lungo l'arco $(i, j)$.
Un flusso ammissibile è un assegnamento di valori $x_{ij}$ che soddisfa due vincoli:
- Vincoli di bilancio: Per ogni nodo $i$, la differenza tra il flusso uscente ($\sum_k x_{ik}$) e quello entrante ($\sum_k x_{ki}$) deve essere pari a $b_i$.
- Vincoli di capacità: $0 \le x_{ij} \le d_{ij}$ per ogni arco.
L'obiettivo è trovare un flusso ammissibile che riduca al minimo il costo di trasporto totale $\sum_{(i, j) \in A} c_{ij}x_{ij}$.
Il problema viene analizzato in due classi: capacità illimitate ($d_{ij} = +\infty$) e capacità limitate ($d_{ij} < +\infty$).
Caso 1: Flusso a Costo Minimo con Capacità Illimitate¶
In questo caso, la risoluzione si basa sul concetto di base.
Basi e Soluzioni di Base¶
Una base ($B$) è un sottoinsieme di $n-1$ archi ($|V|=n$) che formano un albero di supporto del grafo orientato $G$. Gli archi fuori $B$ sono detti archi fuori base.
La soluzione di base associata a $B$ è l’unica soluzione che rispetta i vincoli di bilancio, ottenuta fissando a 0 il flusso lungo gli archi fuori base. Una base $B$ è ammissibile (appartiene a $\mathcal{F}$) se $x(B)_{ij} \ge 0$ per tutti gli archi.
Il problema può essere riformulato come $\min_{B \in \mathcal{F}} c(B)$ (minimizzare il costo tra tutte le basi ammissibili).
Coefficienti di Costo Ridotto e Ottimalità¶
Il coefficiente di costo ridotto ($\bar{c}_{ij}$) è un valore associato a ogni arco fuori base $(i, j)$ che misura la variazione di costo totale che si ottiene incrementando il flusso lungo $(i, j)$ da 0 a 1.
La condizione di ottimalità si ha se $\bar{c}_{ij} \ge 0$ per tutti gli archi fuori base. In questo caso, $x(B)$ è una soluzione ottima.
Ricerca Ottima¶
Se esiste un arco fuori base $(i, j)$ con $\bar{c}_{ij} < 0$, il costo può essere abbassato aumentando il flusso $\Delta$ lungo tale arco.
- Condizione di illimitatezza: Se il ciclo $C^{(i, j)}(B)$ generato dall'aggiunta di $(i, j)$ a $B$ è un ciclo orientato, si può far crescere $\Delta$ a $+\infty$ e il costo totale può decrescere a $-\infty$ (obiettivo illimitato).
- Massimo incremento $\bar{\Delta}$: Altrimenti, $\bar{\Delta}$ è il massimo incremento di flusso possibile mantenendo l'ammissibilità (ossia, $\Delta$ non fa diventare negativo il flusso sugli archi in base in cui il flusso viene ridotto, $x_{hk}(B) - \Delta \ge 0$).
A $\bar{\Delta}$ si ottiene una nuova base ammissibile adiacente $B'$ sostituendo $(i, j)$ con un arco $(h, k) \in C^{(i, j)}(B)$ il cui flusso si è azzerato ($x_{hk}(B) - \bar{\Delta} = 0$).
L'algoritmo di risoluzione è una ricerca locale rule-based che itera tra basi ammissibili adiacenti, garantendo $c(B_{r+1}) \le c(B_r)$.
Problema di I Fase¶
Per avviare la ricerca locale, è necessaria una base ammissibile iniziale $B_0$. Il Problema di I Fase è un problema ausiliario che aggiunge un nodo fittizio $q$ e archi artificiali per garantire una base ammissibile iniziale immediata.
- Se il valore ottimo del problema di I fase è $> 0$, il problema originario non ha soluzioni ammissibili.
- Se il valore ottimo è $= 0$, una base ammissibile può essere estratta dal risultato per il problema originario.
Caso 2: Flusso a Costo Minimo con Capacità Limitate¶
In questo caso, la risoluzione si basa sul concetto di tripla.
Triple e Soluzioni¶
Una tripla ($T$) è una partizione degli archi $A$ in tre sottoinsiemi $(B, N_0, N_1)$:
- $B$: Archi in base (formano un albero di supporto).
- $N_0$: Archi fuori base con flusso fissato a 0.
- $N_1$: Archi fuori base con flusso fissato alla capacità $d_{ij}$.
La soluzione di base associata alla tripla $T$ è l’unica soluzione che rispetta i vincoli di bilancio, data la fissazione dei flussi in $N_0$ e $N_1$. Una tripla $T$ è ammissibile (appartiene a $\mathcal{F}$) se $0 \le x_{ij}(T) \le d_{ij}$ per tutti gli archi.
A differenza del caso illimitato, con capacità limitate il caso di obiettivo illimitato non può verificarsi.
Condizione di Ottimalità¶
La soluzione $x(T)$ è ottima se:
- $\bar{c}_{ij} \ge 0$ per tutti gli archi fuori base a valore nullo ($(i, j) \in N_0$) (non si può abbassare il costo aumentando il flusso).
- $\bar{c}_{ij} \le 0$ per tutti gli archi fuori base a valore pari alla capacità ($(i, j) \in N_1$) (non si può abbassare il costo riducendo il flusso).
L'insieme degli archi che violano l'ottimalità è $\Gamma(T) = {(i, j) \in N_0 : \bar{c}_{ij} < 0} \cup {(i, j) \in N_1 : \bar{c}_{ij} > 0}$.
Ricerca Locale (Pivoting)¶
Per trovare una nuova tripla ammissibile $T'$, si seleziona un arco violante $(i, j) \in \Gamma(T)$ e si calcola l'incremento/decremento massimo di flusso $\bar{\Delta}$:
- Se $(i, j) \in N_0$ e $\bar{c}_{ij} < 0$ (incremento): Il flusso lungo $(i, j)$ viene aumentato. $\bar{\Delta}$ è limitato dagli archi in base il cui flusso si azzera ($x_{hk}(T) - \Delta \ge 0$) o raggiunge la capacità ($x_{hk}(T) + \Delta \le d_{hk}$).
- Se $(i, j) \in N_1$ e $\bar{c}_{ij} > 0$ (decremento): Il flusso lungo $(i, j)$ viene diminuito dalla capacità $d_{ij}$. $\bar{\Delta}$ è limitato dagli archi in base il cui flusso raggiunge la capacità o si azzera.
La nuova tripla $T'$ viene creata scambiando l'arco $(i, j)$ con l'arco $(h, k)$ che ha limitato $\bar{\Delta}$. Questo garantisce che $T'$ sia ammissibile e che $c(T') \le c(T)$.
L'algoritmo di ricerca locale per capacità limitate itera tra triple adiacenti, spesso scegliendo l'arco violante $(i, j)$ che massimizza $|\bar{c}_{hk}|$. Anche in questo caso è possibile definire un problema di I fase per trovare una tripla ammissibile iniziale.
Per comprendere il meccanismo di pivoting nella ricerca locale, si può pensare a un sistema idraulico in equilibrio. Se si ha la possibilità di aprire una valvola (aumentare il flusso lungo un arco fuori base con costo ridotto negativo) o chiudere una valvola (ridurre il flusso lungo un arco a capacità con costo ridotto positivo), l'acqua si ridistribuisce nella rete (lungo il ciclo $C^{(i, j)}(B)$) fino a quando un altro tubo si svuota completamente o raggiunge la sua massima portata, definendo il limite $\bar{\Delta}$ e indicando quale arco deve uscire dalla base.