如何修改最小费用最大流任务分配模型以支持工人并行执行多任务

原模型的核心问题 #

原模型中，工人节点到汇节点的容量直接限制工人数量，但每个任务到工人的流会被算作占用1个工人配额。当工人需要并行处理多个任务时，这种建模方式会错误地将每个并行任务都计入工人占用数，导致实际可用工人被过度消耗（比如5个w1工人处理5个t1+5个t2任务，原模型会认为需要10个工人）。

正确建模思路 #

针对可并行多任务的工人类型，通过拆分节点实现「工人数量限制」和「单工人任务承载量」的双重控制：

• 新增中间节点（如w1_cap）：用来约束实际占用的工人总数
• 原工人节点（w1）作为任务分配的连接点，其到中间节点的边容量设为「工人数量 × 单工人并行任务数」，代表该类型工人能处理的总任务量
• 中间节点到汇节点的边容量设为工人数量，严格限制实际使用的工人总数

修改后的完整代码 #

import pandas as pd
from ortools.graph.python import min_cost_flow

def allocate_workers(df_in, node_name, supply_list):
    # 创建节点ID映射
    node_id = {name: idx for idx, name in enumerate(node_name)}
    df_temp = df_in.replace(node_id)

    smcf = min_cost_flow.SimpleMinCostFlow()
    df_temp[['cost', 'capacity']] = df_temp[['cost', 'capacity']].astype(int)

    # 添加所有边
    for row in df_temp.itertuples():
        smcf.add_arc_with_capacity_and_unit_cost(
            row.start_nodes, row.end_nodes, row.capacity, row.cost
        )
    # 设置节点供需
    for i in range(len(supply_list)):
        smcf.set_node_supply(i, supply_list[i])

    # 求解最小费用流
    status = smcf.solve()
    flow = []
    cost_flow = []
    
    if status == smcf.OPTIMAL:
        for arc in range(smcf.num_arcs()):
            flow.append(smcf.flow(arc))
            cost_flow.append(smcf.unit_cost(arc) * smcf.flow(arc))
    else:
        print('最小费用流输入存在问题')
        print(f'状态码: {status}')

    df_out = df_in.copy()
    df_out['flow'] = flow
    df_out['cost_flow'] = cost_flow
    print(df_out)
    print('总费用 = ', smcf.optimal_cost())
    return df_out

# 修改后的输入数据：针对w1添加并行支持
d = {
    'start_nodes': ['source']*3 + ['t1','t2','t2','t3'] + ['t1','t2','t3'] + ['w1'] + ['w1_cap','w2'],
    'end_nodes': ['t1','t2','t3'] + ['w1','w1','w2','w2'] + ['sink']*3 + ['w1_cap'] + ['sink','sink'],
    'cost': [0]*3 + [1,2,3,4] + [1000]*3 + [0] + [0,0],
    'capacity': [10,5,5] + [10]*4 + [5]*3 + [10] + [5,5]
}

# 更新节点列表：新增w1_cap
node_name = ['source','t1','t2','t3','w1','w2','w1_cap','sink']
# 新增节点的供需为0
supply = [20,0,0,0,0,0,0,-20]

# 初始化DataFrame
graph_df = pd.DataFrame(data=d)
# 执行分配
graph_df = allocate_workers(graph_df, node_name, supply)

# 输出结果
print(graph_df)

关键修改说明 #

1. 节点拆分：新增w1_cap节点，用于约束w1类型的实际工人数量
2. 边配置调整：
   • 移除原w1→sink的边，新增w1→w1_cap（容量10=5个工人×2个并行任务，成本0）和w1_cap→sink（容量5=工人总数，成本0）
   • 任务到w1的边容量调整为10，确保能承载最大并行任务量
3. 供需列表更新：新增节点w1_cap的供需设为0，不影响整体流平衡

效果验证 #

修改后，5个w1工人可以同时处理5个t1和5个t2任务：

• w1_cap→sink的流为5，代表实际占用5名工人
• w1→w1_cap的流为10，代表总共处理10个任务（5+5）
• 完美解决了原模型中任务量统计与实际工人数量不匹配的问题

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