運籌學：教案7_靈敏度（改）

1、5 5 對偶問題的經濟解釋對偶問題的經濟解釋 影子價格影子價格 (P)的最終單純形表中松弛變量的檢驗數對應的最終單純形表中松弛變量的檢驗數對應(D)的最優(yōu)解。的最優(yōu)解。 當某約束條件的右端常數增加一個單位時當某約束條件的右端常數增加一個單位時（假設原問題的最優(yōu)基不變），原問題的目標函數（假設原問題的最優(yōu)基不變），原問題的目標函數最優(yōu)值增加的數量。最優(yōu)值增加的數量。Z*=CX*=Y*b =(y1*,y2*, ,ym*)b1b2bm=y1*b1+y2*b2+ym*bm當某個右端常數當某個右端常數bi bi+1時時bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第第I種資源的影子價種

2、資源的影子價格是第格是第i個約束條件個約束條件的右端常數增加一的右端常數增加一個單位時，目標函個單位時，目標函數增加的數量數增加的數量 甲甲 乙乙可用量可用量機械設備機械設備 1 28原材料原材料A 4 016原材料原材料B 0 412 X X(3)(3)=(4=(4，2 2，0 0，0, 4)0, 4)T T， z z3 3 =14=14cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-2-3/2-1/81/8010-1400-3/2 -1/800125051321 *,.,.yyy經濟意義：經濟意義：在其它條件在其它條件不變的情況不變的情況下，下，單位資源

3、變單位資源變化所引起的化所引起的目標函數的目標函數的最優(yōu)值的變最優(yōu)值的變化?；?。影子價格影子價格 產品產品資源資源 現有資源數現有資源數鋼材鋼材1 2100（噸）（噸）煤煤2 2180（噸）（噸）機時機時1 6240（小時）（小時）利潤（萬元）利潤（萬元）1 30,24061802210023max2121212121xxxxxxxxxxZx1x2x3x4x5 -zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T, Z*=135y1*=3/4y2*=0,y3*=1/4影子價格影子價格經濟意

4、義：經濟意義：在其它條件不變的情況下，在其它條件不變的情況下，單位資源變化所引起的目標函數的最優(yōu)值的變化。單位資源變化所引起的目標函數的最優(yōu)值的變化。影子價格的意義 (1)影子價格客觀地反映資源在系統(tǒng)內的稀缺程度。 如果某一資源在系統(tǒng)內供大于求（即有剩余），其影子價格就為零。如果某一資源是稀缺的（即相應約束條件的剩余變量為零）,則其影子價格必然大零。影子價格越高，資源在系統(tǒng)中越稀缺。 (2)影子價格是對系統(tǒng)資源的一種優(yōu)化估價，只有當系統(tǒng)達到最優(yōu)時才能賦予該資源這種價值，因此也稱最優(yōu)價格。 (3)影子價格的取值與系統(tǒng)狀態(tài)有關。系統(tǒng)內部資源數量、技術系數和價格的任何變化，都會引起影子價格的變化，它

5、是一種動態(tài)價格。 (4)如果考慮擴大生產能力，應該從影子價格高的設備入手。6 對偶單純形法對偶單純形法保持對偶可行性，保持對偶可行性，逐步改進主可行性逐步改進主可行性，求解主問題。，求解主問題。 當當b有負分量，有負分量，A中有一明顯初始對偶可行中有一明顯初始對偶可行基基(檢驗數均非正檢驗數均非正)，因而易得一初始解時，可用，因而易得一初始解時，可用對偶單純形法求解。對偶單純形法求解。 0 XbAXCXZmax設設B為一個基為一個基 010bBX)(基本解基本解X（0）為基本可行為基本可行解的條件？解的條件？B-1b0X（0）為最優(yōu)解的為最優(yōu)解的條件？條件？01 ABCCB原原原始可行性條件原

6、始可行性條件原始最優(yōu)性條件原始最優(yōu)性條件令令Y=CBB-1，代入原始最優(yōu)性條件，代入原始最優(yōu)性條件，YAC無符號限制無符號限制YCYAYbW min對偶可行性條件對偶可行性條件計算步驟：計算步驟： 10 求初始基解，其檢驗數均非正。求初始基解，其檢驗數均非正。 20 計算計算liibbmin ，若，若 bl 0，則已得到最優(yōu)解，結束；，則已得到最優(yōu)解，結束；否則第否則第 l 行的基變量為換出變量。行的基變量為換出變量。 30 若若 alj 0 （ j） ，則無可行解，結束；否則計算） ，則無可行解，結束；否則計算 lkkljljjjaaamin 0 ，xk 為換入變量為換入變量 40 以以 a

7、lk 為主元素作旋轉運算，為主元素作旋轉運算， xk 取代原第取代原第 l 行基變行基變量，返回量，返回 20。 例例 用對偶單純形法求解用對偶單純形法求解 43210242323443214321421,max jxxxxxxxxxxxxZj單純形法單純形法大大M 法法 621024232346432154321421,max jxxxxxxxxxxxxxxZj剩余變量、剩余變量、人工變量人工變量 用（用（-1）乘不等式兩邊，再引入松弛變量。）乘不等式兩邊，再引入松弛變量。cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x600 x5x6-3-2 -1 -2 1

8、- 1 1 0 2 1 -4 -1 0 10 -1 -4 0 -3 0 0先選出基變量先選出基變量后選進基變量后選進基變量原問題，原問題，符合原始符合原始最優(yōu)性條最優(yōu)性條件，但不件，但不可行可行1132411 ,mincj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2

9、 -1 0-10 x1x374 1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 0 -1/2 0 -1/2 -2 -1/2最優(yōu)解最優(yōu)解X*=（7，0，4，0）TZ*=-7解解： 先先將將這這問問題題化化成成下下列列形形式式， 以以便便得得到到對對偶偶問問題題的的初初始始可可行行基基 （P）5210 4 3 2 3 2 43253214321321,j ,xxxxxxxxxxxxzmaxj 例例6 用對偶單純形法求解用對偶單純形法求解0,43232432min321321321321xxxxxxxxxxxxw（P）單單純純形形表表：1 - 4/3 - -1 0

10、 -5/2 1/2 1 -1/2-1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1 0 -4 -1 0 -1- 8/5 - - 22/5 0 1 -1/5 -2/5 1/5 2/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/511/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5 0 0 -3/5 -8/5 -1/5cj - -2 - -3 3 - -4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 - -3

11、 3 - -4 4 - -1 - -2 2 - -2 2 1 - -1 1 - -3 3 1 0 0 0 1 cj- -zj - -2 2 - -3 3 - -4 4 0 0 0 0 - -2 2 x4 x1 cj- -zj - -3 - -2 2 x2 x1 cj- -zj T),/,/(X00052511 對偶單純形法的一個應用：對偶單純形法的一個應用： 增加一個約束條件的分析增加一個約束條件的分析 。 1 檢查原最優(yōu)解是否滿足新的約束條件 滿足，則原最優(yōu)解仍為最優(yōu)解，否則，2。2 將約束方程帶到最優(yōu)單純形表中。max z =x +45x +24x 4040123s.t. 0,120233

12、10032 321321321xxxxxxxxx例新增加一個條件 151x7 靈敏度分析靈敏度分析 系數系數bi、cj 、aij 變化，最優(yōu)解的最變化，最優(yōu)解的最優(yōu)性、可行性是否變化？優(yōu)性、可行性是否變化？ 系數在什么范圍內變化，最優(yōu)解系數在什么范圍內變化，最優(yōu)解或最優(yōu)性不變？或最優(yōu)性不變？ 如何求新的最優(yōu)解？如何求新的最優(yōu)解？本本節(jié)節(jié)重重點點7.1 靈敏度分析的原理靈敏度分析的原理SNBXXXX是最優(yōu)解，則是最優(yōu)解，則000111BCNBCCbBBBN可行性條件可行性條件最優(yōu)性條件最優(yōu)性條件正則性 bi非基變量非基變量cj基變量基變量cB增加新變量增加新變量一個非基變量一個非基變量 系數系數

13、aij的變化，要視的變化，要視aij對應的變量是基變量對應的變量是基變量或非基變量而定?；蚍腔兞慷āB=B-1(b+b)，其中b=(0, br ,0,0)T只要XB0，最終表中檢驗數不變（b變化，不影響檢驗數），則最優(yōu)性不變，但最優(yōu)解的值發(fā)生變化, XB成為新的最優(yōu)解.B-1(b+b)= B-1b+ B-1b0新的最優(yōu)解允許范圍是:當某一個資源系數br 發(fā)生變化，亦即br= br +br ，其他系數不變，這樣最終的單純形表中原問題的解相應地變化為1、資源系數資源系數br的靈敏度變化分析的靈敏度變化分析mrirrrrmrrirrrraaabbabababB11100B-1的第r列進一步得，

14、最終表中 b 列元素bbairir B-1b, 0babririi=1，2，mi=1，2，miririrabba;/0iririrabba/0 x1, x5, x2是基變量，從而可得基B1210010160100480012154321bxxxxx例：求第一章例題中當第二個約束條件b2變化范圍b2。得到公式: 0min0maxiriririririaabbaabcj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-0-21/21/41/2-1/8010-1400-3/2 -1/80可得b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16

15、由公式知b2變化范圍-8,16, 顯然b2變化范圍8,32000125. 05 . 025. 0244002211bbBbB 例題: 將上面例題進行實際應用。每臺設備臺時的影子價格為1.5元。若該廠又從別處抽出4臺時用于生產兩種產品，求這時該廠生產兩種產品的最優(yōu)方案。B=（x1 x5 x2)410004201B2800040125.05 .015 .02025.001bB將這個結果放到最終表中得解：先計算B-1b 2 3 0 0 0 cj203x1x2x54+04-82+2CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 -2 0.5 10 1 0.5 -0.125 0c

16、j-zj 0 0 -1.5 -0.125 0 表中b列中有負數，即解答列有負數，故可用對偶單純形法求最優(yōu)解。 最優(yōu)解見下表 最優(yōu)生產方案應改為第一種產品4件，第二種產品3件，獲利z=17元。 2 3 0 0 0 cj203x1x2x3423CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 1 -0.25 -050 1 0 0 0.25cj-zj 0 0 0 -0.5 -0.75（1）當cj是非基底變量xj的系數，檢驗數為mijijjjjBjjyacPBCc11或當cj變化cj后，檢驗數應要小于或等于零，即jjjjjjjjjBjjjccYPcYPccPBCcc012、目標函

17、數中價值系數、目標函數中價值系數C的變化的變化（2）當cr是基底變量xr的系數，即crCB，cr變化cr后，有aaaCAC B BABCABCrnrrrrB),()0 , 0(21111最優(yōu)解不變0j為非基變量jacaacarjjrrjrjjrrj, 0;, 0njacA)jcrjrjj, 2 , 1,(CBB1cr的變化范圍0min0maxrjrjjjrrjrjjjaacaa 例8： 仍以第一章例1的最終表為例。設基變量x2的系數c2變化c2，在原最優(yōu)解不變的條件下，確定c2的變化范圍。 解：這時最終計算表為cj2 3 000CBXBbx1x2x3x4x5203x1x5x2442100001

18、0-20.50.250.5-0.125010cj-zj00-1.5-0.1250 可見c2-1.5/0.5; c2-0.125/(-0.125) 故c2的變化范圍: -3c21即x2的價值系數c2可在0,4之間變化，不影響原最優(yōu)解。02,1502121202314xxxxxx230150 xxzMaxcj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj00-5-15已知線性規(guī)劃問題最優(yōu)單純形表練習1025. 13) 6 (2 0) 0.125 5 . 1 (5PBCcT31B33 3 aij的變化分析的變化分析(1). aij 為非基變

19、量的系數為非基變量的系數只影響只影響xj的檢驗數，從而影響最優(yōu)性。的檢驗數，從而影響最優(yōu)性。 例例: 第一章例第一章例1，增加一種新產品，增加一種新產品，它的技術系，它的技術系數是數是(2，6，3)T，利潤系數是，利潤系數是5。問該廠是否應生產問該廠是否應生產該產品和生產多少？該產品和生產多少？ 解：設新產品解：設新產品的產量為的產量為x3 (對于原最優(yōu)解來說是對于原最優(yōu)解來說是非基變量非基變量)。因。因 故應生產產品故應生產產品。 x3進基進基25.02 5.1 3620 0.125 0.51 0.5 20 0.25 0 31PB cj 2 3 0 0 0 5 CB XB b x1 x2 x

20、3 x4 x5 x3 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 0 - -2 0.5 1/4 1/2 -1/8 0 1 0 1.5 2 0.25 cj- -zj 0 0 - -1.5 - -1/8 0 1.25 在最終表中的系數是：在最終表中的系數是： 原最終表成為：原最終表成為： 3xcj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x3 2 0 3 x1 3x x2 1 2 1.5 1 0 0 0 0 1 1.5 - -1 0.75 - -0.125 0.25 - -0.1875 - -0.75 0.5 - -0.125 0 1 0 cj-

21、 -zj 0 0 - -0.25 - -0.4375 - -0.625 0 用單純形法求解得：用單純形法求解得： 3x5 .16*z, 2*3x, 5 . 1*2x, 1*1x 0.3752) 5 0)(2 0.125 514T111 .(PBCcB 375050 251 2520 0.125 0.51 0.5 20 0.25 011. -PB (2). aij為基變量系數為基變量系數基變化基變化，影響最優(yōu)性、可行性。，影響最優(yōu)性、可行性。 例例: 第一章例第一章例1，若生產產品，若生產產品的工藝結構有的工藝結構有改進，其技術系數變?yōu)楦倪M，其技術系數變?yōu)椋?， 5 ，2)T，利潤系數，利潤系數

22、為為4，試分析對生產計劃有什么影響？，試分析對生產計劃有什么影響？ 解：解： 設產品設產品產量為產量為x1(產品產品產量在原最優(yōu)解產量在原最優(yōu)解中是基變量中是基變量)。計算。計算 CB XB b x1 x2 x3 x4 x5 4 0 3 x1 x5 x2 4 4 2 1.25 0.5 0.375 0 0 1 0 - -2 0.5 0.25 0.5 0.125 0 1 0 cj- -zj 0.375 0 - -1.5 - -0.125 0 CB XB b x1 x2 x3 x4 x5 4 0 3 1x x5 x2 3.2 2.4 0.8 1 0 0 0 0 1 0 - -2 0.5 0.2 0.

23、4 - -0.2 0 1 0 cj- -zj 0 0 - -1.5 - -0.2 0 得到231.x* ，802.x* ， 215.z* 將和所求系數填入原最終表的將和所求系數填入原最終表的x1列位置，得列位置，得 1x1x將將x1的系數列向量變換為單位向量的系數列向量變換為單位向量 上表中假如對偶可行，主不可行，則用對上表中假如對偶可行，主不可行，則用對偶單純形法求新解；假如主對偶均不可行，要加偶單純形法求新解；假如主對偶均不可行，要加入人工變量，用單純形法繼續(xù)解。入人工變量，用單純形法繼續(xù)解。注意：注意：例例11 假設例假設例10的產品的產品的技術系數向量為的技術系數向量為 p1=（4，5

24、，2），而每件獲利仍為），而每件獲利仍為4元。試該廠應如何安元。試該廠應如何安排最優(yōu)生產方案？排最優(yōu)生產方案？練習2 在練習1中，如果新增加產品，其目標系數為100，消耗系數為（9，3.5） 是否應該生產該產品cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj00-5-15最優(yōu)單純形表4433251 xxxxzMax04,3,2,11000433524131200443324158004232312xxxxxxxxxxxxxxxx(1)求線性規(guī)劃問題的最優(yōu)解；(2)求對偶問題的最優(yōu)解； (3)當b3= -150時最優(yōu)基是否發(fā)生變化？為什么？ (4)求C2的靈敏度范圍; (5)如果x3的系數由1，3，5變?yōu)?，3，2最優(yōu)基是否改變？若改變求新的最優(yōu)解 ;(6)假定新增決策變量x8，且