Google最小成本流解运输流

Question

假设我们有以下数据来解决运输问题：

          A1      A2      A3      Supply
T1        0       600     100     700
T2        500     0       300     800
Demand    500     600     400

我想使用 Google 优化工具最小成本流来解决运输问题。我正在尝试使用以下代码解决该问题：

    private static void SolveMinCostFlow()
    {
        // Define four parallel arrays: sources, destinations, capacities, and unit costs
        // between each pair. For instance, the arc from node 0 to node 1 has a
        // capacity of 15.
        // Problem taken From Taha's 'Introduction to Operations Research',
        // example 6.4-2.

        int numNodes = 5;
        int numArcs = 6;
        int[] startNodes = { 0, 0, 0, 1, 1, 1 };
        int[] endNodes = { 2, 3, 4, 2, 3, 4};
        int[] capacities = { 500, 600, 400, 500, 600, 400 };
        int[] unitCosts = { 0, 600, 100, 500, 0, 300 };

        // Define an array of supplies at each node.

        int[] supplies = { 700, 700, 800, 800, 800 };



        // Instantiate a SimpleMinCostFlow solver.
        MinCostFlow minCostFlow = new MinCostFlow();

        // Add each arc.
        for (int i = 0; i < numArcs; ++i)
        {
            int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                                 capacities[i], unitCosts[i]);
            if (arc != i) throw new Exception("Internal error");
        }

        // Add node supplies.
        for (int i = 0; i < numNodes; ++i)
        {
            minCostFlow.SetNodeSupply(i, supplies[i]);
        }


        //Console.WriteLine("Solving min cost flow with " + numNodes + " nodes, and " +
        //                  numArcs + " arcs, source=" + source + ", sink=" + sink);

        // Find the min cost flow.
        int solveStatus = minCostFlow.Solve();
        if (solveStatus == MinCostFlow.OPTIMAL)
        {
            long optimalCost = minCostFlow.OptimalCost();
            Console.WriteLine("Minimum cost: " + optimalCost);
            Console.WriteLine("");
            Console.WriteLine(" Edge   Flow / Capacity  Cost");
            for (int i = 0; i < numArcs; ++i)
            {
                long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
                Console.WriteLine(minCostFlow.Tail(i) + " -> " +
                                  minCostFlow.Head(i) + "  " +
                                  string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
                                  string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
                                  string.Format("{0,3}", cost));
            }
        }
        else
        {
            Console.WriteLine("Solving the min cost flow problem failed. Solver status: " +
                              solveStatus);
        }
    }

    static void Main(string[] args)
    {
        SolveMinCostFlow();
        Console.Read();
    }

但我得到错误：解决最小成本流问题失败。求解器状态：4 我在这里做错了什么？我想在 SolveMinCostFlow 的开头应该有一些定义参数的东西，但无法弄清楚。

Answer 1

总而言之：平衡的 n x m 运输问题可以使用 or-tools 转换为最大流问题，如下所示：

n + m 个节点供需（需求建模为负供应）
n * m 个具有无限容量和成本的弧 c(i,j)

一些 python 代码来验证这一点：

from ortools.graph import pywrapgraph

#           A1      A2      A3      Supply
# T1        0       600     100     700
# T2        500     0       300     800
# Demand    500     600     400

numNodes = 5
numArcs = 6;
startNodes = [ 0, 0, 0, 1, 1, 1 ]
endNodes = [ 2, 3, 4, 2, 3, 4 ]
capacities =  [9999] * numArcs
unitCosts =  [0, 600, 100, 500, 0, 300 ]
supplies = [700,800,-500,-600,-400]

# Instantiate a SimpleMinCostFlow solver.
min_cost_flow = pywrapgraph.SimpleMinCostFlow()

# Add each arc.
for i in range(0, len(startNodes)):
    min_cost_flow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
                                                capacities[i], unitCosts[i])

# Add node supplies.
for i in range(0, len(supplies)):
    min_cost_flow.SetNodeSupply(i, supplies[i])


# Find the minimum cost flow 
if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
    print('Minimum cost:', min_cost_flow.OptimalCost())
    print('')
    print('  Arc    Flow / Capacity  Cost')
    for i in range(min_cost_flow.NumArcs()):
      cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
      print('%1s -> %1s   %3s  / %3s       %3s' % (
          min_cost_flow.Tail(i),
          min_cost_flow.Head(i),
          min_cost_flow.Flow(i),
          min_cost_flow.Capacity(i),
          cost))
else:
    print('There was an issue with the min cost flow input.')

这会打印：

Minimum cost: 80000

  Arc    Flow / Capacity  Cost
0 -> 2   500  / 9999         0
0 -> 3     0  / 9999         0
0 -> 4   200  / 9999       20000
1 -> 2     0  / 9999         0
1 -> 3   600  / 9999         0
1 -> 4   200  / 9999       60000

更有趣的是一个供给总量>需求总量的非平衡运输问题。 Or-tools 最小成本流算法也可以处理（通过 min_cost_flow.SolveMaxFlowWithMinCost()）。

Answer 2

抱歉，但我认为添加一个接收器并修改主网络的容量会更好。此修改将允许您优化当前数据并满足特定要求。

#           A1      A2      A3      Supply
# T1        0       600     100     700  
# T2        500     0       300     800  
# Demand    500     600     400

numNodes = 6
numArcs = 9;
startNodes = [ 0, 0, 0, 1, 1, 1] + [2,3,4]
endNodes = [ 2, 3, 4, 2, 3, 4 ]+ [5,5,5 ]
capacities =  [0,1000,1000,1000,0,1000]+[500,600,400]
unitCosts =  [0, 600, 100, 500, 0, 300 ]+[0,0,0]
supplies = [700,800,0,0,0,-1500]

因此，通过添加额外的节点（接收器），您可以确保满足您的需求，并且通过更改容量，您可以确保您不会将单元发送到成本单位为 0 的节点（我假设 cero意味着没有任何东西从该特定来源进入该节点）。希望能帮助到你！输出： Costo Minimo: 710000

  Ruta    Flujo / Capacidad  Costo
0 -> 2     0  /   0         0
0 -> 3   600  / 1000       360000
0 -> 4   100  / 1000       10000
1 -> 2   500  / 1000       250000
1 -> 3     0  /   0         0
1 -> 4   300  / 1000       90000
2 -> 5   500  / 500         0
3 -> 5   600  / 600         0
4 -> 5   400  / 400         0


Where costo minimo = minimum cost

Google最小成本流解运输流

Google minimum cost flows to solve transportation flow

c#

algorithm

linear-programming