1、設原問題是（記為LP）： 對偶問題是（記為DP）： 根據(jù)對偶性質6，可以構造一個求線性規(guī)劃的另一種方法，即對偶單純形法。 對偶單純形法的計算步驟：對偶單純形法的條件是：初始表中對偶問題可行，即極大化問題時j0，極小化問題時j0。9/18/2022 （1）將線性規(guī)劃的約束化為等式，求出一組基本解，因為對偶問題可行，即全部檢驗數(shù)j0（max）或j0（min）,當基本解可行時，則達到最優(yōu)解；若基本解不可行，即有某個基變量的解bi0，則進行換基計算；（2）先確定出基變量。 行對應的變量xl出基； （3）再選進基變量。求最小比值（4）求新的基本解，用初等變換將主元素alk化為l,k列其它元素化為零，得到

2、新的基本解，轉到第一步重復運算。9/18/2022【例2.10】用對偶單純形法求解【解】先將約束不等式化為等式，再兩邊同乘以（1），得到用對偶單純形法，迭代過程如下頁或看演示(請啟用宏)。9/18/2022表249/18/2022 應當注意： （1）用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解；（2）初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準則；（3）最小比值中 的絕對值是使得比值非負，在極小化問題時j0，分母aij0 這時必須取絕對值。在極大化問題中，j0分母aij0， 總滿足非負，這時絕對值符號不起作用，可以去掉。如在本例中將目標函數(shù)寫成這里j0在

3、求k時就可以不帶絕對值符號。9/18/2022（4）對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；（5）普通單純形法的最小比值是其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是其目的是保證下一個對偶問題的基本解可行； （6）對偶單純形法在確定出基變量時，若不遵循規(guī)則，任選一個小于零的bi對應的基變量出基，不影響計算結果，只是迭代次數(shù)可能不一樣。9/18/2022【例2.12】用對偶單純形法求解求解過程見演示（鏈接到Excel文件，需啟用宏）。9/18/2022例2.12可用性質6 及性質2來說明，表（2）的第2行對應于對偶問題的第2列（相差一個負號），檢驗數(shù)行對應于對偶問題的常數(shù)項（相差一個負號），比值 對應于對偶問題的比值 失效也說明 即對偶問題具有無界解，由性質2知原問題無可行解。9/18/2022本節(jié)利用對偶性質6：原問題的檢驗數(shù)與對偶問題的基本解的對應關系，介紹了一種特殊線性規(guī)劃的求解方法對偶單純形法。1.對偶單純形法的應用條件；2.出基與進基的順序；3.如何求最小比值；4.最優(yōu)解、無