线性规划、单纯形法⚓︎
约 3739 个字 预计阅读时间 12 分钟
线性规划（Linear Programming）：是在线形约束下求解线性目标函数最优值的数学理论和方法。
数学规划的三要素
- 决策变量 (
Decision Variables): - 目标函数 (
Objective Function): - 约束条件 (
Constraints):
我们可以把线性规划以数学语言表述为：
\[\max(\min)z = \sum^{n}_{j = 1}{c_jx_j}\]
\[\text{s.t.} \sum^{n}_{j = 1}{a_{ij} }{x_j} \leq ( =, \geq) b_i , (i = 1,...m)\]
\[x_j \geq 0, (j = 1,...n)\]
同时，给出线性规划模型的标准形式：
\[\mathop{\max} z = \sum^{n}_{j = 1}{c_jx_j}\]
\[\text{s.t.} \sum^{n}_{j = 1}{a_{ij} }{x_j} = b_i , (i = 1,...m)\]
\[x_j \geq 0, (j = 1,...n)\]
现在，我们对一些概念进行罗列（虽然有点繁琐，但是还是有必要的）。
- 松驰变量
- 引入非负变量，把 "\(\leq\)" 不等式约束转换为等式约束，这样的\(y_i\)就是松弛变量
- 剩余变量
- 引入非负变量，把 "\(\geq\)" 不等式约束转换为等式约束，这样的变量就是剩余变量；
- 可行解、可行域
- 满足约束条件（1-2）和（1-3）的解 \(x = (x_1, x_2,....,x_n)^{T}\) 称为线性规划的可行解
(Feasible solution)，全部可行解的集合称为可行域(Feasible Region).
\[\max \quad z = c^{T}x\tag{1-1}\]
\[\text{s.t.} Ax = b\tag{1-2}\]
\[ x \geq 0\tag{1-3}\]
- 最优解
(Optimal Solution) - 使目标函数(1-1)达到最大值的可行解称为线性规划问题的最优解。
- 基
(Basis)/ 基向量 / 基变量 - 考虑等式约束方程组 \(Ax=b\)，一般假设 \(m \times n\) 矩阵是行满秩的，此时如果 \(B\) 是 \(A\) 中一个 \(m \times m\) 的满秩子矩阵（系数矩阵的一个满秩子矩阵），那么 \(B\) 是线性规划问题的一个基。 组成基的各个列向量，称为基向量；与基向量相对应的各个变量称为基变量；
- 基本解
(Basic Solution) - 令系数矩阵非基变量为0，得到的方程组的解，称为基本解；
- 基本可行解
(Basic Feasible Solution) - 满足非负约束条件（1-3）的基本解；
- 最优基本可行解
(Basic Feasible Solution) - 使目标函数(1-1)达到最大的基本可行解
- 最优基
（Optimal Basis) - 最优基本可行解对应的基；
- 基本解的个数是有限的，最多有\(C^{m}_{n}\)个（想象一下，从 \(n\) 列中抽 \(m\) 列出来，总共几个抽法？）。
- 凸集
(Convex Set) -
设 \(x_1,x_2 \in x\) 是集合S内的任意两点，如果对于任意的 \(x = \alpha x_1 + (1-\alpha)x_2, 0 \leq \alpha \leq 1\) 有 \(x \in S\)，那么集合\(S\)就是凸集；（给定集合 \(C\)，\(C\) 中任意两点的连线仍在 \(C\) 中，那么 \(C\) 就是凸集；
-
凸集的顶点（极点）：如果凸集C中不存在任何两个不同的点 \(X_1,X_2\)，使得 \(X\) 在线段 \(X_1X_2\)，就说 \(X\) 是凸集 \(C\) 的顶点。
-
两个凸集的交集仍然是凸集。
-
图解法：⚓︎
针对两个决策变量，在平面直角坐标系下利用图式进行求解的过程。
步骤: 1. 确定可行域
画出目标函数等值域，确定可行域
确定最优解
线性规划解的三个基本定理⚓︎
- 若线性规划问题存在可行解，那么可行解是凸集；
- 线性规划问题的基本可行解和可行域的顶点一一对应；
- 如果线性规划问题有最优解，那么一定存在一个基本可行解是最优解。
单纯形法⚓︎
单纯形法
- 迭代原理：先找到基本可行解，判断是否为最优解，如果不是，就转换到相邻的基本可行解，并且使得目标函数值不断增大，直到找到最优解；
- 基的转换是在相邻基之间进行的，两个基本可行解之间有且仅有一基变量发生了变化
- 以最大化问题为例子，入基变量就是找到使得目标函数减小得最快（单位变动能创造最大收益的）的非基变量，也就是检验数最大的；出基变量就是原本基本可行解中最先因为资源受限降为0的基变量；
- 检验数：\(\sigma_{j} = (c^{T}_N - c^{T}_B B^{-1}N)_j\)，如果线性规划问题要求极小值，那么当所有检验数\(\sigma_{j} \geq 0\) 时候达到最优解。反之亦然。
- 选中入基变量\(x_k\)和出基变量\(x_l\)，第\(k\)列和第\(l\)行的交叉点元素就是旋转主元，确保基矩阵始终是单位矩阵，对矩阵进行初等变换。
具体步骤 （按照==求解极大值问题==为例）⚓︎
- 列出单纯形表，要求 \((B^{-1}b)_{i} \geq 0\)
- 进行最优性判断，如果所有的 \(\sigma_{j} = (c^{T} - c^{T}_B B^{-1}A)_j \leq 0\)，那么当前基本可行解就是最优解；否则进入下一步
- 确定换入变量：如果存在\(\sigma_j > 0\)，那么计算：\(\mathop{\max} \left\{ \sigma_j | \sigma_j > 0 \right\} = \sigma_s\),将对应的列变量\(x_s\)当作换入变量
- 确定换出变量：检查换入变量\(x_s\)所在的第\(s\)列，如果所有的\(a_{is} \leq 0\)，那么线性规划问题有解但是目标函数无界；如果存在\(a_{is} > 0\)，那么计算 \(\theta = \mathop{\min} \left\{ \dfrac{b_i}{a_{is}} | a_{is} > 0 \right\} = \dfrac{b_r}{a_{rs}}\) 。把对应的行变量\(x_r\)作为换出变量，\(a_{rs}\) 作为旋转主元。
- 重复2-4步骤，直到计算结束；
单纯形法的延伸⚓︎
- 人工变量法
- 如果不能在系数矩阵中观察到单位矩阵，可以通过添加虚构的人工变量来构造单位矩阵。（人工变量的取值一定要是0，所以如果检验数\(\sigma_j \leq 0\)，基变量中依然有人工变量并且不为0，那么原问题无可行解。具体而言，有如下两种情况：
大 \(M\) 法
又称“惩罚法”，就是在目标函数中设人工变量的系数为 \(-M\)，其中 表示一个很大的正数，称为“罚因子”。此时，对于求目标函数最大化的标准线性规划问题来讲，只要人工变量取值大于零，目标函数值就不可能取到最大。
这是一种不是很适合计算机求解的方法。因为会导致边界取值不确定、收敛速度过慢等等。
两阶段法
将线性规划问题的求解分为两个阶段进行。首先，和大 \(M\) 法一样添加人工变量。
在第一阶段中，通过求解目标函数为最小化所有人工变量和的线性规划问题找到原问题的一个基本可行解（或判断出原问题无可行解）。
在第二阶段中，去除人工变量，重新引入原问题的目标函数，然后利用第一阶段的解作为初始基本可行解来继续单纯形法，直至求得最优解。两阶段法的优点是在用计算机处理求解时，无需考虑 \(M\) 的取值，避免了取值误差可能导致的结果误差。
于此同时，我们可以发现，除了能找到最优解的情况外，还有如下的几种情况：无可行解、无界解、无穷多最优解，以及退化和循环。我们会逐个讨论这几种情况。
- 无可行解
- 在最优解中，人工变量必须为0，判断一个线性规划问题无可行解的准则：在得到“最优基本可行解”时（以求解极大值问题为例，就是非基变量检验数都 \(\sigma_j \leq 0\))，如果基变量中依然含有非0的人工变量（两阶段中第一阶段目标函数不是0）。
- 无界解
- 以求解极大值问题为例，存在非基变量检验数大于0，但是其所在列的系数均小于0，意味着它可以无限增大，此时目标函数可以趋近\(+\infty\)，所以无界；
- 无穷多最优解
- 如果所有检验数均满足条件(<0)，同时存在非基变量的检验数为0且\(a_{is} >0\)，那么此时的线性规划问题无穷多最优解；
- 退化和循环
- 基本可行解的基变量部分\(x_B = B^{-1}b\)至少有一个分量等于0，此时称为基本可行解的退化，按照最小比值确定换出值时，会出现两者及以上相同比值；退化解出现是因为模型存在多余的约束条件，使得多个基本可行解对应同一个顶点。
-
Bland法则：若多个检验数大于0，就选择下标最小的变量进基；若\(\theta\)出现两个或者两个以上的相同的最小比值，就选择下标最小的出基；
修正单纯形法⚓︎
在单纯形法迭代中，每一步都对整张单纯形表进行了更新。如果问题规模较大，则计算量也将非常大。而当一个线性规划问题的决策变量远多于约束条件时，即对一个 \(m \times n\) 的系数矩阵 \(\mathbf{A}\) 来说，如果 \(m\) 远小于 \(n\)，那么每一次基变换其实仅涉及 \(\mathbf{A}\) 的一小部分列向量。 如果 \(\mathbf{A}\) 的某一列在整个求解过程中从来没成为过进基向量，那么对该列向量的所有计算都是多余的。因此，为避免这些大量的无用计算，降低单纯形法的计算量，修正单纯形法(Revised Simplex Method) 被提出。
单纯形法的迭代，实际是对初始单纯形表做一系列初等变换 (请复习线性代数！这么一大段就是告诉你，只进行必要的初等行变换即可！)。如果得到当前迭代步的可行基为 \(\mathbf{b}\)，那么这一系列初等变换就等价于对初始单纯形表左乘 \(\mathbf{B^{-1}}\)。也就是说，在单纯形法的迭代中，只需要知道基矩阵的逆 \(\mathbf{B^{-1}}\) 以及初始单纯形表，就可以完成全部计算。
比如基变量的取值就是 \(\mathbf{B^{-1}b}\)，检验数就是 \(\mathbf{c^T_j - c^T_BB^{-1}P_j}\) 。因此，修正单纯形法的核心思想就是在迭代中不断更新基变量以及基矩阵的逆，只用少量的必要信息来完成进基和出基变量的选择。这样，不仅能减少计算量并节省存储空间，同时也可减少迭代中的累积误差，提高计算精度。
修正单纯形法的具体步骤
Step 1 根据线性规划标准形式，确定初始基变量 \(x_B\)，以及初始基矩阵 \(B\) 的逆矩阵 \(B^{-1}\)。
Step 2 计算非基变量检验数 \(\sigma_N = \mathbf{c_N^\top - c_B^\top B^{-1}N}\)，若所有的检验数都小于等于 0，则当前解为最优解
\[\mathbf{x_B = B^{-1}b}\]
计算结束；否则转 Step 3。
Step 3 确定进基变量。若存在检验数 \(\sigma_j > 0\)，那么计算
\[\sigma_q = \max\{\sigma_j > 0\}\]
将对应的列变量 \(x_q\) 作为进基变量，计算其系数列向量 \(\mathbf{y_q}\) 为：
\[\mathbf{y_q = B^{-1}p_q}\]
Step 4 确定出基变量。如果 \(y_q\) 的所有元素都小于等于 0，那么停止计算，问题为无界解；否则计算
\[r = \arg\min_i \left\{ \frac{\mathbf{(B^{-1}b)_i}}{\mathbf{(y_q)_i}} \,\middle|\, \mathbf{(y_q)_i} > 0 \right\}\]
将对应的行变量 \(x_r\) 作为出基变量。
Step 5 计算得到新基矩阵的逆 \(\mathbf{B_{\text{new}}^{-1}}\)，令 \(\mathbf{B^{-1} = B_{\text{new}}^{-1}}\)。
Step 6 重复步骤 Step 2 ~ Step 5，直到计算结束。
感谢这个链接提供的帮助；Bilbili
列生成算法的部分已迁移至列生成算法。
我们该如何理解线性
“线性”的含义：严格的比例、可叠加、可分性、确定性（所以整数规划是独立出来的）
- 线性之流畅在于，你可以把一些难以求解的东西往这里靠拢。
例题详解单纯形法⚓︎
- 给定例题，用单纯形法求解此例题。
\[\max z = 2x_1 + x_2 \\
\\
\text{s.t.} \begin{align*}\begin{equation*}
\begin{cases}
& &5 x_2 &\leq 15 \\
&6x_1 &+ 2x_2 &\leq 24 \\
&x_1 & + x_2 &\leq 5 \\
&&x_1, x_2 &\geq 0
\end{cases}
\end{equation*}\end{align*}\]
- 标准化后的结果：
\[\max z = 2x_1 + x_2 + 0x_3 + 0x_4 + 0x_5\\
\\
\text{s.t.} \begin{align*}\begin{equation*}
\begin{cases}
& &5 x_2 + x_3 & & &= 15 \\
&6x_1 &+ 2x_2 &+x_4 & &=24 \\
&x_1 & + x_2 & &+x_5 &= 5 \\
&&x_1, x_2 x_3, x_4, x_5 &\geq 0
\end{cases}
\end{equation*}\end{align*}\]
据此列出第一个单纯形表如下。可以发现有大于零的检验数。所以基本可行解不是最优解，我们选择 \(x_1\) 是入基变量，因为其检验数更大 (2 > 1)。同时，随之逐渐增大，\(x_4\) 应该是出基变量，因为用 \(\mathbb{b}\) 列除以出基的 \(x_1\) 列向量对应元素， \(\dfrac{24}{6} < \dfrac{5}{1}\)，说明 \(x_4\) 最先达到上限。
\[\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c}
\hline
\hline
& & & 2 & 1 & 0 & 0 & 0 \cr \hline
\textbf{c}_{\textbf{B}} & \textbf{x}_{\textbf{B}} & \textbf{b} & x_1 & x_2 & x_3 & x_4 & x_5 \cr \hline
0 & x_3 & 15 & 0 & 5 & 1 & 0 & 0 \cr \hline
0 & x_4 & 24 & \colorbox{lightgreen}{[6]} & 2 & 0 & 1 & 0 \cr \hline
0 & x_5 & 5 & 1 & 1 & 0 & 0 & 1 \cr \hline
r_c & & & 2 & 1 & 0 & 0 & 0 \cr \hline
\hline
\end{array}\]
进行出入基操作后，我们得到如下的单纯形表格。可见还有一个检验数是非负的。我们如法炮制用上面的思路确定出入基变量（出: \(x_5\)， 入： \(x_2\)）。进行第二次单纯形迭代。
\[\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c}
\hline
\hline
& & & 2 & 1 & 0 & 0 & 0 \cr \hline
\textbf{c}_{\textbf{B}} & \textbf{x}_{\textbf{B}} & \textbf{b} & x_1 & x_2 & x_3 & x_4 & x_5 \cr \hline
0 & x_3 & 15 & 0 & 5 & 1 & 0 & 0 \cr \hline
2 & x_1 & 4 & 1 & 2/6 & 0 & 1/6 & 0 \cr \hline
0 & x_5 & 1 & 0 & \colorbox{lightgreen}{[4/6]} & 0 & -1/6 & 1 \cr \hline
r_c & & & 0 & 1/3 & 0 & -1/3 & 0 \cr \hline
\hline
\end{array}\]
迭代完成后，我们发现，所有的检验数 \(\sigma_j \leq 0\)，并且基变量中不含有人工变量，此时的基本可行解就是最优解\(( \dfrac{7}{2}, \dfrac{3}{2}, \dfrac{15}{2}, 0 ,0 )\)。求得目标函数最大值是 \(\dfrac{17}{2}\).
\[\def\arraystretch{1.5}
\begin{array}{c|c|c|c|c|c|c|c}
\hline
\hline
& & & 2 & 1 & 0 & 0 & 0 \cr \hline
\textbf{c}_{\textbf{B}} & \textbf{x}_{\textbf{B}} & \textbf{b} & x_1 & x_2 & x_3 & x_4 & x_5 \cr \hline
0 & x_3 & 15/2 & 0 & 0 & 1 & 5/4 & -15/2 \cr \hline
2 & x_1 & 7/2 & 1 & 0 & 0 & 1/4 & -1/2 \cr \hline
1 & x_2 & 3/2 & 0 & 1 & 0 & -1/4 & 3/2 \cr \hline
r_c & & & 0 & 0 & 0 & \colorbox{lightblue}{-1/4} & \colorbox{lightblue}{-1/2} \cr \hline
\hline
\end{array}\]
特别感谢热心网友wzy对该单纯形表笔误做出的纠正。欢迎大家继续捉虫！