對(duì)偶單純形法精品課件

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

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

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

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

5、20日，1點(diǎn)56分，星期三 按主元素進(jìn)行換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算），將主元素變成1，主元列變成單位向量，得到新的單純形表。 循環(huán)以上步驟，直至求出最優(yōu)解。第12頁，共22頁，2022年，5月20日，1點(diǎn)56分，星期三3、舉例用對(duì)偶單純形法求解LP： 化為標(biāo)準(zhǔn)型 將兩個(gè)等式約束兩邊分別乘以-1，得第13頁，共22頁，2022年，5月20日，1點(diǎn)56分，星期三以此形式進(jìn)行列表求解，滿足對(duì)偶單純形法的基本條件，具體如下：第14頁，共22頁，2022年，5月20日，1點(diǎn)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點(diǎn)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點(diǎn)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點(diǎn)56分，星期三4、舉例用對(duì)偶單純形法求解LP： 化為標(biāo)準(zhǔn)型 將三個(gè)等式約束兩邊分別乘以-1，然后列表求解如下：第18頁，共22頁，2022年，5月20日，1點(diǎn)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點(diǎn)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點(diǎn)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，目標(biāo)