使用Google Optimization Tools最小费用流求解运输问题报错（状态码4）求助

首先，你遇到的solveStatus=4对应OR-Tools中的MinCostFlow.INFEASIBLE，说明你的问题模型定义存在矛盾，导致没有可行解。核心问题出在节点供应/需求的定义，同时还有容量参数的错误，下面一步步拆解修正：

1. 先明确运输问题的节点映射 #

你的原始运输问题是：

供应点：T1（700）、T2（800）
需求点：A1（500）、A2（600）、A3（400）
单位成本矩阵：

	A1	A2	A3
T1	0	600	100
T2	500	0	300

对应OR-Tools的节点应该这样定义：

• 节点0：T1（供应+700）
• 节点1：T2（供应+800）
• 节点2：A1（需求500 → 供应-500）
• 节点3：A2（需求600 → 供应-600）
• 节点4：A3（需求400 → 供应-400）

总供应=700+800=1500，总需求=500+600+400=1500，问题是平衡的，有可行解。

2. 你的代码中的关键错误 #

错误1：节点供应数组完全错误 #

你写的int[] supplies = { 700, 700, 800, 800, 800 };给所有节点都设了正供应，总供应=700+700+800+800+800=3800，远大于总需求1500，这必然导致问题不可行——没有足够的需求来消耗这些供应。

错误2：容量参数设置错误 #

你把需求点的需求量当成了弧的容量，比如T1到A1的容量设为500，但实际上这条弧的容量应该是供应点T1的最大可输出量（700），或者设为一个足够大的值（比如1e9），因为需求点的供应限制（-500）会自动控制流入量。当然，设为需求点的需求量也能运行，但逻辑上不对，而且如果供应点可以提供更多，会被错误限制。

3. 修正后的代码 #

下面是修正后的完整代码，我标注了关键修改点：

private static void SolveMinCostFlow() {
    // 节点映射：0=T1,1=T2,2=A1,3=A2,4=A3
    int numNodes = 5;
    int numArcs = 6;
    // 起始节点：T1(0)连到三个需求点，T2(1)连到三个需求点
    int[] startNodes = { 0, 0, 0, 1, 1, 1 };
    int[] endNodes = { 2, 3, 4, 2, 3, 4};
    // 修正容量：设为供应点的最大供应量，或足够大的值
    int[] capacities = { 700, 700, 700, 800, 800, 800 };
    // 单位成本和原问题一致，没问题
    int[] unitCosts = { 0, 600, 100, 500, 0, 300 };
    // 修正供应数组：供应点正，需求点负
    int[] supplies = { 700, 800, -500, -600, -400 };

    MinCostFlow minCostFlow = new MinCostFlow();

    // 添加弧，这部分逻辑没问题
    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");
    }

    // 设置节点供应，这部分现在正确了
    for (int i = 0; i < numNodes; ++i) {
        minCostFlow.SetNodeSupply(i, supplies[i]);
    }

    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)} {minCostFlow.Flow(i),3} / {minCostFlow.Capacity(i),3} {cost,3}");
        }
    } else {
        Console.WriteLine($"Solving the min cost flow problem failed. Solver status: {solveStatus}");
    }
}

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

4. 运行结果说明 #

修正后运行会得到最优解，最小成本应该是80000，对应的运输方案为：

• T1→A1：500，成本0
• T1→A3：200，成本20000
• T2→A2：600，成本0
• T2→A3：200，成本60000

这个结果和手动计算的最优运输方案完全一致。

内容的提问来源于stack exchange，提问作者pisk1