单纯形表法（基本原理+例题解析）

大家好，我是讯享网，很高兴认识大家。

基本思想：从一个基本可行解出发，一步步的转到更优的基本可行解，直至最优解。

单纯形法总有两种形式，一是单纯形法，还有一种是单纯形表法。下面我们依次展开讨论。

单纯形法：

基本概念：

单纯形法其实是对消去法的一个总结，归纳和公式化。

标准线性规划问题：

$\left\{\begin{matrix} min f(x)=c^{T}x\\ s.t. Ax=b \\ x\geq 0 \end{matrix}\right.$
讯享网， rank(A)=m

$A=(p_{1},p_{2},...,p_{n})$ ，假设 $B=(p_{1},p_{2},...,p_{m})$ 是可行基 A=(B,N) ，根据 B 矩阵，将 x 分为基变量 $x_{B}=(x_{1},x_{2},...,x_{m})^{T}$ 和非基变量 $x_{N}=(x_{m+1},x_{m+2},...,x_{n})^{T}$ 将 c 同样分为 $c_{B}=(c_{1},c_{2},...,c_{m})^{T}$ 和 $c_{N}=(c_{m+1},c_{m+2},...,c_{n})^{T}$ 。

约束条件 Ax=b 可以写成：

$\bigl(\begin{smallmatrix} B ,&N \end{smallmatrix}\bigr)\binom{x_{B}}{x_{N}}=b\Rightarrow Bx_{B}+Nx_{N}=b\Rightarrow Bx_{B}=b-Nx_{N}$

两边左乘 $B^{-1}$ ，得到 $x_{B}=B^{-1}b-B^{-1}Nx_{N}$

目标函数 $f(x)=c^{T}x$ 可以写成：

$c^{T}x=\bigl(\begin{smallmatrix} c_{B}^{T} ,&c_{N}^{T} \end{smallmatrix}\bigr)\binom{x_{B}}{x_{N}}=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}$

将 $x_{B}=B^{-1}b-B^{-1}Nx_{N}$ 代入目标函数表达式，得：

$c^{T}x=c_{B}^{T}(B^{-1}b-B^{-1}Nx_{N})+c_{N}^{T}x_{N}=c_{B}^{T}B^{-1}b-c_{B}^{T}B^{-1}Nx_{N}+c_{N}^{T}x_{N}$

$=c_{B}^{T}B^{-1}b-(c_{B}^{T}B^{-1}N-c_{N}^{T})x_{N}$

令 $x_{N}=0$ ，可得 $x_{B}=B^{-1}b$ ，从而得到基本解：

$\bar{x}=\binom{x_{B}}{x_{N}}=\binom{B^{-1}b}{0}$

如果 $B^{-1}b\geq 0$ ，则 $\bar{x}$ 是基本可行解，B 是可行基。

目标函数 $f(x)=c_{B}^{T}B^{-1}b-(c_{B}^{T}B^{-1}N-c_{N}^{T})x_{N}$ .

如果 $\bar{x}$ 是基本可行解，并且 $c_{B}^{T}B^{-1}N-c_{N}^{T}\leq 0$ ，则可以断定 $\bar{x}$ 是最优解。

检验数向量：

定义：称 $(c_{B}^{T}B^{-1}A-c^{T})$ 是标准线性规划的检验数向量，如果 $(c_{B}^{T}B^{-1}A-c^{T})\leq 0$ 则取到了最优解。

由此综合，可总结出定理：

1）对于标准线性规划问题，如果基矩阵为 B ，并且 $B^{-1}b\geq 0$ （ B 是可行基），并且所有的检验数都非正（即 $(c_{B}^{T}B^{-1}A-c^{T})\leq 0$ ），则对应于 B 的基本可行解 $\bar{x}=\binom{B^{-1}b}{0}$ 是最优解。

2）如果线性规划的某个检验数 $\sigma _{j}> 0$ ，而相对应的列向量 $p_{j}\leq 0$ ，则这个线性规划无解。

下面给出运用两个定理的例题，用于加深理解。

1，判断 $x=(4,0,5,0)^{T}$ 是否为线性规划问题的最优解？

$\left\{\begin{matrix} minf(x)=x_{1}+2x_{2}+3x_{3}-2x_{4}\\ s.t. x_{1}-2x_{2}+4x_{4}=4 \\ x_{2}+x_{3}-2x_{4}=5 \\ x_{1},x_{2},x_{3},x_{4}\geq 0 \end{matrix}\right.$

解：

$A=\left [ \begin{smallmatrix} 1& -2 &0 &4 \\0 &1 &1 &-2 \end{smallmatrix} \right ]$ ， $b=\left [ \begin{smallmatrix} 4\\5 \end{smallmatrix}\right ]$ ， $c=\left [ \begin{smallmatrix} 1\\2 \\3 \\-2 \end{smallmatrix}\right ]$

由 $x=(4,0,5,0)^{T}$ 知， $x_{1}$ ， $x_{3}$ 是基变量， $x_{2}$ ， $x_{4}$ 是非基变量

$B=\left [\begin{smallmatrix} 1 &0 \\0 &1 \end{smallmatrix} \right ]$ , $c_{B}^{T}=(1,3)$

下面计算检验数向量：

$(c_{B}^{T}B^{-1}A-c^{T})=(1,3)\left [\begin{smallmatrix} 1 &0 \\0 &1 \end{smallmatrix} \right ]\left [ \begin{smallmatrix} 1& -2 &0 &4 \\0 &1 &1 &-2 \end{smallmatrix} \right ]-(1,2,3,-2)$

$=(1,1,3,-2)-(1,2,3,-2)=(0,-1,0,0)\leq 0$

$x=(4,0,5,0)^{T}$ 是最优解。

2，对于下面的线性规划，讨论其有无最优解？

$\left\{\begin{matrix} minf(x)=x_{1}-x_{2}\\ s.t. 3x_{1}-2x_{2}+x_{3}=1 \\ 2x_{1}-x_{2}+x_{4}=5 \\ x_{1},x_{2},x_{3},x_{4}\geq 0 \end{matrix}\right.$

解：

$A=\left [ \begin{smallmatrix} 3& -2 &1 &0 \\2 &-1 &0 &1 \end{smallmatrix} \right ]$ ， $b=\left [ \begin{smallmatrix} 1\\5 \end{smallmatrix}\right ]$ ， $c=\left [ \begin{smallmatrix} 1\\-1 \\0 \\0 \end{smallmatrix}\right ]$

$B=\left [\begin{smallmatrix} 1 &0 \\0 &1 \end{smallmatrix} \right ]$ , $c_{B}^{T}=(0,0)$

下面主要判断 $\sigma _{2}$ 是否大于0?

计算检验数向量：

$(c_{B}^{T}B^{-1}A-c^{T})=(0,0)\left [ \begin{smallmatrix} 3& -2 &1 &0 \\2 &-1 &0 &1 \end{smallmatrix} \right ]-(1,-1,0,0)$

=(0,0,0,0)-(1,-1,0,0)=(-1,1,0,0)

$\sigma _{2}$ =1>0，由定理2可知此线性规划无最优解。

算法步骤：

步骤1：找到初始可行基矩阵 B ，解 $Bx_{B}=b$ ，得到 $x_{B}=B^{-1}b=\bar{b}$ ，令 $x_{m}=0$ ，确定初始基本可行解，计算目标函数 $f=c_{B}x_{B}$

步骤2：求单纯性乘子 w，解 $wB=c_{B}$ ，得到 $w=c_{B}B^{-1}$ ，对于所有的非基变量，计算判别数 $(z_{j}-c_{j})=wp_{j}-c_{j}$ ，令 $(z_{k}-c_{k})=max(z_{j}-c_{j}),j\in R^{n}$ ，若 $(z_{k}-c_{k})\leq 0$ ，则对于所有非基变量 $(z_{j}-c_{j})\leq 0$ ，对于基变量的判别数总为零，该基本可行解是最优解；否则，转步骤3；

步骤3：解 $By_{k}=p_{k}$ ，得到 $y_{k}=B^{-1}p_{k}$ ，若 $y_{k}\leq 0$ ，则停止运算，问题不存在有限最优解；否则，转步骤4；

步骤4：确定下标 r ， $\frac{\bar{b}_{r}}{y_{rk}}={min{\frac{\bar{b}_{i}}{y_{ik}}}|y_{ik}>0}$ ， $x_{Br}$ 为离基变量， $x_{k}$ 为进基变量，用 $p_{k}$ 替换 $p_{B}$ ，得到新的矩阵 B，转步骤1。

例题分析：

例题：利用单纯形法求解下列问题：

$\left\{\begin{matrix} min-4x_{1}-x_{2}\\ s.t. -x_{1}+2x_{2}\leq 4\\ 2x_{1}+3x_{2}\leq 12\\x_{1}-x_{2}\leq 3 \\ x_{1},x_{2}\geq 0 \end{matrix}\right.$

解：将约束条件化为标准型：

$\left\{\begin{matrix} -x_{1}+2x_{2}+x_{3}= 4\\ 2x_{1}+3x_{2}+x_{4}= 12\\x_{1}-x_{2}+x_{5}= 3 \\ x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0 \end{matrix}\right.$

$A=(p_{1},p_{2},p_{3},p_{4},p_{5})=\bigl(\begin{smallmatrix} -1 &2 &1 &0 & 0\\2 &3 &0 &1 &0 \\1 &-1 &0 &0 &1 \end{smallmatrix}\bigr)$ ， $b=\bigl(\begin{smallmatrix} 4\\ 12\\ 3 \end{smallmatrix}\bigr)$

第一次迭代：

$B=(p_{3},p_{4},p_{5})=\left [ \begin{smallmatrix} 1 &0 &0 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{smallmatrix} \right ]$ ， $B^{-1}=\left [ \begin{smallmatrix} 1 &0 &0 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{smallmatrix} \right ]$

$x_{B}=B^{-1}b=\bigl(\begin{smallmatrix} 4\\ 12\\ 3 \end{smallmatrix}\bigr)$ ， $x_{N}=\binom{x_{1}}{x_{2}}=\binom{0}{0}$

$f_{1}=c_{B}x_{B}=(0,0,0)(4,12,3)^{T}=0$

$w=c_{B}B^{-1}=(0,0,0)$

计算检验数：

$\left\{\begin{matrix} (z_{1}-c_{1})=wp_{1}-c_{1}=(0,0,0)(-1,2,1)^{T}-(-4)=4\\(z_{2}-c_{2})=wp_{2}-c_{2}=(0,0,0)(2,3,-1)^{T}-(-1)=1 \end{matrix}\right.$

确定进基变量：又知道对应基变量的判别数均为零，因此最大判别数是 $z_{1}-c_{1}=4$ ,下标为1， $x_{1}$ 为进基变量；

确定离基变量：

$y_{1}=B^{-1}p_{1}=\left [ \begin{smallmatrix} 1 &0 &0 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{smallmatrix} \right ]\left [ \begin{smallmatrix} -1 \\2 \\1 \end{smallmatrix}\right ]=\left [ \begin{smallmatrix} -1 \\2 \\1 \end{smallmatrix}\right ]$ , $\bar{b}=B^{-1}b=\bigl(\begin{smallmatrix} 4\\ 12\\ 3 \end{smallmatrix}\bigr)$

确定下标：

$\frac{\bar{b}_{r}}{y_{r1}}={min{\frac{\bar{b}_{i}}{y_{i1}}}|y_{i1}>0}=min[\frac{12}{2},\frac{3}{1}]=\frac{3}{1}$

$\Rightarrow r=3$

$x_{B}$ 中第三个分量 $x_{5}$ 为离基变量，用 $p_{1}$ 替换 $p_{5}$ ，得到新基，进行下一次迭代。

第二次迭代：

$B=(p_{3},p_{4},p_{1})=\left [ \begin{smallmatrix} 1 &0 &-1 \\ 0 & 1 & 2\\ 0 & 0 & 1 \end{smallmatrix} \right ]$ ， $B^{-1}=\left [ \begin{smallmatrix} 1 &0 &1 \\ 0 & 1 &-2\\ 0 & 0 & 1 \end{smallmatrix} \right ]$

$x_{B}=B^{-1}b=\bigl(\begin{smallmatrix} 7\\ 6\\ 3 \end{smallmatrix}\bigr)$ ， $x_{N}=\binom{x_{2}}{x_{5}}=\binom{0}{0}$

$f_{2}=c_{B}x_{B}=(0,0,-4)(7,6,3)^{T}=-12$

$w=c_{B}B^{-1}=(0,0,-4)$

计算检验数：

$\left\{\begin{matrix} (z_{2}-c_{2})=wp_{2}-c_{2}=(0,0,-4)(2,3,-1)^{T}-(-1)=5\\(z_{5}-c_{5})=wp_{5}-c_{5}=(0,0,-4)(0,0,1)^{T}-(0)=-4 \end{matrix}\right.$

确定进基变量：又知道对应基变量的判别数均为零，因此最大判别数是 $z_{2}-c_{2}=5$ ,下标为2， $x_{2}$ 为进基变量；

确定离基变量：

$y_{2}=B^{-1}p_{2}=\left [ \begin{smallmatrix} 1 &0 &1 \\ 0 & 1 &-2\\ 0 & 0 & 1 \end{smallmatrix} \right ]\left [ \begin{smallmatrix} 2 \\3 \\-1 \end{smallmatrix}\right ]=\left [ \begin{smallmatrix} 1 \\5 \\-1 \end{smallmatrix}\right ]$ , $\bar{b}=B^{-1}b=\bigl(\begin{smallmatrix} 7\\ 6\\ 3 \end{smallmatrix}\bigr)$

确定下标：

$\frac{\bar{b}_{r}}{y_{r2}}={min{\frac{\bar{b}_{i}}{y_{i2}}}|y_{i2}>0}=min[\frac{7}{1},\frac{6}{5}]=\frac{6}{5}$

$\Rightarrow r=2$

$x_{B}$ 中第二个分量 $x_{4}$ 为离基变量，用 $p_{2}$ 替换 $p_{4}$ ，得到新基，进行下一次迭代。

第三次迭代：

$B=(p_{3},p_{2},p_{1})=\left [ \begin{smallmatrix} 1 &2 &-1 \\ 0 & 3 & 2\\ 0 & -1 & 1 \end{smallmatrix} \right ]$ ， $B^{-1}=\left [ \begin{smallmatrix} 1 &-\frac{1}{5} &\frac{7}{5} \\ 0 & \frac{1}{5} & -\frac{2}{5}\\ 0 & \frac{1}{5} & \frac{3}{5} \end{smallmatrix} \right ]$

$x_{B}=B^{-1}b=\bigl(\begin{smallmatrix} \frac{29}{5}\\ \frac{6}{5}\\ \frac{21}{5} \end{smallmatrix}\bigr)$ ， $x_{N}=\binom{x_{4}}{x_{5}}=\binom{0}{0}$

$f_{3}=c_{B}x_{B}=(0,-1,4)\bigl(\begin{smallmatrix} \frac{29}{5}\\ \frac{6}{5}\\ \frac{21}{5} \end{smallmatrix}\bigr)=-18$

$w=c_{B}B^{-1}=(0,-1,-2)$

计算检验数：

$\left\{\begin{matrix} (z_{4}-c_{4})=wp_{4}-c_{4}=(0,-1,-2)(0,1,0)^{T}-(0)=-1\\(z_{5}-c_{5})=wp_{5}-c_{5}=(0,-1,-2)(0,0,1)^{T}-(0)=-2 \end{matrix}\right.$