AI 与工程数学 / 系统课时
用线性规划完成资源分配
用线性规划完成资源分配
这一节把一个有限产能分配任务完整写成线性规划,并用求解器得到最优产量。重点不只是拿到答案,还要检查约束余量、识别真正的瓶颈,并利用影子价格解释增加一单位资源可能带来的收益。
学习目标
- 把利润最大化与资源容量限制转换为线性目标和约束
- 使用
scipy.optimize.linprog求出最优资源分配并验证可行性 - 根据约束余量和影子价格判断资源瓶颈及其边际价值
把资源分配写成线性模型
假设工厂生产产品 A 和产品 B,分别记产量为 和 。每件 A 获利 40 元、每件 B 获利 30 元,因此目标是让 尽可能大。
生产同时受到两类资源限制:机器工时满足 ,人工工时满足 ,并且产量不能为负。只要目标函数和全部约束关于决策变量都是线性的,就可以直接使用线性规划求解。

图中的可行域包含所有同时满足两类资源限制的生产方案。目标函数的等值线不断向利润增大的方向平移,最后接触可行域的位置就是最优解;本例中接触点恰好是两条资源边界的交点。
用求解器得到最优方案
SciPy 的 linprog 默认求最小值,因此把利润系数取负,将最大化 转换为最小化 。示例假设环境中已经安装 NumPy 与 SciPy。
import numpy as np
from scipy.optimize import linprog
profit = np.array([40.0, 30.0])
resource_use = np.array([
[2.0, 1.0],
[1.0, 2.0],
])
capacity = np.array([100.0, 80.0])
# linprog 求最小值,因此对利润系数取负。
result = linprog(
c=-profit,
A_ub=resource_use,
b_ub=capacity,
bounds=[(0, None), (0, None)],
method='highs',
)
if not result.success:
raise RuntimeError(result.message)
x = result.x
used = resource_use @ x
slack = capacity - used
# 最小化问题的边际值符号与利润最大化相反,所以这里再次取负。
shadow_price = -result.ineqlin.marginals
print(f'A={x[0]:.1f}, B={x[1]:.1f}')
print(f'profit={-result.fun:.1f}')
print(f'slack={np.round(slack, 1).tolist()}')
print(f'shadow_price={np.round(shadow_price, 2).tolist()}')预期输出:
A=40.0, B=20.0
profit=2200.0
slack=[0.0, 0.0]
shadow_price=[16.67, 6.67]因此最优方案是生产 40 件 A 和 20 件 B,总利润为 2200。代回约束可得机器资源使用量为 100,人工资源使用量为 80,两项都没有超出容量。
用余量和影子价格识别瓶颈
约束余量等于“容量减去实际使用量”。本例两个余量都为 0,说明机器工时和人工工时在最优点都被完全使用,因此它们都是当前最优方案的活动约束,也就是实际限制继续增产的瓶颈。
影子价格进一步回答“多给一单位资源值多少钱”。机器工时的影子价格约为 16.67,表示在最优基结构不改变的局部范围内,如果机器容量从 100 增加到 101,最优利润预计增加约 16.67;人工工时增加一单位则预计增加约 6.67。
验证模型而不是只相信最优值
拿到求解器结果后至少检查三件事:所有决策变量是否满足上下界,矩阵乘积 resource_use @ x 是否不超过容量,以及重新计算的利润是否与求解结果一致。本例三项都成立,因此数值解和业务约束能够相互验证。
还要确认线性模型本身是否符合真实任务。如果产品必须按整数件生产,而线性规划返回了小数产量,就需要改用整数或混合整数规划;如果单位利润随产量变化、资源消耗存在非线性关系,也不能继续把它们强行写成普通线性规划。真正可靠的资源分配结果,应同时满足数学最优、约束可行和业务假设成立。