Example of a Minimum Cost Capacitated Flow Problem

Question

I am struggling to find an example with a solution for a Minimum Cost Capacitated Flow problem. My network is defined as a graph $G = (V, E)$, where each edge has a capacity $c(u, v) > 0$, a flow $f(u, v) \ge 0$, and a cost $a(u, v)$. The solution must show a minimum cost using the maximum capacity of the network edges. Wikipedia does not have an example, do you know where I can find an example of this?

Thanks, Felipe

Answer 1

Here is one example. it used Mathematica FindMinimumCostFlow to calculate the answer.

vertices = {"vs" -> "v1", "vs" -> "v2", "v2" -> "v1", "v1" -> "v3", 
   "v1" -> "vt", "v2" -> "v3", "v3" -> "vt"};
edgeCapacity = {10, 8, 5, 2, 7, 10, 4};
edgeCost = {4, 1, 2, 6, 1, 3, 2};
helper = "(capacity=" <> ToString@#[[1]] <> ", cost=" <> 
    ToString@#[[2]] <> ")" &;
g = Graph[vertices, EdgeCapacity -> edgeCapacity, 
  EdgeCost -> edgeCost, 
  EdgeWeight -> Map[helper, Transpose[{edgeCapacity, edgeCost}]], 
  VertexLabels -> "Name", EdgeLabels -> "EdgeWeight", 
  GraphLayout -> "TutteEmbedding"]
\[ScriptCapitalF] = 
  FindMinimumCostFlow[g, "vs", "vt", "OptimumFlowData"];
\[ScriptCapitalF]["CostValue"]
\[ScriptCapitalF]["FlowValue"]
\[ScriptCapitalF]["FlowGraph"]
\[ScriptCapitalF]["FlowMatrix"]