AI 与工程数学 / 系统课时
把线性规划写成标准形式
把线性规划写成标准形式
线性规划求解器接收的是变量、目标系数和约束矩阵,而业务描述往往混有最大化、不等式、上下界甚至自由变量。本节从一个生产计划模型出发,把它系统转换成标准形式,并用求解器验证转换前后得到同一个最优解。
学习目标
- 能从业务约束中提取线性目标、变量边界和线性不等式
- 能通过变号、变量替换和松弛变量把模型统一成标准形式
- 能用线性规划求解器验证转换前后的最优值与决策变量一致
从业务描述到线性模型
假设生产两种产品 ,单位利润分别为 3 和 2。两类资源的可用量分别为 4 和 5,对应消耗约束为
并且产量不能为负。原模型可以写成
这已经是求解器常见的输入形式,但还不是“等式约束 + 非负变量”的经典标准形式。
统一方向与变量边界
标准化时先处理符号,再处理等式。最大化目标可以乘以 转成最小化;若约束方向是 ,也可以整体乘以 变成 。
变量边界不能简单丢掉。若变量 有下界 ,可令 且 ;若变量可以取任意实数,则常用 ,其中 。这一步的目的,是最终只保留非负变量。
引入松弛变量得到标准形式
对每个 约束加入一个非负松弛变量:
其中 。于是可写成
其中
松弛变量表示资源剩余量,不改变原问题的可行决策,只是把“不超过”改写成“用掉的量 + 剩余量 = 总量”。
用求解器验证转换
下面分别求解原始不等式模型和加入松弛变量后的等式模型。scipy.optimize.linprog 默认求最小值,所以目标系数使用 [-3, -2]。
python
from scipy.optimize import linprog
# 原始模型:max 3*x1 + 2*x2 等价于 min -3*x1 - 2*x2
original = linprog(
c=[-3.0, -2.0],
A_ub=[[1.0, 1.0], [2.0, 1.0]],
b_ub=[4.0, 5.0],
bounds=[(0, None), (0, None)],
method="highs",
)
# 标准形式:z = [x1, x2, s1, s2],所有变量非负
standard = linprog(
c=[-3.0, -2.0, 0.0, 0.0],
A_eq=[[1.0, 1.0, 1.0, 0.0], [2.0, 1.0, 0.0, 1.0]],
b_eq=[4.0, 5.0],
bounds=[(0, None)] * 4,
method="highs",
)
print("original:", original.success, original.x, -original.fun)
print("standard:", standard.success, standard.x, -standard.fun)预期输出:
text
original: True [1. 3.] 9.0
standard: True [1. 3. 0. 0.] 9.0两个模型都得到 ,最大利润为 9。标准形式中两个松弛变量都为 0,说明最优点恰好同时用满两类资源。
容易出错的地方
最常见的问题不是求解器本身,而是转换时改变了可行域。最大化转最小化时只应改变目标符号;把 约束乘以 时,等号右侧也必须同时变号;引入松弛变量时, 对应“加”非负变量,而 若直接转等式则对应剩余变量的符号不同,通常先统一方向更不易出错。
验证标准形式时至少检查三件事:原决策变量的最优值是否一致、最优目标值是否一致、把求得的解代回原约束后是否满足边界。只要这三项同时成立,模型转换才算完成。
按自己的节奏,确认真正理解。