AI 与工程数学 / 系统课时

把线性规划写成标准形式

把线性规划写成标准形式

线性规划求解器接收的是变量、目标系数和约束矩阵,而业务描述往往混有最大化、不等式、上下界甚至自由变量。本节从一个生产计划模型出发,把它系统转换成标准形式,并用求解器验证转换前后得到同一个最优解。

学习目标

  • 能从业务约束中提取线性目标、变量边界和线性不等式
  • 能通过变号、变量替换和松弛变量把模型统一成标准形式
  • 能用线性规划求解器验证转换前后的最优值与决策变量一致

从业务描述到线性模型

假设生产两种产品 x1,x2x_1,x_2,单位利润分别为 3 和 2。两类资源的可用量分别为 4 和 5,对应消耗约束为

x1+x2≤4x_1+x_2\le4
2x1+x2≤52x_1+x_2\le5

并且产量不能为负。原模型可以写成

max⁡ 3x1+2x2\max\ 3x_1+2x_2
s.t. x1+x2≤4,2x1+x2≤5,x1,x2≥0\text{s.t. } x_1+x_2\le4,\quad 2x_1+x_2\le5,\quad x_1,x_2\ge0

这已经是求解器常见的输入形式,但还不是“等式约束 + 非负变量”的经典标准形式。

统一方向与变量边界

标准化时先处理符号,再处理等式。最大化目标可以乘以 −1-1 转成最小化;若约束方向是 ≥\ge,也可以整体乘以 −1-1 变成 ≤\le。

变量边界不能简单丢掉。若变量 xx 有下界 LL,可令 x=L+yx=L+y 且 y≥0y\ge0;若变量可以取任意实数,则常用 x=x+−x−x=x^+-x^-,其中 x+,x−≥0x^+,x^-\ge0。这一步的目的,是最终只保留非负变量。

引入松弛变量得到标准形式

对每个 ≤\le 约束加入一个非负松弛变量:

x1+x2+s1=4x_1+x_2+s_1=4
2x1+x2+s2=52x_1+x_2+s_2=5

其中 s1,s2≥0s_1,s_2\ge0。于是可写成

min⁡ −3x1−2x2+0s1+0s2\min\ -3x_1-2x_2+0s_1+0s_2
Az=b,z≥0A z=b,\quad z\ge0

其中

z=[x1,x2,s1,s2]Tz=[x_1,x_2,s_1,s_2]^T
A=[11102101],b=[45]A=\begin{bmatrix}1&1&1&0\\2&1&0&1\end{bmatrix},\qquad b=\begin{bmatrix}4\\5\end{bmatrix}

松弛变量表示资源剩余量,不改变原问题的可行决策,只是把“不超过”改写成“用掉的量 + 剩余量 = 总量”。

用求解器验证转换

下面分别求解原始不等式模型和加入松弛变量后的等式模型。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

两个模型都得到 x1=1,x2=3x_1=1,x_2=3,最大利润为 9。标准形式中两个松弛变量都为 0,说明最优点恰好同时用满两类资源。

容易出错的地方

最常见的问题不是求解器本身,而是转换时改变了可行域。最大化转最小化时只应改变目标符号;把 ≥\ge 约束乘以 −1-1 时,等号右侧也必须同时变号;引入松弛变量时,≤\le 对应“加”非负变量,而 ≥\ge 若直接转等式则对应剩余变量的符号不同,通常先统一方向更不易出错。

验证标准形式时至少检查三件事:原决策变量的最优值是否一致、最优目标值是否一致、把求得的解代回原约束后是否满足边界。只要这三项同时成立,模型转换才算完成。

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

目录与阅读设置

阅读设置

17

记录一个想法

把线性规划写成标准形式

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

登录哪都通