Skip to content

线性规划 ​

方法速览 ​

  • 主要用途 在约束下求连续资源分配的最优方案。
  • 必要输入 连续变量及取值范围、目标系数和线性约束系数。
  • 适用条件 单位收益与用量在建模区间近似恒定,各项贡献可相加。
  • 典型不适用情况 决策必须取整数,或目标和约束存在需要保留的非线性。
  • 最低限度的验证方式 代回约束并复算目标。小例可检查顶点或用上下界核实最优性。

识别可用线性规划的任务 ​

线性规划适用于在明确限制下挑选连续决策值,例如分配物流量、混合原料或规划工时。每单位活动带来的收益和消耗在建模区间内应近似恒定,各项贡献能够相加。若有整台设备、固定启动费用或非线性成本,原线性模型会丢失这些条件。先确认最小执行单位及成本含义,再选择线性、整数或非线性规划。

写出变量、目标和约束 ​

设 x 是决策向量,c 是单位收益,矩阵 A 的元素 aij 表示单位活动 j 消耗第 i 种资源多少。b 是可用资源。一种形式为

maxxc⊤xs.t.Ax≤b,x≥0.

线性还允许等式、变量上下界和最小供给约束。二维可行域为非空有界多边形时,目标等值线可以向更优方向平移,直到碰到最优边或点。非空有界多边形至少有一个最优顶点。实际也需识别不可行、无界或多个最优解。SciPy 文档的线性规划形式和求解状态

生产两类产品的假设算例 ​

设产量 x,y 可以连续取值。两类产品分别带来每单位 3 和 2 的收益。原料一每单位均消耗 1,总量 4。原料二分别消耗 2 和 1,总量 6。于是 x+y≤4,2x+y≤6,x,y≥0。顶点 (0,0),(3,0),(2,2),(0,4) 的收益分别为 0,9,10,8,选择 (2,2)。还可把两条资源约束相加,得到 3x+2y≤10。可行解 (2,2) 恰好达到上界,便独立证明最优。

与整数和非线性方法怎么比 ​

若 x 或 y 必须整件交付,这是整数约束。即使某次线性解刚好为整数,也应将规则写清,以免下一批数据得到不可执行的小数。若如阶梯价格或二选一规则,可以考虑带辅助变量的分段及整数模型。连续且边际收益真实变化时,进一步比较非线性规划。用线性近似时,检查误差在解所在区间是否能接受。

容易出错的约束 ​

“容量最多 4”写成 ≤4,“需求至少 4”写成 ≥4。需求和供应同为“4”并不表示可直接相加,先统一公斤、吨、每小时或每天。保留运量等变量的上下界。若模型无界,检查收益方向和漏掉的容量。若不可行,先检查冲突的最小需求和资源上限,别直接放松业务必须满足的限制。

第一次求解怎样复核 ​

将最优解代回每条约束,列出资源用量和松弛量,用原始单位重算目标。特别注意求解接口是最大化还是最小化。用一个手工可行方案对照,以及小例子上的枚举或上界检查。再改变关键容量,看看闲置资源轻微增加时结果是否符合预期,记录哪些约束决定了这个分配。

若有多组最优分配,可以挑出符合执行习惯的一组,同时报告备选分配及二者相同的目标值。若要据此评价资源增量的价值,还要检查这个边际估计在多大的容量变动范围内有效。

动态演示 ​

下面这个演示把二维线性规划可视化:拖动参数或点预设按钮,左边实时重画可行域、约束线与目标等值线,右边给出状态判定。等值线从可行域下方平移越过最优点,观察它停在哪个顶点(或哪条边)达到最大值。

线性规划:目标等值线平移与可行域(max 2x + y)
目标系数
约束 1:x + y ≤ 4
约束 2:x ≤ 3
约束 3:y ≤ 2
唯一最优解等值线在顶点 (3, 1) 达到最大,z = 7。等值线再增大将离开可行域。
0123401234 t = -2.45 (3, 1)

等值线 c·x = -2.45 尚在可行域内,未达到最优 z = 7。

1 / 16
等值线移动是「教学演示动画」,不是算法迭代——二维线性规划用顶点枚举/单纯形一步求出最优(见正文)。 虚线为约束线,箭头指向可行侧;填充区域为可行域。等值线在顶点 (3, 1) 达到最大,z = 7。等值线再增大将离开可行域。

参数说明

  • 目标系数 c₁、c₂:目标函数 max c1x+c2y 的两个系数。
  • 三条约束 a1x+a2y≤b:每条约束各有一个 x 系数、y 系数与右端项;两个系数全为 0 表示空约束(不参与求解)。非负约束 x≥0, y≥0 固定存在,不必填写。
  • 四个预设:P1 唯一最优、P2 多个最优、P3 不可行、P4 无界,对应下表四种状态。
  • 播放控件:上一步/播放/下一步/重置 + 进度条 + 0.5–4× 速度。等值线移动是教学演示动画,不是算法迭代——二维线性规划用顶点枚举或单纯形一次求出最优解,正文已给出;动画只是把「平移等值线」的几何解释演出来。

数值表(与 examples/lp_demo.py 的 scipy linprog(method='highs') 求解一致)

预设目标约束状态最优解最优值 z
P1max 2x+yx+y≤4, x≤3, y≤2唯一最优(3, 1)7
P2max x+yx≤2, y≤2, x+y≤2多个最优线段 (2,0)–(0,2)2
P3max x+yx+y≤1, x+y≥2不可行无—
P4max x+yx−y≤1无界无上界—

P2 中 x≤2, y≤2 是冗余约束(由 x+y≤2 与 x,y≥0 自动成立);P3 的 x+y≥2 写成 −x−y≤−2。P1 的可行域与目标等值线见下图。

P1 可行域与目标等值线(scipy 与手推一致)

四种状态说明

  • 唯一最优解:目标等值线只在单个顶点与可行域相切,再向改善方向平移就会整体离开可行域,该顶点就是唯一最优解(P1 的 (3,1))。
  • 多个最优解:目标等值线平行于可行域某条边界,整条边界上每点的目标值都相同,最优解是一条线段(P2 的 (2,0)–(0,2))。
  • 不可行:约束半平面没有公共交集,可行域为空。典型症状是两条平行反向的约束(P3 的 x+y≤1 与 x+y≥2)。
  • 无界:可行域在目标改善方向没有上限,沿可行射线移动目标可无限增大(P4 沿 y 轴或 y=x−1 方向增大)。

双语言实验 ​

用可行域找到最优产品组合 ​

沿用上面预设 P1。设 x,y 为 A、B 两种产品的生产批量,本轮排产允许小数批。两种产品共用 4 批次的时间,A、B 各自最多生产 3 批和 2 批,每批利润为 2 和 1。前置知识是二元一次方程组和向量点积。

先把每条不等式临时改为等式。两条不平行的边界相交后,把交点代回全部不等式,留下 (0,0),(3,0),(3,1),(2,2),(0,2)。为什么只算这些点?可行多边形中的任意一点是顶点的凸组合,它的线性利润就是相同系数下的凸组合,因而最多等于利润最高的顶点。这里 z=2x+y 在 (3,1) 处达到 7。三个资源约束的剩余量 b−Ax=(0,0,1)⊤,说明共享时间和 A 产能用满,B 仍可多做 1 批,但需要先腾出共享时间。

在图上,虚线 y=z−2x 的位置随利润 z 提高而向上平移。尝试在上方动画中改变目标系数并观察最后接触可行域的位置。顶点法适合本例这种非空且有界的二维多边形。高维模型、无界和不可行情形要读标准求解器的状态。

独立运行 ​

Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_lp.py。MATLAB 将 mmf_lp.m 放入当前文件夹,在命令窗口运行 result = mmf_lp(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。

下载 Python 源码 · 下载 MATLAB 源码

枚举二维有界可行域的边界交点,每点都代回全部不等式。最优解为 (2, 2)、目标值 10。完整实践用标准求解器复核。

最简版依赖 Python:NumPy。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_lp.py

py
import json
from itertools import combinations

import numpy as np

# x+y≤4, x≤2, y≤3, x≥0, y≥0;每行对应一条半平面边界。
a = np.array([[1, 1], [1, 0], [0, 1], [-1, 0], [0, -1]])
b = np.array([4, 2, 3, 0, 0])
profit = np.array([3, 2])
best, value = None, -np.inf
feasible_count = 0
for i, j in combinations(range(len(b)), 2):
    rows = [i, j]
    if abs(np.linalg.det(a[rows])) < 1e-12:
        continue  # 平行边界没有唯一交点。
    point = np.linalg.solve(a[rows], b[rows])
    if np.all(a @ point <= b + 1e-12):
        feasible_count += 1
        if profit @ point > value:
            best, value = point, float(profit @ point)
assert np.allclose(best, [2, 2]) and np.isclose(value, 10)
result = {"point": best.tolist(), "value": value, "feasible_intersections": feasible_count}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

两种脚本分别用 np.linalg.solve 与 MATLAB 反斜杠解边界交点,以矩阵乘法复算约束与目标。Python 的行号从 0 开始,MATLAB 从 1 开始。输出 x、profit、slack、vertices 应分别对应 [3,1]、7、[0,0,1]、5。

用标准求解器复核 ​

两者的接口都求最小值,因此传入 (−2,−1),复核利润时再取负。Python 命令 python -m pip install scipy 安装可选求解器。MATLAB 这一步需要 Optimization Toolbox,上面的顶点枚举仍可独立使用。求解器允许在多解情形返回任一最优点,比较时应复核可行性和目标值。 SciPy linprog · MathWorks linprog

python
from scipy.optimize import linprog

fit = linprog([-2, -1], A_ub=[[1, 1], [1, 0], [0, 1]],
              b_ub=[4, 3, 2], bounds=[(0, None)] * 2, method="highs")
assert fit.success, fit.message
print(fit.x, -fit.fun)
matlab
[x, fval, flag] = linprog([-2; -1], [1 1; 1 0; 0 1], [4; 3; 2], ...
    [], [], [0; 0], []);
assert(flag > 0);
disp([x.' -fval])
参数练习与参考结论

先把共享上限从 4 降到 3,再复跑脚本。新最优为 (3,0)、利润为 6、三个资源约束剩余量为 (0,0,2)。另试在原上限 4 下将目标改为 x+y。可行边界上的 (2,2) 至 (3,1) 整段利润均为 4,脚本只选其中一个端点。要识别多解,可查是否还有不同顶点达到同一最高利润。

关联文章 ​

MathModel FAQ · 数学建模知识库