使用scipy.optimize.linprog求解指派问题时最小成本为None的排查

你的代码存在两个核心错误，导致res.fun始终返回None：

1. 行约束矩阵构造完全错误 #

你当前的A_eq_rows = np.ones((n, n**2))会让每行所有变量的系数都为1，这使得约束变成所有变量的总和等于1，完全违背了指派问题「每个工人对应的任务变量总和为1」的要求。正确的行约束应该是：第i行（对应第i个工人）仅在该工人的n个任务变量位置填1，其余位置为0。

2. 目标函数系数维度不符合要求 #

cost.reshape((n**2,1))生成的是二维列向量，但linprog要求目标函数系数c必须是一维数组，二维输入会导致求解器无法正确解析目标函数。

修正后的完整代码 #

import numpy as np
import time
from scipy.optimize import linprog

n = 10   # 工人/任务数量
cost = np.random.rand(n,n)   # 生成随机成本矩阵

# 将成本矩阵转为一维数组（符合linprog的参数格式要求）
c = cost.flatten()

# 构造行约束：每个工人必须分配一个任务（每行和为1）
A_eq_rows = np.zeros((n, n**2))
for i in range(n):
    # 第i个工人对应的变量是i*n到(i+1)*n的索引区间
    A_eq_rows[i, i*n : (i+1)*n] = 1
b_eq_rows = np.ones(n)

# 构造列约束：每个任务必须分配给一个工人（每列和为1）
A_eq_cols = np.zeros((n, n**2))
for i in range(n):
    A_eq_cols[i, i::n] = 1
b_eq_cols = np.ones(n)

# 合并约束矩阵和右端项
A_eq = np.vstack((A_eq_rows, A_eq_cols))
b_eq = np.hstack((b_eq_rows, b_eq_cols))

# 指定变量非负约束（指派问题变量满足0≤x_ij≤1，线性松弛后允许连续值）
bounds = [(0, 1)] * (n**2)

start_time = time.time()
# 使用高效的highs求解器（scipy新版本默认推荐）
res = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
end_time = time.time()

elapsed_LP = end_time - start_time

print("求解状态：", res.success)
print("Minimum cost = ", res.fun)
print("Elapsed time = ", elapsed_LP)

额外说明 #

• 新增bounds参数限制变量非负，避免求解器得到无意义的负数解；
• 可以通过print(res)查看求解器的详细输出，快速定位约束矛盾、求解失败等问题；
• 修正后的结果可以和linear_sum_assignment的结果做对比，线性规划的松弛解成本会略低于（或等于）整数解成本。

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