线性规划

一、LP标准型

1、问题模型——线性规划

对于如下约束数学规划模型：

$$\begin{aligned}\max & f(\boldsymbol{x}) \quad(\text { 或 } \min f(\boldsymbol{x})), \quad \boldsymbol{x} \in \mathbb{R}^{n} \\\text { s.t. } & h_{i}(\boldsymbol{x})=0, i=1,2, \cdots, l \\& g_{j}(\boldsymbol{x}) \leq 0, j=1,2, \cdots, m\end{aligned}$$

若$f(\boldsymbol{x}),h_{i}(\boldsymbol{x}),g_{j}(\boldsymbol{x})$全为线性函数，则称上述约束优化问题为线性规划 (Linear Programming， LP)。

特点：

• 目标函数求极大(极小)；
• 约束可能有等式约束, 也可能有不等式约束；
• 决策变量有的受非负约束, 有的无任何限制。

2、模型预处理——标准化

这些特点不便于我们进行求解，因此要对原问题进行标准化。得到LP的标准形式，简称 LP 标准型：

$$\begin{aligned}\min & z=\sum_{j=1}^{n} c_{j} x_{j} \\\text { s.t. } & \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad i=1,2, \cdots, m \\& x_{j} \geq 0, \quad j=1,2, \cdots, n\end{aligned}$$

该标准型要求：

• 目标函数求最小值；
• 约束条件均为等式；
• 所有决策变量均为非负。

对于一般的LP问题，将其转化为标准型的步骤如下：

1. 若所求为目标函数极大值，对目标函数取负，变为求极小值：$\max z \rightarrow \min -z=-\sum_{j=1}^{n} c_{j} x_{j}$。
2. 若决策变量$x_{j} \geq d_{j}\left(d_{j} \neq 0\right)$，创建一个新变量，令$x_{n+1}=x_{j}-d_{j}$，则$x_{n+1} \geq 0$。
3. 若决策变量$x_{j} \leq 0$，创建一个新变量，令$x_{n+1}=-x_{j}$，则$x_{n+1} \geq 0$。
4. 若存在不等式约束：$\sum_{i=1}^{n} a_{i j} x_{j} \leq b_{i}$，新建一个松弛变量$x_{n+1}$，则转化为等式约束$\sum_{i=1}^{n} a_{i j} x_{j}+x_{n+1}=b_{i}, x_{n+1} \geq 0$。
5. 若存在不等式约束：$\sum_{i=1}^{n} a_{i j} x_{j} \geq b_{i}$，新建一个剩余变量$x_{n+1}$，则转化为等式约束$\sum_{i=1}^{n} a_{i j} x_{j}-x_{n+1}=b_{i}, x_{n+1} \geq 0$。

转化为标准型后，为了方便计算，保留关键信息，将LP问题表达为矩阵形式：

$$\min z=\boldsymbol{C}^{1} \boldsymbol{X} \quad \text { s.t. } \boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}, \boldsymbol{X} \geq \mathbf{0}$$

其中：$$\boldsymbol{C}=\left(c_{1}, c_{2}, \cdots, c_{n}\right)^{\mathrm{T}}, \quad \boldsymbol{X}=\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{\mathrm{T}} \
\boldsymbol{A}=\left(a_{i j}\right){m \times n}, \boldsymbol{b}=\left(b{1}, b_{2}, \cdots, b_{m}\right)^{\mathrm{T}}$$
完成了对模型的预处理，下面我们开始求解该问题。

3、基本原理

首先，对于一个标准的LP问题，$\min z=\boldsymbol{C}^{1} \boldsymbol{X} \quad \text { s.t. } \boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}, \boldsymbol{X} \geq \mathbf{0}$，有以下基本概念：

• 基矩阵：约束系数矩阵 $\boldsymbol{A}$ 是 $m × n$ 矩阵, $m ≤ n$, 并且 $r (\boldsymbol{A}) = m$。于是 $\boldsymbol{A}$ 中至少有一个维数为 $m × m$ 的子矩阵$\boldsymbol{B}$, 使得 $r (\boldsymbol{B}) = m$。即 $\left | \boldsymbol{B} \right | \ne 0$,则称 $\boldsymbol{B}$ 是 LP 问题的一个基矩阵 (简称为基)。当 $m = n$ 时, 基矩阵唯一；当 $m < n$ 时, 基矩阵就可能有多个, 但数目不超过 $C_{n}^{m}$ 个。
• 基向量: 基矩阵对应的列向量称为基向量, 其余列向量称为非基向量。
• 基变量: 基向量对应的变量称为基变量, 非基向量对应的变量称为非基变量 (自由变量)。
• 基本解: 对于某一确定的基 $\boldsymbol{V}$ , 选定基变量和自由变量, 用自由变量表示基变量, 写出同解方程组。令所有自由变量等于零, 求出$\boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}$ 的解, 称这组解为关于基 $\boldsymbol{V}$ 的基本解。
• 基可行解: 非负的基本解称为基可行解 (基本可行解)。

先说结论：设约束线性方程组 $\boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}$ 的系数矩阵 $\boldsymbol{A}$ 的秩 $r (\boldsymbol{A}) = m$, 记增广矩阵为 $(\boldsymbol{A}, \boldsymbol{b})$, 则以下结论成立:若系数矩阵 $\boldsymbol{A}$ 中存在 $m$ 阶单位子块, 且对应的常数项非负, 那么从增广矩阵中便可读出一个基本可行解。其中, 基变量的取值为单位子块中 1 所对应的右边常数项的值, 自由变量取值全为零。

具体推导过程通过一个例题说明。
例：
求$$\begin{array}{cl}\min & z=x_{1}-3 x_{2}+2 x_{3}+4 x_{4} \\text { s.t. } & 2 x_{1}-4 x_{3}+x_{4}=6 \& -x_{1}+x_{2}+3 x_{3}=5 \& x_{j} \geq 0, j=1, \cdots, 4\end{array}$$的一个基本解和一个基本可行解。

解：
约束方程的增广矩阵$$(\boldsymbol{A}, \boldsymbol{b})=\left(\begin{array}{ccccc}
2 & 0 & -4 & 1 & 6 \
-1 & 1 & 3 & 0 & 5
\end{array}\right)$$
注意到 $\boldsymbol{A}$ 是 $2 \times 4$ 矩阵， $r(\boldsymbol{A})=2$ 。
由于第 $2$ 列和第 $4$ 列线性无关，构成一个 $2$ 阶单位子块，因此可构成一个基矩阵。
取 $x_{2}, x_{4}$ 为基变量， $x_{1}, x_{3}$ 为自由变量，用自由变量表示基变量可得如下同解方程组：

$$\left\{\begin{array}{l} x_{2}=5+x_{1}-3 x_{3} \\ x_{4}=6-2 x_{1}+4 x_{3} \end{array}\right.$$

令 $x_1 = x_3 = 0$ 得: $x_2 = 5, x_4 = 6$。
于是，可得一个基本解：$\boldsymbol{x}=(0,5,0,6)^{T}$
又因 $x \geq 0$，所以也是一个基本可行解。

线性规划的基本定理：
考虑标准形式的线性规划问题

$$\begin{array}{|l|} \hline \min z=\boldsymbol{C}^{\mathrm{T}} \boldsymbol{X} \\ \text { s.t. } \boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}, \quad \boldsymbol{X} \geq \mathbf{0} \\ \hline \end{array}$$

其中， $\boldsymbol{X}=\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{\mathrm{T}} \in \mathbb{R}^{n}, \boldsymbol{b}=\left(b_{1}, b_{2}, \cdots, b_{m}\right)^{\mathrm{T}} \in \mathbb{R}^{m} ， r(\boldsymbol{A})=m<n$ ，则：
（1）线性规划问题若有可行解，那么一定有基本可行解。
（2）线性规划问题若有最优解，则一定有最优的基本可行解。

二、单纯形法

单纯形法 (Simplex Method) 由 G.B.Dantzig 于 1947 年提出。该算法主要思想是, 从具有标准形的 LP 模型的一个基可行解出发, 判断其是否是最优。如果是最优解, 结束运算; 否则, 设法找到一个更优 (使目标函数值减小) 的基本可行解。如此继续, 经过有限次迭代, 就可以找到 LP 的最优解或判别 LP 问题有没有最优解。

1、单纯形表与容许运算

在上面，我们已经能够根据增广矩阵计算出基本可行解，那么如何判断其是否为最优解呢？

单纯形表：
对于这样一个线性规划问题$\min z=\boldsymbol{C}^{1} \boldsymbol{X} \quad \text { s.t. } \boldsymbol{A} \boldsymbol{X}=\boldsymbol{b}, \boldsymbol{X} \geq \mathbf{0}$，我们可以写出它的单纯形表：

$$\begin{array}{|c|c|}\hline \text { 中心部位 } & \text { 右列 } \\ \boldsymbol{A} & \boldsymbol{b} \\\hline \text { 底行（检验行）} & \text { 右下端 } \\ \boldsymbol{C}^{T} & -z_{0}\\\hline\end{array}$$

容许运算：

1. 底线以上的行可进行初等行变换 (三种);
2. 底线以上的行乘常数后加至底行 (包括右下端)。
3. 终止条件 (最优性条件)。当表格具备如下特点:
   ①中心部位具有 m 阶单位子块；
   ②右列元素非负；
   ③底行中对应于单位子块位置的元素为 0, 即目标函数中基变量的系数为零；
   ④底行其他元素非负（自由变量对应的元素非负），则从表格中即可读得 LP 问题的最优解和最优值。
   满足①②时，可读出基本可行解。
   满足①②③④时，可断定该基本可行解是最优解。
   满足①②③，但不满足④时，可判定该基本可行解不是最优解。

最优解及最优值的读法:
单位子块中 1 所在列对应的变量为基变量, 其值取相应右列的值, 0对应的其余变量为自由变量, 且其取值为零, 将它们按照顺序写成一个列向量即为一个最优解。此时, 右下端元素的相反数即为最优值。

2、基可行解的转换

在最优性条件的判断中，我们读出的基本可行解可能不是最优解，即满足①②③，但不满足④。因此需要对当前单纯形表进一步转换，使函数值下降。

设当前表格已具备①②③三个特点，但④不满足：

$$\begin{array}{|cccc|c|} \hline \widetilde{a_{11}} & \widetilde{a_{12}} & \cdots & \widetilde{a_{1 n}} & \widetilde{b_{1}} \\ \vdots & \vdots & & \vdots & \vdots \\ \widetilde{a_{m 1}} & \widetilde{a_{m 2}} & \cdots & \widetilde{a_{m n}} & \widetilde{b_{m}} \\ \hline \widetilde{c_{1}} & \widetilde{c_{2}} & \cdots & \widetilde{c_{n}} & -\widetilde{z} \\ \hline\end{array}$$

转换步骤：

1. 进基变量的确定：从底行中任选一个负元素，例如令 $\widetilde{c}_{j}=\min \left\{\widetilde{c}_{l} \mid \widetilde{c}_{l}<0\right\}$ ，则 $\widetilde{c}_{j}$ 对应的 $x_{j}$ 取为进基变量。
2. 离基变量的确定：从所选元素 $\widetilde{c}_{j}$ 所在的第 $j$ 列底线以上的正元素中，按＂最小比例原则＂（ $\theta$ 原则）选取一个，并记为 $\widetilde{a_{k j}}$ ，其中 $\widetilde{a_{k j}}$ 满足：$$\frac{\widetilde{b_{k}}}{\widetilde{a_{k j}}}=\min \left{\left.\frac{\widetilde{b_{i}}}{\widetilde{a_{i j}}} \right\rvert, \widetilde{a_{i j}}>0, i=1,2, \cdots, m\right}$$
3. 进行旋转运算：利用容许运算将 $\widetilde{a_{k j}}$ 变为 1 ，该列其它元素（包括底行相应的元素）变为 0 ，从而实现将 $x_{j}$ 变为基变量的目的。

这样，我们就能确定一个新的基本可行解，继续对其进行条件①②③④的判定，若满足，则得到最优解，否则继续进行迭代。

3、改进的单纯形法

若迭代过程中右列元素中出现 0 ，此时对应的基本可行解中某基变量的取值为 0 ，则称该基本可行解是退化的，后续迭代可能出现循环。解决办法：选进基变量时，选底行中最左边第一个负元素对应的变量为进基变量，这就是改进的单纯形法。

改进的单纯形法：

1. 将 LP 问题化为 LP 标准型，写出相应的矩阵形式；

2. 建立满足①②③三个特点的初始单纯形表：

   • 若单纯形表满足①②③，直接进入 Step 3；
   • 若单纯形表满足①②，但③不满足，则利用容许运算将底线以上行的若干倍加到底行，使③满足；
   • 若单纯形表不满足①②，则借助大 M 法使①②满足，然后再使③满足。

3. 若底行元素全非负，则得到最优解，结束运算，否则转 Step 4；

4. 确定进基变量：从底行中选取左侧第一个负元素$\widetilde{c}_{j}$，则$\widetilde{c}_{j}$对应的$x_{j}$取为进基变量。

5. 确定离基变量：从所选元素$\widetilde{c}_{j}$所在的第$j$列底线以上的正元素中按＂最小比例原则＂选取一个，记为$\widetilde{a_{k j}}$，其中$\widetilde{a_{k j}}$满足：

   $$\frac{\widetilde{b_{k}}}{\widetilde{a_{k j}}}=\min \left\{\left.\frac{\widetilde{b_{i}}}{\widetilde{a_{i j}}} \right\rvert\, \widetilde{a_{i j}}>0, i=1,2, \cdots, m\right\}$$

6. 进行旋转运算：利用容许运算将$\widetilde{a_{k j}}$变为 1 ，该列其它元素（包括底行相应的元素）变为 0 ，从而实现将$x_{j}$变为基变量的目的。

7. 观察得到的新表是否满足①②③。同时，若底行所有元素均非负，也即④满足，则已得最优解，结束运算；否则，返回 Step 4。

   • 若最终表格中底行元素均非负，且所有自由变量（非基变量）对应的底行元素（检验数）均大于 0 ，则此时 LP 有唯一最优解。
   • 若最终表格中底行元素均非负，且存在某自由变量（非基变量）对应的底行元素（检验数）等于 0 ，则此时 LP 有无穷多最优解。
   • 若最终表格中底行存在负元素，且对应进基变量所在的列中底线以上没有正元素（无法继续迭代），则此 LP 问题无最优解。

4、收敛性定理

在已知一个基本可行解（初始基本可行解）的前提下使用单纯形法求解 LP 问题时，若每次迭代得到的基本可行解中基变量均大于零（称非退化的），则算法必在有限步后终止。

三、大M法（人工变量法一）

1、基本原理

问题背景：试图使用单纯形法求解LP问题时，发现若单纯形表不满足①②，即原 LP 问题的初始基本可行解不易找出或不存在。此时需要通过引入人工变量来解决。

基本思想：

1. 首先利用容许运算使②满足，即使右列元素非负；
2. 然后在中心部位人工添加一些单位列向量，使中心部位具有 m 阶单位子块，使①满足；
3. 其次修改目标函数，从而得到新的 LP 模型；
4. 最后用单纯形法求解新 LP 模型而得到原 LP 模型的最优解。

对于 LP 问题：$$\min z=\boldsymbol{C}^{T} \boldsymbol{x}=\sum_{j=1}^{n} c_{j} x_{j} \quad s.t. \left{\begin{array}{l}\boldsymbol{A} \boldsymbol{x}=\boldsymbol{b} \ \boldsymbol{x} \geq 0\end{array}\right.$$
假设 $r(\boldsymbol{A})=m$ ，且对应的初始单纯形表满足②，不满足①。那么，引入人工变量 $x_{n+1}, x_{n+2}, \cdots, x_{n+m}$ 构造新的线性规划问题

$$\begin{array}{l} \min \bar{z}=\sum_{j=1}^{n} c_{j} x_{j}+M \sum_{j=n+1}^{n+m} x_{j}，其中 M>0 为足够大的数。\\ \text { s.t. }\left\{\begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}+x_{n+i}=b_{i}, i=1,2, \cdots, m \\ x_{j} \geq 0, j=1,2, \cdots, n, n+1, \cdots, n+m \end{array}\right. \end{array}$$

令 $\boldsymbol{y}=\left(x_{n+1}, x_{n+2}, \cdots, x_{n+m}\right)^{\mathrm{T}}, \boldsymbol{E}=(1,1, \cdots, 1)^{\mathrm{T}}$ ，则对应的矩阵形式为

$$\begin{array}{l} \min \bar{z}=\boldsymbol{C}^{\mathrm{T}} \boldsymbol{x}+M \boldsymbol{E}^{\mathrm{T}} \boldsymbol{y} \\ \text { s.t. } \boldsymbol{A} \boldsymbol{x}+\boldsymbol{y}=\boldsymbol{b} \\ \quad \boldsymbol{x} \geq 0, \quad \boldsymbol{y} \geq 0 \end{array} .$$

其中人工变量 $y$ 全是自由变量。

最优解一致性：
设 $\binom{x^{*}}{y^{*}}$ 是引入人工变量后新的线性规划问题的最优解。

• 若 $\boldsymbol{y}^{*}=\boldsymbol{0}$ ，则 $x^{*}$ 是原问题的最优解；反之，若 $\boldsymbol{x}^{*}$ 是原问题的最优解，则 $\binom{x^{*}}{0}$ 是新问题的最优解；
• 若 $\boldsymbol{y}^{*} \neq \mathbf{0}$ ，则原问题没有可行解；
• 若新问题无最优解，则原问题也无最优解。

2、大M法的具体步骤

1. 若不满足②，经初等行变换使右列元素非负，通常为 $\boldsymbol{r}_{i} \times(-1)$ 。
2. 在中心部位添加 m 阶单位子块，即引入人工变量 $y_{1}, y_{2}, \cdots, y_{m} \geq 0$ ，得到新的约束方程组；
3. 将目标函数修改为 $\bar{z}=z+M \sum_{j=1}^{m} y_{j}$ ，其中 M 为足够大的正常数，从而得到新 LP 模型。
4. 用单纯形法求解新 LP 模型，试图将 $y_{1}, y_{2}, \cdots, y_{m}$ 变成自由变量，最终将出现 Step 5 或 Step 6 两种情况：
5. 设求得新 LP 模型的最优解为 $\left(\boldsymbol{x}^{* \mathrm{~T}}, \boldsymbol{y}^{* \mathrm{~T}}\right)^{\mathrm{T}}$ ，若 $\boldsymbol{y}^{*}=\left(y_{1}^{*}, y_{2}^{*}, \cdots, y_{m}^{*}\right)^{\mathrm{T}}=0$ ，则 $\boldsymbol{x}^{*}=\left(x_{1}^{*}, x_{2}^{*}, \cdots, x_{n}^{*}\right)^{\mathrm{T}}$ 是原 LP 问题的最优解。若 $\boldsymbol{y}^{*}=\left(y_{1}^{*}, y_{2}^{*}, \cdots, y_{m}^{*}\right)^{\mathrm{T}} \neq 0$，则原 LP 问题无最优解。
6. 新 LP 无界（无最优解），则原 LP 问题也无最优解。

有关大M法的一些说明

• 若原 LP 标准形表格的中心部位已有 $l(0<l<m)$ 个不同的单位列向量，则只需添加 $(m-l)$ 个单位列向量，使中心部位出现 $m$ 阶单位矩阵即可。也即，只需引入 $(m-l)$ 个人工变量。
• 在迭代过程中，人工变量一旦由基变量变为自由变量，则不会再成为基变量。此时，对应列便可从单纯形表中删去以减少计算。
• 大 M 法是在单纯形法的基础上改进所得，故也是单纯形法，因此算法十分高效且易于编程实现。（优点）
• 对于实际问题，事先无法预计 M 取值范围。若 M 过大会导致计算误差大。（缺点）

四、二阶段法（人工变量法二）

对于线性规划问题

$$\min w=\sum_{j=1}^{n} c_{j} x_{j} \quad \text { s.t. }\left\{\begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, i=1,2, \cdots, m \\ x_{j} \geq 0, j=1,2, \cdots, n \end{array}\right.$$

假设 $r(\boldsymbol{A})=m$ ，且对应的初始单纯形表满足②，不满足①。引入人工变量 $y_{1}, y_{2}, \cdots, y_{m}$ 构造辅助线性规划问题

$$\begin{array}{l} \min z=\sum_{i=1}^{m} y_{i} \quad \text { 目标函数是所有人工变量之和 } \\ \text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}+y_{i}=b_{i}, i=1,2, \cdots, m \\ \quad x_{j} \geq 0, y_{i} \geq 0, i=1, \cdots, m, j=1, \cdots, n \end{array}$$

令 $\boldsymbol{E}=(1,1, \cdots, 1)^{\mathrm{T}}, \boldsymbol{y}=\left(y_{1}, y_{2}, \cdots, y_{m}\right)^{\mathrm{T}}$ ，则由二阶段法构建的新 LP 的矩阵形式为：

$$\begin{aligned} \min & z=E^{\mathrm{T}} \boldsymbol{y} \\ \text { s.t. } & \boldsymbol{A} \boldsymbol{x}+\boldsymbol{y}=\boldsymbol{b} \\ & \boldsymbol{x} \geq 0, \boldsymbol{y} \geq 0 \end{aligned}$$

最优解的一致性：
设 $\binom{x^{*}}{y^{*}}$ 是新LP问题的最优基本可行解。

• 若 $\boldsymbol{y}^{*}=\mathbf{0}$ ，则 $\boldsymbol{x}^{*}$ 是原问题的一个基本可行解；
• 若 $\boldsymbol{y}^{*} \neq \mathbf{0}$ ，则原问题无可行解。

二阶段法的解题思路：

• 第一阶段是构造并求解新LP问题，得到其最优解。若最优解中人工变量全取 0 ，则进入第二阶段。
• 第二阶段是以第一阶段得到的基本可行解为初始基本可行解，采用单纯形法求解原问题。
  若第一阶段结束时，新LP问题的最优解中人工变量取值不全为 0 ，则原问题无可行解。