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

1、例47用對(duì)偶單純形法求解線性規(guī)劃問題.Minz=5x13x2s.t.2x13x≥623x16x≥42Xj≥0（j=12）解：解：將問題轉(zhuǎn)化為Maxz=5x13x2s.t.2x13xx3=623x16xx4≥42Xj≥0（j=12，34）其中，x3，x4為松弛變量，可以作為初始基變量，單純形表見表417.表417417例4747單純形表單純形表Cj6340CB迭代0次XBbX1X2X3X40X462[3]100X543601??jjzcz

2、???05300CB迭代1次XBbX1X2X3X43X422311300X3161021??jjzcz???67010在表417中b=160而y≥0故該問題無可行解.注意注意:對(duì)偶單純形法仍是求解原問題它是適用于當(dāng)原問題無可行基且所有檢驗(yàn)數(shù)均為負(fù)的情況.若原問題既無可行基而檢驗(yàn)數(shù)中又有小于0的情況.只能用人工變量法求解.在計(jì)算機(jī)求解時(shí)只有人工變量法沒有對(duì)偶單純形法.3.3.對(duì)偶問題的最優(yōu)解對(duì)偶問題的最優(yōu)解由對(duì)偶理論可知在原問題和對(duì)偶問題

3、的最優(yōu)解之間存在著密切的關(guān)系可以根據(jù)這些關(guān)系從求解原問題的最優(yōu)單純形表中得到對(duì)偶問題的最優(yōu)解.(1)設(shè)原問題(p)為Xj≥0（j=12，34）用對(duì)偶單純形法求解如表表418418例4848單純形表單純形表Cj6800CB迭代0次XBbX1X2X3X48X4520134146X515101212??jjzcz???1100031在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對(duì)偶

4、單純形表進(jìn)行求解，非常方便。對(duì)于有些線性規(guī)劃模型，如果在開始求解時(shí)不能很快使所有檢驗(yàn)數(shù)非正，最好還是采用單純形法求解。因?yàn)?，這樣可以免去為使檢驗(yàn)數(shù)全部非正而作的許多工作。從這個(gè)意義上看，可以說，對(duì)偶單純形法是單純形法的一個(gè)補(bǔ)充。除此之外，在對(duì)線性規(guī)劃進(jìn)行靈敏度分析中有時(shí)也要用到對(duì)偶單純形方法，可以簡(jiǎn)化計(jì)算。例49：求解線性規(guī)劃問題：求解線性規(guī)劃問題：Minf=2x13x24x3S.t.x12x2x3≥32x1x2x3≥4x1x2x3≥0