主题
线性规划
方法速览
- 主要用途 在约束下求连续资源分配的最优方案。
- 必要输入 连续变量及取值范围、目标系数和线性约束系数。
- 适用条件 单位收益与用量在建模区间近似恒定,各项贡献可相加。
- 典型不适用情况 决策必须取整数,或目标和约束存在需要保留的非线性。
- 最低限度的验证方式 代回约束并复算目标。小例可检查顶点或用上下界核实最优性。
识别可用线性规划的任务
线性规划适用于在明确限制下挑选连续决策值,例如分配物流量、混合原料或规划工时。每单位活动带来的收益和消耗在建模区间内应近似恒定,各项贡献能够相加。若有整台设备、固定启动费用或非线性成本,原线性模型会丢失这些条件。先确认最小执行单位及成本含义,再选择线性、整数或非线性规划。
写出变量、目标和约束
设
线性还允许等式、变量上下界和最小供给约束。二维可行域为非空有界多边形时,目标等值线可以向更优方向平移,直到碰到最优边或点。非空有界多边形至少有一个最优顶点。实际也需识别不可行、无界或多个最优解。SciPy 文档的线性规划形式和求解状态
生产两类产品的假设算例
设产量
与整数和非线性方法怎么比
若
容易出错的约束
“容量最多 4”写成
第一次求解怎样复核
将最优解代回每条约束,列出资源用量和松弛量,用原始单位重算目标。特别注意求解接口是最大化还是最小化。用一个手工可行方案对照,以及小例子上的枚举或上界检查。再改变关键容量,看看闲置资源轻微增加时结果是否符合预期,记录哪些约束决定了这个分配。
若有多组最优分配,可以挑出符合执行习惯的一组,同时报告备选分配及二者相同的目标值。若要据此评价资源增量的价值,还要检查这个边际估计在多大的容量变动范围内有效。
动态演示
下面这个演示把二维线性规划可视化:拖动参数或点预设按钮,左边实时重画可行域、约束线与目标等值线,右边给出状态判定。等值线从可行域下方平移越过最优点,观察它停在哪个顶点(或哪条边)达到最大值。
目标系数
约束 1:x + y ≤ 4
约束 2:x ≤ 3
约束 3:y ≤ 2
等值线 c·x = -2.45 尚在可行域内,未达到最优 z = 7。
1 / 16
参数说明
- 目标系数 c₁、c₂:目标函数
的两个系数。 - 三条约束
:每条约束各有一个 x 系数、y 系数与右端项;两个系数全为 0 表示空约束(不参与求解)。非负约束 固定存在,不必填写。 - 四个预设:P1 唯一最优、P2 多个最优、P3 不可行、P4 无界,对应下表四种状态。
- 播放控件:上一步/播放/下一步/重置 + 进度条 + 0.5–4× 速度。等值线移动是教学演示动画,不是算法迭代——二维线性规划用顶点枚举或单纯形一次求出最优解,正文已给出;动画只是把「平移等值线」的几何解释演出来。
数值表(与 examples/lp_demo.py 的 scipy linprog(method='highs') 求解一致)
| 预设 | 目标 | 约束 | 状态 | 最优解 | 最优值 z |
|---|---|---|---|---|---|
| P1 | max 2x+y | x+y≤4, x≤3, y≤2 | 唯一最优 | (3, 1) | 7 |
| P2 | max x+y | x≤2, y≤2, x+y≤2 | 多个最优 | 线段 (2,0)–(0,2) | 2 |
| P3 | max x+y | x+y≤1, x+y≥2 | 不可行 | 无 | — |
| P4 | max x+y | x−y≤1 | 无界 | 无上界 | — |
P2 中

四种状态说明
- 唯一最优解:目标等值线只在单个顶点与可行域相切,再向改善方向平移就会整体离开可行域,该顶点就是唯一最优解(P1 的
)。 - 多个最优解:目标等值线平行于可行域某条边界,整条边界上每点的目标值都相同,最优解是一条线段(P2 的
– )。 - 不可行:约束半平面没有公共交集,可行域为空。典型症状是两条平行反向的约束(P3 的
与 )。 - 无界:可行域在目标改善方向没有上限,沿可行射线移动目标可无限增大(P4 沿
轴或 方向增大)。
双语言实验
用可行域找到最优产品组合
沿用上面预设 P1。设
先把每条不等式临时改为等式。两条不平行的边界相交后,把交点代回全部不等式,留下
在图上,虚线
独立运行
Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_lp.py。MATLAB 将 mmf_lp.m 放入当前文件夹,在命令窗口运行 result = mmf_lp(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。
枚举二维有界可行域的边界交点,每点都代回全部不等式。最优解为 (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。
用标准求解器复核
两者的接口都求最小值,因此传入 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,再复跑脚本。新最优为