AI 与工程数学 / 系统课时

用线性规划完成资源分配

用线性规划完成资源分配

这一节把一个有限产能分配任务完整写成线性规划,并用求解器得到最优产量。重点不只是拿到答案,还要检查约束余量、识别真正的瓶颈,并利用影子价格解释增加一单位资源可能带来的收益。

学习目标

  • 把利润最大化与资源容量限制转换为线性目标和约束
  • 使用 scipy.optimize.linprog 求出最优资源分配并验证可行性
  • 根据约束余量和影子价格判断资源瓶颈及其边际价值

把资源分配写成线性模型

假设工厂生产产品 A 和产品 B,分别记产量为 xx 和 yy。每件 A 获利 40 元、每件 B 获利 30 元,因此目标是让 40x+30y40x+30y 尽可能大。

生产同时受到两类资源限制:机器工时满足 2x+y≤1002x+y\le100,人工工时满足 x+2y≤80x+2y\le80,并且产量不能为负。只要目标函数和全部约束关于决策变量都是线性的,就可以直接使用线性规划求解。

线性规划可行域与最优点

图中的可行域包含所有同时满足两类资源限制的生产方案。目标函数的等值线不断向利润增大的方向平移,最后接触可行域的位置就是最优解;本例中接触点恰好是两条资源边界的交点。

用求解器得到最优方案

SciPy 的 linprog 默认求最小值,因此把利润系数取负,将最大化 40x+30y40x+30y 转换为最小化 −40x−30y-40x-30y。示例假设环境中已经安装 NumPy 与 SciPy。

python
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()}')

预期输出:

text
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 是否不超过容量,以及重新计算的利润是否与求解结果一致。本例三项都成立,因此数值解和业务约束能够相互验证。

还要确认线性模型本身是否符合真实任务。如果产品必须按整数件生产,而线性规划返回了小数产量,就需要改用整数或混合整数规划;如果单位利润随产量变化、资源消耗存在非线性关系,也不能继续把它们强行写成普通线性规划。真正可靠的资源分配结果,应同时满足数学最优、约束可行和业务假设成立。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用线性规划完成资源分配

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通