運(yùn)籌學(xué)課件第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析

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

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

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

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

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

≤120（木工）2x1+x2

≤50（油漆工）

x1，x2

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

≥503y1+y2

≥30y1，y2

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

2、

換個(gè)角度審視生產(chǎn)計(jì)劃問題例

要求制定一個(gè)生產(chǎn)計(jì)劃方案，在設(shè)備A,B和調(diào)試三種資源限制下，使得產(chǎn)品的總利潤(rùn)最大。

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

對(duì)于產(chǎn)品Ⅱ，同樣可以建立類似的約束條件5y1+2y2+1y3≥1項(xiàng)目產(chǎn)品Ⅰ產(chǎn)品Ⅱ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)(元)21y1y2y39可編輯ppt

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

項(xiàng)目產(chǎn)品Ⅰ產(chǎn)品Ⅱ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)(元)2110可編輯ppt

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

怎樣通過增加更多的資源來增加利潤(rùn)？

怎樣使用不同類型的資源來增加利潤(rùn)？

對(duì)應(yīng)第一個(gè)約束條件對(duì)應(yīng)第二個(gè)約束條件（P）maxZ=2X1+X2

5X2

≤15對(duì)應(yīng)第一個(gè)對(duì)偶變量y1

6X1+2X2

≤24對(duì)應(yīng)第二個(gè)對(duì)偶變量y2

X1+X2

≤5對(duì)應(yīng)第三個(gè)對(duì)偶變量y3

X1，X2

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

6y2+y3

≥25y1+2y2+y3

≥1y1，y2，y3

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

12可編輯ppt則定義其對(duì)偶問題為這兩個(gè)式子之間的變換關(guān)系稱為“對(duì)稱形式的對(duì)偶關(guān)系”。

13可編輯ppt14可編輯ppt（2）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述（D）（L）

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

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

×

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

一、單純形法的矩陣描述進(jìn)一步討論修正單純形法便于理論推導(dǎo)（如對(duì)偶定理的證明）二、矩陣描述關(guān)鍵——寫出兩個(gè)基本的表達(dá)式。

2.1單純形法的矩陣描述23可編輯ppt1、準(zhǔn)備工作：（1）標(biāo)準(zhǔn)型的矩陣形式——

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

24可編輯ppt2、將分塊形式代入矩陣形式標(biāo)準(zhǔn)型，得出兩個(gè)基本表達(dá)式：（1）由約束條件

可得用非基變量表示基變量的表達(dá)式：25可編輯ppt項(xiàng)目非基變量基變量XBXNXS0XSbBNICj-ZjCBCN0項(xiàng)目基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

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

迭代后的單純形表初始單純形表對(duì)應(yīng)初始單純形表中的單位陣I，迭代后為B-1基變量的變換：初始XS=b；迭代后XB=B-1b約束系數(shù)矩陣的變化：[A,I]=[B,N,I]；[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1].約束系數(shù)矩陣的向量變化：PjT=B-1PjCBCN026可編輯ppt檢驗(yàn)數(shù)：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檢驗(yàn)數(shù)的相反數(shù)為其對(duì)偶問題的一個(gè)可行解27可編輯ppt例原問題、對(duì)偶問題之間的關(guān)系28可編輯ppt項(xiàng)目原問題變量原問題松弛變量x1x2x3x4x5X315/2X17/2X23/200100115/4-15/20?-1/20-1/43/2-Cj+zj000?1/2DUAL剩余變量DUAL變量y4y5y1y2y3項(xiàng)目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

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

補(bǔ)充:對(duì)稱性定理對(duì)偶問題的對(duì)偶是原問題。31可編輯ppt定理1

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

和（D）

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

左乘，得由（D）

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

(極大化問題)的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的一個(gè)下界。33可編輯ppt?極大化問題有上界——推論1

對(duì)偶問題(極小化問題)的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的一個(gè)上界。?關(guān)于最優(yōu)解無界情況與對(duì)偶問題的關(guān)系；推論2

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

原問題有可行解而其對(duì)偶問題沒有可行解，則原問題的目標(biāo)函數(shù)無界；對(duì)偶問題有可行解而其原問題沒有可行解，則對(duì)偶問題的目標(biāo)函數(shù)無界；35可編輯ppt定理

2最優(yōu)性定理

若、