专题进阶 · 优化算法推荐总顺序 · 第 128 / 148 课

把文字约束转换为半平面,用二维顶点理解线性规划的可行域与最优解。

先学会这些,再进入本课 高斯消元 贪心思想
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 优化算法

线性规划Linear Programming

在线性约束下优化线性目标,可用单纯形法或内点法求解。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

把文字约束转换为半平面,用二维顶点理解线性规划的可行域与最优解。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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)→10A 达上限,且总量为 4

窄屏可左右滑动表格,阅读完整计算与理由。

最优解 (x,y)=(2,2),最大利润 10。

04为什么这个方法成立

  1. 枚举每对不平行边界可以得到该多边形所有顶点,额外交点通过可行性检查排除。
  2. 有限非空有界多边形上的线性函数至少有一个顶点最优。
  3. 因此检查全部可行顶点可解此受限二维问题;推理不能被用于声称代码会识别一般无界模型。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

把目标改成 x+y,最优解唯一吗?

需要一点提示

查看 x+y=4 这条可行边。

查看解析与答案

不唯一,从 (1,3) 到 (2,2) 的整段都达到 4。

练习 2 · 边界与辨析

为什么 x≥0 写成 (−1,0,0)?

需要一点提示

统一为 ≤ 形式。

查看解析与答案

−x≤0 与 x≥0 等价。

练习 3 · 变式与迁移

只有 x≥0、y≥0,最大化 x+y 会怎样?

需要一点提示

能否一直增大 x?

查看解析与答案

问题无界,没有有限最优值;不能使用本课的有界模型假设。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。