单纯形法学习

单纯形法学习

单纯形法(Simplex Algorithm)是求解线性规划问题最常用、最有效的算法之一

 线性规划

一般形式：

$\begin{matrix} max c^{T} x \\ s.t. a_{i}^{T} x \leq b_{i} \\ a_{j}^{T} x = b_{j} \\ x_{k} \geq 0 \end{matrix}$ $max c^{T} x s.t. a_{i}^{T} x \leq b_{i} a_{j}^{T} x = b_{j} x_{k} \geq 0$
其中 $\mathbf{x}\in\mathbb{R}^n$

标准形式：

$\begin{matrix} max c^{T} x \\ s.t. A x = b \\ x \geq 0 \end{matrix}$ $max c^{T} x s.t. Ax = b x \geq 0$
其中 $\mathbf{A}\in\mathbb{R}^{m\times n},\mathbf{b}\in\mathbb{R}_{+}^m,\mathbf{x}\in\mathbb{R}^n$

$\mathbf{c}^T\mathbf{x}$ 为目标函数
$\mathbf{c}$ 为价值向量, $c_i$ 为价值系数
$\mathbf{b}$ 为右端向量
$\mathbf{A}$ 为约束矩阵
若 $x_i$ 没有符号约束（可以取正，负，零），则称为自由变量

满足所有约束条件的解称为可行解
可行解组成的集合为可行域

一般形式转为标准形式

如果是 $\min \mathbf{c}^T\mathbf{x}$ ,则改为 $\max -\mathbf{c}^T\mathbf{x}$

如果 $x_i$ 为自由变量，则引入 $x_i^+,x_i^-\ge 0$ ，用 $x_i^+-x_i^-$ 来代替 $x_i$ ，并添加约束 $x_i^+,x_i^-\ge 0$

如果 $\mathbf{a}_i^T\mathbf{x}\le b_i$ ，引入松弛变量 $x_s\ge0$ ,将约束变为 $\mathbf{a}_i^T\mathbf{x}+x_s= b_i$ ,并添加约束 $x_s\ge 0$

如果 $\mathbf{a}_i^T\mathbf{x}\ge b_i$ ，引入松弛变量(剩余变量) $x_s\ge0$ ,将约束变为 $\mathbf{a}_i^T\mathbf{x}-x_s= b_i$ ,并添加约束 $x_s\ge 0$

如果 $b_i<0$ 则两边同乘 $- 1$

线性规划可行域几何结构

过 $\mathbf{x}$ 的超平面： $H_{\mathbf{x}}=\left\{\mathbf{z}|\mathbf{c}^T\mathbf{z}=\mathbf{c}^T\mathbf{x}=b\right\}$
半空间： $\left\{\mathbf{z}|\mathbf{c}^T\mathbf{z}\le b=\mathbf{c}^T\mathbf{x}\right\}$

凸集： $C$ 是凸集，若 $\mathbf{x}_1,\mathbf{x}_2\in C$ ，则 $\forall \lambda \in\left[0,1\right],s.t.\ \lambda \mathbf{x}_1+\left(1-\lambda\right)\mathbf{x}_2\in C$

多面体 $P=\left\{\mathbf{x}|\mathbf{A}\mathbf{x}\le \mathbf{b},\mathbf{C}\mathbf{x}=\mathbf{d}\right\}$
容易验证，多面体是一个闭凸集，线性规划可行域是一个多面体

 极点

设 $C\subseteq \mathbb{R}^n$ 是一个非空闭凸集， $\bar{\mathbf{x}}\in C$
如果不存在 $\mathbf{x}_1,\mathbf{x}_2\in C,\lambda \in \left(0,1\right)$ ,使得 $\bar{\mathbf{x}}=\lambda \mathbf{x}_1+(1-\lambda)\mathbf{x}_2$
则 $\bar{\mathbf{x}}$ 是 $C$ 的一个极点(extreme point)

基可行解

设 $B$ 是秩为 $m$ 的约束矩阵 $\mathbf{A}\in \mathbb{R}^{m\times n}$ 种的一个 $m$ 阶满秩子方阵，
则 $\mathbf{B}$ 称为一个基
$\mathbf{B}$ 中 $m$ 个线性无关的列向量称为基向量
变量 $\mathbf{x}$ 中与之对应的 $m$ 个分量称为基变量，其余分量为非基变量
$\mathbf{x}=$
$(\begin{matrix} x_{B} \\ x_{N} \end{matrix})$ = $(\begin{matrix} B^{- 1} b \\ 0 \end{matrix})$ $x = (x_{B} x_{N}) = (B^{- 1} b 0)$ 称为相应于 $\mathbf{B}$ 的基解
当 $\mathbf{B}^{-1}\mathbf{b}\ge 0$ 时， $\mathbf{x}$ 称为基可行解(basic feasible solution,BFS)，此时相应的基 $\mathbf{B}$ 称为可行基

显然，极点至多有 $C_{n}^{m}=$
$(\begin{matrix} n \\ m \end{matrix})$ =\frac{n!}{m!\left(n-m\right)!} $C_{n}^{m} = (n m) = \frac{n !}{m ! ( n - m ) !}$ 个

 定理1

可行解 $\mathbf{x}$ 时基可行解的充要条件时 $\mathbf{x}$ 正分量所对应的 $\mathbf{A}$ 的列向量线性无关

证明：
必要性：由基可行解定义，显然
充分性：
不妨设 $\mathbf{x}$ 为可行解，前 $k$ 个分量为正分量
$\mathbf{A}$ 的列向量为 $\mathbf{A}_1,\mathbf{A}_2,\cdots, \mathbf{A}_n$

$\mathbf{A}_1,\cdots, \mathbf{A}_k$ 线性无关， $k\le m$
若 $k = m$ ，则 $\mathbf{x}$ 为基可行解
若 $k < m k，因为 r a n k ( A ) = m rank\left(\mathbf{A}\right)=m ,可以从剩下 n − k n-k 个列向量中挑选 m − k m-k 个，组成基 B \mathbf{B} ，显然 x \mathbf{x} 为 B \mathbf{B} 对应的基向量$

极点和基可行解等价

$\mathbf{x}$ 是基可行解的充要条件是 $\mathbf{x}$ 是极点

证明：
设 $\mathbf{A}=\left(\mathbf{A}_1,\cdots,\mathbf{A}_n\right),\mathbf{A}_i\in\mathbb{R}^m$
设可行域 $P$
充分性：设 $\mathbf{x}$ 是极点，
假设 $\mathbf{x}$ 不是BFS
不妨假设 $\mathbf{x}$ 的前 $k$ 个分量为正分量
则 $\mathbf{A}_1,\cdots, \mathbf{A}_k$ 线性相关(如果线性无关，则根据定理1， $\mathbf{x}$ 时BFS)
于是 $\exists\mathbf{d}\neq \mathbf{0}$ ，使得 $\sum_{i=1}^{k}\mathbf{A}_i d_i=\mathbf{0}$
$\exists \epsilon>0$ ，使得 $\mathbf{x}+\epsilon\mathbf{d},\mathbf{x}-\epsilon\mathbf{d}\in P$
$\mathbf{x}=\frac{1}{2}\left(\mathbf{x}+\epsilon\mathbf{d}\right)+\frac{1}{2}\left(\mathbf{x}-\epsilon\mathbf{d}\right)$
$\mathbf{x}$ 不是极点，矛盾
所以 $\mathbf{x}$ 是BFS

必要性：设 $\mathbf{x}$ 是BFS
假设 $\mathbf{x}$ 不是极点
则存在 $\mathbf{y},\mathbf{z}\in P,\mathbf{y}\neq \mathbf{x},\mathbf{z}\neq \mathbf{x},\lambda \in\left(0,1\right),\mathbf{x}=\lambda \mathbf{y}+\left(1-\lambda\right)\mathbf{z}$
设 $\mathbf{x}$ 前 $k$ 个分量为正分量，则 $\mathbf{A}_1,\cdots,\mathbf{A}_k$ 线性无关
则 $\sum_{i=1}^{k}\mathbf{A}_i x_i=\mathbf{b}$
$\sum_{i=1}^{k}\mathbf{A}_i y_i=\mathbf{b}$
$\sum_{i=1}^{k}\mathbf{A}_i z_i=\mathbf{b}$
于是 $\sum_{i=1}^{k}\mathbf{A}_i \left(y_i-z_i\right)=0$
因为存在 $y_i\neq z_i$ ，所以 $\mathbf{A}_1,\cdots,\mathbf{A}_k$ 线性相关，矛盾
所以 $\mathbf{x}$ 是极点

 存在性

如果有可行解，则一定有BFS

证明：
设 $\mathbf{x}$ 为可行解，前 $k$ 个分量为正分量
设 $\mathbf{A}=\left(\mathbf{A}_1,\cdots,\mathbf{A}_n\right),\mathbf{A}_i\in\mathbb{R}^m$
如果 $\mathbf{A}_1,\cdots,\mathbf{A}_k$ 线性无关，则 $\mathbf{x}$ 是BFS
如果 $\mathbf{A}_1,\cdots,\mathbf{A}_k$ 线性相关
$\exists \mathbf{\delta}$ ， $\delta_1,\cdots,\delta_k$ 不全为0，使得 $\mathbf{A}\mathbf{\delta}=0$
$\exists \epsilon>0,s.t.\ \mathbf{x}\pm \epsilon\mathbf{\delta}\ge 0$
$\mathbf{x}\pm \epsilon\mathbf{\delta}$ 也是可行解
存在 $\epsilon$ ，使得 $x_i\pm\epsilon \delta_i$ 中至少一个等式为 $0$ ，其中 $i=1,2,\cdots,k$
也就是说 $\mathbf{x}\pm \epsilon\mathbf{\delta}$ 的正分量个数至少比 $\mathbf{x}$ 少一个

这个过程可以继续下去，直到只有1个正分量，此时 $\mathbf{x}$ 也是BFS

最优解是BFS

如果有有限的最优值（不是无界解），则一定存在一个基可行解是最优解

证明：
证明过程与BFS存在性类似

设 $\mathbf{x}$ 是最优解
如果 $\mathbf{x}$ 不是BFS，则 $\mathbf{x}$ 是可行解

$\exists\epsilon>0,\delta\neq \mathbf{0},s.t.\ \mathbf{x}\pm \epsilon\mathbf{\delta}$ 也是可行解
$\mathbf{c}^T\mathbf{x}\ge \mathbf{c}^T\left(\mathbf{x}+ \epsilon\mathbf{\delta}\right)\Rightarrow \mathbf{c}^T\epsilon\mathbf{\delta}\le0\\ \mathbf{c}^T\mathbf{x}\ge \mathbf{c}^T\left(\mathbf{x}- \epsilon\mathbf{\delta}\right)\Rightarrow \mathbf{c}^T\epsilon\mathbf{\delta}\ge0\\$
所以 $\mathbf{c}^T\mathbf{\delta}=0$ ,也就是说 $\mathbf{x}\pm \epsilon\mathbf{\delta}$ 也是最优解
存在 $\epsilon$ ，使得 $x_i\pm\epsilon \delta_i$ 中至少一个等式为 $0$
也就是说 $\mathbf{x}\pm \epsilon\mathbf{\delta}$ 的正分量个数至少比 $\mathbf{x}$ 少一个

这个过程可以继续下去，直到只有1个正分量，此时 $\mathbf{x}$ 也是BFS

单纯形法

基本思路就是先找BFS，判断是不是最优解，如果不是，就找相邻BFS，并使目标函数值增大，直到最优解

$\begin{matrix} max c^{T} x \\ s.t. A x = b \\ x \geq 0 \end{matrix}$ $max c^{T} x s.t. Ax = b x \geq 0$
其中 $\mathbf{A}\in\mathbb{R}^{m\times n},\mathbf{b}\in\mathbb{R}_{+}^m,\mathbf{x}\in\mathbb{R}^n$
$(\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{m} \\ x_{m + 1} \\ ⋮ \\ x_{n} \end{matrix})$ $x = ⎝ ⎛ x_{1} x_{2} ⋮ x_{m} x_{m + 1} ⋮ x_{n} ⎠ ⎞ = ⎝ ⎛ b_{1} b_{2} ⋮ b_{m} 0 ⋮ 0 ⎠ ⎞$
因为 $\mathbf{b}\in\mathbb{R}_+^m$ ,所以 $\mathbf{x}$ 是BFS

一个BFS换到相邻BFS

两个可行基称为相邻的，如果他们之间变换且仅变换一个基变量
设 $\mathbf{x}^{(0)}$ 的前 $m$ 个分量为基变量,即
$\mathbf{x}^{(0)}=$
$(\begin{matrix} x_{1}^{(0)} \\ ⋮ \\ x_{m}^{(0)} \\ 0 \\ ⋮ \\ 0 \end{matrix})$ $x^{(0)} = ⎝ ⎛ x_{1}^{(0)} ⋮ x_{m}^{(0)} 0 ⋮ 0 ⎠ ⎞$
则
$\sum_{i=1}^{m}\mathbf{A}_i x_i^{(0)}=\mathbf{b}$
显然
$\begin{aligned} A_{j} & = \sum_{i = 1}^{m} a_{i j} A_{i} \\ θ (A_{j} - \sum_{i = 1}^{m} a_{i j} A_{i}) & = 0 \end{aligned}$
其中 $\theta>0$
所以
$\begin{aligned} \sum_{i = 1}^{m} A_{i} x_{i}^{(0)} + θ (A_{j} - \sum_{i = 1}^{m} a_{i j} A_{i}) & = b \\ \sum_{i = 1}^{m} (x_{i}^{(0)} - θ a_{i j}) A_{i} + θ A_{j} & = b \end{aligned}$
也就是说 $(\begin{matrix} x_{1}^{(0)} - θ a_{1 j} \\ ⋮ \\ x_{m}^{(0)} - θ a_{m j} \\ 0 \\ ⋮ \\ θ \\ ⋮ \\ 0 \end{matrix})$ 是一个基解，因为 $\theta>0$ ，要想成为基可行解，需要满足
$x_i^{(0)}-\theta a_{ij}\ge 0\quad i=1,2,\cdots m$
解得 $0<\theta \le\min\limits_{i}\left\{\frac{x_i^{(0)}}{a_{ij}}|a_{ij}>0\right\}$
令 $l=\arg\min\limits_{i}=\left\{\frac{x_i^{(0)}}{a_{ij}}|a_{ij}>0\right\}$
取 $\theta = \frac{x_l^{(0)}}{a_{lj}}$ ，则 $x_i^{(0)}-\theta a_{ij}$ 中至少有一个为0
$x_1,\cdots,x_{l-1},x_j,x_{l+1},\cdots,x_m$ 对应的列排列起来
$\begin{array}{ccccccccc} A_{1} & A_{2} & \dots & A_{l - 1} & A_{j} & A_{l + 1} & \dots & A_{m} & b \\ 1 & 0 & \dots & 0 & a_{1 j} & 0 & \dots & 0 & b_{1} \\ 0 & 1 & \dots & 0 & a_{2 j} & 0 & \dots & 0 & b_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & a_{l - 1, j} & 0 & \dots & 0 & b_{l - 1} \\ 0 & 0 & \dots & 0 & a_{l j} & 0 & \dots & 0 & b_{l} \\ 0 & 0 & \dots & 0 & a_{l + 1, j} & 1 & \dots & 0 & b_{l + 1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 0 & a_{m j} & 0 & \dots & 1 & b_{m} \end{array}$
注意到 $a_{lj}>0$ ,所以 $\mathbf{A}_1,\cdots, \mathbf{A}_{l-1},\mathbf{A}_j,\mathbf{A}_{l+1},\cdots,\mathbf{A}_m$ 线性无关，可以构成一个基， $\mathbf{x}^{(1)}$ 是基可行解
通过初等行变换
$\begin{array}{ccccccccc} A_{1} & A_{2} & \dots & A_{l - 1} & A_{j} & A_{l + 1} & \dots & A_{m} & b \\ 1 & 0 & \dots & 0 & 0 & 0 & \dots & 0 & b_{1} - θ a_{1 j} \\ 0 & 1 & \dots & 0 & 0 & 0 & \dots & 0 & b_{2} - θ a_{2 j} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & 0 & 0 & \dots & 0 & b_{l - 1} - θ a_{l - 1, j} \\ 0 & 0 & \dots & 0 & 1 & 0 & \dots & 0 & θ \\ 0 & 0 & \dots & 0 & 0 & 1 & \dots & 0 & b_{l + 1} - θ a_{l + 1, j} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 0 & 0 & 0 & \dots & 1 & b_{m} - θ a_{m j} \end{array}$
变换之后， $\mathbf{x}^{(1)}$ 的基依然是单位矩阵， $\mathbf{x}^{(1)}$ 与 $\mathbf{x}^{(0)}$ 构成相邻基可行解

现在我们知道，要将 $l$ 替换成 $j$ ，那么 $j$ 应该要怎么选择

 最优解检验和解的判别

$z^{(0)}=\sum_{i=1}^{m}c_i x_i^{(0)}$

$\begin{aligned} z^{(1)} & = \sum_{i = 1}^{m} (x_{i}^{(0)} - θ a_{i j}) c_{i} + θ c_{j} \\ = \sum_{i = 1}^{m} c_{i} x_{i}^{(0)} + θ (c_{j} - \sum_{i = 1}^{m} a_{i j}) \\ = z^{(0)} + θ (c_{j} - \sum_{i = 1}^{m} c_{i} a_{i j}) \end{aligned}$ $z^{(1)} = i = 1 \sum m (x_{i}^{(0)} - θ a_{ij}) c_{i} + θ c_{j} = i = 1 \sum m c_{i} x_{i}^{(0)} + θ (c_{j} - i = 1 \sum m a_{ij}) = z^{(0)} + θ (c_{j} - i = 1 \sum m c_{i} a_{ij})$
因为 $\theta>0$ ，所以只要 $c_j-\sum_{i=1}^{m}c_ia_{ij}>0$ 就有 $z^{(1)}>z^{(0)}$
$\sigma_j=c_j-z_j=c_j-\sum_{i=1}^{m}c_ia_{ij}$ 称为检验数
注意到 $\sigma_1,\cdots,\sigma_m\ge 0$ ,所以算检验数的时候，只要算非基变量的检验数

最优解

如果所有 $\sigma_j\le 0$ ,那么 $z^{(1)}$ 就是最优值

证明：
设 $\mathbf{x}$ 是最优解， $\mathbf{y}$ 为可行解
则 $\mathbf{Ax}=\mathbf{b},\mathbf{Ay}=\mathbf{b}$
设 $\mathbf{x}$ 的基为 $\mathbf{B}=\mathbf{I}$ ，前 $m$ 个分量为基变量
$\mathbf{A}=\left(\mathbf{B},\mathbf{N}\right)=\left(\mathbf{I},\mathbf{N}\right)$
令 $\mathbf{d}=\mathbf{y}-\mathbf{x},\mathbf{d}_{\mathbf{B}}=\left(d_1,\cdots,d_m\right)^T,\mathbf{d}_{\mathbf{N}}=\left(d_{m+1},\cdots,d_n\right)^T$
$\mathbf{c}_{\mathbf{B}}=\left(c_1,\cdots,c_m\right)^T,\mathbf{c}_{\mathbf{N}}=\left(c_{m+1},\cdots,c_n\right)^T$

$\begin{aligned} A d & = 0 \\ B d_{B} + N d_{N} & = 0 \\ d_{B} & = - N d_{N} \end{aligned}$ $Ad B d_{B} + N d_{N} d_{B} = 0 = 0 = - N d_{N}$
$\begin{aligned} c^{T} d & = c_{B}^{T} d_{B} + c_{N}^{T} d_{N} \\ = - c_{B}^{T} N d_{N} + c_{N}^{T} d_{N} \\ = (c_{N}^{T} - c_{B}^{T} N) d_{N} \\ = \sum_{j = m + 1}^{n} σ_{j} d_{j} \end{aligned}$
因为 $x_{m+1},\cdots,x_n=0,y_{m+1},\cdots,y_n\ge 0$ ,所以 $d_{m+1},\cdots, d_n\ge 0$
即 $\mathbf{c}^T\mathbf{d}\le 0\Rightarrow \mathbf{c}^T\mathbf{x}\ge \mathbf{c}^T\mathbf{y}$

无穷多解

如果所有 $\sigma_j\le 0$ ，并且其中一个 $\sigma_j=0$ ,则 $z^{(1)}=z^{(0)}$ ,也就是说 $x^{(0)},x^{(1)}$ 都是最优解
因为可行域是个凸集，所以 $\forall \lambda \in\left[0,1\right],\lambda x^{(0)}+\left(1-\lambda\right)x^{(1)}$ 也是最优解，即有无穷多解

无界解

如果 $\sigma_j>0$ ,并且 $\mathbf{A}_j\le 0$ ,那么 $\forall \theta>0,s.t.\ x_i^{(0)}-\theta a_{ij}\ge 0$
那么 $z^{(1)}$ 可以无限增大，故无界

 计算步骤

实在是懒得画表了，直接截图了
第1步：求BFS，列单纯形表

第2步：最优性检验
如果所有的 $c_j-z_j\le 0$ ，且基变量不包含人工变量，则表中的基可行解就是最优解
如果存在 $c_j-z_j>0$ ，如果 $\mathbf{A}_j\le 0$ ,则问题为无界解，否则进行下一步

第3步：从一个BFS转到相邻的目标函数值更大的BFS，列出新的单纯形表
1.确定入基变量
只要检验数 $\sigma_j>0$ ，对应的 $x_j$ 都可以作为入基变量，但是一般找最大的 $\sigma_k$
$\sigma_k=\max_{j}\left\{\sigma_j|\sigma_j>0\right\}$
其对应的变量 $x_k$ 为入基变量

2.确定出基变量
$\theta=\min_{i}\left\{\frac{b_i}{a_{ik}}|a_{ik}>0\right\}=\frac{b_l}{a_{lk}}$
即 $x_l$ 是出基变量， $a_{lk}$ 称为主元素

3.用入基变量 $x_k$ 替换出基变量 $x_l$ ，得到新的基
通过初等行变换使得 $\mathbf{A}_k$ 变换为 $\mathbf{e}_k$

人工变量

$\begin{aligned} max z = - 3 x_{1} + x_{3} + 0 x_{4} + 0 x_{5} \\ s.t. {\begin{aligned} x_{1} & + x_{2} & + x_{3} & + x_{4} & = 4 \\ - 2 x_{1} & + x_{2} & - x_{3} & - x_{5} & = 1 \\ 3 x_{2} & + x_{3} & = 9 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ⩾ 0 \end{aligned} \end{aligned}$ $max z = - 3 x_{1} + x_{3} + 0 x_{4} + 0 x_{5} s.t. ⎩ ⎨ ⎧ x_{1} - 2 x_{1} x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ⩾ 0 + x_{2} + x_{2} 3 x_{2} + x_{3} - x_{3} + x_{3} + x_{4} - x_{5} = 4 = 1 = 9$
这种情况下，找不到单位矩阵作为基，所以需要引入人工变量

 大M法

引入人工变量 $x_6,x_7$

$\begin{aligned} max z = - 3 x_{1} + x_{3} + 0 x_{4} + 0 x_{5} - M x_{6} - M x_{7} \\ s.t. {\begin{array}{rrr} x_{1} & + x_{2} & + x_{3} & + x_{4} & = 4 \\ - 2 x_{1} & + x_{2} & - x_{3} & - x_{5} & + x_{6} & = 1 \\ 3 x_{2} & + x_{3} & + x_{7} & = 9 \\ x_{j} ⩾ 0 (j = 1, \dots, 7) \end{array} \end{aligned}$ $max z = - 3 x_{1} + x_{3} + 0 x_{4} + 0 x_{5} - M x_{6} - M x_{7} s.t. ⎩ ⎨ ⎧ x_{1} - 2 x_{1} x_{j} ⩾ 0 (j = 1, \dots, 7) + x_{2} + x_{2} 3 x_{2} + x_{3} - x_{3} + x_{3} + x_{4} - x_{5} + x_{6} + x_{7} = 4 = 1 = 9$
其中 $M=+\infty$ ,即一个很大的数
想要取到最优解，显然需要人工变量为0
如果人工变量不为0，则无可行解

 两阶段法

大M法手算的时候不会有什么问题，但是机器算的时候会出现问题

两阶段法：
第一阶段是求解只包含人工变量的线性规划问题，即令目标函数中其他变量的系数取零，人工变量的系数取某个正的常数（一般取1)，在保持原问题约束条件不变的清况下求这个目标函数极小化时的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0.这时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段最优值不为0，原问题物可行解

当第一阶段求解结果表明问题有可行解时，第二阶段是在原问题中去除人工变量，并从此可行解（即第一阶段的最优解）出发，继续寻找问题的最优解

还是上面的例子

$\begin{aligned} min z = x_{6} + x_{7} \\ s.t. {\begin{array}{rrr} x_{1} & + x_{2} & + x_{3} & + x_{4} & = 4 \\ - 2 x_{1} & + x_{2} & - x_{3} & - x_{5} & + x_{6} & = 1 \\ 3 x_{2} & + x_{3} & + x_{7} & = 9 \\ x_{j} ⩾ 0 (j = 1, \dots, 7) \end{array} \end{aligned}$ $min z = x_{6} + x_{7} s.t. ⎩ ⎨ ⎧ x_{1} - 2 x_{1} x_{j} ⩾ 0 (j = 1, \dots, 7) + x_{2} + x_{2} 3 x_{2} + x_{3} - x_{3} + x_{3} + x_{4} - x_{5} + x_{6} + x_{7} = 4 = 1 = 9$
转标准型
$\begin{aligned} max z = - x_{6} - x_{7} \\ s.t. {\begin{array}{rrr} x_{1} & + x_{2} & + x_{3} & + x_{4} & = 4 \\ - 2 x_{1} & + x_{2} & - x_{3} & - x_{5} & + x_{6} & = 1 \\ 3 x_{2} & + x_{3} & + x_{7} & = 9 \\ x_{j} ⩾ 0 (j = 1, \dots, 7) \end{array} \end{aligned}$

求完就发现， $x_4,x_2,x_1$ 就是基变量了
然后把目标函数变回原来的目标函数，继续求解（人工变量已经没有用了，可以去掉了）

退化

按最小比值 $\theta$ 来确定出基变量时，可能存在2个或者以上最小比值，从而使下一个表的基可行解中出现一个或多个基变量为0的退化解。

退化解的出现，原因是存在多余约束，使得多个基可行解对应同一个顶点。当存在退化解的时候可能出现循环。
为了避免这个问题：（1）当存在多个 $\sigma_j>0$ 时，选下标最小的作为入基变量
(2)当出现多个 $\theta$ 的最小比值时，选下标最小的作为出基变量
（总结起来就是选下标最小）

代码

摸了

参考
运筹学教程（第5版）（胡运权, 郭耀煌, 龚益鸣, 程佳惠, 陈秉正）
https://mp.weixin.qq.com/s/tm5EuZNLrL8SUWlRXKgR3Q
相关阅读:
呼叫中心的实时语音分析
 Day 59 django ROM 多表查询
 Microolap DAC for MySQL驱动程序或其他库
 【深度学习】YOLOv5 工程落地部署过程 MNN
Vue 简易版无限加载组件实现原理
 unity游戏开发中的随机算法
 ClickHouse备份方案
 LeetCode-3. 无重复字符的最长子串-Java-medium
64位Ubuntu20.04.5 LTS系统安装32位运行库
 day07-缓存套餐
原文地址：https://blog.csdn.net/qq_39942341/article/details/126159840

线性规划

一般形式转为标准形式

线性规划可行域几何结构

极点

基可行解

定理1

极点和基可行解等价

存在性

最优解是BFS

单纯形法

迭代基本原理

一个BFS换到相邻BFS

最优解检验和解的判别

最优解

无穷多解

无界解

计算步骤

人工变量

大M法

两阶段法

退化

代码