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

1、用對(duì)偶單純形法求解線性規(guī)劃問題The final edition was revised on December 14th, 2020.例47用對(duì)偶單純形法求解線性規(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,故該問題無可行解.注意：對(duì)偶單純形法仍是求解原問題，它是適用于當(dāng)原問題無可行基，且所有檢驗(yàn)數(shù)均為負(fù)的情況.若原問題既無可行基，而檢驗(yàn)數(shù)中又有小于0的情況.只能用人工變量法求解. 在計(jì)算機(jī)求解時(shí)，只有人工變量法,沒有對(duì)偶單純形法.3.對(duì)偶問題的最優(yōu)解由對(duì)偶理論可知，在原問題和對(duì)偶問題的最優(yōu)解之間存在著密切的關(guān)系，可以根 據(jù)這些關(guān)系，從求解原問題的最優(yōu)單純形表中，得到對(duì)偶問題的最優(yōu)解.(1)設(shè)原問題(P)為

3、Min z=CXAX=b* X0則標(biāo)準(zhǔn)型(LP)為Max z=CXAX=bX0其對(duì)偶線性規(guī)劃(D)為Max z=b1YAX=bX0用對(duì)偶單純形法求解(LP)，得最優(yōu)基B和最優(yōu)單純形表T (B)。對(duì)于(LP)來說，當(dāng) j二n+i 時(shí)，有 Pj=-ei, cj=O從而，在最優(yōu)單純形表T (B)中，對(duì)于檢驗(yàn)數(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)單純形表 中，剩余變量對(duì)應(yīng)的檢驗(yàn)數(shù)就是對(duì)偶問題的最優(yōu)解。同時(shí)，在最優(yōu)

4、單純形表T (B)中，由于剩余變量對(duì)應(yīng)的系數(shù)所以B1 = (-y n+l,y n+2yn+m)例48求下列線性規(guī)劃問題的對(duì)偶問題的最優(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)用對(duì)偶單純形法求解如表表4-18例4-8單純形表G6-800Cs迭代0次XbbX：x=XsX,-8X.5/201-3/41/4_6Xs15101/2-1/2-Z = c丿-亦-1100031在引入松弛變

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