张叶安的小站

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 第十一章 线性规划基础 ======

===== 本章导读 =====

线性规划（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$$

---

*本章完*