




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第2章對(duì)偶規(guī)劃與靈敏度分析第2章 對(duì)偶規(guī)劃與靈敏度分析本章要點(diǎn):o 線性規(guī)劃對(duì)偶問(wèn)題的提出o 線性規(guī)劃問(wèn)題的對(duì)偶理論o 對(duì)偶解的經(jīng)濟(jì)解釋o 對(duì)偶單純形法o 靈敏度分析2.1 線性規(guī)劃的對(duì)偶問(wèn)題與對(duì)偶理論一、對(duì)偶問(wèn)題的提出例2.1 某家具公司(設(shè)為甲公司)生產(chǎn)桌子和椅子兩種家具,有關(guān)資料如下表所示,問(wèn)該家具公司應(yīng)如何安排生產(chǎn)才能每月的銷售收入最大?桌子椅子可供工時(shí)量(小時(shí)/月)木工工時(shí)(小時(shí)/件)43120油漆工工時(shí)(小時(shí)/件)2150售價(jià)(元/件)5030家具加工時(shí)間加工工種設(shè)兩種產(chǎn)品產(chǎn)量分別為x1,x2,則其線性規(guī)劃模型為:213050 xxZMax0, 050212034. .212121
2、xxxxxxtso 假設(shè)現(xiàn)有乙公司準(zhǔn)備租借用(購(gòu)買)該木器廠的木工和油漆工兩種勞力的勞務(wù),需要考慮這兩種勞務(wù)以什么樣的價(jià)格租入最合算?而同時(shí)甲公司要以什么條件才會(huì)租讓?甲公司肯定會(huì)以自己利用兩種勞力的勞務(wù)組織生產(chǎn)所獲得的利潤(rùn)最大為條件,設(shè)每個(gè)木工的租用價(jià)格為y1,每個(gè)油漆工的租用價(jià)格為y2,則乙公司愿意租用的出資為:甲公司愿意出租的條件會(huì)是公司單個(gè)勞力出售的勞務(wù)收入之和自己組織生產(chǎn)所創(chuàng)造的利潤(rùn).即:2.1 線性規(guī)劃的對(duì)偶問(wèn)題與對(duì)偶理論2150120yySMin30350242121yyyy同時(shí):y1和y2要滿足非負(fù)條件.2.1 線性規(guī)劃的對(duì)偶問(wèn)題與對(duì)偶理論(2)o 即:213050 xxZMa
3、x0, 050212034. .212121xxxxxxts2150120yySM in0, 03035024. .212121yyyyyyts(P)(D)MaxCXZ OXbAXts . .MinYbSTOYCYAtsTT. .任何線性規(guī)劃問(wèn)題都有對(duì)偶問(wèn)題,而且都有相應(yīng)的經(jīng)濟(jì)意義。2.1 線性規(guī)劃的對(duì)偶問(wèn)題與對(duì)偶理論(3)二、原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題(或?qū)ε紗?wèn)題)對(duì)偶問(wèn)題(或原問(wèn)題)目標(biāo)函數(shù)最大化(MaxZ)目標(biāo)函數(shù)最小化(MinS)無(wú)限制變量00型型型約束型型型約束無(wú)限制變量00n個(gè)變量n個(gè)約束m個(gè)約束m個(gè)變量約束條件限定向量(右邊項(xiàng))目標(biāo)函數(shù)價(jià)值向量(系數(shù))目標(biāo)函數(shù)價(jià)值向量約束條
4、件限定向量2.1 線性規(guī)劃的對(duì)偶問(wèn)題與對(duì)偶理論(4)321342xxxZMax0, 0832353410. .21321321321xxxxxxxxxxxt sn寫出下列問(wèn)題的對(duì)偶問(wèn)題:3218510yyySMin. .t s23321yyy424321yyy333321yyy0, 031yy2.2 線性規(guī)劃的對(duì)偶理論o 線性規(guī)劃對(duì)偶理論的主要基本定理:定理1:對(duì)稱性定理 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題定理2:設(shè)X和Y分別是原問(wèn)題P和對(duì)偶問(wèn)題D的可行解則:必有CXbTY 。定理3:對(duì)偶原理 原問(wèn)題P和對(duì)偶問(wèn)題D存在如下對(duì)應(yīng)關(guān)系:1)P有最優(yōu)解的充要條件是D有最優(yōu)解;2)若P無(wú)界則D無(wú)可行解,若D無(wú)界則
5、P無(wú)可行解;3)若X*和Y*分別是P和D的可行解,則它們分別為P和D的最優(yōu)解的充要條件是CX*=Y*b2.2 線性規(guī)劃的對(duì)偶理論(2)o 線性規(guī)劃對(duì)偶理論的主要基本定理:定理4:互補(bǔ)松馳性定理: 如果X和Y分別為P和D的可行解,它們分別為P和D的最優(yōu)解的充要條件是 (C-YTA)X=0和YT(b-AX)=0max543210002xxxxxz)5 , 1(052426155.52142132jxxxxxxxxxstjmin543210052415yyyyys)5 , 1(012526.5321432iyyyyyyyysti對(duì)偶變量y1y2y3對(duì)偶變量x1x2原問(wèn)題P:max543210002x
6、xxxxz)5 , 1(052426155.52142132jxxxxxxxxxstj對(duì)偶變量y1y2y3對(duì)偶問(wèn)題D:原問(wèn)題與對(duì)偶問(wèn)題互補(bǔ)松馳對(duì)應(yīng)關(guān)系用單純形法求解:Cj原問(wèn)題變量原問(wèn)題松馳變量xBbx1x2x3x4x5x315/2 0015/4-15/2x17/21001/4-1/2x27/2010-1/43/2-z-3/2000-1/4-1/2對(duì)偶變量的剩余變量對(duì)偶問(wèn)題變量y4y5y1y2y3Cj對(duì)偶問(wèn)題變量對(duì)偶變量的剩余變量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原問(wèn)題松馳變量原問(wèn)題變量x3x4x
7、5x1x22.3 對(duì)偶單純法一、對(duì)偶單純法的基本思想n求解線性規(guī)劃的單純法的思路是:對(duì)原問(wèn)題的一個(gè)基本可行解(即所有右端常數(shù)0) ,判別是否所有的檢驗(yàn)數(shù)j0。若是,又基變量中無(wú)人工變量,即找到了問(wèn)題的最優(yōu)解;若為否,再找出相鄰的目標(biāo)函數(shù)值更大的基本可行解,并繼續(xù)判別,只要最優(yōu)解存在,就一直迭代進(jìn)行到找出最優(yōu)解為止。n根據(jù)對(duì)偶原理性質(zhì)可知:在同一個(gè)單純形表中,如果原問(wèn)題為可行解(即所有右端常數(shù)0),而且判別行所有檢驗(yàn)數(shù)j0,則原問(wèn)題和對(duì)偶問(wèn)題都達(dá)到最優(yōu)解。n對(duì)偶單純法的基本思想是:先找出對(duì)偶問(wèn)題的基本可行解(即單純形表中判別行所有的檢驗(yàn)數(shù)j0),但原問(wèn)題為非可行解(即不滿足所有右端常數(shù)0),然后
8、一直保持對(duì)偶問(wèn)題為可行解的條件下,利用對(duì)偶單純法進(jìn)行迭代,一直到原問(wèn)題也為可行解(即滿足所有右端常數(shù)0),這時(shí)也就同時(shí)得到了原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。2.3 對(duì)偶單純法(2)o可知:對(duì)偶單純形法是利用對(duì)偶原理求解原問(wèn)題的一種方法,而不是求解對(duì)偶問(wèn)題解的單純形法。riibbb0|minrssrjrjjjaaa0|min1)寫出問(wèn)題初始單純形表:?jiǎn)渭冃伪碇信袆e行所有的檢驗(yàn)數(shù)j0;若b列的數(shù)字都為非負(fù)(即0 ),則已得到最優(yōu)解;否則,轉(zhuǎn)下一步;2)確定退出基變量。3)確定進(jìn)入基變量。4)繼續(xù)迭代,直至求出最優(yōu)解。二、對(duì)偶單純法計(jì)算步驟2.3 對(duì)偶單純法(3)o 例:2153xxz0,96603082
9、4. .212121xxxxxxtsMin2153xxzz0,966030824. .4321421321xxxxxxxxxxtsMax2153xxz0,966030824. .4321421321xxxxxxxxxxtsMax化標(biāo)準(zhǔn)型式:化為對(duì)偶單純法求解形式2.3 對(duì)偶單純法(4):求解過(guò)程CBCj-3-500 xBbx1x2x3x40 x3-8-4-2100 x4-96-30(-60)01-Z0-3-500j1/101/12CBCj-3-500 xBbx1x2x3x40 x3-4.8-301-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/22.3
10、對(duì)偶單純法(5):求解過(guò)程CBCj-3-500 xBbx1x2x3x40 x3-4.8(-3)01-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/2CBCj-3-500 xBbx1x2x3x4-3x11.610-1/31/90-5X20.8011/6-1/45-Z-8.800-1/6-7/90j用對(duì)偶單純形法求解:初始單純形表最終單純形表單純形法矩陣解析2.4 對(duì)偶解的經(jīng)濟(jì)解釋一、對(duì)偶線性規(guī)劃的解:P55Cj原問(wèn)題變量原問(wèn)題變量xBbx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x27/2010-1/43/2z3/2
11、0001/41/2對(duì)偶變量的剩余變量對(duì)偶問(wèn)題變量y4y5y1y2y3Cj對(duì)偶問(wèn)題變量對(duì)偶變量的剩余變量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原問(wèn)題松馳變量原問(wèn)題變量x3x4x5x1x22.4 對(duì)偶解的經(jīng)濟(jì)解釋(2)二、影子價(jià)格CXZ bYT就是影子價(jià)格即,YBC:YBT1bBCXNBCCbBCBNBNB111)(1。影子價(jià)格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度。2。影子價(jià)格是一種邊際價(jià)值。3。影子價(jià)格是對(duì)系統(tǒng)資源的一種最優(yōu)估價(jià)。4。影子價(jià)格的價(jià)格與系統(tǒng)狀態(tài)有關(guān)。是一種動(dòng)態(tài)價(jià)格。首先將線性規(guī)劃與經(jīng)濟(jì)
12、問(wèn)題聯(lián)系起來(lái)的是 T.G.Koopman(庫(kù)普曼)和 L.V.Kamtorovich(康脫羅維奇)二人因此而共同分享了1975年的第7屆諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。2.5 靈敏度分析一、靈敏度分析的含義o 是指系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感性程度的分析。o 對(duì)于線性規(guī)劃問(wèn)題的靈敏度分析是指參數(shù)A,b,C變化引起的對(duì)原問(wèn)題解的變化的分析。其中:A為技術(shù)參數(shù)矩陣,b為資源向量,C為價(jià)值向量o 可以用參數(shù)變化后的問(wèn)題重新用單純形法求解? 沒(méi)必要,意義不大,有些問(wèn)題看不出來(lái)。o 把相應(yīng)的變化反映到最終單純形表中,再根據(jù)情況用相應(yīng)的方法求解。2.5 靈敏度分析(2)加入變化參數(shù)反映到最終單純形表,視情況分別
13、處理如下:原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量,編制新的單純形表重新計(jì)算2.5 靈敏度分析(3)二、三種變化(A,b,C的變化)1。 Cj的變化線性規(guī)劃目標(biāo)函數(shù)據(jù)中變量系數(shù)Cj的變化僅僅影響到檢驗(yàn)數(shù)的變化,所以將Cj的變化直接反映到最終單純表中。例2-1:美佳公司計(jì)劃制造I,II兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A,B的臺(tái)時(shí)、調(diào)試時(shí)間、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件時(shí)的獲得情況,如表所示。問(wèn)該公司應(yīng)制造兩種家電各多少件,使
14、獲取的利潤(rùn)為最大。項(xiàng)目III每天可用能力設(shè)備A(h)0515設(shè)備B(h)6224調(diào)試工序(h)115利潤(rùn)(元)212.5 靈敏度分析(3)212xxZMax0,052426155.2121212xxxxxxxts解:設(shè)x1和x2分別表示美佳公司制造家電I和II的數(shù)量。則該問(wèn)題可用線性規(guī)劃模型表示如右:則用單純形法求解的最終單純形表如下:CBCj21000ixBbx1x2x3x4x50 x315/2 0015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/22.5 靈敏度分析(4)例2-2:在例2-1中,(1)若家電I的利潤(rùn)降至1.5元/
15、件,而家電II的利潤(rùn)增至2元/件時(shí),美佳公司最優(yōu)的生產(chǎn)計(jì)劃有何變化;(2) 若家電I的利潤(rùn)不變,則家電II的利潤(rùn)在什么范圍內(nèi)變化時(shí),則該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化.解:(1)則將家電I,II的利潤(rùn)變化直接反映到最終單純形表中得到下表:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21.521.52-33/40001/8-9/46145/42.5 靈敏度分析(5)CBCj1.5 2000ixBbx1x2x3x4x50 x46004/51-61.5 x1210-1/
16、5012X23011/500-Z-900-1/100-3/2迭代后得到下表可知為最優(yōu)表,可得出最優(yōu)解為:X*=(2,3,0,6,0)T 最優(yōu)目標(biāo)值Zmax=92.5 靈敏度分析(6)(2) 則加入?yún)?shù)a變化到最終表為:CBCj21000 xBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21+a1+a-1/4+a/4-1/2-3a/20023214141aa131a2232 C根據(jù)最優(yōu)判別條件,要保持最優(yōu)基不變,則: 0j則有:2.5 靈敏度分析(7)2. bi的變化例2-3 在例2-1中
17、,(1)若設(shè)備A和調(diào)試工序的每天能力不變,而設(shè)備B每天的能力增加到32h,分析公司最優(yōu)計(jì)劃的變化;(2)若設(shè)備A和B每天可用能力不變,則調(diào)試工序能力在什么范圍內(nèi)變化時(shí),問(wèn)題的最優(yōu)基不變. 解: (1)因有:080bbBbbBb11,則也有22100802/34/102/14/102/154/511bBb變化到最終單純形表值為:2.5 靈敏度分析(8)2121123523272152210bb,b則變化到最終單純形表中如下:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z000-1/4-1/2
18、-1/435/211/2-1/22.5 靈敏度分析(9)CBCj21000ixBbx1x2x3x4x50 x315051002X15110010X420-401-6-Z-100-100-2則迭代后得到如下表:2.5 靈敏度分析(10)(2)設(shè)調(diào)試工序每天可用能力為(5+a)h,因有:ab00aaaabBb23212151002/34/102/14/102/154/51aaaaaabb,b2323212721521523212152327215則6411,03b,a,b即可求得由2.5 靈敏度分析(11)3.技術(shù)系數(shù)發(fā)生變化的分析例2-4 在例2-1基礎(chǔ)上,若家電II每件需須設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h、4h和1h,該產(chǎn)品的利潤(rùn)變?yōu)?元/件,試重新確定美佳公司最優(yōu)生產(chǎn)計(jì)劃。解:分兩步:第一步:計(jì)算檢驗(yàn)數(shù)。設(shè)新家電產(chǎn)品II的產(chǎn)量為x,則對(duì)應(yīng)檢驗(yàn)數(shù)為:02/32122PBCCB第二步:計(jì)算新增變量在最終單純形表中的列向量。(如上一步中計(jì)算為0則無(wú)需進(jìn)行這一步)2/12/12/111482/34/102/14/102/1
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 工程師賦能職業(yè)教育的關(guān)鍵能力與創(chuàng)新驅(qū)動(dòng)路徑
- 傳統(tǒng)文化教育與職業(yè)技能培養(yǎng)的協(xié)同效應(yīng)分析
- 浙江省杭州市名校2024年數(shù)學(xué)八上期末聯(lián)考試題含解析
- 遼寧省盤錦市2024-2025學(xué)年九年級(jí)化學(xué)第一學(xué)期期末經(jīng)典試題含解析
- 浙江省紹興越城區(qū)五校聯(lián)考2025屆物理八上期末檢測(cè)試題含解析
- 黑龍江省哈爾濱南崗區(qū)2024年九上化學(xué)期末監(jiān)測(cè)模擬試題含解析
- 廣東省深圳市桃源中學(xué)2024-2025學(xué)年物理八年級(jí)第一學(xué)期期末聯(lián)考試題含解析
- 河北省秦皇島市名校2024-2025學(xué)年數(shù)學(xué)七年級(jí)第一學(xué)期期末經(jīng)典試題含解析
- 餐飲企業(yè)品牌形象店租賃及宣傳協(xié)議
- 酶法合成技術(shù)革新:法尼龍單體生產(chǎn)的前沿探索
- 高新技術(shù)企業(yè)研發(fā)費(fèi)用管理辦法
- 老年急重癥診療及護(hù)理
- 中小學(xué)家長(zhǎng)會(huì)期中期末家長(zhǎng)會(huì)253
- 驅(qū)動(dòng)電機(jī)與電機(jī)控制器
- 2024年便攜式儲(chǔ)能行業(yè)分析報(bào)告
- 醫(yī)聯(lián)體協(xié)議書(2024版)
- 2023年全國(guó)職業(yè)院校技能大賽-中藥傳統(tǒng)技能賽項(xiàng)規(guī)程
- 11 《愛(ài)蓮說(shuō)》對(duì)比閱讀-2024-2025中考語(yǔ)文文言文閱讀專項(xiàng)訓(xùn)練(含答案)
- 動(dòng)物園野生動(dòng)物馴養(yǎng)繁殖或馴養(yǎng)觀賞可行性研究報(bào)告
- 煤礦開掘技術(shù)操作規(guī)程
- 2023年上海市長(zhǎng)寧區(qū)高三年級(jí)下冊(cè)二模英語(yǔ)試卷含詳解
評(píng)論
0/150
提交評(píng)論