Il problema del flusso di costo minimo (minimum-cost flow problem, abbreviato MCFP) è un problema di decisione e ottimizzazione che consiste nel trovare il modo meno costoso possibile di far passare un certo ammontare di flusso tramite una rete di flusso.
Una rete di flusso è un grafo orientato G = ( V , E ) {\displaystyle G=(V,E)} con un nodo sorgente s ∈ V {\displaystyle s\in V} e un pozzo t ∈ V {\displaystyle t\in V} , in cui ogni arco ( u , v ) ∈ E {\displaystyle (u,v)\in E} ha capacità c ( u , v ) > 0 {\displaystyle c(u,v)>0} , flusso f ( u , v ) ≥ 0 {\displaystyle f(u,v)\geq 0} e costo a ( u , v ) {\displaystyle a(u,v)} (gli algoritmi di MCF supportano archi di costo negativo). Il costo di spedire questo flusso tramite un arco ( u , v ) {\displaystyle (u,v)} è f ( u , v ) ⋅ a ( u , v ) {\displaystyle f(u,v)\cdot a(u,v)} . Il problema fissa un certo ammontare di flusso d {\displaystyle d} che deve essere spedito dalla sorgente al pozzo.
Il problema richiede di minimizzare il costo totale del flusso passante per tutti gli archi.
con i seguenti vincoli:
Una variante del problema è quella di trovare la soluzione al problema del flusso massimo che abbia costo minimo. Può risultare utile per trovare l'accoppiamento massimo di costo minimo.
Un altro problema correlato è quello della circolazione di costo minimo, che può essere sfruttato per risolvere il MCFP.
Inoltre, i seguenti problemi possono essere considerati casi particolari：
Il problema del flusso di costo minimo può essere risolto tramite programmazione lineare. Esistono, inoltre, molti algoritmi combinatoriali.[1] Alcuni di essi sono generalizzazioni degli algoritmi per il flusso massimo, altri utilizzano approcci completamente differenti.
Gli algoritmi più conosciuti: