单纯形法（四）理论部分（终结）

本文主要是介绍单纯形法（四）理论部分（终结），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

典式

我们对于 A A A先随便选择一个基，不妨假设 A A A的前 m m m列就是一个基(不是的话先对 A A A换列即可，这不是重点，这里假设完全是为了证明简洁，实际操作的时候并不需要)，则等式约束 A x = b Ax=b Ax=b变为:


同样，目标函数 c T x c^Tx cTx我们改写为：

从而，原来的线性规划变为：

我们之后，都将转为来求解这个线性规划，那么应该注意到，变量仍然是 x x x，但是 B , b , N , c B T , c N T B,b,N,c_B^T,c_N^T B,b,N,cBT​,cNT​都是常量了。
上述矩阵有点抽象，为了具体研究，我们把上面的常量进行展开。我们令

【复习一下】 B − 1 b > = 0 B^{-1}b>=0 B−1b>=0吗？
答案：不一定哦，不明白的自己恶补之前的单纯形法系列。

经过上述常量展开，线性规划最终成为了：

我们将上述线性规划称之为与原线性规划(LP)对应的典式(LP')。
注意，除了 x x x，其他的全是常量。我们要找一个 x x x，使得这个目标函数值最小。

之后，我们均基于上述典式来讨论。
λ i \lambda_i λi​在单纯形法中有一个专门的名字叫做检验数。

定理

定理1: \quad 如果上述用到的基B是一个可行基，而且所有检验数小于等于0，那么可行基对应的基可行解就是最优解。

证明: \quad 由于基B是一个可行基，那么对应的基可行解就是 ( x B , x N ) = （ x B , 0 ) = ( B − 1 b , 0 ) = ( α 1 , ⋯   , α m , 0 , ⋯   , 0 ) ≥ 0 (x_B,x_N)=（x_B,0)=(B^{-1}b,0)=(\alpha_1,\cdots,\alpha_m,0,\cdots,0)\ge 0 (xB​,xN​)=（xB​,0)=(B−1b,0)=(α1​,⋯,αm​,0,⋯,0)≥0，我们把这个基可行解代入到目标函数中去，发现值为 f 0 f_0 f0​，那么有没有其他更小的值了呢？下面继续证明，所有检验数小于等于0时，没有了。
由于 f 0 f_0 f0​为常数，而且所有检验数小于等于0，所以如果 x N x_N xN​中但凡有一个元素不为0，目标函数值都会变大（我们是最小化）。举个例子，如果 λ m + 1 = − 1 , x m + 1 = 10 , f 0 = 2 \lambda_{m+1}=-1,x_{m+1}=10,f_0=2 λm+1​=−1,xm+1​=10,f0​=2，那么 z = f 0 − ( − 1 ∗ 10 + 0 ) = 12 z=f_0-(-1*10+0)=12 z=f0​−(−1∗10+0)=12，我们发现了什么？ x N x_N xN​中不能有元素取非0，否则目标函数值都会变大。

而且细心的你也发现了，姑且不论你 x m + 1 = 10 x_{m+1}=10 xm+1​=10会使目标函数变大不说，而且还可能破坏 x B > = 0 x_B>=0 xB​>=0,因为你应该注意到 x 1 x_1 x1​会与 x m + 1 x_{m+1} xm+1​有关（下面的那 m m m个等式条件）。

证毕。

我们对于这个典式一下子就求完了最优解，超快有没有，而且前面说了这个和原始线性规划是等价的，你可以从典式一步一步写回去，所以典式最优解就是原来线性规划的最优解。

但是，所有检验数都小于等于0，我们通常没有这么好的运气。只是说，我们选了一个可行基之后，改造为典式，发现其检验数全小于等于0，我们就下结论，可行基对应的基可行解就是最优解。

所以我们要面对一般性的情况，如果有检验树大于0怎么办？

引理2: \quad 如果原线性规划存在最优解，而且上述用到的基B是一个可行基，而且存在一个检验数 λ m + k > 0 \lambda_{m+k}>0 λm+k​>0，那么 x m + k x_{m+k} xm+k​对应的对应的系数 β 1 , m + k , ⋯   , β m , m + k \beta_{1,m+k},\cdots,\beta_{m,m+k} β1,m+k​,⋯,βm,m+k​至少有一个大于0。

证明: \quad 我们采用反证法，假设 x m + k x_{m+k} xm+k​对应的对应的系数 β 1 , m + k , ⋯   , β m , m + k \beta_{1,m+k},\cdots,\beta_{m,m+k} β1,m+k​,⋯,βm,m+k​全部小于等于0。我们上面已经知道了，把基可行解代入的时候目标函数值是 f 0 f_0 f0​。我们将基可行解进行改造，让这个非基变量 x m + k x_{m+k} xm+k​从0增大到 + ∞ +\infty +∞，其他非基变量的值保持0不变，不过，其他的m个基变量也因为等式约束的问题，因 x m + k x_{m+k} xm+k​增大而变了，我们发现其他的m个基变量只增不减，从而仍然大于等于0。为什么？为了给大家更好理解，我们假设 k = 1 k=1 k=1，即 λ m + 1 > 0 \lambda_{m+1}>0 λm+1​>0，根据反证法假设 β 1 , m + 1 , ⋯   , β m , m + 1 \beta_{1,m+1},\cdots,\beta_{m,m+1} β1,m+1​,⋯,βm,m+1​全小于等于0。又，我们只改造了 x m + 1 x_{m+1} xm+1​这个非基变量，其他非基变量仍然为0，所以等式约束变成了下面这样。

我们增大 x m + 1 x_{m+1} xm+1​，又前面的系数全小于等于0，那么基变量 x i x_i xi​当然只增不减了。

即，这个被改造的解 ( a 1 , ⋯   , a m , + ∞ , 0 , ⋯   , 0 ) (a_1,\cdots,a_m,+\infty,0,\cdots,0) (a1​,⋯,am​,+∞,0,⋯,0)仍然是可行解，我们代入到目标函数中，看看值是多少。由于 λ m + k > 0 \lambda_{m+k}>0 λm+k​>0， x m + k − > + ∞ x_{m+k}\quad -> +\infty xm+k​−>+∞所以 λ m + k x m + k − > + ∞ \lambda_{m+k}x_{m+k} \quad ->+\infty λm+k​xm+k​−>+∞，那么代入目标函数值，此时为 f 0 − + ∞ + 0 = − ∞ f_0-+\infty +0 =-\infty f0​−+∞+0=−∞。发现这个线性规划没有最优解，可以为负无穷，与定理中的条件有最优解矛盾，从而反证法中的假设不成立，即： x m + k x_{m+k} xm+k​对应的对应的系数 β 1 , m + k , ⋯   , β m , m + k \beta_{1,m+k},\cdots,\beta_{m,m+k} β1,m+k​,⋯,βm,m+k​至少有一个大于0。

证毕。

还是要说的是，上面这个引理并没有指明遇到这种情况的时候，怎么找最优解。所以给出定理3。

定理3: \quad 如果上述用到的基B是一个非退化的可行基（即对应的基可行解是非退化的），而且存在一个检验数 λ m + k > 0 \lambda_{m+k}>0 λm+k​>0，而且 x m + k x_{m+k} xm+k​对应的对应的系数 β 1 , m + k , ⋯   , β m , m + k \beta_{1,m+k},\cdots,\beta_{m,m+k} β1,m+k​,⋯,βm,m+k​至少有一个大于0。那么一定存在另外一个非退化的可行基，它对应的基可行解比当前的基可行解得到的目标函数值小，即更优。

证明: \quad 有了引理2，这个较容易证明。根据定理中的条件，我们假设检验数 λ m + 1 > 0 , β 1 , m + 1 > 0 \lambda_{m+1}>0,\beta_{1,m+1}>0 λm+1​>0,β1,m+1​>0，我们依然是采用上面构造一个新的可行解的思想。不过这次我们不敢让 x m + 1 x_{m+1} xm+1​增大到无穷大了，因为：

如果增大到无穷大，又由于 β 1 , m + 1 > 0 \beta_{1,m+1}>0 β1,m+1​>0，那么 x 1 x_1 x1​必然无穷小。从而不满足可行解的要求。所以我们出于减小目标函数值得目的，我们当然会适当的增大 x m + 1 = θ > 0 x_{m+1}=\theta>0 xm+1​=θ>0，使得其刚好满足等式 x 1 = 0 = α 1 − β 1 , m + 1 θ x_1=0=\alpha_1-\beta_{1,m+1}\theta x1​=0=α1​−β1,m+1​θ，这个时候我们改造成了可行解为 ( 0 , a 2 , ⋯   , a m , θ , 0 , ⋯   , 0 ) (0,a_2,\cdots,a_m,\theta,0,\cdots,0) (0,a2​,⋯,am​,θ,0,⋯,0)，代入目标函数值，发现其为 f 0 − λ m + 1 x m + 1 = f 0 − λ m + 1 θ < f 0 f_0 -\lambda_{m+1} x_{m+1}=f_0-\lambda_{m+1}\theta<f_0 f0​−λm+1​xm+1​=f0​−λm+1​θ<f0​，真的更优了！这个时候其实相当于将 x 0 = 0 x_0=0 x0​=0变成了出基，变成了非基变量， x m + 1 x_{m+1} xm+1​变成了入基，成为了基变量，而且这个解也是非退化的基可行解，大家想想是不是！根据单纯形法系列篇的知识，一个这样的基可行解也对应着一个新的的可行基，即我们可以将原线性规划的基更换为这个新的可行基，然后化成典式，回到定理1，查看检验数是不是全部小于等于0，如果是，那么这个新基对应的基可行解就是最优解，否则根据定理3，继续入基出基。

这篇关于单纯形法（四）理论部分（终结）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！