第三章 線性規(guī)劃的對(duì)偶理論

1、第 三 章 對(duì) 偶 理 論 (Duality Theory) 線性規(guī)劃對(duì)偶問題的提出 線性規(guī)劃的矩陣表示 對(duì)偶問題的性質(zhì) 對(duì) 偶 單 純 形 法 靈 敏 度 分 析 應(yīng)用實(shí)例 2.對(duì)偶問題： Max z = 30 x1 + 25x2 s.t. 2x1 + 4x2 40 3x1 + 2x2 30 x1 ,x2 0 A：x1公斤； B：x2 公斤。 若第二章例1中制藥廠的設(shè)備都用 于外協(xié)加工，即該廠的決策者不是 考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而 是將廠里的現(xiàn)有資源用于接受外來 加工任務(wù)，工廠只收取加工費(fèi)。試 問：設(shè)備甲、乙每工時(shí)各應(yīng)如何收 費(fèi)才最有競(jìng)爭(zhēng)力？ 下面從另一個(gè)角度來討論這個(gè)問題： 分析問題

2、： 1.每種資源收回的費(fèi)用不能低于自己生產(chǎn)時(shí)的可獲利潤(rùn)； 2.定價(jià)又不能太高，要使對(duì)方能夠接受。 每一個(gè)線性規(guī)劃（ LP ）必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，其中的一個(gè)問 題叫“原問題”，記為“LP”，另一個(gè)稱為“對(duì)偶問題”，記為“DP”。 對(duì)稱形式： 互為對(duì)偶 (LP) Max = (DP) Min = T s.t. s.t. T 0 0 “Max - ” “Min- ” (2)從約束系數(shù)矩陣看：一個(gè)模型中為， 則另一個(gè)模型中為AT。一個(gè)模型是m個(gè)約束， n個(gè)變量，則它的對(duì)偶模型為n個(gè)約束，m個(gè) 變量。 (3)從數(shù)據(jù)b、C的位置看：在兩個(gè)規(guī)劃模型 中，b和C的位置對(duì)換。 (4)兩個(gè)規(guī)劃

3、模型中的變量皆非負(fù)。 1 對(duì)偶規(guī)劃問題 P. 44 任一L.P.問題，都有一個(gè)與之密切相關(guān)的L.P.問題， 叫對(duì)偶問題。 給定一個(gè)L.P.問題，如何引出其對(duì) 偶問題？見P.52 . 表 31。 x1 x2 . xn 原關(guān)系 Min y1 a 11 a 12 . a 1n b1 y2 a 21 a 22 . a 2n b2 . . . . . . . . . . ym a m1 a m2 . a mn bm 對(duì)偶關(guān)系 . (X0,Y0,) Max Z c1 c2 . cn 橫向組合得原問題： Max Z= c1 x1 + c2 x2 + . + cn xn a 11 x1 + a 12x2 +

4、. + a 1n xnb1 a 21 x1 + a 22x2 + . + a 2n xnb2 . . . . . . . a m1 x1 + a m2x2 + . + a mn xnbm X 0 縱向組合得對(duì)偶問題： Min = b1y1 +b2y2 + . +bmym a 11 y1 + a 21 y2 + . + a m1 ym c1 a 12 y1 + a 22 y2 + . + a m2 ym c2 . . . . . . . . a 1n y1 + a 2n y2 + . + a mn ym cn Y 0 若寫成矩陣形式，可得： 原問題： 對(duì)偶問題： Max Z=CX Min =bT

5、Y AX b AT Y CT X 0 Y 0 注意：其中C是行向量，X、Y與b是 列向量，Amn為aij所構(gòu)成的矩陣。 2 3 4 1 其矩陣形式為： 對(duì)偶（原）問題為 : 以下舉例說明對(duì)偶問題的作法，見 P.52 例 2 原（對(duì)偶）問題： Min Z=2x1+5x2 y1 x1 4 y2 x2 3 y3 x1+2x2 8 x1 , x2 0 x1 x2 1 0 1 0 1 2 y1 y2 y3 對(duì)偶（原）問題為： MaxW=4y1 +3 y2 +8y3 y1 +y3 2 x1 y2 +2y3 5 x2 y10,y20,y30 2 5 1 0 0 1 1 2 4 3 8 x1 x2 y1 y2

6、 y3 Xo Yo Max W=(4 , 3 , 8 ) 原（對(duì)偶）問題： Min Z=(2,5) ： 1. 0, 564 3 7 3 2 532 . . 432max 321 321 321 321 321 xxx xxx xxx xxx ts xxxZ 2. Min w = 12y1+ 8y2+ 16y2+ 12y2 s.t. 2y1+ y2+ 4y3 2 2y1+2y2+ 4y4 3 y1, y2 , y3 , y4 0 解：2.首先將原式變形 0, 5 64 3 7 3 2532 432max 321 321 321 32 321 xxx xxx xxx xxx xxxZ 0, 467

7、5 343 232 532min 321 321 321 321 321 yyy yyy yyy yyy yyyW 對(duì)偶問題： 解：1. 例如：對(duì)約束條件是等式的LP問題 max z=CX s.t. AX=b X0 AX=b AX=b AXb -AX-b 所以，原問題可化為 max z=CX s.t. AXb -AX-b X0 A b X -A -b 解： 首先將原問題化 成 對(duì)稱形式，令 x2=x3-x4, x30， x40， 原問題化為 max z=4x1+5x3-5x4 s.t. 3x1+2x3-2x4 20 -4x1+3x3-3x4 - 10 x1+ x3x4 5 -x1- x3+ x

8、4 -5 x1 ，x3 ，x4 0 將對(duì)稱形式線性規(guī)劃問題化為對(duì)偶問題如 下 Min W =20w1-10w2+5w3-5w4 s.t. 3w1-4w2+w3-w44 2w1+3w2+w3-w45 -2w1-3w2-w3+w4-5 w1，w2，w3，w40 -1，得 2w1+3w2+w3-w4 5 令y1=w1，y2=w2，y3=w3-w4，得 Min W =20y1-10y2+5y3 s.t. 3y1-4y2+y3 4 2y1+3y2+y3 =5 y1，y20 ,y3符號(hào)不限 原規(guī)劃與對(duì)偶規(guī)劃的線性關(guān)系 56 表33 原（對(duì)偶）規(guī)劃對(duì)偶（原）規(guī)劃 目標(biāo) max zmin f 目標(biāo) 約束 m個(gè)

9、 = m個(gè) 0 0 自由 變量 變量 n個(gè) 0 0 自由 n個(gè) = 約束 限制向量b 價(jià)值向量C 系數(shù)矩陣A 價(jià)值向量C 限制向量b 系數(shù)矩陣AT （3）若原規(guī)劃的某個(gè)約束條件為等式約束， 則在對(duì)偶規(guī)劃中與此約束對(duì)應(yīng)的那個(gè)變量取 值沒有非負(fù)限制； （4）若原規(guī)劃的某個(gè)變量的值沒有非負(fù)限 制，則在對(duì)偶問題中與此變量對(duì)應(yīng)的那個(gè)約 束為等式。 沒有非負(fù)限制 3214 321 431 4321 4321 , 0,105 30422 60272 2523 75max xxxx xxx xxx xxxx xxxxz 解：先將約束條件變形為如下形式 再根據(jù)非對(duì)稱形式的對(duì)應(yīng)關(guān)系，直接寫出對(duì)偶規(guī)劃 沒有非負(fù)限制

10、 4321 4 4 321 431 4321 ,0,0 5 10 30422 60272 2523 xxxx x x xxx xxx xxxx 0,0, 72 5472 123 122 510306025min 43521 5421 321 31 321 54321 yyyyy yyyy yyy yy yyy yyyyyf 沒有非負(fù)限制 max z=x1-x2+5x3-7x4 解答： 1 Min W =15y1+20y2 s.t. 2y1+4y2 4 y1+3y2 3 y1符號(hào)不限，y2 0 2 Min W =-5y1+14y2+3y3 s.t. Y1 +3y2-4y3 3 2y1-y2-5y

11、3 -6 -3y1+y2+3y3 =5 -y1-7y2+2y3 =4 y20 ，y3 0 ，y1符號(hào)不限 25 無約束、， 4321 4321 432 4321 4321 321 321 321 321 321 ,00 24732 543 3432 s.t. 4323min2 0, 564 37 3 2532 s.t. 422min.1 xxxx xxxx xxx xxxx xxxxZ. xxx xxx xxx xxx xxxZ 0.yy0,y 46y7y5y 24yy 3y 2y 3y2y s.t. 532max.1 321 321 321 321 321 yyyW 無約束 321 321

12、321 321 31 321 y0,y0,y 44y4y4y 37y3y3y 23yy 2y 32y y s.t. 253max.2 yyyW 答案： 四、線性規(guī)劃的矩陣表示 0, . . max INB INB IINNBB XXX bIXNXBXts XCXCXCz 0, ,. . ,max INB I N B I N B INB XXX b X X X INBts X X X CCCz 0 . . max X bAXts CXz 0, . . max I I II XX bIXAXts XCCXz 0, . . )()(max 111 111 INB INB IBINBNB XXX bB

13、IXBNXBXt s XIBCCXNBCCbBCz 0, . . max INB INB IINNBB XXX bIXNXBXts XCXCXCz 0, . . max 111 INB INB IINNBB XXX IXBNXBbBXt s XCXCXCz XB Xj 請(qǐng)分別指出， B-1， B-1， CN-CB B-1 N， CI-CB B-1 習(xí)題：一個(gè)極大化（目標(biāo)函數(shù)為max Z）的線 性規(guī)劃問題，有三個(gè)非負(fù)變量x1,x2,x3，兩個(gè) “”型約束條件，x4,x5是松弛變量，用單純形 法計(jì)算時(shí)得到的初始單純型表及最終單純型表 如下，最優(yōu)單純型表中，x1、x5為基變量，請(qǐng) 將表中空白處數(shù)字填

14、上。 1 0 0 1 1 3 6 10 1 1 0-3-1-20 33 性質(zhì)一、對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題。 第二節(jié) 對(duì)偶問題的性質(zhì) max z=-CTX s.t. -AX-b X 0 min y =-bTW s.t. -ATW-C W 0 max y=bTW s.t. ATWC W 0 min z=CTX s.t. AXb X 0 對(duì)偶的定義 對(duì)偶的定義 其他形式問題的對(duì)偶其他形式問題的對(duì)偶 min z=CTX s.t.AXb X 0 max y=bTW s.t. ATWC W 0 min z=CTX s.t.AX=b X 0 max y=bTW s.t. ATWC W ：unr 弱

15、對(duì)偶定理說明：如果原問題是最大化問題， 則它的任一可行解對(duì)應(yīng)的目標(biāo)函數(shù)值不大與 其對(duì)偶問題（最小化問題）的可行解對(duì)應(yīng)的 目標(biāo)函數(shù)值。 性質(zhì)三 （最優(yōu)性判定定理 ）可行解是最優(yōu)解時(shí)的性質(zhì) 當(dāng)X* 是原問題（Max）的可行解，Y* 是其對(duì)偶問題（Min）的可行解時(shí)，若 CX*=Y*b，則 X*與 Y* 是各自問題的最優(yōu)解。 證明 ： 設(shè)X* 是原問題的任意一個(gè)可行解，由性質(zhì) 2即弱對(duì)偶定理可知， CX* Y*b， 又由 CX*=Y*b知: CX* Y*b = CX*, 就是說,X* 使目標(biāo)函數(shù)所達(dá)到的值比其它任何可行解使目標(biāo)函數(shù)所達(dá)到的值不會(huì)小， 所以X* 是最優(yōu)解。 同理（設(shè)Y*b CX* =Y

16、*b ） ，Y* 是其對(duì)偶問題的最優(yōu)解。 證畢。 性質(zhì)四 （強(qiáng)對(duì)偶定理）若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函 數(shù)最優(yōu)值相等。 證明 設(shè)原問題的形式為：Max Z=CX，AX b; X 0 ，于是AX+XS=b，即 （A，I） =b，其中A為 m x n 矩陣，I為 m 階單位矩陣，XS為m 維列向量。 既知有最優(yōu)解，必有最優(yōu)基變量對(duì)應(yīng)的矩陣，記之為 B，那么，在最終單純形表 中，檢驗(yàn)數(shù)所形成的行向量為： （C- CBB-1A，- CBB-1） 0，于是 C- CBB-1A0 ，即 CBB-1A C （YA C） 令 Y*= CBB-1 ，又 - CBB-10，即 CBB-1 0 ，

17、可得 Y*= CBB-1 0 ，則 YA C, Y*是對(duì)偶問題 （ Min W=Yb; YA C; Y 0）的可行解，而 W =Y* b =CB B-1b。因 為 B 是最優(yōu)基變量對(duì)應(yīng)的矩陣，所以 Zmax=CX=CB B-1b = Y*b， 由性質(zhì)3 ，定理獲證。 X XS 對(duì) 偶 性 質(zhì) 4 性質(zhì)五 （52頁）互補(bǔ)松馳定理 若X*與Y*分別為原問題和對(duì)偶問題的可行解，那 么Y*XS=0和 YSX*=0的充分必要條件是 X*、Y* 為最優(yōu)解。 XS與 YS分別為原問題 和對(duì)偶問題的松弛變量和剩余變量。 Max Z=CX AX+XS=b X 0 Min W=Yb YA -YS=C Y 0 證明

18、 必要性：設(shè)原問題和對(duì)偶 問題的標(biāo)準(zhǔn)形式分別為： 和 于是 C=YA -YS，b= AX+XS， 所以Z（X）=CX=（ YA -YS ）X=YAX- YS X， 而 W（Y）=Y b=Y（ AX+XS）=YAX+YXS 可見,若 Y*XS= YSX*=0 ,則 Z（X*）=Y*AX*=W（ Y* ）,由性質(zhì)3知 X*,Y* 為最 優(yōu)解。必要性獲證。以下證充分性。 若X*與Y*分別為原問題和對(duì)偶問題的最優(yōu)解，由性質(zhì)4可知 Z（X*）= Y*AX* - YS X* = Y*AX* +Y*XS= W（Y*）。又由于X*與Y*為可行解，存在X*、Y* 、XS， YS 0， 則必有YSX*0 ， Y*

19、XS0， 于是由上式知 Y*XS= YSX*=0，充分性獲證， 完！ 原始問題和對(duì)偶問題最優(yōu)解之間的互補(bǔ)松弛關(guān)系 min z=CTX s.t. AX-XS=b X, XS0 max y=bTW s.t. ATW+WS=C W, WS0 min z=CTX s.t. AXb X 0 max y=bTW s.t. ATWC W0 對(duì)偶對(duì)偶 引進(jìn)剩余變量引進(jìn)剩余變量 引進(jìn)松弛變量引進(jìn)松弛變量 XWS=0 WXS=0 互補(bǔ)松弛關(guān)系 X，XsW，Ws 設(shè)有L.P.問題 Max Z=x1+2x2+3x3+4x4 x1+x2+2x3+3x4 20 2 x1+ x2+3 x3+2 x420 xj 0, 1 j

20、 4 已知其對(duì)偶問題的最優(yōu)解為：y1* =1.2, y2* =0.2, 相應(yīng)的目標(biāo)函數(shù)值W* =28, 試用對(duì) 偶理論求原問題的解。 解： 其對(duì)偶問題為： Min W=20 y1 +20 y2 y1 +2 y21 2y1 + y2 2 2y1 +3 y2 3 3y1 + 2y2 4 y1 , y2 0 x1 x2 x3 x4 Max Z=x1+2x2+3x3+4x4 x1+x2+2x3+3x4 +u1*=20 2 x1+ x2+3 x3+2 x4+u2*=20 Min W=20 y1 +20 y2 y1 +2 y2 -v1*=1 2y1 + y2 -v2*=2 2y1 +3 y2 -v3*=3

21、 3y1 + 2y2 -v4*=4 y1 , y2 0 x1 x2 x3 x4 將y1* =1.2, y2* =0.2 代入對(duì)偶問題的約束條件，得（1），（2）為嚴(yán)格不等 式，所以v1* 0 ， v2* 0 ；由互補(bǔ)松弛性得 x1* v1* =x2* v2* =0 ，所以 x1*=x2*=0 。又因?yàn)椋?y1* 0, y2* 0,所以 u1*= u2*= 0,即原問題的兩個(gè)約束條件 為等式約束，故得方程組： 2x3*+ 3x4* = 20 3x3*+ 2x4*= 20 解之得 x3*=x4*=4 ；而W*=Z*=28。 故原問題的 最優(yōu)解為： X*=（0，0，4，4）T，W*=28。 （1）

22、（2） （3） （4） 練習(xí)題： 設(shè)有L.P.問題 ，已知原問題的最優(yōu) 解為X* =（0.0.4），Z=12 試求對(duì) 偶問題的最優(yōu)解。 無無約約束束 321 321 321 321 321 , 0, 0 4 16 3 2532 34max xxx xxx xxx xxx xxxZ 解：其對(duì)偶問題為： 無約束無約束 321 321 321 321 321 , 0, 0 365 4 3 132 42min yyy yyy yyy yyy yyyW 將X* =（0 . 0 . 4）代入原問題中，有下式： 4 4 1 246 3 220532 321 321 321 xxx xxx xxx 無約束無約

23、束 321 321 321 321 321 , 0, 0 365 4 3 132 42min yyy yyy yyy yyy yyyW （1） （2） （3） 將X* =（0 . 0 . 4）代入原問題中，有下式： 4 4 1 246 3 2 20532 321 321 321 xxx xxx xxx 所以，根據(jù)互補(bǔ)松弛條件y1* xs1 = y2* xs2 = 0 ，必有 y1*= y2*=0， 代入對(duì)偶問題 （3）式， y3*=3。 因此，對(duì)偶問題的最優(yōu)解為 Y*=（0 . 0 . 3）， W=12。 性質(zhì)六 （62頁）原問題的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問題的一個(gè)基本解。 Max Z=CX AX+X

24、S=b; X 0 Min W=Yb YA -YS=C Y 0 A=(B,N)；C=（CB,CN）；Y(B,N)（CB,CN）；Y0 或YB-Ys1=CB； YN-Ys2=CN；Y0，Ys10，Ys20。 Ys1,Ys2分別對(duì)應(yīng)原問題基變量和非基變量的檢驗(yàn)數(shù)； 假設(shè)原問題找到了一個(gè)基本可行解（XB,0），對(duì)應(yīng)的檢驗(yàn)數(shù) （0，CN-CBB-1N，CI-CBB-1），分別令檢驗(yàn)數(shù)的相反數(shù)為： Ys1 =0 Ys2=-( CN-CBB-1N) Y=CBB-1 將其帶入約束條件式，滿足上式，則說明原問題的檢驗(yàn)數(shù)的相反數(shù)是其對(duì)偶問題 的一個(gè)解，得證。 設(shè)原問題為：Max Z=CX; AX+XS=b （ 0

25、 ）, X 0 , XS 0 ; 對(duì)偶問題為： Min W=Yb; YA YS=C; Y 0; YS 0 。 則原問題單純形表的檢驗(yàn)數(shù)行，對(duì)應(yīng)于其對(duì)偶問題的一個(gè)基解。 性質(zhì)6的意思究竟是什么？先列出原問題的單純形表： 表中給出了對(duì)偶問題的變量與原問題各檢驗(yàn)數(shù)的對(duì)應(yīng)關(guān)系。當(dāng)給出了原問題的一 個(gè)基后，算出各檢驗(yàn)數(shù)，反號(hào)之后，就得到對(duì)偶問題的一個(gè)基本解。 (X,Xs)中的： 基變量、非基變量 分別對(duì)應(yīng)于 (Ys,Y)中的： 非基變量、基變量。 性 質(zhì) 6 x1 x2 xn xs1 xs2 xsm a11 a12 a1n 1 0 0 a21 a22 a2n 0 1 0 am1 am2 amn 0 0

26、1 (-) 1 2 n n+1 n+2 n+m ys1 ys2 ysn y1 y2 ym Z= 7.5 Z= XB Xj -15/8-35/4Z=337.5 2/3-20/3Z=60 XB Xj Z=66 （診療問題）教材第37頁，試分別 對(duì)這三個(gè)表指出其對(duì)偶問題的解。 其他性質(zhì) 無界性 若原問題（對(duì)偶問題）為無界解，則其對(duì)偶問題（原問題） 為無可行解。 證明：若原問題為最大化問題，由題意 CX* +，所以若對(duì)偶問題（最小化） 有可行解 Y*，根據(jù)性質(zhì) 2 , C X* Y* b，于是 CX* 將有上界，與 CX* 無界矛盾。 證畢。 若原問題為最小化問題，由題意 Y*b -，所以若對(duì)偶問題（

27、最大化）有可行 解 X* ，根據(jù)性質(zhì) 2 , C X* Y* b，于是 Y*b 將有下界，與 Y*b 無界矛盾。 證畢。 注意：本性質(zhì)的逆不成立。當(dāng)原問題（對(duì)偶問題）無可行解時(shí)，其對(duì)偶問題 （原問題）可以沒有可行解（見下例）, 也可以是無界解，但決沒有最優(yōu)解。 綜上所述，互為對(duì)偶的線性規(guī)劃原問題與對(duì)偶 問題，它們之間解的對(duì)應(yīng)關(guān)系僅僅存在下面的 三種可能： 1.兩個(gè)問題都有可行解，則他們都存在最優(yōu)解， 且他們的最優(yōu)解的目標(biāo)函數(shù)值相等； 2.一個(gè)問題有無界可行解，而另一個(gè)問題無可 行解； 3.兩個(gè)問題均無可行解。 習(xí)題 判斷下列說法是否正確，為什么？ （1）如線性規(guī)劃的原問題存在可行解，則其對(duì)偶規(guī)

28、劃問題也一定存在可行解； （2）如線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解； 錯(cuò)；當(dāng)原問題有無界解時(shí)（此時(shí)當(dāng)然有可行解）， 其對(duì)偶問題無可行解。 （2）答： （1）答： 錯(cuò)；原問題可以有無界解時(shí)（此時(shí)當(dāng)然有可行解）， 也可以無可行解。 資源影子價(jià)格：對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、.、ym稱為 m種資源的影子價(jià)格（Shadow Price） 影子價(jià)格越大，說明這種資源越是相對(duì)緊缺； 影子價(jià)格越小，說明這種資源相對(duì)不緊缺； 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0 （互補(bǔ) 松弛定理）。 種資源的邊際利潤(rùn)第 種資源的增量第 最大利潤(rùn)的增量 i i

29、b z y i i mmii ybybybybwz 2211 mmiii ybybbybybzz)( 2211 ii ybz 資源效益分析和影子價(jià)格 原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤(rùn) max z=min w 種資源的邊際利潤(rùn)第 種資源的增量第 最大利潤(rùn)的增量 i ib z y i i 項(xiàng)目項(xiàng)目 放射科業(yè)務(wù)放射科業(yè)務(wù) X X線平片檢查線平片檢查CTCT檢查檢查磁共振檢查磁共振檢查 平均每人次檢查時(shí)平均每人次檢查時(shí) 間（小時(shí)間（小時(shí)/ /次）次） 0.10.10.250.250.50.5 每月機(jī)器實(shí)際可使每月機(jī)器實(shí)際可使 用時(shí)間（小時(shí)）用時(shí)間（小時(shí)） 300300120120120120 平

30、均每人次檢查利平均每人次檢查利 潤(rùn)（元潤(rùn)（元/ /次）次） 表3-13 放射科3項(xiàng)檢查資源需求、資源限制 及利潤(rùn) A醫(yī)院放射科目前可以開展X線平片檢查、CT檢查 和磁共振檢查業(yè)務(wù)，經(jīng)過資料收集和信息處理，A 醫(yī)院估計(jì)今后放射科如果開展此3項(xiàng)業(yè)務(wù)，在現(xiàn)有 放射科醫(yī)務(wù)人員力量和病人需求的情況下，每月此 3項(xiàng)業(yè)務(wù)的最多提供量為1800人次。平均每人次檢 查時(shí)間、每月機(jī)器實(shí)際可使用時(shí)間、平均每人次檢 查利潤(rùn)如表3-13 。 應(yīng)用實(shí)例（教材第75-79頁） XB Xj 模 型max Z = 20 x1 + 60 x2 +10 x3 x1 , x2 , x3 0 s.t. 0.1x1 300 0.25x2

31、 120 0.5x3120 x1 + x2+ x31800 每月業(yè)務(wù)量 X線：x1次； CT ：x2 次； 磁共振：x3次。 問題：（1） A醫(yī)院從放射 科收益的角度 考慮，如何開 展最優(yōu)業(yè)務(wù)量？ （2）在最優(yōu) 業(yè)務(wù)安排情況 下，A醫(yī)院如 何利用影子價(jià) 格進(jìn)行決策？ （1）該線性規(guī)劃模型的最優(yōu)解 X*=（1320,480,0,168,0,120,0）T，最優(yōu)值 Z*=55200。則A醫(yī)院從放射科收益的角度考慮，在每月X線平片檢查和CT檢查業(yè) 務(wù)量各為1320人次和480人次，且不開展磁共振檢查業(yè)務(wù)時(shí)，放射科利潤(rùn)最大， 達(dá)55200元。 （2）該對(duì)偶規(guī)劃的最優(yōu)解為Y*=(0,160,0,20)，

32、即對(duì)應(yīng)于原問題資源約束的影子 價(jià)格。 X線y1*=0，xs1=x4=168 CT檢查y2*=160，xs2=x5=0 磁共振機(jī)y3*=0 ，xs3=x6=120 放射科服務(wù)量y4*=20，xs4=x7=0。 )( o iii yyb 一、對(duì)偶單純形法的基本思想 設(shè)有標(biāo)準(zhǔn)型的線性規(guī)劃模型 Max Z=CX， AX =b; X 0 ， 上一章討論的單純形法基本思想是從某 一基本可行解出發(fā)，B-1b0, 在初始單純形表中，檢驗(yàn)數(shù)C- CBB-1A0 不一定成立，在保持B-1b0成立的條件下， 經(jīng)過逐步換基迭代，使檢驗(yàn)數(shù)C- CBB-1A0 成立，從而得到最優(yōu)解或判斷無最優(yōu)解。 如果求解線性規(guī)劃時(shí)，是

33、否可以這樣 來進(jìn)行，某個(gè)初始基本解使得檢驗(yàn)數(shù)C- CBB-1A0一定成立，B-1b0不成立，我們 能否對(duì)約束等式和目標(biāo)函數(shù)進(jìn)行適當(dāng)?shù)男谐?等變換使條件C- CBB-1A0始終成立，直至 B-1b0成立，從而求得最優(yōu)解或判斷無最優(yōu) 解。這就是對(duì)偶單純形法的基本思想。 對(duì)偶單純形法的基本思想：求解一 般的線性規(guī)劃問題時(shí)，由滿足C- CBB-1A0 的對(duì)偶可行解出發(fā)，逐次換基迭代，但始終 保持對(duì)偶可行性成立，也即C- CBB-1A0成 立，直至B-1b0成立，從而求得最優(yōu)解或判 斷無最優(yōu)解。 第三節(jié) 對(duì)偶單純形法 二、對(duì)偶單純形法求解線性規(guī)劃問題 的一般步驟和過程： 三、對(duì)偶單純形法求解線性規(guī)劃問題

34、的一般步驟和過程： 三 單純形法與對(duì)偶單純形法計(jì) 算步驟的對(duì)比 單純形法單純形法 （極大化）（極大化） 對(duì)偶單純形法對(duì)偶單純形法 （極大化）（極大化） 前提條件前提條件b列所有元素列所有元素bi0 所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù) cj-Zj0 最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) 所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù) cj-Zj0 b列所有元素列所有元素bi0 換入、換出換入、換出 變量的確定變量的確定 先確定換入變量先確定換入變量 再確定換出變量再確定換出變量 先確定換出變量先確定換出變量 再確定換入變量再確定換入變量 解的變化解的變化可行可行最優(yōu)最優(yōu)非可行非可行最優(yōu)最優(yōu) 四、表解形式對(duì)偶單純形法求解實(shí)例 初始可行基 （大M法） 將

35、約束條件等式的兩邊都乘以-1，得到 MaxZ = -1600 x1 - 2500 x2 -400 x3 s.t. - x1 - 5 x2 - x3+ x4 = -4 -2x1 - 2.5x2 +x5= -3 x1 , x2 , x3 , x4 , x5 0 ， 四、表解形式對(duì)偶單純形法求解實(shí)例 XB Xj 對(duì)偶問題的 初始可行基 建立此問題的初始單純形表如下： 800500400 XB Xj 400200 200400 XB Xj 原問題的最優(yōu)解為（1，0.4，0，0，0），最優(yōu)值為2600。對(duì)偶問題的最優(yōu)解 為（200，600，0，0，200），最優(yōu)值為2600。 最優(yōu)解 五、對(duì)偶單純形法的

36、優(yōu)缺點(diǎn)及用途 對(duì)偶單純形法的優(yōu)點(diǎn)： 1.初始解可以是非可行解，避免加入人工變量， 簡(jiǎn)化運(yùn)算； 2.對(duì)變量多于約束條件時(shí)的LP問題，直接用對(duì) 偶單純形法求解，對(duì)變量少于約束條件的LP問 題，可先將其轉(zhuǎn)化為對(duì)偶問題，再用對(duì)偶單純 形法運(yùn)算求解，可減少迭代次數(shù)，簡(jiǎn)化計(jì)算； 3.在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法 處理簡(jiǎn)化。 對(duì)偶單純形法缺點(diǎn)： 在初始單純形表中對(duì)偶問題是基可行解，這點(diǎn) 對(duì)多數(shù)線性規(guī)劃問題很難做到。 14/3 8/5 Y=（8/5 , 1/5），Ys = （0，0，9/5） X=（11/5 ， 2/5 ， 0，0，0）， Z =28/5 3 1 1 1 -1 0 1 1 0 1 2

37、 -1 = B-1= B-1 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 = B-1P3 1 -1 -2 0 1/2 1/2 0 -1/2 1/2 = 1 1/2 -3/2 10 15 5 已知線性規(guī)劃問題用單純形法計(jì)算時(shí)得到 的初始單純型表及最終單純型表如表318， 請(qǐng)將表中空白處數(shù)字填上。 0 1 0 0 10 15 1 1/2 00-3/20-3/2 015-3/2 -1/2 靈敏度分析的目的在于，當(dāng)求解 L.P.問題，且已獲最優(yōu)解之后，再假定原問題 中某參數(shù)如 bi 或 cj 或 aij 發(fā)生變化，或增加一個(gè)變量，或增加一個(gè)約束條件后， 于是得到一個(gè)新的L.P.問題，這樣

38、一個(gè)新的L.P.問題對(duì)原L.P.問題的最優(yōu)解和最優(yōu) 值產(chǎn)生什么樣的影響？ 希望從原來的最終單純形表出發(fā)，經(jīng)少量運(yùn)算而獲得新問題的最終（優(yōu)）單純 形表；或確定參數(shù)的變化范圍，使原L.P.問題的最優(yōu)解或最優(yōu)基變量不變。（既然 參數(shù)發(fā)生變化，或增加一個(gè)變量，或增加一個(gè)約束條件后，當(dāng)然可以重新從頭求 解） 靈 敏 度 分 析 第四節(jié) 線性規(guī)劃的靈敏度分析 0 b max X AX CXzj=cjCBB 1Pj j P b =B 1Pj =B 1b 第四節(jié) 靈 敏度分析 關(guān)于靈敏度分析，我們討論如下 五種情況： 1. 目標(biāo)函數(shù)系數(shù)cj的靈敏度分析； 2. 約束條件的常數(shù)項(xiàng)bi的靈敏度分析； 3.分析參數(shù)

39、aij的變化； 4.增加新變量xij的靈敏度分析； 5. 添加一個(gè)新的約束條件的靈敏度分析。 一、目標(biāo)函數(shù)中價(jià)值系數(shù)Cj發(fā)生變化的分析 （1）若cj不是基變量的系數(shù), 這種情形最為容易。由檢驗(yàn)數(shù)的計(jì)算公式： 由j = cj - CB B-1Pj知， 若cj 變?yōu)閏j +cj ，則j變?yōu)閏j+cj - CB B-1Pj 。 若cj +cj - CB B-1Pj 0(1 j n)， cj -j那么原最優(yōu)解不變； 否則須從原最終單純形表出發(fā)繼續(xù)迭代,至新的j 0。 （2）若cj是基變量 Xj的系數(shù),這種情形較為復(fù)雜。 因 cj CB（設(shè)cj為 CB 的第s個(gè)分量），故當(dāng)cj 變?yōu)閏j +cj時(shí), C

40、B將變?yōu)镃B +CB ， cj變化后最終單純形表中檢驗(yàn)數(shù)那一行將變?yōu)椋?C-（CB +CB）B-1A= C-CBB-1A -CB B-1A =（C-CBB-1A)-(0,0,cj,0,.,0)B-1A =（C-CB B-1A）- cj(as1,as2,.,asn). （cj變化前最終單純形表中的第S行） 即新的檢驗(yàn)數(shù)行等于原來檢驗(yàn)數(shù)行減去cj 乘原來最終單純形表的第S行（Xj的檢驗(yàn)數(shù) 除外，應(yīng)全為0）。 以下舉例說明。 第S個(gè) 問應(yīng)如何安排生產(chǎn)使制藥公司獲利最多？ 產(chǎn)品 原料 1.若第3種藥品的單位利潤(rùn)c3發(fā)生變化，那么c3 在什么范圍內(nèi)變化時(shí)，原問題的最優(yōu)解不變？ 2.基本變量x1的系數(shù)c1

41、=5有改變量，那么c1在 什么范圍內(nèi)變化時(shí)，原問題的最優(yōu)解不變？ 表3-9 初始單純形表和最終單純形表 解： CB cj5+c18600 b x1x2x3x4 x5 5+c1x11002-14 8x2011-118 Cj00-2-2-2-3+Z=84+4c1 XB Xj 表3-10 基本變量x1的系數(shù)c1=5改變c1對(duì)最 優(yōu)解影響 1.若非基變量c4有改變量c4，那么c4在何范圍內(nèi) 變化時(shí)，問題的最優(yōu)解不變？2.若基變量c2有改變量 c2，那么c2在何范圍內(nèi)變化時(shí)，問題的最優(yōu)解不 變？最優(yōu)值為多少？ 解： 二、右端項(xiàng) b 發(fā)生變化 b=第i個(gè)分量 靈 敏 度 分 析 第四節(jié) 靈敏度分析 假定

42、bi 發(fā)生變化，設(shè)分量bi 獲得增量 bi 而變?yōu)?bi+bi ,則 b 將獲得增量b,根 據(jù)單純形法矩陣表示式的討論，最優(yōu)解的基本變量 xB = B-1b， B-1b將獲得增量B- 1b 而變?yōu)锽-1b+ B-1b ，即基本變量保持不變，只有最優(yōu)值的變化；否則，需要 利用對(duì)偶單純形法繼續(xù)計(jì)算。 只要B-1b+ B-1b 0，則在原最終單純形表中只要用 B-1b+ B-1b 代替 B-1b 這 一列，就可獲得新最終單純形表。此處： 0 . . 0 bi 0 . . . 0 例10以例9為例： （1）若b1=12有改變，為使最優(yōu)基本變量x1、x2地位不變，求b1的變化范圍。 （2）若b1的變化超

43、出了所允許的范圍，如b1=9，試求取新的最優(yōu)解？ 由表 3-9 最后二列（因最終單純形表之最后二列x4,x5構(gòu)成單位矩陣）知 B-1= ，而b= 易見由 B-1b+ B-1b= + 知 -2 b1 8，當(dāng) b1 在此范圍內(nèi)變化時(shí)，只須修改表 3-9 的B-1b列即可獲得新問題 的最終單純形表！ 2 -1 -1 1 b1 0 4 8 0 0 4+2b1 8-b1 = 2 -1 -1 1 b1 0 XB Xj 若b1的變化超出了所允許的范圍，如b1=9， 最優(yōu)解的基本變量發(fā)生變化，此時(shí)檢 驗(yàn)數(shù)不變，需用對(duì)偶單純形法求出新的最優(yōu)解。 表3-11 b1改變量b1=9時(shí)對(duì)最優(yōu)解影響 2 -200-4Z=

44、100-5 三、技術(shù)系數(shù)aij的變化 XB Xj 00-2-2-3Z=84 Z=80 00 -10/3 0-11/3 0 2/3 -2/3 B-1b 習(xí)題二第5題：給出線性規(guī)劃問題及其最優(yōu)單 純型表如下： max z=6x1+2x2+12x3 s.t. 4x1+x2+3x324 2x1+6x2 +3x330 xj 0,j=1,2,3 （1）試求出最優(yōu)解不變的c3變化范圍； （2）試求出最優(yōu)基變量不變的b2變化范圍； （3）在原線性規(guī)劃的約束條件上，增加下 面的約束條件： x1+2x2+2x312，其最優(yōu)解 是否變化，如變化，試求出最優(yōu)解。 （2）B-1= ， 而b= 易見由 B-1b+ B-1

45、b = + = 知 6+b2 0，當(dāng) b2 -6， b224 時(shí)，只須修改表的B-1b列即可獲得新問題的最 終單純形表！ 1/3 0 -1 1 0 b2 8 6 8 6+b2 （1）若是最優(yōu)解不變，則必須滿足下式 6 -4c3/30 2 c3/ 30 - c3/ 30 （1） （2） （3） c39/2 c36 c30 c36 0 b2 解： 習(xí)題：對(duì)上述最大化的線性規(guī)劃問題，已知其初始和 最優(yōu)單純形表：（1）請(qǐng)?zhí)顚懽顑?yōu)表中空白處的數(shù)字； （2）寫出原線性規(guī)劃問題；（3）寫出其對(duì)偶規(guī)劃及其 最優(yōu)解；（4）當(dāng)b變?yōu)閎+b， b=1，-1，0T，問 在何范圍內(nèi)變化，原最優(yōu)性不變；（5）目標(biāo)函數(shù)x2

46、的 系數(shù)c2從-1變 為-2，原最優(yōu)性是否改變？求出c2=-2時(shí)最優(yōu)解的最 優(yōu)目標(biāo)函數(shù)值。 （1）、請(qǐng)?zhí)顚懽顑?yōu)表中空白處的數(shù)字； 0 1/2 00 1 0 0 0 0 1 0 0 -3/2 1 -3/2 -1/2 -3/2 1 (4)-5 30 (5)-2 c20b1=60,b2=10,b3=20 1. 解： 將y*1 =4/5, y*2 =3/5 代入對(duì)偶問題的約束條 件，得（2），（3）（4) 為嚴(yán)格不等式，所 以ys2 0 ， ys3 0 ， ys4 0 ；由互補(bǔ)松弛 性得 x*2 ys2 =x*3 ys3=x*4 y s4=0 所以 x*2=x*3=x*4=0 。又因?yàn)椋?y*1 0,

47、 y*2 0, 所以 x*s1= x*s2= 0,即原問題的兩個(gè)約束條件 為等式約束，故得方程組： x*1+3 x*5= 4 2x*1+x*5= 3 解之得 x*1= x*5=1；而W*=Z*=5。 故原問題 的最優(yōu)解為： X*=（1，0，0，0，1）T， W*=5。 其對(duì)偶問題為 Max Z=4 y1 +3 y2 y1 +2 y22 y1 - y2 3 2 y1 +3 y2 5 y1 + y22 3 y1 + y2 3 y1 , y2 0 Min W=2x1+3x2+5x3+2x4+3x5 s.t. x1+x2+2x3+x4+3x54 2 x1- x2+3 x3+ x4+ x53 xj 0,

48、 1 j 5 （1） （2） （3） （4） （5） 原（對(duì)偶）規(guī)劃對(duì)偶（原）規(guī)劃 目標(biāo)函數(shù)max z=目標(biāo)函數(shù)min f= 約束條件 有m個(gè)（i=1,.m)m個(gè) 0 0 自由 變量 變量 n個(gè) 0 0 自由 n個(gè) 約束條件 本章內(nèi)容小結(jié) 1、原對(duì)偶問題關(guān)系 對(duì)稱形式： 互為對(duì)偶 (LP) Max = T (DP) Min =T s.t. s.t. T 0 0 “Max - ” “Min- ” 2、 資源影子價(jià)格 對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解w1、w2、.、wm稱為m種 資源的影子價(jià)格（Shadow Price） 影子價(jià)格越大，說明這種資源越是相對(duì)緊缺 影子價(jià)格越小，說明這種資源相對(duì)不緊缺 如果最優(yōu)生產(chǎn)計(jì)劃下某種資