Formulazione del problema del flusso a costo minimo

$min \space \sum_{(i,j) \in A} c_{ij}x_{ij} \\\sum_{j\in FS(i)} x_{ij} - \sum_{k \in BS(i)} x_{ki} = b_i \space\space\space\space i = 1,..,n \\ x_{ij} \geq 0 \space\space\space\space\forall (i,j) \in A$

$x_{ij} =$ quantità di flusso che transita sull’arco $(i,j)$

$c_{ij} =$ costo di trasporto di una unità di flusso sull’arco $(i,j)$

$b_i =$ valore intero associato al nodo $i$ (ne definisce il ruolo nel problema)

• $b_i >0$: nodo di offerta
• $b_i <0$: nodo di domanda
• $b_i = 0$: nodo di passaggio

Osservazioni

1. la matrice $A$ è la matrice di incidenza nodo-arco con dimensione $n \times m$ ogni colonna $\underline{a}{ij}$ è associata all’arco $(i,j)$, ed in particolare abbiamo che $\underline{a}{ij} = \underline{e}_i-\underline{e}_j$ ($\underline{e}_i$ vettore colonna con tutti $0$ eccetto un $1$ nella posizione $i$-esima)
2. il rango di questa matrice è $r(A)=n-1$

Problema del trasporto

• $m$ fornitori producono $o_1,..,o_m$ quantità di un certo prodotto
• $n$ clienti richiedono $d_1,..,d_n$ quantità di prodotto
• il prodotto può essere trasportato da ogni fornitore ad ogni cliente
• il grafo sottostante è un grafo bipartito dove i nodi origine (fornitori) hanno solo archi uscenti ed i nodi destinazione (clienti) hanno solo archi entranti
• ad ogni arco $(i,j)$ è associato un costo $c_{ij}$ positivo

Obiettivo

Determinare la quantità di merce da trasportare su ogni arco $(i,j)$ (fornitore-cliente) affinché ogni fornitore $i$ invii la merce $i_i$ prodotta, ogni cliente $j$ riceva la quantità $d_j$ richiesta ed il costo complessivo di trasporto sia minimizzato