資源描述：
《用對偶單純形法求解線性規(guī)劃問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、例4-7用對偶單純形法求解線性規(guī)劃問題.Minz=5x1+3xs.t.-2x1+3x≥63x1-6x≥4Xj≥0（j=1,2）解：將問題轉(zhuǎn)化為Maxz=-5x1-3xs.t.2x1-3x+x3=-6-3x1+6x+x4≥-4Xj≥0（j=1,2，3,4）其中，x3，x4為松弛變量，可以作為初始基變量，單純形表見表4-17.表4-17例4-7單純形表Cj-6-3-40CBXBbX1X2X3X4迭代0次0X4-62[-3]100X5-4-36010-5-300CBXBbX1X2X3X4迭代1次-3X42-2/31-1/300X3-1610216-70-10在表4-
2、17中,b=-16<0,而y≥0,故該問題無可行解.注意:對偶單純形法仍是求解原問題,它是適用于當(dāng)原問題無可行基,且所有檢驗數(shù)均為負(fù)的情況.若原問題既無可行基,而檢驗數(shù)中又有小于0的情況.只能用人工變量法求解.在計算機求解時,只有人工變量法,沒有對偶單純形法.3.對偶問題的最優(yōu)解由對偶理論可知,在原問題和對偶問題的最優(yōu)解之間存在著密切的關(guān)系,可以根據(jù)這些關(guān)系,從求解原問題的最優(yōu)單純形表中,得到對偶問題的最優(yōu)解.(1)設(shè)原問題(p)為Minz=CXs.t.則標(biāo)準(zhǔn)型(LP)為Maxz=CXs.t.其對偶線性規(guī)劃（D）為Maxz=bTYs.t.用對偶單純形法求解（L
3、P），得最優(yōu)基B和最優(yōu)單純形表T（B）。對于（LP）來說，當(dāng)j=n+i時，有Pj=-ei，cj=0從而，在最優(yōu)單純形表T（B）中，對于檢驗數(shù)，有（σn+1，σn+2…σn+m）=（cn+1，cn+2…，cn+m）-CBB-1（Pn+1,Pn+2…,Pn+m）=-CBB-1(-I)于是，Y*=（σn+1，σn+2…σn+m）T。可見，在（LP）的最優(yōu)單純形表中，剩余變量對應(yīng)的檢驗數(shù)就是對偶問題的最優(yōu)解。同時，在最優(yōu)單純形表T（B）中，由于剩余變量對應(yīng)的系數(shù)所以B-1=（-yn+1，-yn+2…-yn+m）例4-7求下列線性規(guī)劃問題的對偶問題的最優(yōu)解。Minz=6
4、x1+8xs.t.x1+2x≥203x1+2x≥50Xj≥0（j=1,2）解：將問題轉(zhuǎn)化為Maxz=-6x1-8xs.t.-x1—2x+x3=20-3x1-2x+x4=50Xj≥0（j=1,2，3,4）用對偶單純形法求解如表表4-18例4-8單純形表Cj-6-800CBXBbX1X2X3X4迭代0次-8X45/201-3/41/4-6X515101/2-1/2-1100031在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進(jìn)行求解，非常方便。對于有些線性規(guī)劃模型，如果在開始求解時不能很快
5、使所有檢驗數(shù)非正，最好還是采用單純形法求解。因為，這樣可以免去為使檢驗數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除此之外，在對線性規(guī)劃進(jìn)行靈敏度分析中有時也要用到對偶單純形方法，可以簡化計算。例4-9：求解線性規(guī)劃問題：Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0標(biāo)準(zhǔn)化：Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0表格對偶單純形法Cj-6-800CBXBbX1X2X
6、3X4迭代0次-8X45/201-3/41/4-6X515101/2-1/2-1100031
