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

1、第六章 單形法敏感度分析及對(duì)偶特性本章內(nèi)容：6.1 以單形表做敏感度分析6.2 對(duì)偶特性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)評(píng)估值而定。（1）目標(biāo)函數(shù)基本變數(shù)之敏感度分析（只改變一個(gè)基本變數(shù)係數(shù)）。例：Max 50X140X2 s.t. 3X15X12150 裝配可用工時(shí) 1X220 P型顯示器 8X15X2300 倉儲(chǔ)空間 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ù)。計(jì)算目標(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ū)間係計(jì)算非基本變數(shù)（S1，S3）之CjZj，使其0。驗(yàn)証：型產(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）驗(yàn)証：型產(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ì)算單形表，引進(jìn)S3後之最適解為X116.6件，X220件，已改變原最適解。（2）目標(biāo)函數(shù)非基

5、本變數(shù)之敏感度分析（只改變一個(gè)非基本變數(shù)係數(shù)）。例：Max 50X140X2 s.t. 3X15X2150 裝配可用工時(shí) 1X220 P型顯示器 8X15X2300 倉儲(chǔ)空間 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計(jì)

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

8、值”解釋為”可用的資源”，例如”可用的裝配時(shí)間”、”可用的倉儲(chǔ)空間”等。l 對(duì)偶價(jià)格(dual price)多稱影子價(jià)格(shadow price)：每增加限制式右手邊（資源）一單位對(duì)最適解值之改善。l RHS的範(fàn)圍即在求影子價(jià)格維持不變。例：（極大化問題）Max 50X140X2 s.t. 3X15X2150 裝配可用工時(shí) 1X220 P型顯示器 8X15X2300 倉儲(chǔ)空間 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，即裝配時(shí)間限制的對(duì)偶價(jià)格為14/5。只要目標(biāo)函數(shù)S1之最適範(fàn)圍為CS114/52.8元，則目前最適解仍為最適解。由於S10（非基本變數(shù)）表示己用完裝配時(shí)間，因此Zj2.8相當(dāng)於S1這個(gè)惰變數(shù)所列的資源(即每一條限制式)每增加一單位的價(jià)值（邊際值）。因此如果可以獲得額外的時(shí)間海德公司最多願(yuàn)意出每小時(shí)2.8元的價(jià)格。註：S1=0 dual price=14/5 資源全使用完，銷路不錯(cuò)，消 費(fèi)者願(yuàn)意購買工廠生產(chǎn)量可再增加，但第一部資源 RHS全用完，工廠需向外僱用工人，工廠願(yuàn)付小於2.8元 僱用，MR-MC僱用-工人願(yuàn)付2.8工資l S2之Zj

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

11、制條件的對(duì)偶價(jià)格在表內(nèi)位置限制式形式對(duì)偶價(jià)格 此限制式的惰變數(shù)的Zj值 此限制式剩餘變數(shù)Zj值的負(fù)值 此限制式人工變數(shù)的Zj值例：（極小化問題）Min 2X13X2 s.t. 1X1125 產(chǎn)量A需求量 1X11X2350 總產(chǎn)量 2X11X2600 生產(chǎn)時(shí)間 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é)公司問題對(duì)偶價(jià)

12、格限制條件產(chǎn)品1需求量總生產(chǎn)量生產(chǎn)時(shí)間條件式形式對(duì)偶價(jià)格 0-4 1l RHS值與可行區(qū)間1.右手邊係數(shù)的可行性範(fàn)圍為其係數(shù)的範(fàn)圍能使影子價(jià)格維持不變。2.可行性範(fàn)圍也是目前基本變數(shù)組合仍然能維持最適組合的範(fàn)圍(雖然其值已改變)。例：（極大化問題）Max 50X140X2 s.t. 3X15X2150 裝配可用工時(shí) 1X220 P型顯示器 8X15X2300 倉儲(chǔ)空間 X1，X20其中 X1D型產(chǎn)品件數(shù) X2P型產(chǎn)品件數(shù)若裝配可用時(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小時(shí)增加為160小時(shí)，其最後單形表如下：（新解）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行的四個(gè)元素到以前表的最後一行即可。 舊解 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)解中一單位，則目前每個(gè)基本變數(shù)要自解中帶

15、走之單位數(shù)；即S1的變動(dòng)對(duì)X2的影響(即S1與X2的替代關(guān)係)。反之亦然。因此在S1行的元素可以解釋為每增加一單位b1目前基本解的改變量。上述新解為可用裝配時(shí)間增加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原裝配時(shí)間為150小時(shí)，b115

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

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

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

19、題轉(zhuǎn)變?yōu)榕碱}之規(guī)定：1.偶題是極小化正規(guī)型問題。2.當(dāng)原題有n個(gè)決策變數(shù)（n=2在海德例題），偶題就有個(gè)限制式。偶題的第一個(gè)限制式是與原題的X1變數(shù)相配合，偶題的第二個(gè)限制式與原題的X2變數(shù)相配合。3.當(dāng)原題有m個(gè)限制式（海德問題m3），偶題就有m個(gè)變數(shù)，偶題變數(shù)u1與原題的第一個(gè)限制式相配合，偶題變數(shù)u2與原題的第二個(gè)限制式相配合。4.原題的右邊值變成偶題的目標(biāo)函數(shù)係數(shù)。5.原題的目標(biāo)函數(shù)係數(shù)變成偶題的限制式右邊值。6.在原題限制式中第個(gè)變數(shù)的係數(shù)，變成偶題中第個(gè)限制式的係數(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 對(duì)偶變數(shù)之經(jīng)濟(jì)涵義：原始目標(biāo)函數(shù)值的結(jié)果為：50X140X21980(D型單價(jià))(D型產(chǎn)量)(P型單價(jià))(P型產(chǎn)量)生產(chǎn)總值對(duì)偶目標(biāo)函數(shù)為：150u120u2300u31980(資源1數(shù)量)u1+(資源2數(shù)量)u2+(資源3數(shù)量)u3=生產(chǎn)總值u1每小時(shí)裝配工時(shí)的價(jià)值=(產(chǎn)出-投入)=MR-MCu2每件P型顯示器的價(jià)值=每小時(shí)資源價(jià)值u3每平方呎倉儲(chǔ)空間的價(jià)值對(duì)偶價(jià)格：RHS每增加1單位的價(jià)值。在本章“對(duì)偶價(jià)格說明”中，已求得對(duì)偶價(jià)格，如下所示：資源裝配時(shí)間P型顯示器倉儲(chǔ)空間每額外單位價(jià)值(對(duì)偶價(jià)格)$