用對偶單純形法求解線性規(guī)劃問題

1、用對偶單純形法求解線性規(guī)劃問題The final edition was revised on December 14th, 2020.例47用對偶單純形法求解線性規(guī)劃問題.Min z =5xi+3x, -2 xi + 3x? M63 xi - 6 x. M4Xjo (j=l,2)解:將問題轉(zhuǎn)化為Max z 二一5 xi - 3 x、 2 xi 一 3x 分 + X3 二63xi+ 6 x2 + X*-4XjMO (j=l,2. 3,4)其中，X3| x為松弛變量，可以作為初始基變量，單純形表見表4-17表4-17例4-7單純形表G6-3-40Cb迭代0 次XbbXxx2XsX,0X,-62-

2、3100X5-4-3601 匕-亦0-5-300G迭次XBbX：Xox3x.-3X.2-2/31-1/300X：-161021-Z = c 廠6-70-10在表4-17中,b=16v0,而yO,故該問題無可行解.注意：對偶單純形法仍是求解原問題，它是適用于當原問題無可行基，且所有檢驗數(shù)均為負的情況.若原問題既無可行基，而檢驗數(shù)中又有小于0的情況.只能用人工變量法求解. 在計算機求解時，只有人工變量法,沒有對偶單純形法.3.對偶問題的最優(yōu)解由對偶理論可知，在原問題和對偶問題的最優(yōu)解之間存在著密切的關系，可以根 據(jù)這些關系，從求解原問題的最優(yōu)單純形表中，得到對偶問題的最優(yōu)解.(1)設原問題(P)為

3、Min z=CXAX=b* X0則標準型(LP)為Max z=CXAX=bX0其對偶線性規(guī)劃(D)為Max z=b1YAX=bX0用對偶單純形法求解(LP)，得最優(yōu)基B和最優(yōu)單純形表T (B)。對于(LP)來說，當 j二n+i 時，有 Pj=-ei, cj=O從而，在最優(yōu)單純形表T (B)中，對于檢驗數(shù)，有(on+1, on+2on+m) = (cn+i, cn+2., Cn+m) -CbB1 (Pn+l,Pn+2.,Pn+m) =- CbB1 (-1)于是，Y*二(cm+1, on+2on+m) T o可見，在(LP)的最優(yōu)單純形表 中，剩余變量對應的檢驗數(shù)就是對偶問題的最優(yōu)解。同時，在最優(yōu)

4、單純形表T (B)中，由于剩余變量對應的系數(shù)所以B1 = (-y n+l,y n+2yn+m)例48求下列線性規(guī)劃問題的對偶問題的最優(yōu)解。Min z =6xi+8x, xi + 2x2 M203xi+2x分 M50XjMO (j=l,2)解:將問題轉(zhuǎn)化為Max z =-6xi-8x.(-xi _ 2x2 + X3二20 一3 XI - 2x 分 + X| =50Xjo (j二 1,2, 3,4)用對偶單純形法求解如表表4-18例4-8單純形表G6-800Cs迭代0次XbbX：x=XsX,-8X.5/201-3/41/4_6Xs15101/2-1/2-Z = c丿-亦-1100031在引入松弛變

5、量化為標準型之后，約束等式兩側(cè)同乘-1,能夠立即得到檢驗數(shù) 全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進行求解，非常方 便。對于有些線性規(guī)劃模型，如果在開始求解時不能很快使所有檢驗數(shù)非正，最 好還是采用單純形法求解。因為，這樣可以免去為使檢驗數(shù)全部非正而作的許 多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除 此之外，在對線性規(guī)劃進行靈敏度分析中有時也要用到對偶單純形方法，可以 簡化計算。例4-9 求解線性規(guī)劃問題:Min/= 2x1 + 3x2 + 4x3.x + 2x2 +x3 M32x1 - x2 + x3 M 4xl , x2 , x3 M 0標準化:Max z = 2x1- 3x2 4x3-xl-2x2-x3+x4= -3-2x 1+x2-3x3+