【运筹学学习笔记】单纯形法（持续更新）

运筹学绪论

运筹学是一门应用于管理有组织系统的科学，根据问题的要求，通过数学分析与计算，做出综合性的合理安排，以期达到资源的最优化利用。

运筹学考虑系统的整体优化、多学科的配合以及模型方法的应用，其研究可以分为以下几个步骤：

1.分析与表述问题。
2.建立模型
3.对问题求解
4.对模型和由模型导出的解进行检验
5.建立对解的有效控制
6.方案的实施。

其中，建模是运筹学方法的核心和精髓。

线性规划与单纯形法

线性规划模型的组成要素和特征

决策变量 指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。

目标函数 指问题要达到目标的要求，表示为决策变量的函数。

约束条件 指决策变量取值时受到的各种限制，表示为决策变量的等式或不等式。

定义：目标决策变量为可控的连续变量，目标函数和约束条件都是线性的，这类模型称为线性规划模型。

线性规划问题的一般形式

1.标量形式

决策变量 $\{x_i|i=1,2,...,n\}${xi​∣i=1,2,...,n}

目标函数 $max(min)~z=c_1x_1+c_2x_2+...+c_nx_n$max(min) z=c1​x1​+c2​x2​+...+cn​xn​

约束条件 $s.t.=\left\{ \begin{matrix} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n \le(=,\ge)b_1,\\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n \le(=,\ge)b_2,\\ ~~\vdots\\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n \le(=,\ge)b_m,\\ x_j\ge0~或~x_j\le0~或~x_j无约束 \end{matrix} \right.$s.t.=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​a11​x1​+a12​x2​+...+a1n​xn​≤(=,≥)b1​,a21​x1​+a22​x2​+...+a2n​xn​≤(=,≥)b2​,  ⋮am1​x1​+am2​x2​+...+amn​xn​≤(=,≥)bm​,xj​≥0 或 xj​≤0 或 xj​无约束​

一般用$~n~$ n 表示决策变量的个数，$~m~$ m 代表约束等式/不等式的个数

通常情况下要求$~m<n~$ m<n ，否则可能导致没有可行解

2.向量形式

决策变量 $X=(x_1~x_2~\ldots~x_n)^T$X=(x1​ x2​ … xn​)T

目标函数 $max(min)~z=CX$max(min) z=CX

约束条件 $s.t.=\left\{ \begin{matrix} \displaystyle\sum_{j=1}^{n}x_jP_j\le(=,\ge)b\\ X\ge 0 \end{matrix} \right.$s.t.=⎩⎪⎨⎪⎧​j=1∑n​xj​Pj​≤(=,≥)bX≥0​

其中 $C=(c_1~c_2~...~c_n),P_j=(a_{1j}~a_{2j}~\ldots~a_{mj})^T,b=(b_1~b_2~...~b_m)^T$C=(c1​ c2​ ... cn​),Pj​=(a1j​ a2j​ … amj​)T,b=(b1​ b2​ ... bm​)T.

注意列向量$~P\ge Q~$ P≥Q 意味着 $\forall i~~P_i\ge Q_i$∀i  Pi​≥Qi​，矩阵也类似

3.矩阵形式

$max(min)~z=CX\\ s.t.=\left\{ \begin{matrix} AX\le(=,\ge)b\\ X\ge 0 \end{matrix} \right.\\ 其中~C=(c_1~c_2~...~c_n),\\ A=\left[\begin{matrix} a_{11}&a_{12}&\ldots&a_{1n}\\ a_{21}&a_{22}&\ldots&a_{2n}\\ \vdots&\vdots&&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mn}\\ \end{matrix} \right],X=\left(\begin{matrix}x_1\\x_2\\\vdots\\x_n\\\end{matrix}\right),b=\left(\begin{matrix}b_1\\b_2\\\vdots\\b_n\\\end{matrix}\right)$max(min) z=CXs.t.={AX≤(=,≥)bX≥0​其中 C=(c1​ c2​ ... cn​),A=⎣⎢⎢⎢⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​………​a1n​a2n​⋮amn​​⎦⎥⎥⎥⎤​,X=⎝⎜⎜⎜⎛​x1​x2​⋮xn​​⎠⎟⎟⎟⎞​,b=⎝⎜⎜⎜⎛​b1​b2​⋮bn​​⎠⎟⎟⎟⎞​

称为约束方程组变量的系数矩阵，简称为约束变量的系数矩阵。

线性规划问题的标准形式

对于一般的线性规划模型缺乏统一的结构，这在问题的求解上无疑增加了一定的难度，因此，我们在定义线性规划的标准形式如下：

决策变量 $\{x_i|i=1,2,...,n\}${xi​∣i=1,2,...,n}

目标函数 $max(min)~z=c_1x_1+c_2x_2+...+c_nx_n$max(min) z=c1​x1​+c2​x2​+...+cn​xn​

约束条件 $s.t.=\left\{ \begin{matrix} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1,\\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n=b_2,\\ ~~\vdots\\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=b_m,\\ x_1\ge0,x_2\ge0,\dots x_n\ge0 \end{matrix} \right.$s.t.=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​a11​x1​+a12​x2​+...+a1n​xn​=b1​,a21​x1​+a22​x2​+...+a2n​xn​=b2​,  ⋮am1​x1​+am2​x2​+...+amn​xn​=bm​,x1​≥0,x2​≥0,…xn​≥0​

其中$~b_j\ge0,1\le j\le m.$ bj​≥0,1≤j≤m.

矩阵形式
$max~z=CX\\ s.t.=\left\{ \begin{matrix} AX=b\\ X\ge 0 \end{matrix} \right.$max z=CXs.t.={AX=bX≥0​

其中$A\in \mathbb{R}^{m\times n}$A∈Rm×n是一个行满秩矩阵

标准形式的转化

1.目标函数

目标函数的极小值$\Leftrightarrow$⇔目标函数相反数的最大值，即$~min~z=CX \Rightarrow max~z'=-CX$ min z=CX⇒max z′=−CX

2.约束条件

$\displaystyle\sum_{i=1}^{n} a_{ij}x_j\le b_i~~\Rightarrow~~\sum_{i=1}^{n} a_{ij}x_j+x_{n+i}=b_i~~(x_{n+i}\ge0)$i=1∑n​aij​xj​≤bi​  ⇒  i=1∑n​aij​xj​+xn+i​=bi​  (xn+i​≥0)，其中$~x_{n+i}~$ xn+i​ 称为松弛变量

$\displaystyle\sum_{i=1}^{n} a_{ij}x_j\ge b_i~~\Rightarrow~~\sum_{i=1}^{n} a_{ij}x_j-x_{n+i}=b_i~~(x_{n+i}\ge0)$i=1∑n​aij​xj​≥bi​  ⇒  i=1∑n​aij​xj​−xn+i​=bi​  (xn+i​≥0)，其中$~x_{n+i}~$ xn+i​ 称为剩余变量

松弛变量可以理解为资源的剩余，剩余变量可以理解为需求的溢出

$b_i\le0~~\Rightarrow~~b_i=-b'_i,a_{ij}=-a'_{ij}~$bi​≤0  ⇒  bi​=−bi′​,aij​=−aij′​ 其中$~1\le j\le n~,~b'_i\ge0$ 1≤j≤n , bi′​≥0

3.决策变量

无约束决策变量：$x_j~$xj​ 无限制$\Rightarrow x_j=x'_j-x''_j~$⇒xj​=xj′​−xj′′​ ，其中$x'_j,x''_j\ge0$xj′​,xj′′​≥0

非正变量：$x_j\le0\Rightarrow x_j=-x'_j$xj​≤0⇒xj​=−xj′​，其中$~x'_j\ge0$ xj′​≥0

线性规划问题的解

可行解：如果一个非负矩阵$~X~$ X 满足约束方程，则称矩阵$~X~$ X 为可行解。

可行域：可行解组成的集合$\Omega=\{X\mid AX=b,X\ge0,X\in\mathbb{R}^n\}$Ω={X∣AX=b,X≥0,X∈Rn}称为可行域，可行域中使得目标函数达到最大值的可行解称为最优解。

基：若$~B~$ B 是$~A~$ A 的一个$~m\times m~$ m×m 阶的满秩子矩阵，则称$~B~$ B 为线性规划问题的一个基。$B~$B 中的每一个列向量用$~P_j~$ Pj​ 表示，注意这里基是一组系数矩阵。
$B=\left[\begin{matrix} b_{11}&b_{12}&\ldots&b_{1m}\\ b_{21}&b_{22}&\ldots&b_{2m}\\ \vdots&\vdots&&\vdots\\ b_{m1}&b_{m2}&\ldots&b_{mm}\\ \end{matrix}\right]=(P_1,P_2,\dots,P_m)$B=⎣⎢⎢⎢⎡​b11​b21​⋮bm1​​b12​b22​⋮bm2​​………​b1m​b2m​⋮bmm​​⎦⎥⎥⎥⎤​=(P1​,P2​,…,Pm​)
基解：假设$~B~$ B 为一个基，可知存在$~x_1,\ldots,x_m~$ x1​,…,xm​ 使得$~x_1P_1+\ldots x_mP_m=b$ x1​P1​+…xm​Pm​=b，则称$X=(x_1,\ldots,x_m,0,\ldots,0)^T$X=(x1​,…,xm​,0,…,0)T为基$~B~$ B 的基解，其中$~x_1,\dots,x_m~$ x1​,…,xm​ 称为基变量，其余的决策变量称为非基变量。

基可行解：若满足变量非负约束条件的基解称为基可行解。

可行基：假对应于基可行解的基称为可行基。

退化解：当基解中的非零分量小于$~m~$ m 个时，该基解是退化解

解的维恩图表示：

线性规划问题的解法

1.图解法（略） 2.单纯形法

预备知识

凸集：假设$~C\subset\mathbb{R}^n$ C⊂Rn.若对任意$~X,Y\in C~$ X,Y∈C 和$~0<\lambda<1~$ 0<λ<1 ,都有$~\lambda X+(1-\lambda)Y\subset C~$ λX+(1−λ)Y⊂C ,则称$~C~$ C 为一个凸集（Convex set）。从直观上讲，凸集没有凹入部分，其内部也没有空洞。

凸组合：设向量$~\{x_i\},i=1,2,\dots,n$ {xi​},i=1,2,…,n，如果有实数$\lambda_i\ge0~$λi​≥0 且$~ \displaystyle\sum_{i=1}^n \lambda_i=1$ i=1∑n​λi​=1,则称$~\displaystyle\sum_{i=1}^n\lambda_ix_i~$ i=1∑n​λi​xi​ 为向量$~\{x_i\}~$ {xi​} 的凸组合（凸线性组合）

顶点：假设$~C~$ C 是凸集，且$~X\in C~$ X∈C .若不存在$~X_1,X_2\in C~$ X1​,X2​∈C 使得$~X=\lambda X_1+(1-\lambda)X_2~$ X=λX1​+(1−λ)X2​ ,其中$0<\lambda<1$0<λ<1，则$~X~$ X 称为$~C~$ C 的一个顶点.

凸集内点与其顶点的关系：若$~C~$ C 是有界的凸集，则对任意$~X\in C~$ X∈C ，都可以表示成$~D~$ D 的顶点的凸组合。

几个基本定理（证明不考）

定理1：若线性规划问题存在可行解，则其可行域是凸集。
证明：我们我们考察如下的标准形式的线性规划问题：
$max~z=CX\\ s.t.=\left\{ \begin{matrix} AX=b\\ X\ge 0 \end{matrix} \right.$max z=CXs.t.={AX=bX≥0​
两个不同的解是$~X~$ X 和$~Y~$ Y 满足$~AX=BX=b,X\ge0,Y\ge0~$ AX=BX=b,X≥0,Y≥0 ，则对于任意$~0<\lambda<1$ 0<λ<1，我们有$~A(\lambda X+(1-\lambda)Y)=b,\lambda X+(1-\lambda)Y\ge0~$ A(λX+(1−λ)Y)=b,λX+(1−λ)Y≥0 .所以可行域为凸集。

定理2：线性规划问题的基可行解对应线性规划问题可行域的顶点。

引理 1：线性规划问题的可行解 X 为基可行解的充要条件是 X 的正分量所对应的系数列向量是线性无关的.（由基可行解的定义可知必要性是显然的. ）

证明：假设$X$X为一个基可行解，若$~X~$ X 不是一个顶点，则可行域中存在两个不同的点$~Y,Z~$ Y,Z 使得$~X=\lambda Y+(1-\lambda)Z,0<\lambda<1~$ X=λY+(1−λ)Z,0<λ<1 ，不妨设$~X~$ X 只有前$~k~$ k 个分量大于0，显然$~Y,Z~$ Y,Z 后$~n-k~$ n−k 个分量都为0，我们有
$\sum_{i=1}^kx_iP_i=b,~\sum_{i=1}^ky_iP_i=b,~\sum_{i=1}^kz_iP_i=b.$i=1∑k​xi​Pi​=b, i=1∑k​yi​Pi​=b, i=1∑k​zi​Pi​=b.

由于$~P_1,P_2,\dots,P_k~$ P1​,P2​,…,Pk​ 线性无关（也就是方程只有一个解），我们得到$~X=Y=Z~$ X=Y=Z ，与我们的假设矛盾，所以$X$X一定是一个顶点。

如果假设$X$X是一个顶点，并且假设其只有前$~k~$ k 个分量大于0，若果$~X~$ X 不是一个基可行解，则由引理可知$~P_1,P_2,\dots,P_k~$ P1​,P2​,…,Pk​ 线性相关，说以存在$~k~$ k 个不为零的实数使得
$d_1P_1+d_2P_2+\dots+d_kP_k=0\\ D=(d_1,d_2,\dots,d_k,0,\dots,0)^T$d1​P1​+d2​P2​+⋯+dk​Pk​=0D=(d1​,d2​,…,dk​,0,…,0)T
显然有$~AX=0\rightarrow A(X+sD)=A(X-sD)=b~$ AX=0→A(X+sD)=A(X−sD)=b ，对任意实数$~s~$ s 都成立，$\exist s>0, X+sD\ge0~\wedge~X-sD\ge0$∃s>0,X+sD≥0 ∧ X−sD≥0，则$~X~$ X 是可行域中$~X+sD~$ X+sD 和$~X-sD~$ X−sD 的中点，这与$X$X是一个顶点矛盾，所以$X$X一定是一个基可行解。

定理3：若线性规划问题存在最优解，则一定存在一个基可行解是最优解。

引理2：若$X$X是一个最优解，且$~X=\lambda Y+(1-\lambda)Z~$ X=λY+(1−λ)Z ，其中$~Y,Z~$ Y,Z 是两个可行解，$0<\lambda<1$0<λ<1，则$~CX=CY=CZ~$ CX=CY=CZ .（反证法易得）

证明：设$X$X是一个最优解，且不妨假设其只有前$k$k个分量大于0，若$X$X是一个基可行解，则证毕；否则存在$k$k个不全为0的实数使得（5）式成立，且$A(X+rD)=A(X-sD)=b~$A(X+rD)=A(X−sD)=b 对任意实数$~s,r~$ s,r 都成立，同时$X+rD$X+rD和$X-sD$X−sD至少有一个正分量的数量小于$~k$ k。则由上一个引理可知我们得到了一个新的最优解，且这个最优解的正分量的数量小于$~k$ k，若新的到的最优解依然不是基可行解，重复上面的过程，我们可以得到一个新的最优解，这个最优解的正分量的数量小于$~k$ k，以此类推，经过有限步之后，我们肯定可以得到一个基可行解. 证毕.

定理4：若线性规划问题有可行解，则必有基可行解

定理5：若线性规划问题有最优解，则必有最优基可行解

单纯形法

确定初始基可行解

当线性规划问题全部为“$\le$≤”时，在化为标准型时，加入的m个松弛变量所构成的单位矩阵就可以构成一组基：设给定线性规划问题
$max~z=\sum_{j-1}^n c_jx_j\\ s.t.=\left\{ \begin{matrix} \displaystyle\sum_{j=1}^{n}x_jP_j\le b\\ x_j\ge 0 \end{matrix} \right.$max z=j−1∑n​cj​xj​s.t.=⎩⎪⎨⎪⎧​j=1∑n​xj​Pj​≤bxj​≥0​
在第$~i~$ i 个约束条件上加上松弛变量$~s_{si},(i=1,\dots,m)$ ssi​,(i=1,…,m)，化为标准形式
$max~z=\sum_{j-1}^n c_jx_j+0\sum_{i=1}^m x_{si}\\ s.t.=\left\{ \begin{matrix} \displaystyle\sum_{j=1}^{n}a_{ij}x_j+x_{si}=b,(i=1,2,\dots,m)\\ x_j\ge 0 \end{matrix} \right.$max z=j−1∑n​cj​xj​+0i=1∑m​xsi​s.t.=⎩⎪⎨⎪⎧​j=1∑n​aij​xj​+xsi​=b,(i=1,2,…,m)xj​≥0​
其约束方程的系数矩阵为
$\left[\begin{matrix} a_{11}&a_{12}&\dots&a_{1n}&1&0&\dots&0\\ a_{21}&a_{22}&\dots&a_{2n}&0&1&\dots&0\\ \vdots&\vdots& &\vdots&\vdots&\vdots& &\vdots\\ a_{m1}&a_{m2}&\dots&a_{mn}&0&0&\dots&1\\ \end{matrix}\right]$⎣⎢⎢⎢⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​………​a1n​a2n​⋮amn​​10⋮0​01⋮0​………​00⋮1​⎦⎥⎥⎥⎤​
这个系数矩阵中含有一个单位向量$(P_{s1},P_{s2},\dots,P_{sm})$(Ps1​,Ps2​,…,Psm​)，只要以这个单位矩阵作为基，就可以立即解出基变量值$~x_{si}=b_i~$ xsi​=bi​ ，因为$~b_i\ge0~$ bi​≥0 ,因此$~X=(0,\dots,0,b_1,\dots,b_m)^T$ X=(0,…,0,b1​,…,bm​)T就是一个基可行解。

当线性规划问题中约束条件包含"$=$=“或”$\ge$≥"时，化为标准型后一般不包含单位矩阵，这时常用添加人工变量的方法人为构造一个单位矩阵作为基，称为人工基，具体方法在第五章讨论。

基可行解的转换

不失一般性，设初始基可行解为
$~X^{(0)}=(x^0_1,x^0_2,\dots,x^0_m,\overbrace{0,\dots,0}^{n-m个})^T=\left(\begin{matrix}X_B\\X_N\end{matrix}\right),A=(B~N)$ X(0)=(x10​,x20​,…,xm0​,0,…,0​n−m个​)T=(XB​XN​​),A=(B N)
其中$B$B是对应的可行基，相应的，设$C=(C_B,C_N)$C=(CB​,CN​)，我们有$AX^{(0)}=(B,N)\left(\begin{matrix}X_B\\X_N\end{matrix}\right)=BX_B=b$AX(0)=(B,N)(XB​XN​​)=BXB​=b，我们有$X_B=B^{-1}b,X_N=0$XB​=B−1b,XN​=0，

此时目标函数值$~z^{(0)}=CX=(C_B~C_N)\left(\begin{matrix}X_B\\X_N\end{matrix}\right)=C_BX_B-C_NX_N=C_BB^{-1}b.$ z(0)=CX=(CB​ CN​)(XB​XN​​)=CB​XB​−CN​XN​=CB​B−1b.

原始方程组的增广形式为：

$\left.\begin{matrix}\\ P_1~&P_2&~~\dots&~~P_m&~P_{m+1}~~&\dots&~~P_j&\dots~&P_n&~~b\\ \end{matrix}\right.\\ \left[\begin{array}{ccccccccc|c} a_{11}&a_{12}&\dots&a_{1m}&a_{1,m+1}&\dots&a_{1j}&\dots&a_{1n}&b_1\\ a_{21}&a_{22}&\dots&a_{2m}&a_{2,m+1}&\dots&a_{2j}&\dots&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&&\vdots&&\vdots&\vdots\\ a_{m1}&a_{m2}&\dots&a_{mm}&a_{m,m+1}&\dots&a_{mj}&\dots&a_{mn}&b_m\\ \end{array}\right]$P1​ ​P2​​  …​  Pm​​ Pm+1​  ​…​  Pj​​… ​Pn​​  b​⎣⎢⎢⎢⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​……⋱…​a1m​a2m​⋮amm​​a1,m+1​a2,m+1​⋮am,m+1​​………​a1j​a2j​⋮amj​​………​a1n​a2n​⋮amn​​b1​b2​⋮bm​​⎦⎥⎥⎥⎤​

因为$~P_1,P_2,\dots,P_m~$ P1​,P2​,…,Pm​ 是$~\mathbb{R^m}~$ Rm 的一组基，所以其余的$P_j$Pj​都可以用这个基来表示，我们可以将$P_j$Pj​替换为$BB^{-1}P_j$BB−1Pj​，所以有$~B(X_B-\theta B^{-1}P_j)+\theta P_j=b$ B(XB​−θB−1Pj​)+θPj​=b，我们假设$X_B-\theta B^{-1}P_j\ge0$XB​−θB−1Pj​≥0，那么我们得到了一个新的可行解
$\tilde{X}=\left(\begin{matrix}X_B-\theta B^{-1}P_j\\0\end{matrix}\right)+\theta e_j$X~=(XB​−θB−1Pj​0​)+θej​
其中，$e_j~$ej​ 为第$~j~$ j 个分量为1其余分量为0的单位列向量，这个可行解的目标函数值为
$\begin{aligned} \widetilde{z}&=C\tilde{X}\\ &=(C_B~C_N)\left(\left(\begin{matrix}X_B-\theta B^{-1}P_j\\0\end{matrix}\right)+\theta e_j\right)\\ &=C_BX_B+\theta(c_j-C_BB^{-1}P_j)\\ &=z^{(0)}+\theta(c_j-C_BB^{-1}P_j) \end{aligned}$z​=CX~=(CB​ CN​)((XB​−θB−1Pj​0​)+θej​)=CB​XB​+θ(cj​−CB​B−1Pj​)=z(0)+θ(cj​−CB​B−1Pj​)​

我们令$~\sigma_j=c_j-C_BB^{-1}P_j$ σj​=cj​−CB​B−1Pj​，则$\tilde{z}=z^{(0)}+\theta\sigma_j$z~=z(0)+θσj​，$\sigma_j~$σj​ 被称为检验数。

​ 如果$~\theta_j>0$ θj​>0，则新的可行解可以使目标函数变大，且$~\theta~$ θ 应该越大越好. 此时注意到为了保证$\tilde{X}$X~是一个可行解，应该有$~X_B-\theta B^{-1}P_j\ge0$ XB​−θB−1Pj​≥0，显然这个$(B^{-1}P_j)$(B−1Pj​)很难处理，我们不妨在求解之前通过初等行变换把$B$B化为单位矩阵（想一想，为什么可以这么做？），即化成

$\left.\begin{matrix}\\ P_1&P_2&\dots&P_m&P_{m+1}&\dots&P_j&\dots&~~P_n&~~b&\\ \end{matrix}\right.\\ \left[\begin{array}{ccccccccc|c} 1&0&\dots&0&a_{1,m+1}&\dots&a_{1j}&\dots&a_{1n}&b_1\\ 0&1&\dots&0&a_{2,m+1}&\dots&a_{2j}&\dots&a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&&\vdots&&\vdots&\vdots\\ 0&0&\dots&1&a_{m,m+1}&\dots&a_{mj}&\dots&a_{mn}&b_m\\ \end{array}\right]$P1​​P2​​…​Pm​​Pm+1​​…​Pj​​…​  Pn​​  b​​⎣⎢⎢⎢⎡​10⋮0​01⋮0​……⋱…​00⋮1​a1,m+1​a2,m+1​⋮am,m+1​​………​a1j​a2j​⋮amj​​………​a1n​a2n​⋮amn​​b1​b2​⋮bm​​⎦⎥⎥⎥⎤​

假设$B$B是一个单位矩阵且$b>0$b>0，那么$~\theta~$ θ 的最大值显然是$\displaystyle\theta^*=min\{\frac{b_i}{a_{ij}}:a_{ij}>0,1\le i\le m\}$θ∗=min{aij​bi​​:aij​>0,1≤i≤m}，不妨设$\displaystyle\theta^*=\frac{b_r}{a_{rj}}$θ∗=arj​br​​，则$(P_1,\dots,P_{r-1},P_{r+1},\dots,P_m,P_j)$(P1​,…,Pr−1​,Pr+1​,…,Pm​,Pj​)构成一组新的基，这个基的基解和目标函数值为

$X^{(1)}=\left(\begin{matrix}X_B-\theta^* B^{-1}P_j\\0\end{matrix}\right)+\theta^* e_j,z^{(1)}=z^{(0)}+\theta^*\sigma_j$X(1)=(XB​−θ∗B−1Pj​0​)+θ∗ej​,z(1)=z(0)+θ∗σj​

最优性检验和解的判别

（1） 当$~\forall~\sigma_j\le0$ ∀ σj​≤0时，表明现有顶点的目标函数的值比起相邻各顶点的目标

函数值都大，现以顶点对应的基可行解即为最优解。（为什么局部最优解等于全局最优解？）

（2）当$~\forall~\sigma_j\le0\wedge\exist~ \sigma_r=0$ ∀ σj​≤0∧∃ σr​=0时，$\tilde{X}=\left(\begin{matrix}X_B-\theta B^{-1}P_j\\0\end{matrix}\right)+\theta e_j~$X~=(XB​−θB−1Pj​0​)+θej​ 和$~X^{(0)}$ X(0)的线性组合都是最优解，因此有无限多个解

（3）当$\exist~\sigma_j>0\wedge(\forall~\theta>0)~X_B-\theta B^{-1}P_j\ge0$∃ σj​>0∧(∀ θ>0) XB​−θB−1Pj​≥0时，目标函数值可以取到无限大，最优解无界。

单纯性法的计算步骤

$to~be~continue...$to be continue...