01先把问题说具体
生产 x 件 A、y 件 B,利润为 3x+2y,总产量最多 4,A 最多 2,B 最多 3,怎样安排最好?
02一步步得到方法
把问题完整写出来
最大化 3x+2y,约束 x+y≤4、x≤2、y≤3、x≥0、y≥0。这里 x、y 可以是实数,所以是线性规划;若必须为整数,还要添加整数约束,变成不同的问题。
每条不等式在平面上给出一个半平面,交集是凸多边形。目标等值线 3x+2y=c 平行移动,直到无法继续向利润更大的方向移动。
为什么看边界交点
这个非空有界多边形中,线性函数的最大值至少在一个顶点取得。可以把任意内部点表示成顶点的凸组合,它的目标值也就是顶点目标值的同样加权平均,不会超过最大的那个。
最优点不必唯一。目标方向若与一条边平行,整条边都可能最优。无约束或无界区域则需要另行判断是否存在使目标无限增加的方向。
从教学枚举到通用算法
二维中可枚举两条边界直线的交点,再筛选满足所有不等式的点。下面代码明确针对已知非空、有界的二维模型,不负责判定一般问题的无界性。
通用线性规划通常使用单纯形法或内点法。单纯形沿相邻基解移动,最坏情况并非多项式;内点法从内部推进。在工程中还应考虑浮点容差、尺度差异和求解器返回状态。
03把一个小例子完全算清楚
最大化 3x+2y,满足 x+y≤4、x≤2、y≤3、x,y≥0。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 下边与左边顶点 | (0,0)→0,(2,0)→6 | 均满足全部约束 |
| 上方顶点 | (0,3)→6,(1,3)→9 | 总量约束截去右上角 |
| 最优顶点 | (2,2)→10 | A 达上限,且总量为 4 |
窄屏可左右滑动表格,阅读完整计算与理由。
最优解 (x,y)=(2,2),最大利润 10。
04为什么这个方法成立
- 枚举每对不平行边界可以得到该多边形所有顶点,额外交点通过可行性检查排除。
- 有限非空有界多边形上的线性函数至少有一个顶点最优。
- 因此检查全部可行顶点可解此受限二维问题;推理不能被用于声称代码会识别一般无界模型。
05把推导翻译成代码
Python · 已知有界的二维线性规划顶点枚举
from itertools import combinations
def bounded_lp_2d(objective, constraints, tolerance=1e-9):
candidates = []
for (a,b,c),(d,e,f) in combinations(constraints,2):
determinant = a*e-b*d
if abs(determinant) <= 1e-12:
continue
x = (c*e-b*f)/determinant
y = (a*f-c*d)/determinant
if all(u*x+v*y <= w+tolerance for u,v,w in constraints):
candidates.append((objective[0]*x+objective[1]*y,x,y))
if not candidates:
raise ValueError("no feasible vertex; check bounded-model assumptions")
value,x,y = max(candidates)
return (x,y),value
constraints = [(1,1,4),(1,0,2),(0,1,3),(-1,0,0),(0,-1,0)]
print(bounded_lp_2d((3,2),constraints))逐个理解关键决定
(a,b,c)- 表示 ax+by≤c,非负约束也必须显式传入。
determinant- 两条平行或重合边界不能通过这个公式得到唯一交点。
all(u*x+v*y <= w+tolerance- 交点必须同时满足所有约束,不能只满足用于求交的那两条。
06时间、空间与实现范围
m 条约束枚举 O(m²) 对交点,每点检查 m 条约束,总时间 O(m³)。
此版保存候选点需 O(m²) 空间,可只保留当前最好值降到 O(1) 额外空间;输入约束本身占 O(m)。
07改变条件,检查哪里会出错
把实数解直接四舍五入当整数最优
可能违反约束,且通常不能保证整数最优。
找到可行顶点就排除无界
无界区域同样可能有顶点;此代码依赖调用者提供有界模型。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
把目标改成 x+y,最优解唯一吗?
需要一点提示
查看 x+y=4 这条可行边。
查看解析与答案
不唯一,从 (1,3) 到 (2,2) 的整段都达到 4。
为什么 x≥0 写成 (−1,0,0)?
需要一点提示
统一为 ≤ 形式。
查看解析与答案
−x≤0 与 x≥0 等价。
只有 x≥0、y≥0,最大化 x+y 会怎样?
需要一点提示
能否一直增大 x?
查看解析与答案
问题无界,没有有限最优值;不能使用本课的有界模型假设。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法