线性规划、单纯形法⚓︎

约 2606 个字预计阅读时间 9 分钟

线性规划（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-9）和（1-10）的解 \(x = (x_1, x_2,....,x_n)^{T}\) 称为线性规划的可行解(Feasible solution)，全部可行解的集合称为可行域(Feasible Region).

\[\max \quad z = c^{T}x\tag{1-8}\]

\[\text{s.t.} Ax = b\tag{1-9}\]

\[ x \geq 0\tag{1-10}\]

使目标函数(1-8)达到最大值的可行解称为线性规划问题的最优解(Optimal Solution)。
基(Basis)：考虑等式约束方程组\(Ax=b\)，一般假设\(m \times n\) 矩阵是行满秩的，此时如果\(B\)是\(A\)中一个 \(m \times m\) 的满秩子矩阵（系数矩阵的一个满秩子矩阵），那么B是线性规划问题的一个基。
基向量：组成基的各个列向量，称为基向量；
基变量：与基向量相对应的各个变量称为基变量；
基本解(Basic Solution)：令系数矩阵非基变量为0，得到的方程组的解，称为基本解；
基本解的个数是有限的，最多有\(C^{m}_{n}\)个（想象一下，从 \(n\) 列中抽 \(m\) 列出来，总共几个抽法？）。
基本可行解(Basic Feasible Solution)：满足非负约束条件（1-10）的基本解；
最优基本可行解(Basic Feasible Solution)：使目标函数(1-8)达到最大的基本可行解
最优基（Optimal Basis)：最优基本可行解对应的基；
凸集(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\) 的顶点。
两个凸集的交集仍然是凸集

图解法：⚓︎

确定可行域
画出目标函数等值域，确定可行域
确定最优解
线性规划解的三个基本定理：
- 若线性规划问题存在可行解，那么可行解是凸集；
- 线性规划问题的基本可行解和可行域的顶点一一对应；
- 如果线性规划问题有最优解，那么一定存在一个基本可行解是最优解。

单纯形法⚓︎

单纯形法：
- 迭代原理：先找到基本可行解，判断是否为最优解，如果不是，就转换到相邻的基本可行解，并且使得目标函数值不断增大，直到找到最优解；
- 基的转换是在相邻基之间进行的，两个基本可行解之间有且仅有一基变量发生了变化，
- 以最大化问题为例子，入基变量就是找到使得目标函数减小得最快（单位变动能创造最大收益的）的非基变量，也就是检验数最大的；出基变量就是原本基本可行解中最先因为资源受限降为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（极大数）【不适用计算机运算】
  - 两阶段法：Step.1 目标函数为最小化“所有人工变量和”(\(\mathop{\min} -x_6-x_7\))的线性规划问题，找到一个基本可行解（或者判断是否无可行解）；Step.2 去除人工变量，重新引入原问题的目标函数，利用第一阶段的解作为初始基本可行解
- 无可行解：在最优解中，人工变量必须为0，判断一个线性规划问题无可行解的准则：在得到“最优基本可行解”时（以求解极大值问题为例，就是非基变量检验数都 \(\sigma_j \leq 0\))，如果基变量中依然含有非0的人工变量（两阶段中第一阶段目标函数不是0）。
- 无界解：以求解极大值问题为例，存在非基变量检验数大于0，但是其所在列的系数均小于0，意味着它可以无限增大，此时目标函数可以趋近\(+\infty\)，所以无界；
- 无穷多最优解：如果所有检验数均满足条件(<0)，同时存在非基变量的检验数为0且\(a_{is} >0\)，那么此时的线性规划问题无穷多最优解；
- 退化和循环：基本可行解的基变量部分\(x_B = B^{-1}b\)至少有一个分量等于0，此时称为基本可行解的退化，按照最小比值确定换出值时，会出现两者及以上相同比值；退化解出现是因为模型存在多余的约束条件，使得多个基本可行解对应同一个顶点。
  - Bland法则：若多个检验数大于0，就选择下标最小的变量进基；若\(\theta\)出现两个或者两个以上的相同的最小比值，就选择下标最小的出基；
- 修正单纯形法：
  - \(Ax = b \to Bx_B = b \to x_B = B^{-1}b\)
  - 传统单纯形法针对换基后新的基变量对应的原始矩阵求逆，用逆矩阵左乘系数矩阵从而实现目的；
  - 当前表的基的逆以及初始表，就可以计算出下一张表；
  - 修正单纯形法的复杂程度主要取决于\(B^{-1}\)的大小；
  - 修正单纯形算法的基本思想就是在给定一个初始可行基矩阵\(B\) 的逆矩阵以及初始基本可行解之后，通过不断地修正旧的可行基矩阵的逆矩阵 \(B^{-1}\)，获得新的可行基矩阵的逆矩阵 \(B^{−1}\)，进行操作得出 \(y_q = B^{-1}\alpha_q\)进而完成单纯形算法所需要的其他运算。在迭代过程中，修正单纯形算法只保留一些重要的核心信息，其他的信息可以根据需求适时地生成出来;
  - 锁定主元，除以本身，系数列向量完成更新，对于非主元的其他元素，用同样的转化即可，对于原本仍然在基里的变量，没有任何变化（因为只0和1）
  - 目的就是直接把\(x_2\)转化成\(x_5\)的形式，只需要对整个矩阵（包括b）做初等行变换即可； !!! note "" 感谢这个链接提供的帮助；Bilbili

列生成算法的部分已迁移至第12章

Tips

“线性”的含义：严格的比例、可叠加、可分性、确定性（所以整数规划是独立出来的）几种极端情况：

无可行解：在人工变量时:
无穷多最优解：
无界解：
退化和循环

例题详解单纯形法⚓︎

给定例题，用单纯形法求解此例题。

\[\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对该单纯形表笔误做出的纠正。欢迎大家继续捉虫！

Operations Research：台湾翻译成“作业研究”，我更喜欢国内的这个翻译：“运筹学”

Introduction to LP

Geometric Interpretation of LP

Simplex Method

Duality and Sensitivity Analysis

Interior Point Method （摆脱了Simplex Method的框架，从内部逼近；在有限时间内的多项式算法）

Related Topics