第六章 單形法敏感度分析及對偶特性

1、第六章 單形法敏感度分析及對偶特性本章內(nèi)容：6.1 以單形表做敏感度分析6.2 對偶特性n 6.1 以單形表做敏感度分析l 目標(biāo)函數(shù)係數(shù)l 目標(biāo)函數(shù)與最適區(qū)間之意義：1.若目標(biāo)函數(shù)之係數(shù)範(fàn)圍能使目前的最適解仍維持最適，則此範(fàn)圍稱為目標(biāo)函數(shù)之最適區(qū)間。2.最適區(qū)間可能使目標(biāo)函數(shù)值改變。3.目標(biāo)函數(shù)係數(shù)的最適區(qū)間，由CjZj0淨(jìng)評估值而定。（1）目標(biāo)函數(shù)基本變數(shù)之敏感度分析（只改變一個基本變數(shù)係數(shù)）。例：Max 50X140X2 s.t. 3X15X12150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20其中 X1D型產(chǎn)品件數(shù) X2P型產(chǎn)品件數(shù)最後單形表如下：X

2、1X2S1S2S3基底CB5040000X2S2X1400500011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50026/5-26/51980解：X130，X212，S10，S28，S30，Z1980。X1，X2，S2為基本變數(shù)，S1，S3為非基本變數(shù)。計算目標(biāo)函數(shù)X1基本變數(shù)之係數(shù)C1之最適區(qū)間，須先將最後單形表修改如下：X1X2S1S2S3基底CBC140000X2S2X1400C10011008/25-8/25-5/25010-3/253/255/2512830ZjCjZjC10400(64-C1)/5(C1-64

3、)/500(C1-24)/5(24-C1)/5480+30C1最適區(qū)間應(yīng)使CjZj0即需(C1-64/50)及(24-C1/50)所以的最適區(qū)間為24C164。註：基本變數(shù)（X1，X2，S2）之最適區(qū)間係計算非基本變數(shù)（S1，S3）之CjZj，使其0。驗証：型產(chǎn)品利潤由原來50元減少為30元之最適解為何？若將C1改為30元之最後單形表如下：X1X2S1S2S3基底CB3040000X2S2X1400300011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj30040034/5-34/5006/5-6/51380解：X130，X212，S10，S28，S3

4、0，Z1380。結(jié)論：最適解不變，但總利潤解降為1380元。 （30X140X2303040121380）驗証：型產(chǎn)品利潤由原來50元減少為20元之最適解為何？若將C1改為20元，最後單形表如下：X1X2S1S2S3基底CB2040000X2S2X1400200011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj20040044/5-44/5004/54/51080解：X130，X212，S10，S28，S30，Z1080。但因S3之CjZj4/50，因此需繼續(xù)計算單形表，引進(jìn)S3後之最適解為X116.6件，X220件，已改變原最適解。（2）目標(biāo)函數(shù)非基

5、本變數(shù)之敏感度分析（只改變一個非基本變數(shù)係數(shù)）。例：Max 50X140X2 s.t. 3X15X2150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20其中 X1D型產(chǎn)品件數(shù) X2P型產(chǎn)品件數(shù)最後單形表如下：X1X2S1S2S3基底CB5040000X2S2X1400500011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50026/5-26/51980解：X130，X212，S10，S28，S30，Z1980。X1，X2，S2為基本變數(shù)，S1，S3為非基本變數(shù)。 指dual price計

6、算目標(biāo)函數(shù)S1非基本變數(shù)之係數(shù)CS1之最適區(qū)間需先將最後單形表修改如下：X1X2S1S2S3基底CB5040CS100X2S2X1400500011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj50040014/5CS1-(14/5)0026/5-26/51980最適區(qū)間應(yīng)使CjZj0，因此需CS1-(14/5)0，所以CS1的最適區(qū)間為CS114/5。註：在一個極大化的問題，非基本變數(shù)沒有下限上限就是 Zj，因此任何非基本變數(shù)目標(biāo)函數(shù)係數(shù)之最適區(qū)間是Cj Zj。註：第一部資源S10表示資源150全使用完，上限為14/5， 表示第一部資源增加單位，則目標(biāo)

7、函數(shù)增加14/5，而為 1980(14/5) dual price14/5l 計算最適區(qū)間的步驟：1.將在最後單形表中，Xk所有的目標(biāo)函數(shù)係數(shù)從數(shù)字改成Ck。2.重新計算每個非基本變數(shù)之CjZj (如果Xk是非基本變數(shù)只須計算CjZj)。3.在CjZj0的條件下，解每個不等式找出Ck的任何上界或下界。如果Ck有兩個或多個上界，其小者就是最適區(qū)間的上限。如果有兩個以上的下界，其大者就是最適區(qū)間的下限。4.如果原來問題是極小化問題應(yīng)將其轉(zhuǎn)變成極大化問題，以便用單形法求解。將第3步的不等式乘以1，並改變不等號的方向，以找出原來求極小化問題的最適區(qū)間。l 右手邊值：在許多線性規(guī)劃問題中，我們將”右手邊

8、值”解釋為”可用的資源”，例如”可用的裝配時間”、”可用的倉儲空間”等。l 對偶價格(dual price)多稱影子價格(shadow price)：每增加限制式右手邊（資源）一單位對最適解值之改善。l RHS的範(fàn)圍即在求影子價格維持不變。例：（極大化問題）Max 50X140X2 s.t. 3X15X2150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20最後單形表如下：X1X2S1S2S3基底CB5040000X2S2X1400500011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50

9、026/5-26/51980l S1之Zj值為14/5，即裝配時間限制的對偶價格為14/5。只要目標(biāo)函數(shù)S1之最適範(fàn)圍為CS114/52.8元，則目前最適解仍為最適解。由於S10（非基本變數(shù)）表示己用完裝配時間，因此Zj2.8相當(dāng)於S1這個惰變數(shù)所列的資源(即每一條限制式)每增加一單位的價值（邊際值）。因此如果可以獲得額外的時間海德公司最多願意出每小時2.8元的價格。註：S1=0 dual price=14/5 資源全使用完，銷路不錯，消 費者願意購買工廠生產(chǎn)量可再增加，但第一部資源 RHS全用完，工廠需向外僱用工人，工廠願付小於2.8元 僱用，MR-MC僱用-工人願付2.8工資l S2之Zj

10、值為0，表示顯示器限制的對偶價格為零。S28（基本變數(shù)）表示尚有8個顯示器未使用，此額外多的資源對公司沒什麼價值，所以該限制式的對偶為零。(重點：在最適解中，如果惰變數(shù)是基本變數(shù)，則這個限制式對偶價格（Zj）為零)。註：S2 slack=8 dual price=0,S2是否需額外增加? 不需增加 因為S2有剩餘l S3之Zj值為26/5，即倉儲限制的對偶價格為26/5。 如果限制式為，dual price為“-z”，RHS值更滿足此限制式，dual price代表預(yù)期改變 的程度，如果dual price為負(fù)值，表示Z最大化問題 中，如果限制式為 dual price=-Z 表6.1 各種限

11、制條件的對偶價格在表內(nèi)位置限制式形式對偶價格 此限制式的惰變數(shù)的Zj值 此限制式剩餘變數(shù)Zj值的負(fù)值 此限制式人工變數(shù)的Zj值例：（極小化問題）Min 2X13X2 s.t. 1X1125 產(chǎn)量A需求量 1X11X2350 總產(chǎn)量 2X11X2600 生產(chǎn)時間 X1，X20其中 X1產(chǎn)品1產(chǎn)量 X2產(chǎn)品2產(chǎn)量求極小化問題，我們將目標(biāo)函數(shù)乘以（-1）變成極大化問題，上例之最後單形表以極大化問題求得下表：X1X2S1S2S3基底CB-2-3000x1x2S1-2-M01O00100011-211-11250100125ZjCjZj-20-30004-41-1-800表6.2 MD化學(xué)公司問題對偶價

12、格限制條件產(chǎn)品1需求量總生產(chǎn)量生產(chǎn)時間條件式形式對偶價格 0-4 1l RHS值與可行區(qū)間1.右手邊係數(shù)的可行性範(fàn)圍為其係數(shù)的範(fàn)圍能使影子價格維持不變。2.可行性範(fàn)圍也是目前基本變數(shù)組合仍然能維持最適組合的範(fàn)圍(雖然其值已改變)。例：（極大化問題）Max 50X140X2 s.t. 3X15X2150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20其中 X1D型產(chǎn)品件數(shù) X2P型產(chǎn)品件數(shù)若裝配可用時間（b1）改變，試問目前的基本變數(shù)是否仍合理?最後單形表如下：（舊解）X1X2S1S2S3基底CB5040000X2S2X1400500011008/25-8/25

13、-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50026/5-26/51980解：X130，X212，S10，S28，S30，Z1980（基本變數(shù)X1，X2，S2）。若b1由原來150小時增加為160小時，其最後單形表如下：（新解）X1X2S1S2S3基底CB5040000X2S2X1400500011008/25-8/25-5/25010-3/253/255/2515.24.828.0ZjCjZj50040014/5-14/50026/5-26/52008.0解：X128，X215.2，S10，S24.8，S30，Z2008（基本變數(shù)X1，X2，

14、S2）。注意：新解與舊解之基本變數(shù)不變，且合理（因X1，X2，S20）。由原來1980元增至2008元，增加28元，此種改變可從原最後單形表求得，因最後單形表僅改變(與b1150的最後單形表比較)基本變數(shù)值及目標(biāo)函數(shù)值，亦即只改變單形表的最後一行。在單形表的新最後一行，只要加上10乘在S1行的四個元素到以前表的最後一行即可。 舊解 b1改變量 S1行 新解 12 8/25 15.2新解 8 10 -8/25 4.8 30 -5/25 28.0 1980 14/5 2008S1行之每一係數(shù)為每當(dāng)增加一單位的S1，使各基本變數(shù)減少的量，換句話說，變數(shù)S1帶進(jìn)解中一單位，則目前每個基本變數(shù)要自解中帶

15、走之單位數(shù)；即S1的變動對X2的影響(即S1與X2的替代關(guān)係)。反之亦然。因此在S1行的元素可以解釋為每增加一單位b1目前基本解的改變量。上述新解為可用裝配時間增加10單位，而得到的基本變數(shù)及目標(biāo)函數(shù)值的改變量。將上述新解以下式表示，即可求得b1之合理範(fàn)圍： x2 12 8/25 128/25b1 s2 8 b1 -8/25 88/25b1 (6.6) x1 30 -5/25 305/25b1為保持基本變數(shù)仍為合理且最適，因此b1的改變，需滿足以下條件：128/25b10 (6.7) 88/25b10 (6.8)305/25b10 (6.9)得-37.5b125原裝配時間為150小時，b115

16、0b1之合理範(fàn)圍為112.5b1175只要可用時間在112.5及175小時之間，目前最適解仍然合理且原基本變數(shù)仍為基本變數(shù)，但基本變數(shù)之值會改變。驗証：若b1由150小時增至175小時，試問b1變動前的基本變數(shù)是否仍為變動後的基本變數(shù)嗎?其值是否改變?對目標(biāo)函數(shù)值會有什麼影響?解：1.b1由150小時增至175小時，共增加25小時，基本變數(shù)變成： X21225（8/25）20 S2825（-8/25）0 X13025（-5/25）25基本變數(shù)不變，但X1由30單位減至25單位，由X2由12單位增至20單位，不改變基本變數(shù)，但會改變基本變數(shù)值。2.利潤增加至1980（14/5）（25）2050元

17、，利潤增加（14/5）（25）70元。引申得知：1.若限制式為“”，其合理範(fàn)圍以下式求得： b1 a1j 0 b2 a2j 0最後單形表中對應(yīng)限制式i惰變數(shù)的行 . b1 . . （6.12）目前解（最後單形表的最後一行） . . . . . . bm amj 02.限制式為“”，其合理範(fàn)圍以下式求得： b1 a1j 0 b2 a2j 0最後單形表中對應(yīng)限制式i剩餘變數(shù)的行 . b1 . . （6.13）目前解（最後單形表的最後一行） . . . . . . bm amj 0l 多項同時改變：方法與第三章之“百分之百規(guī)則”同。n 6.2 對偶特性l 正規(guī)型（canonical form）：一個

18、極大（?。┗瘑栴}，所有限制條件均為“”（“”）及各變數(shù)均為非負(fù)，稱為正規(guī)型。l 原題與偶題之關(guān)係（以下以海德公司為例）：例：（原題：極大化問題的正規(guī)型)Max 50X140X2 s.t. 3X15X2150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20（偶題：極小化問題的正規(guī)型）Min 150u120u2300u3 s.t. 3u10u28u350 5u11u25u340 u1，u2，u30 u1，u2，u3稱為對偶變數(shù)(dual variables)極小化問題所有限制式均為“”及“非負(fù)值”。因此正規(guī)型的極大化問題的偶題是正規(guī)型的極小化型。l 極大化正規(guī)型問

19、題轉(zhuǎn)變?yōu)榕碱}之規(guī)定：1.偶題是極小化正規(guī)型問題。2.當(dāng)原題有n個決策變數(shù)（n=2在海德例題），偶題就有個限制式。偶題的第一個限制式是與原題的X1變數(shù)相配合，偶題的第二個限制式與原題的X2變數(shù)相配合。3.當(dāng)原題有m個限制式（海德問題m3），偶題就有m個變數(shù)，偶題變數(shù)u1與原題的第一個限制式相配合，偶題變數(shù)u2與原題的第二個限制式相配合。4.原題的右邊值變成偶題的目標(biāo)函數(shù)係數(shù)。5.原題的目標(biāo)函數(shù)係數(shù)變成偶題的限制式右邊值。6.在原題限制式中第個變數(shù)的係數(shù)，變成偶題中第個限制式的係數(shù)。海德公司偶題之單形表如下（以偶題表格型解之）：u1u2u3S1S2a1a2基底CB-150-20-30000-M-M

20、a1a2-M-M350185-100-110015040ZjCjZj-8M-150+8M-M-20+M-13M-300+13MM-MM-M-M0-M0-90Mu1u2u3S1S2基底CB-150-20-30000u3u1-300-15001-3/258/2510-5/255/253/25-8/2526/514/5ZjCjZj-1500-12-8-300030-3012-12-1980解：u114/5，u20，u326/5，S10，S20，Z1980（因其為使負(fù)偶題目標(biāo)函數(shù)的負(fù)值極大化，因此偶題目標(biāo)函數(shù)值應(yīng)為(1980）1980）。海德公司原題之最後單形表如下：X1X2S1S2S3基底CB504

21、0000X2S2X1400500011008/25-8/25-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50026/5-26/51980解：X130，X212，S10，S28，S30，Z1980。原題與偶題之關(guān)係為何?二者之目標(biāo)函數(shù)值相同。l 特性1：若偶題有最適解，原題亦有最適解，反之亦如此，且原題與偶題之目標(biāo)值相等。特性1告訴我們，只解偶題亦能得知原題目標(biāo)函數(shù)值。l 對偶變數(shù)之經(jīng)濟涵義：原始目標(biāo)函數(shù)值的結(jié)果為：50X140X21980(D型單價)(D型產(chǎn)量)(P型單價)(P型產(chǎn)量)生產(chǎn)總值對偶目標(biāo)函數(shù)為：150u120u2300u31980(資源1數(shù)量)u1+(資源2數(shù)量)u2+(資源3數(shù)量)u3=生產(chǎn)總值u1每小時裝配工時的價值=(產(chǎn)出-投入)=MR-MCu2每件P型顯示器的價值=每小時資源價值u3每平方呎倉儲空間的價值對偶價格：RHS每增加1單位的價值。在本章“對偶價格說明”中，已求得對偶價格，如下所示：資源裝配時間P型顯示器倉儲空間每額外單位價值(對偶價格)$