第四章 對偶單純形法和對偶問題

1、整理ppt4.1 4.1 對偶問題的提出對偶問題的提出整理pptABC擁有量工 時1113材 料1479單件利潤233整理ppt0, 0, 09743. .321321321xxxxxxxxxts321332maxxxxZ+=整理pptABC擁有量工 時1113材 料1479單件利潤233 整理pptABC擁有量工 時1113材 料1479單件利潤233在考慮這個問題時我們應(yīng)做到：在考慮這個問題時我們應(yīng)做到：1、價格應(yīng)該盡量低，這樣，才能有競爭力、價格應(yīng)該盡量低，這樣，才能有競爭力; 2、出賣資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利、出賣資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利; 3、價格應(yīng)該是非負的、價格應(yīng)該是

2、非負的 整理pptABC擁有量工 時1113材 料1479單件利潤233 現(xiàn)在我們用數(shù)學語言描述，設(shè)現(xiàn)在我們用數(shù)學語言描述，設(shè)y1和和y2分別表示單分別表示單位工時和材料的出售價格位工時和材料的出售價格總價格最小總價格最小 min W=3y1+9y2保證獲利大于保證獲利大于A產(chǎn)品利潤產(chǎn)品利潤 y1+y22 保證保證獲利大于獲利大于B產(chǎn)品利潤產(chǎn)品利潤 y1+4y23 保證保證獲利大于獲利大于C產(chǎn)品利潤產(chǎn)品利潤 y1+7y23 售價非負售價非負 y10 y20整理pptABC擁有量工 時1113材 料1479單件利潤2332193minyyW+=0, 037342. .21212121yyyyyy

3、yyts321332maxxxxZ+=0, 0, 09743. .321321321xxxxxxxxxts整理ppt任何一個線性規(guī)劃問題都有一個與之相對應(yīng)任何一個線性規(guī)劃問題都有一個與之相對應(yīng)的線性規(guī)劃問題，如果前者稱為原始問題，后者的線性規(guī)劃問題，如果前者稱為原始問題，后者就稱為就稱為“對偶對偶”問題。問題。對偶問題是對原問題從另一角度進行的描述對偶問題是對原問題從另一角度進行的描述. .其最優(yōu)解與原問題的最優(yōu)解有著密切的聯(lián)系，在其最優(yōu)解與原問題的最優(yōu)解有著密切的聯(lián)系，在求得一個線性規(guī)劃最優(yōu)解的同時也就得到對偶線求得一個線性規(guī)劃最優(yōu)解的同時也就得到對偶線性規(guī)劃的最優(yōu)解，反之亦然。性規(guī)劃的最優(yōu)

4、解，反之亦然。對偶理論就是研究線性規(guī)劃及其對偶問題的對偶理論就是研究線性規(guī)劃及其對偶問題的理論，是線性規(guī)劃理論的重要內(nèi)容之一。理論，是線性規(guī)劃理論的重要內(nèi)容之一。 整理ppt4.2 4.2 建立對偶問題的規(guī)則建立對偶問題的規(guī)則整理ppt原問題原問題max z=C X A X b X0對偶問題對偶問題min w=b T YAT Y C TY0整理ppt二、對偶問題的特點二、對偶問題的特點（1）目標函數(shù)在一個問題中是求最大值在另）目標函數(shù)在一個問題中是求最大值在另一問題中則為求最小值一問題中則為求最小值（2）一個問題中目標函數(shù)的系數(shù)是另一個問）一個問題中目標函數(shù)的系數(shù)是另一個問題中約束條件的右端項

5、題中約束條件的右端項（3）一個問題中的約束條件個數(shù)等于另一個）一個問題中的約束條件個數(shù)等于另一個問題中的變量數(shù)問題中的變量數(shù)（4）原問題的約束系數(shù)矩陣與對偶問題的約）原問題的約束系數(shù)矩陣與對偶問題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣束系數(shù)矩陣互為轉(zhuǎn)置矩陣整理ppt對偶問題對應(yīng)表對偶問題對應(yīng)表原問題（對偶問題）原問題（對偶問題）對偶問題（原問題）對偶問題（原問題）目標函數(shù)目標函數(shù)max目標函數(shù)目標函數(shù)min變量數(shù)：變量數(shù)：n個個第第j個變量個變量 0第第j個變量個變量 0第第j個變量是自由變量個變量是自由變量 目標函數(shù)中變量的系數(shù)目標函數(shù)中變量的系數(shù)約束條件：約束條件：n個個第第j個約束類型為個約束類型為

6、“”第第j個約束類型為個約束類型為“”第第j個約束類型為個約束類型為“”約束條件右端項約束條件右端項約束條件：約束條件： m個個第第i個約束類型為個約束類型為“”第第i個約束類型為個約束類型為“”第第i個約束類型為個約束類型為“” 約束條件右端項約束條件右端項變量數(shù)：變量數(shù)： m個個第第i個變量個變量0第第i個變量個變量0第第i個變量是自由變量個變量是自由變量 目標函數(shù)中變量的系數(shù)目標函數(shù)中變量的系數(shù)整理ppt原問題： 對偶問題：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 4y1+5y2

7、+10y3 1203X1+10X2 300 y1 0, y2 0, y3 0X10 X20整理ppt練習寫出如下LP問題的對偶問題123min23fxxx123123123123,3264235390,xxxxxxxxxxxx符號不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符號不限整理ppt4.3 4.3 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)( (選學選學) )整理ppt一、對稱性一、對稱性定理1、對偶問題的對偶就是原始問題定理2 （可行解的目標函數(shù)值之間的關(guān)系） 設(shè)X、Y分別是原始問題和對偶問題的可行解，則 CX YTb弱對偶

8、性弱對偶性整理ppt1.如果原問題（對偶問題）具有無界解，則其對偶問題（原問題）無可行解。2.若原問題可行,而對偶問題不可行,則原問題的目標函數(shù)值無界3.若對偶問題可行,而原問題不可行,則對偶問題的目標函數(shù)值無界推論 :整理ppt例如12123123123 : max22 21,0Zxxxxxxxxx x x 原1212121212: min221 2 0,0Wyyyyyyyyy y對試用對偶理論證明原問題無界。 解： =（0.0.0）是 原問題 的一個可行解，而 對偶 的第一個約束條件不能成立（因為y1 , y2 0)。因此，原問題無界。_X整理ppt11 (1,2, ) (1,2,) (1

9、,2, ) (1,2,)jinmjjiijijixjny imc xb yxjny im 如果是原問題的可行解是其對偶問題的可行解且有則是原問題的最優(yōu)解是其對偶問題的最優(yōu)解定理3整理ppt四、對偶定理四、對偶定理 定理4 如果原問題有最優(yōu)解，則其對偶問題也一定有最優(yōu)解，且兩者的目標函數(shù)值相等 定理5 若X為原問題的滿足最優(yōu)檢驗的基本解。則Y=CBb-1為對偶問題的可行解 (原問題在得到基本可行解的同時，其檢驗數(shù)的相反數(shù)就構(gòu)成對偶問題的一個基本解，且各自目標函數(shù)值恒相等。)整理pptCj -6 -3 -2 0 0 0jCBXBb X1 X2 X3 X4 X5 X6-20-3X3X6X216104

10、 0 0 1 -2 4 0 -1 0 0 -1 0 1 1 1 0 1 -4 0j = cj-zj -3 0 0 -1 -4 0Cj 20 6 10 0 0 0jCBYBb Y1 Y2 Y3 Y4 Y5 Y60620Y4Y2Y1341 0 0 1 1 1 -10 0 1 0 0 4 -4 1 0 1 0 -1 2j = cj-zj 0 0 -10 0 -4 -16整理ppt4.4 4.4 對偶單純形法對偶單純形法整理ppt 當一個線性規(guī)劃問題是求目標函數(shù)值最小，約束方程是時，求解時用大M法或兩階段法比較麻煩，此時較有效的算法是將要介紹的對偶單純形法 對偶單純形法并不是求解對偶問題解的方法，而是

11、利用對偶理論求解原問題的解的方法。整理ppt第一第一 步步 找出一個初始正則解正則解B0，要求對應(yīng)的單純形表中的全部檢驗數(shù) 0，但右邊項中允許有負數(shù)第二步第二步 若右邊項中各數(shù)均非負，則B0已是最優(yōu)基，即已求得最優(yōu)解，計算終止；否則轉(zhuǎn)為下一步第三步第三步 取右邊項中取值最?。簇摰淖疃啵┑臄?shù)所對應(yīng)的變量為換出變量。二、對偶單純形法的計算步驟二、對偶單純形法的計算步驟整理ppt第四步第四步 按公式 其中j c j z j 計算最小比值,則該列所對應(yīng)的變量即為換入變量第五步第五步 以換出變量的行和換入變量列交點處的元素為主元進行單純形迭代，再轉(zhuǎn)入第二步整理ppt 用對偶單純形法求解線性規(guī)劃問題：

12、min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 yj0，對一切j解：先將問題改寫為 max w=-15y1-24y2-5y3 max w=-15y1-24y2-5y3 6y2+y3-y4 =2 -6y2-y3+y4 =-2 5y1+2y2+y3 -y5=1 -5y1-2y2-y3 +y5=-1 yj0，對一切j yj0，對一切j整理ppt第一步第一步 建立一個初始單純形表，使表中檢驗行的值全部 0 即對其對偶問題而言是一基本可行解。Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -

13、1 0 1j=cj-zj-15 -24 -5 0 0整理ppt第二步第二步 檢驗當前可行解是否可行，若可行，已得最優(yōu)解，否則轉(zhuǎn)入下一步Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0整理pptCj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0整理ppt第四步第四步 按公式 計算最小比值,則該列所對應(yīng)的變量即為入基變量。（其中j

14、c j z j ）Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0 / 4 5 / /整理ppt第五步第五步 用換入變量替換對偶問題中的換出變量得到一個新的單純形表。表中數(shù)字計算同用單純形法時完全一樣。新表中對偶問題仍保持基本可行解 Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y5-240Y2Y51/3-1/3 0 1 1/6 -1/6 0 -5 0 -2/3 -1/3 1j=cj-zj-15 0 -1 -4 0 3 / 3/2 12

15、/整理pptCj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y5-24-5Y2Y31/41/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2j=cj-zj-15/2 0 0 -7/2 -3/2 Y1=0，Y2=1/4,Y3=1/2,W最優(yōu)為17/2整理ppt四、練習四、練習課本60頁 2整理ppt4.5 對偶問題的經(jīng)濟意義影子價格整理ppt定義：約束條件方程右端的定義：約束條件方程右端的bi增加一單位時，最優(yōu)增加一單位時，最優(yōu)目標函數(shù)目標函數(shù)z的變化量稱為資源的變化量稱為資源i的影子價格的影子價格.影子價格越大，說明這種資源越是相對緊缺影子價格越大，說

16、明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于的影子價格一定等于0種資源的邊際利潤第種資源的增量第最大利潤的增量iibzwiooiqi整理ppt4.6 對偶單純形法的一個應(yīng)用（增加約束條件）整理ppt 在求出線性規(guī)劃問題的最優(yōu)解后，又增加一個約束條件，此時可以利用對偶單純形法求解，不必對原問題從頭做起。其步驟如下：1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當前最優(yōu)解要發(fā)生變化；將新增約束條件加入松弛變量或剩余變量后加入到原

17、來的最優(yōu)單純形表，令原來的基變量和新增加的變量組成新的基，進行初等變換將基變量對應(yīng)的系數(shù)矩陣變?yōu)閱挝痪仃嚒?、利用對偶單純形法繼續(xù)迭代整理ppt二、例題0,1000354312004345800232435max43214321432143214321xxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz整理pptCj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 045X5X4X2100200100 1/4 0 -13/4 0 1 1/4 -1 2 0 -2 1 0 1 -1-3/4 1 11/4 0 0 -3/4 1j=cj-zj-13/

18、4 0 -11/4 0 0 -1/4 -1X1=0，X2=100，X3=0，X4=200， X5=100，X6=0，X7=0,Z=1300整理pptj, 06503321000354312004345800232435max43214321432143214321對一切jxxxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz整理pptCj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100650 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4 0 0 -3/4 1 0 1 2 3 3 0 0 0 1Cj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100450 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4 0 0 -