4.3 线性规划 – 李云浩的博客

本文最后更新于120 天前，其中的信息可能已经过时，如有错误请发送邮件至 2641805259@qq.com

一、线性规划及标准形式

1. 核心定义

线性规划（Linear Programming, LP）是一类特殊的凸优化问题，其核心特征包括：目标函数为仿射函数（即线性函数加常数项），约束函数同样为仿射函数，且可行集是由线性等式和不等式约束共同界定的多面体。

2. 主要形式

一般形式：

\begin{aligned} \text{minimize} & \quad c^Tx + d\\ \text{subject to} & \quad Gx \preceq h\\ & \quad Ax = b \end{aligned}

线性规划是凸优化问题。

显然目标函数中的 $d$ 并不会影响最优点 $x^*$ ，因此可以简化为一下两种形式：

标准形式：仅有的不等式都是分量的非负约束 $x \geq 0$ 。
$\begin{aligned} \text{minimize} & \quad c^Tx\\ \text{subject to} & \quad AX = b\\ & \quad x \succeq 0 \end{aligned}$
不等式形式：约束条件仅为线性不等式约束 $Ax \preceq b$ 。
$\begin{aligned} \text{minimize} & \quad c^Tx\\ \text{subject to} & \quad AX \preceq b \end{aligned}$

3. 形式转换方法

（1）一般形式转标准形式

给定一般形式的线性规划问题，转换步骤如下：

引入松弛变量 $s$ ：
$\begin{aligned} \text{minimize} & \quad c^Tx + d\\ \text{subject to} & \quad Gx + s = h\\ & \quad Ax = b\\ & \quad s \succeq 0 \end{aligned}$
处理无符号约束的变量 $x$ ，令 $x = x^+ - x^-$ ，其中 $x^+ \succeq 0$ 且 $x^- \succeq 0$ ；
$\begin{aligned} \text{minimize} & \quad c^Tx^+ - c^T x^- + d\\ \text{subject to} & \quad Gx + s = h\\ & \quad Ax^+ - AX^- = b\\ & \quad s \succeq 0, x^+ \succeq 0, x^- \succeq 0 \end{aligned}$
转换后，目标函数变为 $\min c^T x^+ - c^T x^- + d$ ，约束条件变为 $Ax^+ - Ax^- = b$ 、 $x^+ \succeq 0$ 、 $x^- \succeq 0$ 和 $s \succeq 0$ 。

（2）典型问题转换示例

饮食问题：目标是最小化总成本 $c^T x$ ，约束条件为满足营养素需求 $Ax \geq b$ 且食物数量 $x \geq 0$ ，该问题可直接对应不等式形式的线性规划，仅需根据实际约束调整符号即可。
分段线性最小化问题：原始问题为 $\min \max_{i=1,...,m}(a_i^T x + b_i)$ ，引入辅助变量 $t$ 后，可转化为目标函数 $\min t$ ，约束条件为 $t \geq a_i^T x + b_i$ （ $i=1,...,m$ ）的线性规划。
带非负项求和的问题：原始问题为 $\min \sum_{i=1}^m \max\{0, a_i^T x + b_i\}$ ，引入辅助变量 $t_i \geq 0$ ，约束条件设为 $t_i \geq a_i^T x + b_i$ （ $i=1,...,m$ ），目标函数则变为 $\min \sum_{i=1}^m t_i$ ，从而转化为线性规划。
多面体包含性判断问题：需验证 $P_1 = \{x|Ax \preceq b\}$ 是否包含于 $P_2 = \{x|Cx \preceq d\}$ ，可构建线性规划：目标函数 $\min z$ ，约束条件为 $Ax \preceq b$ 、 $Cx \leq d + z \cdot 1_p$ （其中 $1_p$ 是 $p$ 维全 1 向量）且 $z \in \mathbb{R}$ 。若求得的最优值 $z^* > 0$ ，则 $P_1$ 不包含于 $P_2$ ；若 $z^* \leq 0$ ，则 $P_1 \subseteq P_2$ 。

二、线性规划问题的解

1. 解的四种结局

线性规划问题求解后，可能出现四种结果：一是存在唯一最优解；二是存在无穷多最优解；三是无界解，即目标函数可无限减小；四是无解，即不存在可行解，可行集为空集。

2. 求解方法

（1）图解法

图解法适用于二维变量的线性规划问题，具体步骤如下：

根据所有约束条件，在二维坐标系中绘制出可行域，可行域通常为多面体形状；
绘制目标函数的等高线，等高线的斜率由目标函数的系数决定；
沿着目标函数值减小（或增大，根据优化方向）的方向移动等高线，找到与可行域相切或相交的极值点，该极值点即为最优解。

示例：已知约束条件为 $2x_1 + x_2 \leq 1$ 和 $x_1 + 3x_2 \leq 1$ ，针对不同目标函数的求解结果如下：

当目标函数为 $(a) \min -x_1 - x_2$ 时，最优解为 $(0.4, 0.2)$ ，最优值为 $-0.6$ ；
当目标函数为 $(b) \min x_1 + x_2$ 时，最优值为 $0$ ；
当目标函数为 $(c) \min x_1$ 时，最优解集为 $\{(0, x_2) | x_2 \leq \frac{1}{3}\}$ ；
当目标函数为 $(d) \min - \min\{x_1, x_2\}$ 时，最优解为 $(\frac{1}{4}, \frac{1}{4})$ 。

（2）解析解（特殊情况）

对于方阵线性规划问题，即约束条件中的矩阵 $A$ 为非奇异方阵，问题形式为 $\min c^T x$ ，约束 $Ax \leq b$ ，求解步骤如下：

进行变量变换，令 $y = Ax$ ，则原问题可转化为 $\min c^T A^{-1} y$ ，约束条件为 $y \leq b$ ；
最优值的计算分为两种情况：若 $A^{-T} c \leq 0$ ，则最优值 $p^* = c^T A^{-1} b$ ；否则，该线性规划问题的最优解无下界，即 $p^* = -\infty$ 。

（3）鲁棒线性规划（区间系数）

考虑区间系数的鲁棒线性规划问题：目标函数 $\min c^T x$ ，约束条件为 $Ax \preceq b$ （对所有 $A \in \mathcal{A}$ 成立），其中 $\mathcal{A} = \{A | \overline{A}_{ij} - V_{ij} \leq A_{ij} \leq \overline{A}_{ij} + V_{ij}\}$ （ $\overline{A}$ 和 $V$ 为给定矩阵）。该问题可等价转换为：目标函数 $\min c^T x$ ，约束条件为 $\overline{A}x + V y \preceq b$ 和 $-y \preceq x \preceq y$ （其中 $y \geq 0$ ，且最优解满足 $y^* = |x|$ ）。

三、广义线性规划问题

1. 线性分式规划

（1）定义

在多面体上极小化仿射函数之比的问题称为线性分式规划：

\begin{aligned} \text{minimize} & \quad \frac{c^Tx + d}{e^Tx + f}, \quad \textbf{dom} f_0 = \{x | e^Tx + f > 0\} \\ \text{subject to} & \quad Gx \preceq h\\ & \quad Ax = b \end{aligned}

这个目标函数是拟凸的（并且是拟线性的），因此线性分式规划是一个拟凸优化问题。

（2）等价转换

如果可行集

\{x | Gx \preceq h, Ax = b, e^Tx + f > 0\}

非空，线性分式规划可以转换为等价的线性规划

\begin{aligned} \text{minimize} & \quad c^Ty + dz\\ \text{subject to} & \quad Gy - hz \preceq 0\\ & \quad Ay - bz = 0\\ & \quad e^Ty + fz = 1\\ & \quad z \geq 0 \end{aligned}

其优化变量为 $y, z$ 。

等价性说明：

如果 $x$ 是可行解，那么
$y = \frac{x}{e^Tx + f}, \quad z = \frac{1}{e^Tx + f}$
也是可行解，并且有 $f_0(x) = c^T y + dz$ .

2. 布尔线性规划的松弛

（1）原始问题

布尔线性规划的目标函数为 $\min c^T x$ ，约束条件为 $Ax \preceq b$ 和 $x_i \in \{0,1\}$ （ $i=1,...,n$ ），即变量的每个分量只能取 0 或 1。

（2）松弛问题

对布尔线性规划进行松弛，得到的松弛问题目标函数仍为 $\min c^T x$ ，约束条件调整为 $Ax \preceq b$ 和 $0 \leq x_i \leq 1$ （ $i=1,...,n$ ）。需要注意的是，松弛问题的最优解也是原布尔线性规划的最优解。

3. 关键定理

凸包上的线性最小化等价性定理：对于集合 $X \subset \mathbb{R}^m$ 和向量 $c \in \mathbb{R}^m$ ，有 $\inf_{x \in conv X} c^T x = \inf_{x \in X} c^T x$ ，其中 $conv X$ 表示集合 $X$ 的凸包。同时，等式左侧（即在凸包上的下确界）可达的充分必要条件是等式右侧（即在原集合 $X$ 上的下确界）可达。

该定理的证明核心在于：凸包 $conv X$ 中的任意一点 $\bar{x}$ 都可表示为集合 $X$ 中若干点的凸组合，即 $\bar{x} = \sum_{i=1}^{m} \alpha_{i} x_{i}$ （其中 $x_1,...,x_m \in X$ ， $\alpha_1,...,\alpha_m \geq 0$ 且 $\sum_{i=1}^{m} \alpha_{i}=1$ ）。由于 $c^T x_i \geq \inf_{x \in X} c^T x$ ，可得 $c^T \overline{x} = \sum_{i=1}^{m} \alpha_{i} c^T x_{i} \geq (\sum_{i=1}^{m} \alpha_{i}) \inf_{x \in X} c^T x = \inf_{x \in X} c^T x$ 。对不等式左边在 $\bar{x} \in conv X$ 上取下确界，可得 $\inf _{\overline{x} \in conv X} c^T \overline{x} \geq \inf _{x \in X} c^T x$ 。又因为 $X \subset conv X$ ，所以 $\inf _{x \in conv X} c^T x \leq \inf _{x \in X} c^T x$ ，综合两方面可证得等式成立。此外，通过分析最优解的存在性，可得出等式两侧下确界可达性的等价关系。