目录
第十一章 线性规划基础
本章导读
线性规划（Linear Programming, LP）是最优化方法中最成熟、应用最广泛的分支之一。由于目标函数和约束都是线性的，线性规划问题具有特殊的几何结构和性质。本章介绍线性规划的标准形式、几何性质和基本可行解的概念。
11.1 线性规划问题
11.1.1 一般形式
线性规划问题的一般形式为：
$$\begin{aligned}
\min \quad & \mathbf{c}^T \mathbf{x}
\text{s.t.} \quad & a_{i1}x_1 + \cdots + a_{in}x_n \leq b_i, \quad i = 1, \ldots, m_1
& a_{j1}x_1 + \cdots + a_{jn}x_n \geq b_j, \quad j = m_1+1, \ldots, m_2
& a_{k1}x_1 + \cdots + a_{kn}x_n = b_k, \quad k = m_2+1, \ldots, m
& x_j \geq 0, \quad j \in J \subseteq \{1, \ldots, n\}
\end{aligned}$$
11.1.2 标准形式
定义 11.1（标准形式）
线性规划的标准形式为：
$$\begin{aligned}
\min \quad & \mathbf{c}^T \mathbf{x}
\text{s.t.} \quad & A\mathbf{x} = \mathbf{b}
& \mathbf{x} \geq \mathbf{0}
\end{aligned}$$
其中 $A$ 是 $m \times n$ 矩阵（$m \leq n$），$\text{rank}(A) = m$。
转化为标准形式的方法：
- 最大化 $\rightarrow$ 最小化：$\max \mathbf{c}^T\mathbf{x} \Leftrightarrow \min (-\mathbf{c})^T\mathbf{x}$
- 不等式 $\rightarrow$ 等式：引入松弛变量或剩余变量
- $\sum a_{ij}x_j \leq b_i$：加松弛变量 $s_i \geq 0$
- $\sum a_{ij}x_j \geq b_j$：减剩余变量 $s_j \geq 0$
- 自由变量：$x_j = x_j^+ - x_j^-$，$x_j^+, x_j^- \geq 0$
例 11.1
将下列问题化为标准形式：
$$\begin{aligned}
\max \quad & 3x_1 + 2x_2
\text{s.t.} \quad & x_1 + x_2 \leq 4
& x_1 - x_2 \geq 1
& x_1 \geq 0
\end{aligned}$$
解： 1. 目标：$\min -3x_1 - 2x_2$ 2. 约束1：$x_1 + x_2 + s_1 = 4$，$s_1 \geq 0$ 3. 约束2：$x_1 - x_2 - s_2 = 1$，$s_2 \geq 0$ 4. $x_2 = x_2^+ - x_2^-$，$x_2^+, x_2^- \geq 0$
11.2 线性规划的几何性质
11.2.1 凸多面体
定义 11.2（凸多面体）
满足 $A\mathbf{x} = \mathbf{b}$，$\mathbf{x} \geq \mathbf{0}$ 的点集称为凸多面体（Convex Polytope）。
定理 11.1
线性规划的可行域是凸多面体（如果非空）。
11.2.2 顶点与极值点
定义 11.3（极值点/顶点）
点 $\mathbf{x} \in \mathcal{F}$ 称为极值点（Extreme Point），若不能表示为 $\mathcal{F}$ 中两个不同点的凸组合。
定理 11.2（极值点的代数刻画）
$\mathbf{x}$ 是可行域的极值点 $\Leftrightarrow$ 存在基 $B$ 使得 $\mathbf{x} = \begin{bmatrix} \mathbf{x}_B
\mathbf{x}_N \end{bmatrix} = \begin{bmatrix} B^{-1}\mathbf{b}
\mathbf{0} \end{bmatrix} \geq \mathbf{0}$
11.2.3 最优解的位置
定理 11.3（线性规划基本定理）
对于线性规划标准形式： 1. 若可行域非空，则存在极值点 2. 若存在最优解，则至少有一个极值点是最优解 3. 若目标函数在可行域上无下界，则无有限最优解
11.3 基本可行解
11.3.1 基与基本解
设 $A$ 是 $m \times n$ 矩阵，$\text{rank}(A) = m$。
定义 11.4（基）
选择 $A$ 的 $m$ 个线性无关列构成 $m \times m$ 可逆矩阵 $B$，称为基矩阵。其余列构成 $N$。
对应变量分为：
- 基变量 $\mathbf{x}_B$（$m$ 个）
- 非基变量 $\mathbf{x}_N$（$n-m$ 个）
定义 11.5（基本解）
令 $\mathbf{x}_N = \mathbf{0}$，解得 $\mathbf{x}_B = B^{-1}\mathbf{b}$，称为关于基 $B$ 的基本解。
定义 11.6（基本可行解）
若 $\mathbf{x}_B = B^{-1}\mathbf{b} \geq \mathbf{0}$，则称为基本可行解（Basic Feasible Solution, BFS）。
11.3.2 退化与非退化
定义 11.7（退化）
若基本可行解中某个基变量为零，则称其为退化的（Degenerate）。
11.4 单纯形法的几何解释
单纯形法的基本思想： 1. 从一个基本可行解（极值点）出发 2. 检查是否最优 3. 若不是最优，则沿着可行域的边移动到相邻的更好的极值点 4. 重复直到最优
11.5 习题
理论题
1. 证明：线性规划可行域的极值点对应基本可行解。
2. 举例说明退化基本可行解。
3. 证明：若线性规划有最优解，则必在某极值点达到。
计算题
4. 将下列问题化为标准形式：
$$\max 2x_1 + 3x_2 - x_3 \quad \text{s.t.} \quad x_1 + 2x_2 \leq 5, \quad x_1 - x_3 \geq 2, \quad x_2 \geq 0$$
5. 求下列约束的所有基本可行解：
$$x_1 + x_2 + x_3 = 2, \quad x_1, x_2, x_3 \geq 0$$
—
*本章完*