单纯形法(四)理论部分(终结)

2021/4/18 18:56:05

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

典式

我们对于 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,继续入基出基。



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


扫一扫关注最新编程教程