運籌學課件第二章線性規(guī)劃的對偶理論與靈敏度分析

第二章線性規(guī)劃的對偶理論與靈敏度分析1可編輯ppt一、對偶問題的提出1、

對偶思想舉例周長一定的矩形中，以正方形面積最大；面積一定的矩形中，以正方形周長最?。坏谝还?jié)LP的對偶問題2可編輯ppt對偶問題？......對偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結構的重要理論基礎。同時，由于問題提出本身所具有的經濟意義，使得它成為對線性規(guī)劃問題系統(tǒng)進行經濟分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產生這樣一種問題呢？……3線性規(guī)劃的對偶理論引例——倆家具制造商間的對話：唉!我想租您的木工和油漆工一用。咋樣？價格嘛……好說，肯定不會讓您兄弟吃虧訕。

王老板做家具賺了大錢，可惜我老李有高科技產品，卻苦于沒有足夠的木工和油漆工咋辦？只有租咯。Hi：王老板，聽說近來家具生意很好，也幫幫兄弟我哦!家具生意還真賺錢，但是現在的手機生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。價格嘛……好商量，好商量。只是…...

家具-王總李總桌子椅子能力木工43120漆工2150價格50304可編輯ppt線性規(guī)劃的對偶理論王老板的家具生產模型：x1、

x2是桌、椅生產量。Z是家具銷售總收入（總利潤）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）2x1+x2

≤50（油漆工）

x1，x2

≥0原始線性規(guī)劃問題，記為（P）王老板的資源出租模型：y1、y2單位木、漆工出租價格。W是資源出租租金總收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0對偶線性規(guī)劃問題，記為（D）桌子椅子能力木工43120漆工2150價格50305可編輯ppt線性規(guī)劃的對偶理論王老板按（D）的解y1、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。按時下最流行的一個詞，叫什么來著————6可編輯ppt對偶問題Minw=YbT=YTbs.t. ATY≥CT Y≥0原始問題maxz=CXs.t.AX≤bX≥0≤maxbACCTATbT≥minmnmn7可編輯ppt

2、

換個角度審視生產計劃問題例

要求制定一個生產計劃方案，在設備A,B和調試三種資源限制下，使得產品的總利潤最大。

maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0st.8可編輯ppt轉換思路:投資人:如果某投資公司準備購買該工廠，它至少應付出多大的代價，才能使工廠自己放棄生產產品Ⅰ、Ⅱ，而將可利用的資源都出讓。被兼并人:該工廠的底線：最低可接受價格，指按這種價格轉讓資源比自己生產產品Ⅰ、Ⅱ合算的價格。設y1,y2，y3為代表單位時間這三種資源的出讓價格，為了使工廠出讓資源合算，顯然應該使出讓原來生產一件產品Ⅰ的資源所得收入不低于自己生產產品Ⅰ的利潤，即0y1+6y2+1y3≥2

對于產品Ⅱ，同樣可以建立類似的約束條件5y1+2y2+1y3≥1項目產品Ⅰ產品Ⅱ每天可用能力設備A(h)設備B(h)調試工序(h)06152115245利潤(元)21y1y2y39可編輯ppt

當原問題和對偶問題都取得最優(yōu)解時，這一對線性規(guī)劃對應的目標函數值是相等的：Zmax=Wmin顯然在滿足這兩個約束的前提下，價格越高，該工廠越合算，但價格太高，投資人方面又不會愿意購買。因此，我們需要確定的價格是使工廠合算的最低價格，故應建立目標函數：minw=15y1+24y2+5y3

項目產品Ⅰ產品Ⅱ每天可用能力設備A(h)設備B(h)調試工序(h)06152115245利潤(元)2110可編輯ppt

考察原問題和對偶問題的解，給作決策的管理者另一個自由度；

怎樣通過增加更多的資源來增加利潤？

怎樣使用不同類型的資源來增加利潤？

對應第一個約束條件對應第二個約束條件（P）maxZ=2X1+X2

5X2

≤15對應第一個對偶變量y1

6X1+2X2

≤24對應第二個對偶變量y2

X1+X2

≤5對應第三個對偶變量y3

X1，X2

≥0（D）minw=15y1+24y2+5y3

6y2+y3

≥25y1+2y2+y3

≥1y1，y2，y3

≥011可編輯ppt二、原問題和對偶問題的關系1、對稱形式的對偶關系（1）定義：若原問題是

12可編輯ppt則定義其對偶問題為這兩個式子之間的變換關系稱為“對稱形式的對偶關系”。

13可編輯ppt14可編輯ppt（2）對稱形式的對偶關系的矩陣描述（D）（L）

（3）從原問題寫出其對偶問題按照定義；記憶法則：“上、下”交換，換后矩陣轉置。不等式變號，“極大”變“極小”15可編輯ppt例寫出下面線性規(guī)劃的對偶問題：

16可編輯ppty2=y2’-y2’’y3=-y3’2、非對稱形式的對偶關系：（1）原問題對偶問題17可編輯ppt（2）怎樣寫出非對稱形式的對偶問題？把一個等式約束寫成兩個不等式約束，再根據對稱形式的對偶關系定義寫出；按照原-對偶表直接寫出；（3）原-對偶表18可編輯ppt項目原問題（對偶問題）對偶問題（原問題）目標函數類型maxmin目標函數系數與右邊項的對應關系目標函數各變量系數對應約束條件右邊項的系數右邊項的系數對應目標函數系數變量個數與約束條件個數的對應關系變量個數n約束條件個數m約束條件個數n變量個數m原問題變量類型與對偶問題約束條件類型的對應關系≥0(對稱)變量類型≤0(非對稱)自由≥(對稱)約束條件類型≤(非對稱)=原問題約束條件類型與對偶問題變量類型的對應關系≥(非對稱)約束條件類型≤(對稱)=≤(非對稱)變量類型≥(對稱)自由19可編輯ppt例題：寫出下面線性規(guī)劃的對偶規(guī)劃：20可編輯ppt（原問題是極小化問題，因此應從原-對偶表的右邊往左邊查?。?/p>

×

項目原問題（對偶問題）對偶問題（原問題）目標函數類型maxmin原問題變量類型與對偶問題約束條件類型的對應關系≥0(對稱)變量類型≤0(非對稱)自由≥(對稱)約束條件類型≤(非對稱)=原問題約束條件類型與對偶問題變量類型的對應關系≥(非對稱)約束條件類型≤(對稱)=≤(非對稱)變量類型≥(對稱)自由21可編輯ppt第二節(jié)對偶問題的基本性質原問題對偶問題為對稱形式的線性規(guī)劃問題22可編輯ppt

一、單純形法的矩陣描述進一步討論修正單純形法便于理論推導（如對偶定理的證明）二、矩陣描述關鍵——寫出兩個基本的表達式。

2.1單純形法的矩陣描述23可編輯ppt1、準備工作：（1）標準型的矩陣形式——

（2）將式中矩陣寫成分塊矩陣形式

24可編輯ppt2、將分塊形式代入矩陣形式標準型，得出兩個基本表達式：（1）由約束條件

可得用非基變量表示基變量的表達式：25可編輯ppt項目非基變量基變量XBXNXS0XSbBNICj-ZjCBCN0項目基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

迭代后的單純形表初始單純形表對應初始單純形表中的單位陣I，迭代后為B-1基變量的變換：初始XS=b；迭代后XB=B-1b約束系數矩陣的變化：[A,I]=[B,N,I]；[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1].約束系數矩陣的向量變化：PjT=B-1PjCBCN026可編輯ppt檢驗數：CN-CBB-1N≤0(1);-CBB-1≤0;

令:CB-CBI=0(2)(1)+(2)得到CN-CBB-1N

+CB-CBI=CN-CBB-1N

+CB-CBB-1B=CB+CN-CBB-1(B+N)=C-CBB-1A≤0-CBB-1≤0;令YT=CBB-1

單純形乘子

ATY≥CT;

Y≥0Wmin=YTb=CBB-1b=ZmaxC-YTA≤0C≤

YTACT≤(YTA)T檢驗數的相反數為其對偶問題的一個可行解27可編輯ppt例原問題、對偶問題之間的關系28可編輯ppt項目原問題變量原問題松弛變量x1x2x3x4x5X315/2X17/2X23/200100115/4-15/20?-1/20-1/43/2-Cj+zj000?1/2DUAL剩余變量DUAL變量y4y5y1y2y3項目dual變量dual剩余變量y1y2y3y4y5y21/4y31/2-5/41015/201-1/4??-3/2Cj-zj

15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x229可編輯ppty1yiymym+1ym+jyn+m

x1xjxn

xn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于030可編輯ppt二、對偶問題的基本性質對偶基本性質揭示原問題的解與對偶問題的解之間關系

補充:對稱性定理對偶問題的對偶是原問題。31可編輯ppt定理1

弱對偶定理——若一對對稱形式的對偶線性規(guī)劃（L）

和（D）

均有可行解，分別為和，則C≤b。證明思路：由（L）

左乘，得由（D）

右乘，得32可編輯ppt該結論對非對稱形式的對偶問題同樣成立。?推論:關于“界”的結果；極小化問題有下界——推論1原問題

(極大化問題)的任意一個可行解所對應的目標函數值是其對偶問題目標函數值的一個下界。33可編輯ppt?極大化問題有上界——推論1

對偶問題(極小化問題)的任意一個可行解所對應的目標函數值是其原問題目標函數值的一個上界。?關于最優(yōu)解無界情況與對偶問題的關系；推論2

若原問題可行，則其目標函數無界的充要條件是對偶問題沒有可行解。34可編輯ppt推論3原問題可行，且目標函數值無界==>對偶問題不可行對偶問題可行，且目標函數值無界==>原問題不可行若對偶問題不可行，其原問題或沒有可行解或無界解。

原問題有可行解而其對偶問題沒有可行解，則原問題的目標函數無界；對偶問題有可行解而其原問題沒有可行解，則對偶問題的目標函數無界；35可編輯ppt定理

2最優(yōu)性定理

若、