本页目录
优化 IV · 线性规划与动态规划
两大经典算法范式收官运筹线。线性规划是约束优化理论的完全体标本——几何清晰、对偶完美、算法成熟；动态规划则是另一种完全不同的求解哲学：把时间/阶段结构变成递推。两者也各自通向 AI 的一条大动脉（LP 对偶 → 组合优化；DP → 强化学习的 Bellman 方程）。
学习层：一个可行点，为什么还不能交卷？
1. 具体实例：产品配额的两个账本
工厂生产两种产品，数量分别为 \(x,y\)，单位利润为 \(3,5\)。原料与工时给出
先不要画图。给出一个满足全部不等式的点并不难，难的是回答：它是不是利润最大的点？如果把产品改成整件发货，连续解还能不能直接当作答案？如果把“阶段”换成背包容量，为什么要写状态 \(V(i,w)\)，而不是继续找一个连续顶点？
2. 先预测：哪两条边会同时绷紧？
在打开实验前，预测默认实例的最优点，并勾出全部取等号的约束，包括资源边和 \(x=0,y=0\) 两条下界。退化时可以有三条甚至更多约束同时紧。同时写下你认为对偶目标值会不会与原目标值相等。滑块改变容量后再预测一次；只看“可行”不能替代最优性判断。
3. 最小模型：连续 LP 的双重证书
对一般形式
对偶是
一个完整的最优证书要同时检查：原始可行 \(Ax\le b,\ x\ge0\)；对偶可行 \(A^\top u\ge c\)；原始目标与对偶目标的间隙为零；以及互补松弛
默认实例的连续答案是 \((x,y)=(2,6)\)，利润 \(36\)；对偶证书可取 \(u=(0,\frac32,1)\)，其目标 \(12\cdot\frac32+18=36\)。原始松弛是 \((2,0,0)\)，对偶松弛是 \((0,0)\)；不是全部松弛都为零，而是每个乘积为零。有两单位资源 1 剩余，其价格 \(u_1=0\)，恰好使乘积消失。
为什么零间隙能证明最优？对任意双侧可行点，
两类项都非负，故任意对偶可行值是所有原始可行值的上界。若某个原始点达到这个上界，就已最优；互补松弛是该非负和为零的逐项表达，不是还需要独立添加的第三种神秘条件。
4. 正式桥：顶点、整数与状态不是同一个对象
对本例这样的非空有界多面体，线性目标至少有一个顶点最优解；一般多面体还须核对是否含有直线，不能无条件套用顶点结论。强对偶把两个可行账本的相等变成最优性证书。把 \(x,y\) 改成整数后，可行集变成格点，连续对偶值仍是整数问题的上界，却不必由整数点达到；四舍五入也可能破坏约束。动态规划则把阶段和资源写成离散状态，例如
它依靠最优子结构和重叠子问题，不是把整数状态误当作连续 LP 的顶点。
5. 误区与边界：证书能证明什么，不能证明什么？
- 可行不等于最优。 本页用双侧可行加零间隙提供最优性证明；也可以用完整顶点枚举或其他有效论证，单凭“图上这个点可行”不够。
- 互补不等于任意活动集。 约束绷紧时乘子可以为零；变量为零时对应的对偶约束可以有正松弛。
- 连续证书不自动解决整数问题。 LP 松弛的对偶值是界，分支定界还要处理整数性；DP 的表格状态也要保留离散转移。
- 退化、多解与舍入要分开。 一个顶点可有多组基，一个最优面可包含多个点，一个最优点也可能有多个对偶证书；这些不是同一个概念。通用浮点求解器需报告残差及容差，本实验的整数容量和固定系数则允许用整数分子作精确判断。
6. 可迁移问题：换一个资源，先保留哪条检查？
若目标系数或容量改变，先重算候选顶点，再用原始/对偶账本核验；若加入整数约束，另解整数候选或 DP 递推。问自己：当前图形是在证明连续模型，还是只是在展示一个 toy 的几何直觉？这条区分会一路跟到组合优化和强化学习。
迁移题参考答案：只改容量，哪些证书仍可行？
保持 \(A,c\) 不变，只改右端容量 \(b\) 时，原始可行域改变，但对偶约束 \(A^\mathsf Tu\ge c,u\ge0\) 没变。旧对偶解仍可行，却可能不再最优；它给新问题的上界 \(b_{\rm new}^\mathsf Tu_{\rm old}\)。
默认容量下 \(u=(0,3/2,1)\)。固定前两项容量为 \(4,12\)，只把混合资源容量记为 \(C\)，枚举三个对偶转折点可得
在 \(C=18\) 附近，一单位混合资源增加一单位利润；从 \(C=24\) 再增加资源，利润却不变。折点处左右导数不同，对偶影子价格可能不唯一。因此旧价格能给增量上界，不能承诺任意幅度变化都带来线性收益。若再加整数约束，还要另解格点或 DP；连续价格不直接等于整件生产的边际利润。
无 JavaScript 时的静态 fallback：默认连续 LP 的最优点为 \((2,6)\)，原始目标为 \(36\)；对偶变量为 \((0,\frac32,1)\)，对偶目标也为 \(36\)，原始松弛为 \((2,0,0)\)、对偶松弛为 \((0,0)\)，五个互补乘积均为零。页面开启脚本后，可改变三个容量，先勾出全部活动约束再揭示几何、连续与整数解、对偶值和精确证书账本；完整 DP 表可选格查看前驱。整数约束与 DP 状态仍需单独判断；可行点本身不代表最优。
1. 线性规划：最优点不一定只有一个顶点
标准形常写成
不等式可以加松弛变量，自由变量可拆为两个非负变量之差。可行域是有限个闭半空间及超平面的交，称为多面体；若还有界，则为多胞体。
准确的顶点结论：非空多面体不含整条直线，并且线性目标有有限最优值时，至少有一个最优顶点。标准非负形的可行域不含直线，所以满足这一结论；有界非空多面体也满足。注意是“至少有一个”，不是“所有最优点都是顶点”。
两个反例：没有顶点，以及整条边都最优
在直线 \(P=\{(x,0):x\in\mathbb R\}\) 上最小化零函数，每一点都最优，却没有顶点，因为任一点都是左右两个不同可行点的中点。
在正方形 \([0,1]^2\) 上最大化 \(x\)，整条边 \(\{1\}\times[0,1]\) 都最优，只有两端是顶点。这解释了平行等值线“推到边界”时可能贴住整条面；零目标甚至让整个区域最优。
标准形的证明线索：若一个最优解的正分量所对应的列线性相关，取只支撑在这些分量上的非零向量 \(d\)，使 \(Ad=0\)。足够小的正负步都保持非负；最优性迫使 \(c^\mathsf Td=0\)。选择一个方向移动，直到某个正分量变零，保持目标不变而缩小支撑。重复有限次后，正分量对应列独立，可扩充为一组基，得到最优基本可行解。这同时说明“方向上不能再改进”不代表最优解只有一个。MIT 线性规划讲义。
2. 单纯形法：换基有时不移动
先去除冗余等式，使 \(A\) 有满行秩 \(m\)。选 \(m\) 个独立列组成 \(B\)，解 \(Bx_B=b\)，令非基变量为零；若 \(x_B\ge0\)，这就是基本可行解。实际求解线性系统，而非显式算逆矩阵。不同基可对应同一个退化顶点。
对最小化问题，非基列 \(A_j\) 的检验数（约化成本）为
若所有 \(\bar c_j\ge0\)，当前原始可行基和 \(y=B^{-\mathsf T}c_B\) 组成对偶证书，可停机。否则选一个 \(\bar c_j<0\)，让 \(x_j=t\) 增长，基本变量变成 \(x_B-tq\)，其中 \(Bq=A_j\)。
- 若存在 \(q_i>0\)，可行步长由 \(t_{\max}=\min_{q_i>0}(x_B)_i/q_i\) 决定，相应变量出基。
- 若没有 \(q_i>0\)，则 \(t\) 可无限增大且目标持续下降，说明问题无界。
- 若 \(t_{\max}=0\)，发生退化换基，点和目标都可能不变。不能声称每次换基都严格改善。
初始化还需要一个可行基，可用第一阶段辅助问题寻找；找不到可能意味着原问题不可行。某些选基规则在退化时会循环，Bland 规则用固定最小下标选择打破循环。某些单纯形规则有指数最坏例子；这不妨碍它在许多实际问题中高效。具有复杂度保证的内点法提供另一类方法，通常沿内部或相对内部的中心路径近似推进，但不可行起始变体不要求每一步原始可行。
3. LP 对偶：先核对不等号和乘子的符号
本页实验使用最大化不等式形，其对偶 \(u\ge0\) 已在学习层推导。标准等式最小化形则有
等式对应的 \(y\) 是自由变量，不能强加非负。弱对偶来自 \(c^\mathsf Tx-b^\mathsf Ty=x^\mathsf T(c-A^\mathsf Ty)\ge0\)。原始等式已经恒紧，互补条件剩下 \(x_j(c-A^\mathsf Ty)_j=0\)，不能把不等式形的资源乘子口诀机械搬来。
有限维 LP 强对偶：若一侧可行且有有限最优值，另一侧也取得最优解，且两值相等，不需要 Slater 严格可行条件。若原始无界则对偶不可行；原始不可行时，对偶既可能无界也可能不可行，不能简单把两种状态一一对换。
对实验中的最大化资源模型，记最优利润为 \(V(b)\)。任意在 \(b\) 处最优的对偶解 \(u^*\)，对新的非负容量 \(b'\) 给出
这说明 \(u^*\) 是凹价值函数的一个上支撑斜率（超梯度）。在同一对偶解持续最优的区间内等号成立；可微时它才给出通常的边际导数。折点的多重影子价格、容量大幅变化和整数批量都会使“一单位资源总值这个价格”的说法失效。学习层的分段例子和右侧静态图可逐段验证。
4. 整数规划一瞥
变量限整数（选址、排班、背包）。难点：可行域不再凸，许多整数规划是 NP 难的，连续 LP 结论不能直接搬过来。两个思想级武器：LP 松弛（去掉整数约束解 LP；最大化问题得到上界，最小化问题得到下界，同时常给出分数解）；分支定界（对分数变量分两支 \(x_j \leq \lfloor v \rfloor\) / \(\geq \lceil v \rceil\) 递归，用 LP 界剪枝——"用松弛问题的界导航穷举"）。
5. 动态规划：先把状态和边界写完整
状态必须包含决定未来可行动作、转移及代价所需的信息。如果未来依赖“之前是否买过某项许可”，仅用当前地点作状态就不够；要把许可状态也纳入。最优子结构是：固定一个充分状态后，最优方案的后段也必须解决该状态的子问题。
有限阶段为什么可以倒着算？
对阶段 \(t=0,\dots,T-1\)，终端代价 \(g_T\)、阶段代价 \(\ell_t\)、确定转移 \(F_t\)，Bellman 递推为
先知道终端值，才能从 \(T-1\) 倒推。这里假设可行动作非空且最小值取得，例如有限状态、有限动作的情形；否则应分别处理无可行动作、用下确界代替最小值及策略存在性。阶段下标和终端条件不能省略后仍声称能直接“倒着算”。
本页有界背包的每一格是什么？
产品 \(x\) 最多有 \(a\) 份、每份占混合资源 \(3\)、利润 \(3\)；产品 \(y\) 最多有 \(\lfloor b/2\rfloor\) 份、每份占资源 \(2\)、利润 \(5\)。把每份视为一件可取或不取的物品，便得到 \(n=a+\lfloor b/2\rfloor\) 件物品、容量 \(C=c\) 的 0/1 背包。
\(V(i,w)\) 表示只用前 \(i\) 件、重量至多为 \(w\) 的最高价值。允许什么也不取，所以 \(V(0,w)=0\)；若要求恰好装满，就应把 \(V(0,w>0)\) 改为不可达，而不能继续用零。
第 \(i\) 件重 \(w_i\)、值 \(v_i\)，两种选择为
取较大者。两项都读上一行，保证每件只用一次；若压成一行数组却从小容量向大容量更新，会意外重复使用同一件物品，变成另一种问题。实验保留完整表，选格后会指出两个前驱及取舍；并列时示范保留“不取”，这只决定输出哪一个最优方案。
复杂度 \(O(nC)\) 对容量的数值是多项式，但整数 \(C\) 的二进制输入长度只有 \(O(\log C)\)，所以通常称为伪多项式。重叠子问题让缓存有用，不保证状态总数对输入长度是多项式；状态维度增加还会遇到维数灾难。MIT 背包与伪多项式讲义。
与最短路、强化学习的连接
有向无环图的最短路可按拓扑序递推；Bellman–Ford 可以用“允许经过的边数”作阶段；Dijkstra 还利用非负边权的贪心性质，不能把任何带负边的图直接交给它。若存在从起点可达且能通向终点的负环，最短路价值可能为 \(-\infty\)，不再有有限最短路径。
随机转移时把后续值改为条件期望。对有限状态和动作、奖励有界、折扣 \(0\le\gamma<1\) 的无限期 MDP，
由 \(\|TV-TW\|_\infty\le\gamma\|V-W\|_\infty\)，Bellman 算子有唯一不动点，价值迭代收敛。这与没有折扣的无限期问题不是同一套保证；Q-learning 还需要自己的采样与步长条件，不能只写出 Bellman 方程就宣布学会最优策略。Bertsekas 动态规划课程讲义。
6. 典型例题：从最优值追到选择本身
例 1：列全顶点。 默认产品模型的可行顶点是 \((0,0),(4,0),(4,3),(2,6),(0,6)\)，对应利润 \(0,12,27,36,30\)，所以 \((2,6)\) 最优。这里连续和整数最优恰好相同，不是整数问题的一般性质。
例 2：从互补解对偶。 默认点在资源 1 上有正松弛，故 \(u_1=0\)；两个产品数量都正，故对偶两条约束取等号：
解得 \(u_3=1,u_2=3/2\)，目标 \(4u_1+12u_2+18u_3=36\)。在混合容量保持 \(12<C<24\) 的区间内，边际价格为 \(1\)；超出区间需重新判断，加班成本还需与适用区间内的实际增量收益比较。
例 3：分数解为什么不能直接四舍五入？ 改成 \(a=4,b=11,c=18\)。连续解为 \((7/3,11/2)\)，目标 \(69/2=34.5\)。普通四舍五入得到 \((2,6)\)，违反 \(2y\le11\)；整数最优为 \((2,5)\)，利润 \(31\)。本例向下取整恰好成功，但它不是一般整数规划算法；本页由完整枚举和 DP 另行证明整数最优。
例 4：手填背包表。 容量 \(5\)，物品 \((w_i,v_i)=(2,3),(3,4),(4,5)\)。先预测最优价值和选中物品，再展开。
完整状态表与回溯
| 已考虑物品 | \(w=0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|---|
| 无 | 0 | 0 | 0 | 0 | 0 | 0 |
| 第 1 件 | 0 | 0 | 3 | 3 | 3 | 3 |
| 前 2 件 | 0 | 0 | 3 | 4 | 4 | 7 |
| 前 3 件 | 0 | 0 | 3 | 4 | 5 | 7 |
\(V(3,5)=\max(V(2,5),V(2,1)+5)=\max(7,5)=7\)，不取第 3 件；\(V(2,5)\) 选择 \(V(1,2)+4=7\)，取第 2 件；剩余容量 \(2\) 再取第 1 件。总重 \(5\)、总值 \(7\)。若只有一件 \((2,3)\) 却用同一行从小到大更新，容量 \(4\) 会错误得到 \(6\)，相当于把同一件拿了两次。