第 29 章线性规划 (Linear Programming)

核心结论

问题形式化：线性规划（LP）= 线性目标函数 + 线性约束（等式 / 不等式）；求解在凸多面体顶点上的线性函数极值。最一般形式为「minimize / maximize \(c^T x\) subject to \(Ax \leq b, x \geq 0\)」。
标准形与松弛形：标准形（standard form）所有约束为 ≤ 不等式；松弛形（slack form）所有约束为等式（用松弛变量把不等式转为等式）；单纯形算法在松弛形上工作。
可行域与最优解：可行域是凸多面体（simplex 之意）；线性目标函数在凸多面体上的极值必在顶点取得——这是单纯形算法的几何基础。
单纯形算法（§29.3）：从初始基本可行解出发，通过「pivot」操作在相邻顶点间移动（交换基本变量与非基本变量），目标值不减；终止时（无正系数非基本变量）即最优。
LP 对偶（§29.4）：每个 LP（primal）都有对应「对偶」LP；弱对偶：原任意可行解 ≤ 对偶任意可行解；强对偶：两者最优值相等；单纯形同时解原问题与对偶问题。
初始基本可行解（§29.5）：用「辅助 LP」处理「原点不可行」情形；通过构造辅助问题求解后回退到原问题。

本章主旨

线性规划是连续优化的「最易处理」形式——可行域是凸多面体，目标函数是线性，故最优在顶点。单纯形算法（Dantzig 1947）是工业标准：实践快但最坏指数；多项式算法有椭球法（Karmarkar 1979 的内点法）。LP 对偶是优化理论的基石——每个 LP 都有一个对偶 LP，两者的最优值相等；很多组合问题（最短路径、最大流、最小割）的「对偶定理」都是 LP 对偶的特例。本章重点是 LP 形式化、单纯形法、LP 对偶。

一、核心概念

本章围绕 6 个核心概念展开：从 LP 形式化出发，先介绍标准形与松弛形，然后讨论单纯形算法（含 pivot / 基本解），最后介绍 LP 对偶与初始基本可行解。

概念	定义 + 重要性	实现提示
线性规划 (Linear program)	最大化 / 最小化线性目标函数 \(c^T x\)，受线性约束 \(Ax \leq b, x \geq 0\)；可行域是凸多面体，最优在顶点。	§29.0；CLRS 政治选举例子展示建模过程。
标准形与松弛形	标准形：所有约束 \(\leq\) + 非负变量；松弛形：所有约束等式（每个 \(\leq\) 引入松弛变量）；两者通过加减松弛变量转换。	§29.1；标准形便于人写，松弛形便于算法处理。
基本解与基本可行解	基本解：松弛形中设非基本变量 = 0；基本可行解：基本解且满足非负约束；基本可行解 ⟺ 可行域顶点。	§29.3；单纯形在基本可行解间迭代。
单纯形 pivot	选「进入变量」（非基本变量，正目标系数）与「离开变量」（基本变量，受约束限制最小）；交换两者角色，重写松弛形；目标值不减。	§29.3；PIVOT 操作是单纯形的核心。
LP 对偶 (Duality)	原 LP（primal，最大化）与对偶 LP（dual，最小化）的目标最优值相等；弱对偶：任 primal ≤ 任 dual；强对偶：存在 primal = dual = 最优。	§29.4；定理 29.10；最大流最小割是其特例。
初始基本可行解	用辅助 LP 处理「原点不在可行域」；解辅助问题后回退到原问题；保证单纯形可启动。	§29.5；INITIALIZE-SIMPLEX 是关键预处理。

概念

定义 + 重要性

实现提示

线性规划 (Linear program)

最大化 / 最小化线性目标函数 \(c^T x\)，受线性约束 \(Ax \leq b, x \geq 0\)；可行域是凸多面体，最优在顶点。

§29.0；CLRS 政治选举例子展示建模过程。

标准形与松弛形

标准形：所有约束 \(\leq\) + 非负变量；松弛形：所有约束等式（每个 \(\leq\) 引入松弛变量）；两者通过加减松弛变量转换。

§29.1；标准形便于人写，松弛形便于算法处理。

基本解与基本可行解

基本解：松弛形中设非基本变量 = 0；基本可行解：基本解且满足非负约束；基本可行解 ⟺ 可行域顶点。

§29.3；单纯形在基本可行解间迭代。

单纯形 pivot

选「进入变量」（非基本变量，正目标系数）与「离开变量」（基本变量，受约束限制最小）；交换两者角色，重写松弛形；目标值不减。

§29.3；PIVOT 操作是单纯形的核心。

LP 对偶 (Duality)

原 LP（primal，最大化）与对偶 LP（dual，最小化）的目标最优值相等；弱对偶：任 primal ≤ 任 dual；强对偶：存在 primal = dual = 最优。

§29.4；定理 29.10；最大流最小割是其特例。

初始基本可行解

用辅助 LP 处理「原点不在可行域」；解辅助问题后回退到原问题；保证单纯形可启动。

§29.5；INITIALIZE-SIMPLEX 是关键预处理。

二、详细笔记

29.1 线性规划的形式化

What：线性规划是「在凸多面体上优化线性函数」；一般形式为「最大化 \(c^T x\) subject to \(Ax \leq b, x \geq 0\)」。

Why：大量现实问题可建模为 LP——资源分配、生产计划、运输、投资组合、选举策略；LP 是组合优化的「母问题」。

How：

一般 LP 定义：

目标：minimize 或 maximize \(\sum c_j x_j\)。
约束：\(\sum a_{ij} x_j \leq b_i\)（或 = 或 ≥）；\(x_j \geq 0\)。
可行解：满足所有约束；最优解：可行且目标值最优。

CLRS 政治选举例子（式 29.6-29.10）：4 个政策（变量）x1-x4，需赢得 5 万城市 / 10 万郊区 / 2.5 万农村选民，最小化广告支出。

可行解与目标函数的几何视图（CLRS 图 29.2）：

可行域 = 约束半空间的交集 = 凸多面体（simplex）。
等值线 \(c^T x = z\) 是超平面；移动超平面至不再与可行域相交时即最优。
关键观察：最优解在顶点处取得——这是 LP 与凸优化的本质特性。

When：连续决策、资源分配、生产计划；任何「线性目标 + 线性约束」的问题。

Example：CLRS 政治选举 LP：最优解 x1=20（道路）、x2=0（枪支）、x3=4（农业）、x4=9（汽油税），最小支出 33 千美元。

29.2 标准形与松弛形

What：标准形（standard form）所有约束是 ≤ 不等式，变量非负；松弛形（slack form）所有约束是等式（不等式通过加松弛变量转换）。

Why：标准形便于人类书写与交流；松弛形便于算法处理（基本解明确）；单纯形法在松弛形上工作。

How：

标准形（式 29.19-29.21）：

\[\text{maximize } c^T x \quad \text{subject to } Ax \leq b,\ x \geq 0\]

松弛形（每个不等式加松弛变量 x_{n+i}）：

\[x_{n+i} = b_i - \sum_{j=1}^{n} a_{ij} x_j, \quad x_{n+i} \geq 0\]

转换规则：

min → max：取负目标函数。
无非负变量 \(x_j\)：替换为 \(x_j' - x_j''\)，两者均 ≥ 0。
等式约束：拆为两个不等式（≤ 和 ≥）。
≥ 不等式：取负转为 ≤。

松弛形的特点：

基本变量（basic）= 等式左边的变量；非基本变量（nonbasic）= 等式右边的变量。
基本解 = 设非基本变量 = 0，从等式解出基本变量。
基本可行解 = 基本解且基本变量 ≥ 0。

When：从问题 → LP（标准形）→ 算法输入（松弛形）；单纯形预处理。

Example：CLRS 政治选举 LP 的松弛形：x5, x6, x7 是松弛变量；基本可行解 (0, 0, 0, 0, 33, …) 等价于原点解。

29.3 单纯形算法

What：单纯形在松弛形上迭代：选「进入变量」与「离开变量」做 pivot，交换两者在基本 / 非基本集合中的角色；目标值不减；终止时所有非基本变量目标系数 ≤ 0 即最优。

Why：单纯形是 LP 求解的工业标准——实践中极快（虽最坏指数）；直观的几何解释（沿可行域顶点移动）便于理解。

How：

迭代流程：

选「进入变量」x_e：目标系数 c_e > 0 的非基本变量（增加 x_e 可改进目标）。
选「离开变量」x_l：受约束限制使 x_e 增大后首先变 0 的基本变量；最小比值规则（min ratio test）确定。
PIVOT(N, B, A, b, c, v, l, e)：交换 x_e 与 x_l 的角色，重写松弛形。

PIVOT 操作（CLRS §29.3）：

解 x_l 的等式得 x_e 表达式（系数 = 1/a_{le}）。
代入其他等式与目标函数。
更新基本 / 非基本集合：x_e 进入 B，x_l 进入 N。

终止条件：

无目标系数为正的「进入变量」⟹ 当前基本可行解最优（目标值 v）。
若所有约束「比值规则」无下界⟹ LP 无界（unbounded）。

复杂度：最坏指数，但实践中极快；平均多项式。

When：标准 LP 求解（除非有内点法更快的特殊情形）；LP 求解器的核心算法。

Example：CLRS §29.3 的 3 变量例子经过 3 次 pivot 收敛到最优 (x1=8, x2=4, x3=0)，目标值 28。

29.4 LP 对偶

What：每个 LP（primal）都有对应「对偶」LP；弱对偶：任意 primal 可行解 ≤ 任意 dual 可行解；强对偶：两者最优值相等。

Why：对偶提供「最优性证明」（找到匹配的 primal/dual 解即证最优）；对偶变量常具「影子价格」的经济意义；最大流最小割是其特例。

How：

对偶构造（式 29.83-29.85）：

原（primal）：

\[\max c^T x \text{ subject to } Ax \leq b,\ x \geq 0\]

对偶（dual）：

\[\min b^T y \text{ subject to } A^T y \geq c,\ y \geq 0\]

弱对偶（引理 29.8）：任 primal \(\bar x\)、dual \(\bar y\) 可行，\(c^T \bar x \leq b^T \bar y\)。

强对偶（定理 29.10）：若 primal 与 dual 都可行，则最优值相等。

从单纯形读对偶解（式 29.91）：

终止时基本集合 B 中的松弛变量索引 n+i 对应 dual 变量 \(\bar y_i = -c'_{n+i}\)；否则 \(\bar y_i = 0\)。
dual 目标值 = primal 目标值 = 最优值。

最大流最小割作为 LP 对偶：最大流 LP 的对偶是最小割 LP。

When：验证 LP 解的最优性；用对偶变量做灵敏度分析（影子价格）；理论分析 LP 结构。

Example：CLRS §29.3 例子终止时，dual 解 \(\bar y = (0, 1/6, 2/3)\)，dual 目标值 = 30·0 + 24·(1/6) + 36·(2/3) = 28 = primal 目标值。

29.5 初始基本可行解

What：单纯形需要「原点是基本可行解」才能启动；若原 LP 的 b 含负值，则原点不在可行域；用「辅助 LP」找到初始基本可行解。

Why：现实 LP 的约束 b 常含负值（如「库存约束 ≥ 某值」）；直接设 x = 0 不可行；需要特殊处理。

How：

辅助 LP 构造：

加新变量 x_0 = 自由变量；修改约束：\(x_{n+i} = -b_i - x_0 + \sum a_{ij} x_j\)（对所有 i）。
目标：minimize x_0；若最优 x_0 = 0 则原 LP 可行；否则无可行解。

求解流程（CLRS 算法）：

INITIALIZE-SIMPLEX(A, b, c)：
1. 构造辅助 LP L_aux。
2. 选 b 中最负的 b_l 作为「初始枢轴」。
3. 在辅助 LP 上跑单纯形。
4. 若 L_aux 最优 x_0 > 0：原 LP 不可行。
5. 否则：从辅助解回退到原 LP 的初始基本可行解（可能需额外 pivot 调整）。

When：原 LP 中 b 含负值；或任意 LP 求解前的预处理；保证单纯形可启动。

Example：若原 LP 约束为 \(Ax \geq b\)，先取负为 \(-Ax \leq -b\)，但 b' = -b 可能含正；若原约束是等式或 ≥，需要更多变换。

29.6 LP 算法与复杂度

What：单纯形法（指数最坏）vs 椭球法（多项式但慢）vs 内点法（多项式且快）；实践中单纯形 + 内点法混合使用。

Why：理解不同 LP 算法的特性有助于选择工具；工业 LP 求解器（CPLEX、Gurobi）集成多种算法。

How：

算法对比：

单纯形：沿顶点移动；实践中极快，最坏指数；适合小到中等规模。
椭球法（Khachiyan 1979）：第一个多项式 LP 算法；实践中很慢；纯理论意义。
内点法（Karmarkar 1984）：沿可行域内部移动；多项式且实践中快；适合大规模稀疏 LP。

复杂度理论：

LP 在 P 中（内点法）。
整数线性规划（ILP）是 NP-hard；仅找可行解也是 NP-hard（CLRS 练习 34.5-3）。

实际工具：CPLEX（IBM）、Gurobi（商业）；GLPK、lp_solve（开源）；SciPy.optimize.linprog（Python）。

When：选择 LP 求解器；理解 LP 与 ILP 的根本区别；大规模优化问题的预处理。

Example：Netflix 用 LP 优化推荐系统的资源分配；航空公司用 ILP（带整数约束的 LP）排班；整数约束使 ILP NP-hard。

三、关键图表

核心公式对照表

公式编号

内容

式 29.1-29.5

政治选举 LP 的约束与目标

式 29.6-29.10

政治选举 LP 的标准形

式 29.16-29.18

标准形一般定义

式 29.19-29.21

紧凑形式 \(c^T x, Ax \leq b, x \geq 0\)

式 29.53-29.57

单纯形例题 LP

式 29.58-29.61

单纯形例题松弛形

式 29.62-29.67

第一次 pivot 后形式

式 29.83-29.85

对偶 LP：minimize \(b^T y\) subject to \(A^T y \geq c\)

式 29.86-29.90

对偶例题

式 29.91

从单纯形终止读对偶解 \(\bar y_i = -c'_{n+i}\)

引理 29.1

PIVOT 后基本解的更新

引理 29.8

弱对偶：任 primal ≤ 任 dual

推论 29.9

primal = dual = 最优的等价条件

定理 29.10

强对偶：LP 最优值 = 对偶最优值

四、思维导图

mindmap
  root((第 29 章 线性规划))
    形式化
      目标函数
      线性约束
      可行域
      凸多面体
    标准松弛形
      标准形不等式
      松弛形等式
      转换规则
      基本变量
    单纯形算法
      初始基本解
      pivot操作
      进入离开变量
      最坏指数
    LP对偶
      弱对偶
      强对偶
      影子价格
      最优性证明
    初始基本解
      辅助LP
      x₀变量
      回退原问题
      可行性判定
    算法对比
      单纯形
      椭球法
      内点法
      整数LP

五、重点与易错点

LP 与 ILP 的根本区别：LP 是多项式可解的（内点法）；ILP 是 NP-hard。整数约束让问题变得极难。
最优在顶点取得是 LP 的核心性质：源于凸性 + 线性——任何 LP 都有顶点最优解（若最优存在）。
标准形与松弛形的转换：标准形便于人写，松弛形便于算法。两者等价（同一问题的两种表示）。
基本解 vs 基本可行解：基本解设非基本 = 0；基本可行解还需基本变量 ≥ 0。单纯形在「基本可行解」间迭代。
pivot 操作的「最负比值规则」(min ratio test)：决定进入变量增大到何时停止——第一个基本变量变 0 时停止。
单纯形最坏指数但实践快：构造 Klee-Minty 立方体可达指数；实践中几乎所有 LP 都在多项式时间内解出。
LP 对偶不是「两个问题」：对偶 LP 与原 LP 是同一优化问题的两个视角；强对偶说它们的最优值相等。
影子价格：dual 变量 \(y_i\) 是约束 i 右端 b_i 变化对最优目标值的影响率——经济学 / 灵敏度分析核心。
最大流最小割是 LP 对偶：原（最大流）LP 与对偶（最小割）LP 等价；与第 26 章一致。
单纯形同时解原与对偶：终止时基本集合中松弛变量对应的对偶系数 = primal 目标系数；可同时验证最优性。
初始基本可行解：辅助 LP 的「x_0 = minimize」是处理 b 含负值的关键技巧；解后回退到原问题。
整数 LP 是 NP-hard：仅找可行解也是 NP-hard（CLRS 34.5-3）；整数约束极大增加难度。
LP 应用：资源分配、运输、投资组合、生产计划、网络流、机器学习线性模型；是运筹学的核心工具。
与第 24 章差分约束的衔接：差分约束是 LP 的一种特殊情形（约束皆 ≤ 0）；用 Bellman-Ford 解（与单纯形等价但更专用）。
与第 35 章近似算法的衔接：LP 松弛 + 舍入是近似算法的核心技术；很多 NP-hard 问题的最优近似比来自 LP 对偶。

第 29 章 线性规划 (Linear Programming)

核心结论

一、核心概念

二、详细笔记

29.1 线性规划的形式化

29.2 标准形与松弛形

29.3 单纯形算法

29.4 LP 对偶

29.5 初始基本可行解

29.6 LP 算法与复杂度

三、关键图表

四、思维导图

五、重点与易错点

第 29 章线性规划 (Linear Programming)