運(yùn)籌學(xué)第二章線性規(guī)劃的對(duì)偶理論(編輯修改稿)
2025-05-29 05:04 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 0)(性質(zhì) 3),所以 Yξ X(0)=0和 Y(0) Xξ =0 。 X(0) ， Y(0) 是最優(yōu)解 22 運(yùn)籌學(xué)基礎(chǔ) 7﹒ 設(shè)原問(wèn)題： max z=CX； AX+ Xξ = b； X, Xξ ≥0 對(duì)偶問(wèn)題：min ω=Yb； YA－ Yξ =C； Y , Yξ ≥0 。則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解。其關(guān)系如表： Ｘ Ｂ Ｘ Ｎ Ｘ ξ 0 Yξ1 CN1－ CB B1N1 ﹣ Yξ2 － CB B1 ﹣ Y 這里 Yξ1對(duì)應(yīng)原問(wèn)題的基變量 XB的剩余變量， Yξ2對(duì)應(yīng)原問(wèn)題的非基變量 XN的剩余變量。 證： max z=CBXB+ CNXN BXB+BXN +Xξ=b XN,XB,Xξ ≥0 設(shè) B是一可行基，于是 A=(B,N) min ω =Yb YB－ Yξ1=CB () Y, Yξ1 Yξ2 ≥0 YN－ Yξ2=CN () 23 對(duì)偶問(wèn)題的基本性質(zhì) 運(yùn)籌學(xué)基礎(chǔ) 證： max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0 設(shè) B是一可行基，于是 A=(B,N) min ω =Yb YB－ Yξ1=CB () Y, Yξ1 Yξ2 ≥0 YN－ Yξ2=CN () 其中 Yξ=(Yξ1, Yξ2) 當(dāng)原問(wèn)題的解為： XB=B1b 時(shí)，其檢驗(yàn)參數(shù)為 CN－CBB1N 與－ CBB1。 令 Y=CBB1 ，將它代入 ()和 ()得 Yξ1=0 ， ﹣ Yξ2 = CN－ CBB1N 因此，結(jié)論成立。 24 對(duì)偶問(wèn)題的基本性質(zhì) 運(yùn)籌學(xué)基礎(chǔ) 8﹒ 單純形乘子 Y的定理： 若 B是原問(wèn)題的一最優(yōu)可行基，則單純形乘子 Y=CBB1是對(duì)偶問(wèn)題的一個(gè)最優(yōu)解。 證：設(shè) X (0) 是對(duì)應(yīng)基 B的原問(wèn)題的最優(yōu)解，則 顯然， Y A≥C 。 所以 Y 是對(duì)偶問(wèn)題的可行解。 又因 Yb = CBB1 b=CX (0) 由性質(zhì) 4可知 Y 是對(duì)偶問(wèn)題的最優(yōu)解。 因此，結(jié)論成立。 C－ CBB1A≤0，且 z=C X (0) CBB1b 。 根據(jù)本性質(zhì)，可以從原問(wèn)題最優(yōu)解的單純形表中直接得到對(duì)偶問(wèn)題的最優(yōu)解。 25 運(yùn)籌學(xué)基礎(chǔ) 9﹒ 最優(yōu)對(duì)偶變量 (影子價(jià)格 )的經(jīng)濟(jì)解釋 從對(duì)偶定理可知 ，當(dāng)達(dá)到最優(yōu)解時(shí)，原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)值相等，即 z=CX(0)=Y(0)b=CBB1b . 也即 z=CX(0)=Y(0)b=CBB1b =y1(0)b1+ y2(0) b2 + …+ ym(0) bm 其中 X(0),Y(0)分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。 現(xiàn)在考慮在最優(yōu)解處 ，常數(shù)項(xiàng) bi的微小變動(dòng)對(duì)目標(biāo)函數(shù)值的影響(不改變?cè)瓉?lái)的最優(yōu)基 ).求 z對(duì) bi的偏導(dǎo)數(shù)，可得： y1(0) ＝ ?z — ?b1 , y2(0) ＝ ?z — ?b2 , ym(0) ＝ ?z — ?bm , … 這說(shuō)明 ，若原問(wèn)題的某一約束條件的右端常數(shù)項(xiàng) bi 增加一個(gè)單位，則由此引起的最優(yōu)目標(biāo)函值的增加量，就等于該約束條件相對(duì)應(yīng)的對(duì)偶變量的最優(yōu)值。 最優(yōu)變量 yi(0的值 ，就相當(dāng)于對(duì)單位第 I種資源在實(shí)現(xiàn)最大利潤(rùn)時(shí)的一種估價(jià)。這種估價(jià)是針對(duì)具體企業(yè)具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為“ 影子價(jià)格 ”。 “影子價(jià)格 ” 對(duì)市場(chǎng)有調(diào)節(jié)作用。 26 運(yùn)籌學(xué)基礎(chǔ) 例 已知線性規(guī)劃問(wèn)題 x1+x2 +2x3 +x4 +3x5 ≥4 2x1－ x2 +3x3 +x4 +x5 ≥3 min ω=2x1+3x2 +5x3 +2x4 +3x5 x1,x2 ,x3,x4 ,x5≥0 其對(duì)偶問(wèn)題的最優(yōu)解為 y1*=4/5, y2*=3/5； z=5 。試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。 解： 對(duì)偶問(wèn)題 max z＝ 4y1+3y2 y1+ 2y2 ≤2 ① y1 － y2 ≤3 ② 2y1+3y2 ≤5 ③ y1﹐ y2≥0 y1 + y2 ≤2 ④ 3y1 + y2 ≤3 ⑤ C=(2,3, 5,2,3) b=(4, 3)T 1 1 2 1 3 A= 2 1 3 1 1 Y A C 確定約束條件 Y=(y1, y2) 原 對(duì) min 變 ≥0 ≤0 無(wú) max 約 ≤ ≥ ＝ 約 ≥ ≤ ＝ 變 ≥0 ≤0 無(wú) 關(guān)系表 形成 27 運(yùn)籌學(xué)基礎(chǔ) 原 對(duì) min 變 ≥0 ≤0 無(wú) max 約 ≤ ≥ ＝ 約 ≥ ≤ ＝ 變 ≥0 ≤0 無(wú) 解： 對(duì)偶問(wèn)題 max z＝ 4y1+3y2 y1+ 2y2 ≤2 ① y1－ y2 ≤3 ② 2y1+3y2 ≤5 ③ y1﹐ y2≥0 y1 + y2 ≤2 ④ 3y1 + y2 ≤3 ⑤ C=(2,3, 5,2,3) b=(4, 3)T 1 1 2 1 3 A= 2 1 3 1 1 Y A C 確定約束條件 Y=(y1, y2) 關(guān)系表 形成 設(shè) Xξ=(xξ1, xξ2)T， Yξ=(yξ1, yξ2 , yξ3 , yξ4 , yξ5) 把 y1*=4/5, y2*=3/5 代入約束條件中可得 Yξ=(0, 14/5 ,8/5 ,2/5 , 0) 據(jù)互補(bǔ)松弛性： YξX*=0 YξX*=14/5x2*+8/5x3*+2/5x4*=0 所以 x2*= x3*= x4*=0 又因 Y*Xξ=4/5xξ1 +3/5xξ2=0 所以 xξ1 =xξ2 =0 28 對(duì)偶問(wèn)題的基本性質(zhì) 運(yùn)籌學(xué)基礎(chǔ) 設(shè) Xξ=(xξ1, xξ2)T， Yξ=(yξ1, yξ2 , yξ3 , yξ4 , yξ5) 把 y1*=4/5, y2*=3/5 代入約束條件中 可得 Yξ=(0, 14/5 ,8/5 ,2/5 , 0) 據(jù)互補(bǔ)松弛性： YξX*=0 YξX*=14/5x2*+8/5x3*+2/5x4*=0 所以 x2*= x3*= x4*=0 又因 Y*Xξ=4/5xξ1 +3/5xξ2=0 所以 xξ1 =xξ2 =0 因?yàn)? 所以 x1*+x2 * +2x3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1