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

1、例47用對偶單純形法求解線性規(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故該問題無可行解.注意注意:對偶單純形法仍是求解原問題它是適用于當原問題無可行基且所有檢驗數(shù)均為負的情況.若原問題既無可行基而檢驗數(shù)中又有小于0的情況.只能用人工變量法求解.在計算機求解時只有人工變量法沒有對偶單純形法.3.3.對偶問題的最優(yōu)解對偶問題的最優(yōu)解由對偶理論可知在原問題和對偶問題

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

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