最小费用流问题求解 | Python+Gurobi-COPT-SCIP

写在前面

前两篇我们了解了网络流的两块基石：

• 最短路问题：送 1 个单位的流，走最省的路径（"怎么走得最省"）

• 最大流问题：不计费用，把流量推到极限（"最多能送多少"）

今天我们把两者合流：既要满足一批供给点和需求点的收发要求，又要让总费用最小。

把路网抽象一下：

• 供给节点：仓库，需要发货

• 需求节点：门店，等着收货

• 转运节点：中转站，只过路不留货

• 边：运输路段，带最大运力

• 目标：满足全部供需，运输费用尽可能少

为了让模型落地且便于读者手算验证，我们构造一个小型路网。

from gurobipy import GRB, Model, quicksum# ============================================================# 1. 定义案例数据# ============================================================# 节点集合N = [1, 2, 3, 4, 5, 6]# 有向边集合 (弧)A = [(1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 6), (4, 5), (4, 6)]# 边单位费用 c_{ij}C = {(1, 3): 2, (1, 4): 4, (2, 3): 1, (2, 4): 3, (3, 5): 2, (3, 6): 5, (4, 5): 3, (4, 6): 2}# 边容量 u_{ij}U = { (1, 3): 6, (1, 4): 5, (2, 3): 4, (2, 4): 6, (3, 5): 5, (3, 6): 4, (4, 5): 4, (4, 6): 6}# 节点供需 b_i (>0 供给, <0 需求, =0 转运; 总和为 0)B = { 1: 8, 2: 5, 3: 0, 4: 0,  5: -6,  6: -7 }# ============================================================# 2. 建模与求解# ============================================================def build_and_solve(N: list, A: list, C: dict, U: dict, B: dict):        # ---- 建模 ----        model = Model("MinCostFlow_Gurobi")        # 决策变量 x_{ij}: 0 <= x_{ij} <= u_{ij}        x = model.addVars(A, lb=0, ub=U, vtype=GRB.CONTINUOUS, name="x")        # 目标: min sum c_{ij} * x_{ij}        model.setObjective( quicksum(C[i, j] * x[i, j] for (i, j) in A),GRB.MINIMIZE)        # 约束: 流平衡 (含供需 b_i)        for i in N:                out_expr = quicksum(x[i, j] for (ii, j) in A if ii == i)                in_expr = quicksum(x[j, i] for (j, ii) in A if ii == i)                model.addConstr(out_expr - in_expr == B[i], name=f"balance_{i}")        # ---- 求解 ----        model.optimize()        # ---- 结果 ----        if model.Status == GRB.OPTIMAL:                flows = {(i, j): x[i, j].X for (i, j) in A}                total = model.ObjVal                return {"status": "OPTIMAL", "total_cost": total, "flows": flows}        return {"status": f"status={model.Status}", "total_cost": None, "flows": None}# ============================================================、# 3. 主流程# ============================================================def main():        # 供需平衡自检        assert abs(sum(B.values())) < 1e-9, "供需不平衡: sum(b_i) 必须为 0"        res = build_and_solve(N, A, C, U, B)        if res["status"] == "OPTIMAL":                print(f"求解状态: OPTIMAL")                print(f"最小总费用: {res['total_cost']}")                print(f"各边流量: {res['flows']}")                # 输出非零流量的运输方案                print(f"实际运输方案 (非零边):")                for (i, j) in A:                        if res['flows'][(i, j)] > 1e-9:                                print(f"  {i} -> {j}: 流量 {res['flows'][(i, j)]}, "f"费用 {res['flows'][(i, j)] * C[(i, j)]}")        else:                print(f"求解状态: {res['status']} (无可行流)")if __name__ == "__main__":        main()

from coptpy import COPT, Envr# ============================================================# 1. 定义案例数据# ============================================================# 节点集合N = [1, 2, 3, 4, 5, 6]# 有向边集合 (弧)A = [ (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 6), (4, 5), (4, 6)]# 边单位费用 c_{ij}C = { (1, 3): 2, (1, 4): 4, (2, 3): 1, (2, 4): 3, (3, 5): 2, (3, 6): 5, (4, 5): 3, (4, 6): 2}# 边容量 u_{ij}U = { (1, 3): 6, (1, 4): 5, (2, 3): 4, (2, 4): 6, (3, 5): 5, (3, 6): 4, (4, 5): 4, (4, 6): 6}# 节点供需 b_i (>0 供给, <0 需求, =0 转运; 总和为 0)B = { 1: 8,  2: 5, 3: 0,  4: 0, 5: -6,  6: -7  7}# ============================================================# 2. 建模与求解# ============================================================def build_and_solve(N: list, A: list, C: dict, U: dict, B: dict):        # ---- 建模 ----        model = Envr().createModel("MinCostFlow_COPT")        # 决策变量 x_{ij}: 0 <= x_{ij} <= u_{ij}        x = model.addVars(A, lb=0, ub=U, vtype=COPT.CONTINUOUS, nameprefix="x")        # 目标: min sum c_{ij} * x_{ij}        model.setObjective(sum(C[i, j] * x[i, j] for (i, j) in A), COPT.MINIMIZE)        # 约束: 流平衡 (含供需 b_i)        for i in N:                out_expr = sum(x[i, j] for (ii, j) in A if ii == i)                in_expr = sum(x[j, i] for (j, ii) in A if ii == i)                model.addConstr(out_expr - in_expr == B[i], name=f"balance_{i}")        # ---- 求解 ----        model.solve()        # ---- 结果 ----        if model.status == COPT.OPTIMAL:                flows = {(i, j): x[i, j].X for (i, j) in A}                # 纯 LP 用 LpObjVal 取目标值 (BestObj 为 MIP 属性, LP 下返回 0)                total = float(model.getAttr(COPT.Attr.LpObjVal))                return {"status": "OPTIMAL", "total_cost": total, "flows": flows}        return {"status": f"status={model.status}", "total_cost": None, "flows": None}# ============================================================# 3. 主流程# ============================================================def main():        # 供需平衡自检        assert abs(sum(B.values())) < 1e-9, "供需不平衡: sum(b_i) 必须为 0"        res = build_and_solve(N, A, C, U, B)        if res["status"] == "OPTIMAL":                print(f"求解状态: OPTIMAL")                print(f"最小总费用: {res['total_cost']}")                print(f"各边流量: {res['flows']}")                # 输出非零流量的运输方案                print(f"实际运输方案 (非零边):")                for (i, j) in A:                        if res['flows'][(i, j)] > 1e-9:                                print(f"  {i} -> {j}: 流量 {res['flows'][(i, j)]}, "f"费用 {res['flows'][(i, j)] * C[(i, j)]}")        else:                print(f"求解状态: {res['status']} (无可行流)")if __name__ == "__main__":        main()

from pyscipopt import Model, quicksum# ============================================================# 1. 定义案例数据# ============================================================# 节点集合N = [1, 2, 3, 4, 5, 6]# 有向边集合 (弧)A = [(1, 3), (1, 4), (2, 3), (2, 4),(3, 5), (3, 6), (4, 5), (4, 6)]# 边单位费用 c_{ij}C = {    (1, 3): 2, (1, 4): 4, (2, 3): 1, (2, 4): 3,    (3, 5): 2, (3, 6): 5, (4, 5): 3, (4, 6): 2}# 边容量 u_{ij}U = {    (1, 3): 6, (1, 4): 5, (2, 3): 4, (2, 4): 6,    (3, 5): 5, (3, 6): 4, (4, 5): 4, (4, 6): 6}# 节点供需 b_i (>0 供给, <0 需求, =0 转运; 总和为 0)B = {    1: 8, 2: 5,3: 0,   4: 0,   5: -6,     6: -7 }# ============================================================# 2. 建模与求解# ============================================================def build_and_solve(N: list, A: list, C: dict, U: dict, B: dict):        # ---- 建模 ----        model = Model("MinCostFlow_SCIP")        # 决策变量 x_{ij}: 0 <= x_{ij} <= u_{ij}        x = {}        for (i, j) in A:                x[i, j] = model.addVar(lb=0, ub=U[i, j], vtype="C", name=f"x_{i}_{j}")        # 目标: min sum c_{ij} * x_{ij}        model.setObjective(quicksum(C[i, j] * x[i, j] for (i, j) in A), "minimize")        # 约束: 流平衡 (含供需 b_i)        for i in N:                out_expr = quicksum(x[i, j] for (ii, j) in A if ii == i)                in_expr = quicksum(x[j, i] for (j, ii) in A if ii == i)                model.addCons(out_expr - in_expr == B[i], name=f"balance_{i}")        # ---- 求解 ----          model.optimize()        # ---- 结果 ----        if model.getStatus() == "optimal":                flows = {(i, j): model.getVal(x[i, j]) for (i, j) in A}                total = model.getObjVal()                return {"status": "OPTIMAL", "total_cost": total, "flows": flows}        return {"status": f"status={model.getStatus()}", "total_cost": None, "flows": None}# ============================================================# 3. 主流程# ============================================================def main():        # 供需平衡自检        assert abs(sum(B.values())) < 1e-9, "供需不平衡: sum(b_i) 必须为 0"        res = build_and_solve(N, A, C, U, B)        if res["status"] == "OPTIMAL":                print(f"求解状态: OPTIMAL")                print(f"最小总费用: {res['total_cost']}")                print(f"各边流量: {res['flows']}")                # 输出非零流量的运输方案                print(f"实际运输方案 (非零边):")                for (i, j) in A:                        if res['flows'][(i, j)] > 1e-9:                                print(f"  {i} -> {j}: 流量 {res['flows'][(i, j)]}, "f"费用 {res['flows'][(i, j)] * C[(i, j)]}")        else:                print(f"求解状态: {res['status']} (无可行流)")if __name__ == "__main__":        main()

参考资料：