第六章 单形法敏感度分析及对偶特性

1、第六章 單形法敏感度分析及對偶特性本章內容：6.1 以單形表做敏感度分析6.2 對偶特性n 6.1 以單形表做敏感度分析l 目標函數係數l 目標函數與最適區間之意義：1.若目標函數之係數範圍能使目前的最適解仍維持最適，則此範圍稱為目標函數之最適區間。2.最適區間可能使目標函數值改變。3.目標函數係數的最適區間，由CjZj0淨評估值而定。（1）目標函數基本變數之敏感度分析（只改變一個基本變數係數）。例：Max 50X140X2 s.t. 3X15X12150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20其中 X1D型產品件數 X2P型產品件數最後單形表如下：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為基本變數，S1，S3為非基本變數。計算目標函數X1基本變數之係數C1之最適區間，須先將最後單形表修改如下：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最適區間應使CjZj0即需(C1-64/50)及(24-C1/50)所以的最適區間為24C164。註：基本變數（X1，X2，S2）之最適區間係計算非基本變數（S1，S3）之CjZj，使其0。驗証：型產品利潤由原來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。結論：最適解不變，但總利潤解降為1380元。 （30X140X2303040121380）驗証：型產品利潤由原來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，因此需繼續計算單形表，引進S3後之最適解為X116.6件，X220件，已改變原最適解。（2）目標函數非基

5、本變數之敏感度分析（只改變一個非基本變數係數）。例：Max 50X140X2 s.t. 3X15X2150 裝配可用工時 1X220 P型顯示器 8X15X2300 倉儲空間 X1，X20其中 X1D型產品件數 X2P型產品件數最後單形表如下：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為基本變數，S1，S3為非基本變數。 指dual price計

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

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

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

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

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

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

13、-5/25010-3/253/255/2512830ZjCjZj50040014/5-14/50026/5-26/51980解：X130，X212，S10，S28，S30，Z1980（基本變數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（基本變數X1，X2，

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

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

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

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

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

19、題轉變為偶題之規定：1.偶題是極小化正規型問題。2.當原題有n個決策變數（n=2在海德例題），偶題就有個限制式。偶題的第一個限制式是與原題的X1變數相配合，偶題的第二個限制式與原題的X2變數相配合。3.當原題有m個限制式（海德問題m3），偶題就有m個變數，偶題變數u1與原題的第一個限制式相配合，偶題變數u2與原題的第二個限制式相配合。4.原題的右邊值變成偶題的目標函數係數。5.原題的目標函數係數變成偶題的限制式右邊值。6.在原題限制式中第個變數的係數，變成偶題中第個限制式的係數。海德公司偶題之單形表如下（以偶題表格型解之）：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（因其為使負偶題目標函數的負值極大化，因此偶題目標函數值應為(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。原題與偶題之關係為何?二者之目標函數值相同。l 特性1：若偶題有最適解，原題亦有最適解，反之亦如此，且原題與偶題之目標值相等。特性1告訴我們，只解偶題亦能得知原題目標函數值。l 對偶變數之經濟涵義：原始目標函數值的結果為：50X140X21980(D型單價)(D型產量)(P型單價)(P型產量)生產總值對偶目標函數為：150u120u2300u31980(資源1數量)u1+(資源2數量)u2+(資源3數量)u3=生產總值u1每小時裝配工時的價值=(產出-投入)=MR-MCu2每件P型顯示器的價值=每小時資源價值u3每平方呎倉儲空間的價值對偶價格：RHS每增加1單位的價值。在本章“對偶價格說明”中，已求得對偶價格，如下所示：資源裝配時間P型顯示器倉儲空間每額外單位價值(對偶價格)$