《用对偶单纯形法求解线性规划问题》由会员分享，可在线阅读，更多相关《用对偶单纯形法求解线性规划问题（3页珍藏版）》请在金锄头文库上搜索。
1、例4-7用对偶单纯形法求解线性规划问题.Minz=5x+3x12s.t.-2X1+3x2三63x6x三412Xj20(j=l,2)解：将问题转化为Maxz=-5x-3x12x1-3x2+x3=-6-3X1+6X2+心4XjO(j=l,2,3,4)其中，x，x为松弛变量，可以作为初始基变量，单纯形表见表4-17.34表4-17例4-7单纯形表C.-6-3-40CB迭代0次XBbX1X2X3X40X4-62-3100X-4-3601-z=-zjj0-5-300CB迭代1次XBbX1X2X3X4-3X42-2/31-1/300X-3-161021-z=1-zjj6-70-10在表4-17中,b=-1
2、6v0,而y0,故该问题无可行解.注意:对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.若原问题既无可行基，而检验数中又有小于0的情况只能用人工变量法求解.在计算机求解时,只有人工变量法,没有对偶单纯形法.3.对偶问题的最优解由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.设原问题(p)为Minz=CXrAX二bs.t.0则标准型(LP)为Maxz=CXrAX二bs.t.tX0其对偶线性规划(D)为Maxz=bTYrAX二bs.t.tX0用对偶单纯形法求解(LP),得最优基B
3、和最优单纯形表T(B)。对于(LP)来说，当j=n+i时，有Pj=-ei，cj=0从而，在最优单纯形表T(B)中，对于检验数，有(On+l,Qn+2Pn+m)=(cn+i,，)-CbB-1(Pn+l,Pn+2.,Pn+m)=-CB-1(-I)B于是，Y*=(On+1，On+2On+m)T。可见，在(LP)的最优单纯形表中，剩余变量对应的检验数就是对偶问题的最优解。同时，在最优单纯形表T(B)中，由于剩余变量对应的系数所以B-l=-yn+l，-yn+2-yn+m例4-8求下列线性规划问题的对偶问题的最优解。Minz=6x+8xl2s.t.x2x三20l+23x+2x三50l2Xj20(j=1,2
4、)解：将问题转化为Maxz=-6x-8xl2s.t.-x2x+x=20l23-3x-2x+x=50l24Xj20(j=1,2，3,4)用对偶单纯形法求解如表表4-18例4-8单纯形表在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。例4-9：求解线性规划问题：Minf=2x1+3x2+4x3S.t.x1+2x2+x3三32x1-x2+x3三4x1,x2,x3三0标准化：Maxz=-2x1-3x2-4xx1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4兀1竝舟3尹4尹5M0表格对偶单纯形法C.-6-800CB迭代0次XBbX1X2X3X4-8X5/201-3/41/4-6X-15101/2-1/2-z=1-zjj-1100031
