對偶單純形法精品課件

1、對偶單純形法第1頁，共22頁，2022年，5月20日，1點56分，星期三 二、對偶單純形法的基本思想 1、對“單純形法”求解過程認識的提升 從更高的層次理解單純形法 初始可行基（對應一個初始基本可行解） 迭代另一個可行基（對應另一個基本可行解），直至所有檢驗數(shù)0為止。第2頁，共22頁，2022年，5月20日，1點56分，星期三 所有檢驗數(shù)0意味著 ，說明原始問題的最優(yōu)基也是對偶問題的可行基。換言之，當原始問題的基B既是原始可行基又是對偶可行基時，B成為最優(yōu)基。定理2-5 B是線性規(guī)劃的最優(yōu)基的充要條件是，B是可行基，同時也是對偶可行基。第3頁，共22頁，2022年，5月20日，1點56分，星期

2、三LP原問題:若B是A中的一個基可行基B對應的解是基本可行解，則B是可行基對偶可行基若單純形乘子 是對偶問題的可行解，則B是對偶可行基 是對偶問題的可行解檢驗數(shù)等價 第4頁，共22頁，2022年，5月20日，1點56分，星期三 證明：第5頁，共22頁，2022年，5月20日，1點56分，星期三單純形法的求解過程就是： 在保持原始可行的前提下(b列保持0)， 通過逐步迭代實現(xiàn)對偶可行(檢驗數(shù)行0)。 2、 對偶單純形法思想： 換個角度考慮LP求解過程：保持對偶可行的前提下（檢驗數(shù)行保持0） ，通過逐步迭代實現(xiàn)原始可行（b列0，從非可行解變成可行解）。 第6頁，共22頁，2022年，5月20日，1

3、點56分，星期三對偶單純形法的思想（圖示）原問題初始基本可行解保持為基本可行解初始對偶可行解保持對偶可行性最優(yōu)解基本可行性對偶可行性始終滿足解的可行性始終滿足對偶可行性第7頁，共22頁，2022年，5月20日，1點56分，星期三 三、對偶單純形法的實施1、使用條件： 檢驗數(shù)全部0； 解答列至少一個元素 0；2、實施對偶單純形法的基本原則：在保持對偶可行的前提下進行基變換每一次迭代過程中取出基變量中的一個負分量作為換出變量去替換某個非基變量(作為換入變量),使原始問題的非可行解向可行解靠近。 第8頁，共22頁，2022年，5月20日，1點56分，星期三3、計算步驟： 建立初始單純形表，計算檢驗數(shù)

4、行。解答列0已得最優(yōu)解；至少一個元素0,轉下步;解答列0原始單純形法；至少一個元素0,另外處理； 檢驗數(shù)全部0（非基變量檢驗數(shù)0第9頁，共22頁，2022年，5月20日，1點56分，星期三 基變換： 先確定換出變量解答列中的負元素（一般選最小的負元素）對應的基變量出基； 即相應的行為主元行。第10頁，共22頁，2022年，5月20日，1點56分，星期三然后確定換入變量原則是：在保持對偶可行的前提下，減少原始問題的不可行性。如果 (最小比值原則),則選 為換入變量 , 相應的列為主元列 , 主元行和主元列交叉處的元素 為主元素。若 ,要計算最小比值嗎？為什么？第11頁，共22頁，2022年，5月

5、20日，1點56分，星期三 按主元素進行換基迭代（旋轉運算、樞運算），將主元素變成1，主元列變成單位向量，得到新的單純形表。 循環(huán)以上步驟，直至求出最優(yōu)解。第12頁，共22頁，2022年，5月20日，1點56分，星期三3、舉例用對偶單純形法求解LP： 化為標準型 將兩個等式約束兩邊分別乘以-1，得第13頁，共22頁，2022年，5月20日，1點56分，星期三以此形式進行列表求解，滿足對偶單純形法的基本條件，具體如下：第14頁，共22頁，2022年，5月20日，1點56分，星期三 -2/-2 - -4/-3 - - 比 值 -2 -3 -4 0 0 0 -Z -1 -2 -1 1 0 -2 1

6、-3 0 1 -3 -4 x4 x5 0 0 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB第15頁，共22頁，2022年，5月20日，1點56分，星期三- -4/-5/2 - -1/-1/2 比 值 0 -4 -1 0 -1 0 cj-zj 0 -5/2 1/2 1 -1/2 1 -1/2 3/2 0 -1/2 -1 2 x4 x1 0 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB第16頁，共22頁，2022年，5月20日，1點56分，星期三 0 0 -3/5 -8/5 -1/5 0 cj-zj 0 1 -1/5

7、 -2/5 1/5 1 0 7/5 -1/5 -2/5 2/5 11/5 x2 x1 -3 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB最優(yōu)解: X*=（11/5，2/5, 0, 0, 0）T，最優(yōu)值: minW= -maxZ* = -11/5(-2)+2/5(-3)= 28/5第17頁，共22頁，2022年，5月20日，1點56分，星期三4、舉例用對偶單純形法求解LP： 化為標準型 將三個等式約束兩邊分別乘以-1，然后列表求解如下：第18頁，共22頁，2022年，5月20日，1點56分，星期三 -3/-1 -9/-1 - - - 比 值 -3 -9

8、 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y4 y5 0 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第19頁，共22頁，2022年，5月20日，1點56分，星期三 - -6/-3 -3/-1 - - 比 值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB第20頁，共22頁，2022年，5月20日，1點56分，星期三 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB最優(yōu)解是Y*=（5/3，1/3，0，0，1）T，目標