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

1、運(yùn)籌學(xué)教程第二章第二章 線性規(guī)劃的對偶實(shí)際與靈敏度分析線性規(guī)劃的對偶實(shí)際與靈敏度分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程對偶實(shí)際是線性規(guī)劃中最重要的實(shí)際之一，是深化了解線性規(guī)劃問題構(gòu)造的重要實(shí)際根底。同時，由于問題提出本身所具有的經(jīng)濟(jì)意義，使得它成為對線性規(guī)劃問題系統(tǒng)進(jìn)展經(jīng)濟(jì)分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產(chǎn)生這樣一種問題呢？運(yùn)籌學(xué)教程線性規(guī)劃的對偶實(shí)際線性規(guī)劃的對偶實(shí)際引例引例倆家具制造商間的對話：倆家具制造商間的對話：唉唉!我想租您的木工和油漆工一我想租您的木工和油漆工一用。咋樣？價錢嘛用。咋樣？價錢嘛好說，好說，一定不會讓您兄弟吃虧訕。一定不會讓您兄弟吃虧訕。 王老板做家

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

3、150價格5030運(yùn)籌學(xué)教程線性規(guī)劃的對偶實(shí)際線性規(guī)劃的對偶實(shí)際王老板的家具消費(fèi)模型：王老板的家具消費(fèi)模型：x1 、 x2是桌、椅消費(fèi)量。是桌、椅消費(fèi)量。Z是家具銷售總收入總利潤。是家具銷售總收入總利潤。max Z = 50 x1 + 30 x2s.t. 4x1+3x2 120木工木工 2x1+ x2 50 油漆工油漆工 x1，x2 0原始線性規(guī)劃問題，記為原始線性規(guī)劃問題，記為P王老板的資源出租模型：王老板的資源出租模型：y1、 y2單位木、漆工出租價錢。單位木、漆工出租價錢。W是資源出租租金總收入。是資源出租租金總收入。min W =120y1 + 50y2s.t. 4y1+2y2 50

4、3y1+ y2 30 y1，y2 0對偶線性規(guī)劃問題，記為對偶線性規(guī)劃問題，記為D桌子椅子能力木工43120漆工2150價格5030運(yùn)籌學(xué)教程線性規(guī)劃的對偶實(shí)際線性規(guī)劃的對偶實(shí)際 王老板按王老板按D的解的解 y1 、y2出租其擁有的木、漆工資出租其擁有的木、漆工資源，既保證了本人不吃虧出租資源的租金收入并不低于本人源，既保證了本人不吃虧出租資源的租金收入并不低于本人消費(fèi)時的銷售收入，又使得出租價錢對李老板有極大的吸引消費(fèi)時的銷售收入，又使得出租價錢對李老板有極大的吸引力李老板所付出的總租金力李老板所付出的總租金W最少。最少。運(yùn)籌學(xué)教程對偶問題Min w=YbT=YTbs.t.ATY CTY 0

5、原始問題max z=CXs.t. AX bX 0maxbACCTATbTminmnmn運(yùn)籌學(xué)教程 2、 換個角度審視消費(fèi)方案問題例例 要求制定一個消費(fèi)方案方案，在設(shè)備要求制定一個消費(fèi)方案方案，在設(shè)備A,B和調(diào)試三種資源限制下，使得產(chǎn)品的總和調(diào)試三種資源限制下，使得產(chǎn)品的總利潤最大利潤最大 。 maxZ=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20st.運(yùn)籌學(xué)教程轉(zhuǎn)換思緒轉(zhuǎn)換思緒: :投資人投資人: :假設(shè)某投資公司預(yù)備購買該工廠，它至少應(yīng)付出多大假設(shè)某投資公司預(yù)備購買該工廠，它至少應(yīng)付出多大的代價，才干使工廠本人放棄消費(fèi)產(chǎn)品的代價，才干使工廠本人放棄消費(fèi)產(chǎn)品、，而將

6、可利用，而將可利用的資源都出讓。的資源都出讓。被兼并人被兼并人: :該工廠的底線：最低可接受價錢，指按這種價錢轉(zhuǎn)該工廠的底線：最低可接受價錢，指按這種價錢轉(zhuǎn)讓資源比本人消費(fèi)產(chǎn)品讓資源比本人消費(fèi)產(chǎn)品、合算的價錢。合算的價錢。設(shè)設(shè)y1,y2， y3為代表單位時間這三種資源的出讓價錢，為了為代表單位時間這三種資源的出讓價錢，為了使工廠出讓資源合算，顯然應(yīng)該使出讓原來消費(fèi)一件產(chǎn)品使工廠出讓資源合算，顯然應(yīng)該使出讓原來消費(fèi)一件產(chǎn)品的資源所得收入不低于本人消費(fèi)產(chǎn)品的資源所得收入不低于本人消費(fèi)產(chǎn)品的利潤，即的利潤，即 0y1+6y2+1y3 2 對于產(chǎn)品對于產(chǎn)品，同樣可以建立類似的約束條件，同樣可以建立類似

7、的約束條件 5y1+2y2+1y31項目產(chǎn)品產(chǎn)品每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(元)21y1y2y3運(yùn)籌學(xué)教程 當(dāng)原問題和對偶問題都獲得最優(yōu)解時，這一對線性規(guī)劃對應(yīng)的目的函數(shù)值是相等的： Zmax=Wmin顯然在滿足這兩個約束的前提下，價錢越高，該顯然在滿足這兩個約束的前提下，價錢越高，該工廠越合算，但價錢太高，投資人方面又不會情工廠越合算，但價錢太高，投資人方面又不會情愿購買。因此，我們需求確定的價錢是愿購買。因此，我們需求確定的價錢是 使工廠合算的最低價錢，故應(yīng)建立目的函數(shù)：使工廠合算的最低價錢，故應(yīng)建立目的函數(shù)： min w=15y1+24y

8、2+5y3 項目項目產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品每天可用每天可用能力能力設(shè)備設(shè)備A(h)設(shè)備設(shè)備B(h)調(diào)試工序調(diào)試工序(h)06152115245利潤利潤(元元)21運(yùn)籌學(xué)教程 調(diào)查原問題和對偶問題的解，給作決策的管理者另一個自在度； 怎樣經(jīng)過添加更多的資源來添加利潤？怎樣經(jīng)過添加更多的資源來添加利潤？ 怎樣運(yùn)用不同類型的資源來添加利潤？怎樣運(yùn)用不同類型的資源來添加利潤？ 對應(yīng)第一個約束條件對應(yīng)第一個約束條件 對應(yīng)第二個約束條件對應(yīng)第二個約束條件Pmax Z = 2X1 + X2 5X2 15 對應(yīng)第一個對偶變量對應(yīng)第一個對偶變量 y1 6X1 + 2X2 24 對應(yīng)第二個對偶變量對應(yīng)第二個對偶變量 y

9、2 X1 + X2 5 對應(yīng)第三個對偶變量對應(yīng)第三個對偶變量 y3 X1 ， X2 0 Dmin w = 15y1 + 24y2 + 5y3 6y2 + y3 2 5y1 + 2y2 + y3 1 y1， y2， y3 0運(yùn)籌學(xué)教程1定義：假設(shè)原問題是定義：假設(shè)原問題是 0,.21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ運(yùn)籌學(xué)教程0,.21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW 這兩

10、個式子之間的變換關(guān)系稱為這兩個式子之間的變換關(guān)系稱為“對稱方式的對偶關(guān)系。對稱方式的對偶關(guān)系。 運(yùn)籌學(xué)教程0,. .21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW0,. .21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ運(yùn)籌學(xué)教程2對稱方式的對偶關(guān)系的矩陣描畫對稱方式的對偶關(guān)系的矩陣描畫0.YCYAtsYbbYMinWTTTTD0. .XbAXtsCXMaxZL 3從原問題寫出其對偶問題按照

11、定義； 記憶法那么： “上、下交換，換后矩陣轉(zhuǎn)置。 不等式變號，“極大變“極小運(yùn)籌學(xué)教程例例 寫出下面線性規(guī)劃的對偶問題：寫出下面線性規(guī)劃的對偶問題： 0,10251543. .221212121xxxxxxtsxxMaxZ0,124253. .101521212121yyyyyyt syyMinW運(yùn)籌學(xué)教程3332213333323213122323222121223232221211131321211133332211321333323213123232221211313212111332211, 0, 0)()(.max, 0, 0.maxxxxxxxybxaxaxaybxaxaxayb

12、xaxaxaybxaxaxastxcxcxcxcZxxxbxaxaxabxaxaxabxaxaxastxcxcxcZ自由, 0, 0.min0, 0, 0, 0.min3213333223113233222211213312211113322113221333322322311333332232231132332222222112133122122111133222211yyycyayayacyayayacyayayastybybybWyyyycyayayayacyayayayacyayayayacyayayayastybybybybW自由y2=y2-y2y3=-y3運(yùn)籌學(xué)教程2怎樣寫出非對稱

13、方式的對偶問題？怎樣寫出非對稱方式的對偶問題？把一個等式約束寫成兩個不等式約束，把一個等式約束寫成兩個不等式約束，再根據(jù)對稱方式的對偶關(guān)系定義寫出；再根據(jù)對稱方式的對偶關(guān)系定義寫出；按照原按照原-對偶表直接寫出對偶表直接寫出 ；3原原-對偶表對偶表運(yùn)籌學(xué)教程項目項目原問題原問題（對偶問題）（對偶問題）對偶問題對偶問題（原問題）（原問題）目標(biāo)函數(shù)類型目標(biāo)函數(shù)類型maxmin目標(biāo)函數(shù)系數(shù)與右邊項目標(biāo)函數(shù)系數(shù)與右邊項的對應(yīng)關(guān)系的對應(yīng)關(guān)系目標(biāo)函數(shù)各變量系數(shù)對應(yīng)目標(biāo)函數(shù)各變量系數(shù)對應(yīng)約束條件右邊項的系數(shù)約束條件右邊項的系數(shù)右邊項的系數(shù)對應(yīng)目標(biāo)函數(shù)右邊項的系數(shù)對應(yīng)目標(biāo)函數(shù)系數(shù)系數(shù)變量個數(shù)與約束條件個變量個

14、數(shù)與約束條件個數(shù)的對應(yīng)關(guān)系數(shù)的對應(yīng)關(guān)系變量個數(shù)變量個數(shù) n約束條件個數(shù)約束條件個數(shù) m約束條件個數(shù)約束條件個數(shù) n變量個數(shù)變量個數(shù) m原問題變量類型與對偶原問題變量類型與對偶問題約束條件類型的對問題約束條件類型的對應(yīng)關(guān)系應(yīng)關(guān)系 0 (對稱對稱)變量類型變量類型 0 (非對稱非對稱) 自由自由 (對稱對稱)約束條件類型約束條件類型 (非對稱非對稱) =原問題約束條件類型與原問題約束條件類型與對偶問題變量類型的對對偶問題變量類型的對應(yīng)關(guān)系應(yīng)關(guān)系 (非對稱非對稱)約束條件類型約束條件類型 (對稱對稱) = (非對稱非對稱)變量類型變量類型 (對稱對稱) 自由自由運(yùn)籌學(xué)教程例題：寫出下面線性規(guī)劃的對偶

15、規(guī)劃：例題：寫出下面線性規(guī)劃的對偶規(guī)劃：0, 01413121110987654. .32432121321321321xxxxxxxxxxxtsxxxMinZ符號不限運(yùn)籌學(xué)教程0, 0,31062139541284. .1411732121321321321yyyyyyyyyyyt syyyMaxW符號不限0, 0,31062139541284. .1411732121321321321yyyyyyyyyyytsyyyMaxW符號不限原問題是極小化問題，因此應(yīng)從原原問題是極小化問題，因此應(yīng)從原-對偶表對偶表的右邊往左邊查！的右邊往左邊查！ 0,01413121110987654.324321

16、21321321321xxxxxxxxxxxtsxxxMinZ符號不限項目項目原問題原問題（對偶問（對偶問題）題）對偶問題對偶問題（原問題）（原問題）目標(biāo)函數(shù)類型目標(biāo)函數(shù)類型maxmin原問題變量類原問題變量類型與對偶問題型與對偶問題約束條件類型約束條件類型的對應(yīng)關(guān)系的對應(yīng)關(guān)系 0 (對稱對稱)變量類型變量類型 0 (非非對稱對稱) 自由自由 (對稱對稱)約束條件類型約束條件類型 (非對稱非對稱) =原問題約束條原問題約束條件類型與對偶件類型與對偶問題變量類型問題變量類型的對應(yīng)關(guān)系的對應(yīng)關(guān)系 (非對稱非對稱)約束條件類型約束條件類型 (對稱對稱) = (非對稱非對稱)變量類型變量類型 (對稱對

17、稱) 自由自由運(yùn)籌學(xué)教程原問題對偶問題為對稱方式的線性規(guī)劃問題原問題對偶問題為對稱方式的線性規(guī)劃問題njxmibxat sxcMaxZjnjijijnjjj, 2 , 10, 2 , 1. .11miynjcyat sybMinWimijiijmiii, 2 , 10, 2 , 1. .11，運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程0,0.0SSSXXbIXAXtsXCXMaxZ)(NBCCC)(NBXXX)(),.,(,21INBPPPPIAmnn運(yùn)籌學(xué)教程bIXNXBXIXXXNBIXAXSNBSNBS)( 可得可得 用非基變量表示基變量的表達(dá)式：用非基變量表示基變量的表達(dá)式：SNSNBXBNXBbBIXNX

18、bBX1111)(運(yùn)籌學(xué)教程項目非基變量基變量XB XNXS0 XS b B N ICj-ZjCB CN 0項目基變量非基變量XB XN XSCB XB B-1 b IB-1 N B-1 Cj-Zj 0CN -CB B-1 N -CB B-1 迭代后的單純形表迭代后的單純形表初始單純形表初始單純形表對應(yīng)初始單純形表對應(yīng)初始單純形表中的單位陣中的單位陣 I，迭，迭代后為代后為B-1基變量的變換：基變量的變換： 初始初始 XS=b；迭；迭代后代后XB= B-1b約束系數(shù)矩陣的變化：約束系數(shù)矩陣的變化：A,I=B,N,I；B-1 A, B-1 I=B-1 B, B-1 N, B-1 I=I, B-1

19、 N, B-1.約束系數(shù)矩陣的向量變化：約束系數(shù)矩陣的向量變化：PjT = B-1 PjCBCN0運(yùn)籌學(xué)教程檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：CN-CB B-1 N0 (1); CN-CB B-1 N0 (1); -CB B-1 0; -CB B-1 0; 令令:CB-CBI=0 (2):CB-CBI=0 (2)(1)+(2)(1)+(2)得到得到 CN-CB B-1 N +CB-CBI= CN-CB B-1 N +CB-CBB-1BCN-CB B-1 N +CB-CBI= CN-CB B-1 N +CB-CBB-1B=CB+CN-CBB-1(B+N)=C-CBB-1A 0=CB+CN-CBB-1(B+N)=C

20、-CBB-1A 0 -CB B-1 0; -CB B-1 0;令令YT= CB B-1 YT= CB B-1 單純形乘子單純形乘子 ATY CT; ATY CT; Y0 Wmin= YTb= CBB-1b=Zmax Y0 Wmin= YTb= CBB-1b=ZmaxC-YTA 0C YTA C T (YTA)T檢驗(yàn)數(shù)的相反數(shù)為其檢驗(yàn)數(shù)的相反數(shù)為其對偶問題的一個可行對偶問題的一個可行解解運(yùn)籌學(xué)教程052426155.0002max3521242113254321jxyxxxyxxxyxxstxxxxxZ012526.0052415min25321143154321iyxyyyyxyyystyyy

21、yyW例例 原問題、對偶問題之間的關(guān)系原問題、對偶問題之間的關(guān)系項目原問題變量原問題松弛變量 x1 x2x3 x4 x5X3 15/2X1 7/2X2 3/2 0 0 1 0 0 11 5/4 -15/20 -1/20 -1/4 3/2 -Cj+zj 0 00 1/2DUAL 剩余變量DUAL 變量 y4 y5y1 y2 y3項目dual變量dual剩余變量 y1 y2 y3y4 y5y2 1/4y3 1/2 -5/4 1 015/2 0 1-1 /4 -3/2Cj-zj 15/2 0 07/2 3/2原問題松弛變量原問題 變量 x3 x4 x5x1 x2運(yùn)籌學(xué)教程y1 yi ym ym+1

22、ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對偶問題的變量 對偶問題的松弛變量 原始問題的變量 原始問題的松弛變量xjym+j=0 yixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于0，另一個一定等于0運(yùn)籌學(xué)教程0.XbAXtsCXMaxZL 0.YCYAtsbYMinW和和 D 均有可行解，分別為均有可行解，分別為 和和 ，那么，那么C b。XXYY證明思緒：證明思緒：由由L bXA 左乘左乘 ，得，得 bYXAYY由由D CAY 右乘右乘 ，得，得 XXCXAYbYXC運(yùn)籌學(xué)教程 推論推論:關(guān)于關(guān)于“界的結(jié)果；界的結(jié)果；極小化問題有下界極小化問題有下界推論推論1 原問題原問題 (極大化問題極大化問題) 的恣意一個可行解的恣意一個可行解所對應(yīng)的目的函數(shù)值是其對偶問標(biāo)題的函數(shù)值所對應(yīng)的目的函數(shù)值是其對偶問標(biāo)題的函數(shù)值的一個下界。的一個下界。運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程運(yùn)籌學(xué)教程XXXYYY運(yùn)籌學(xué)教程CX=Y CX=Y b bCX*Y*b弱對偶弱對偶定定 理理已已 知知結(jié)論結(jié)論Y*bY b由 于由 于XY可 行可 行解解CX CX*設(shè)設(shè)X*,Y*分別為原問題和對偶問題的最優(yōu)解分別為原問題和對偶問題的最優(yōu)解;