對偶理論 「敏感度分析」，研究數學規劃問題中參數值(如各類係數)的改變對於最佳解以及目標函數值的影響。 「對偶理論」(duality)；瞭解每一個線性規劃問題都會有一個「對偶問題」(dual)與其對應，而此對偶問題在經濟上具有相當有趣的含意。 6-1

敏感度分析—運用簡捷列表 目標函數係數 敏感度分析中，我們常見到對於目標函數係數值有一個限制範圍，我們稱之為「最佳化範圍」。 當我們一次只改變一個目標函數係數時，只要改變後的目標函數係數落在此限制範圍內，則改變前的最佳解仍然是改變後問題的最佳解。 6-2

LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 9.000000 1) 9.000000 VARIABLE VALUE REDUCED COST X1 5.000000 0.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.500000 3) 0.000000 0.250000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 1.000000 0.333333 0.200000 X2 4.000000 1.000000 1.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 10.000000 3.333333 2.000000 3 16.000000 4.000000 4.000000 6-3

範例說明(1/4) 在考慮弘光問題--題目請見課本p130 運用簡捷法，最後可得簡捷列表： X1 X2 S1 S2 Basis CB 1 4 0 0 X2 4 0 1 1/2 -1/4 1 X1 1 1 0 -3/2 5/4 5 zj 1 4 1/2 1/4 9 cj - zj 0 0 -1/2 -1/4 得基本可行解X1 = 5、X2 = 1、S1 = 0、S2 = 0 目標函數值為: Z = X1 + 4X2 = 1(5) + 4(1) = 9 6-4

範例說明(2/4) 每單位A產品之利潤c1的範圍，在簡捷列表內，以c1取代目標函數X1的係數，並重新計算zj與cj - zj兩列，可得簡捷表如下： 為維持最佳化，則cj - zj列的所有數皆須  0可得(3/2)c1-2  0  c1  4/3，1-(5/4)c1  0 c1 4/5 6-5

範例說明(3/4) 從以上二式，可得到c1的範圍如下： 4/5 c1 4/3 同樣地，以c2取代目標函數中X2的係數(4)，並重新計算zj與cj - zj兩列，並讓cj - zj列上的所有數皆必須  0，可得 3/2-1/2c2  0  c2  3 1/4c2 -5/4 0  c2  5 從以上二式，c2的範圍：3  c2  5 6-6

範例說明(4/4) 6-7

限制式右側值 在許多線性規劃問題中，限制式的右側值是代表可以運用的資源數量。 對偶價(dual price)： 是提供決策者有關於取得額外資源(即增加右側值)，所必須額外支出的資訊。每條限制式都有一對應的對偶價，其意義為該限制式的右側值每增加一單位，目標函數值的「改善」量。 6-8

範例說明(1/2) 以弘光為例，最終簡捷列表如下： X1 X2 S1 S2 Basis CB 1 4 0 0 X2 4 0 1 1/2 -1/4 1 X1 1 1 0 -3/2 5/4 5 zj 1 4 1/2 1/4 9 cj - zj 0 0 -1/2 -1/4 S1與S2所對應zj值分別為1/2與1/4，表示第一條與第二條限制式的對偶價分別為0.50與0.25 6-9

範例說明(2/2) 最大化問題中，當限制式為  時，則對偶價為0或負數。因為，當右側值增加時，則限制式更難滿足，對於利潤可能沒幫助，甚或損及利潤，故對偶價不會是個正數。因此， 限制式的對偶價，可由簡捷列表內，剩餘變數欄所對應的zj值變號而得，亦即 –zj 值。 6-10

可行性範圍 簡捷列表中的zj列可以決定對偶價，以預測當右側值bi改變一單位時，目標函數值的改變量。然而，此結論只有當bi改變量不大時，即不足以使目前的可行解變成不可行解時，方能適用。 「可行性範圍」 算出維持可行解右側值bi可能改變的範圍。 6-11

範例說明(1/4) 最終簡捷列表如下： X1 X2 S1 S2 過程說明請見課本p135 。 Basis CB 1 4 0 0 zj 1 4 1/2 1/4 10 cj - zj 0 0 -1/2 -1/4 6-12

範例說明(2/4) 原先解 b1改變量 S1欄 新解 新解 = + 2 = 新解 = + 2 = S1欄內的每個值亦可以表示當右側值b1增加一單位時，基本變數值的改變量。新的解則等於原來的解加上此改變量。 6-13

範例說明(3/4) 若b1改變b1，則弘光問題之新基本解，如下 = + b1 = 6-14

範例說明(4/4) 將上述可行性範圍的計算步驟，彙整於下： m = 限制式的個數 若 =目前的解，i = 1, 2, …, m bi = 第i個限制式右側值的改變量 = 簡捷列表中第i列第j欄的數值，其中j為第i個限制式之寬裕(或剩餘)變數所對應的欄 則bi 範圍的計算如下： 若限制式為  0， + bi  0， i = 1, 2, , m 若限制式為  0， - bi  0， i = 1, 2, , m 6-15

對偶理論(1/5) 每一個線性規劃問題都會有一個「對偶問題」與其對應，而原來的問題則稱之為「原始問題」。 有關於原始對偶間的關係，一個最基本的性質，那就是原始與對偶問題兩者有相同的最佳目標函數值，此特性稱之為「對偶理論」 6-16

對偶理論(2/5) (Primal) Max X1 + 4X2 s.t. X1 + 5X2  10 2X1 + 6X2  16 (Dual) Min 10u 1 + 16u2 1u 1 + 2u 2  1 5u 1 + 6u 2  4 u 1, u 2  0 6-17

對偶理論(3/5) 目標函數轉變為：Max -10u 1 - 16u2 則最初簡捷列表如下： u1 u 2 S1 S2 a1 a2 Basis CB -10 -16 0 0 -M -M a1 -M 1 2 -1 0 1 0 1 a2 -M 5 6 0 -1 0 1 4 zj -6M -8M M M -M -M -5M cj – zj -10+6M –16+8M -M -M 0 0 6-18

對偶理論(4/5) 將過三次的基底變換，可以得到最終簡捷列表如下： u1 u2 S1 S2 Basis CB -10 -16 0 0 u2 -16 0 1 -5/4 1/4 1/4 u1 -10 1 0 3/2 -1/2 1/2 zj -10 -16 5 1 -9 cj - zj 0 0 -5 -1 對偶問題的最佳解為： u1 = 1/2， u2 = 1/4， S1 = S2 = 0。因為我們將對偶問題的目標函數變號後來求解，故其最佳目標函數值應為：- (- 9) = 9。 6-19

對偶理論(5/5) 可以驗證原始與對偶問題具有相同最佳目標值(=9)。任何一組原始與對偶問題，皆存在此種關係，我們稱此為「性質一」。 性質一 若原始問題有最佳解，則其對偶問題亦有最佳解反之亦然。此外，原始問題與對偶問題的最佳目標函數值是相同的。 6-20

對偶變數在經濟上的涵義(1/2) 原始問題與對偶問題有相同最佳目標值。 原始目標函數為： X1 + 4X2 = 9 (6.1) 對偶目標函數為： 10u1 + 16u2 = 9 (6.2) 由(6.1)式，X1與X2分別表示，A產品與B產品的產量，則(每單位A產品價值)(A產品產量) + (每單位B產品價值)(B產品產量) = 總產值 6-21

對偶變數在經濟上的涵義(2/2) 由(6.2)式，對偶問題目標函數係數(10與16)可解釋為可以運用的資源數。 (可運用資源一之數量) u1 + (可運用資源二之數量) u2 = 總產值 對偶變數，乃代表單位資源所產生的價值。以弘光而言， u1 =每單位組裝時間所產生的價值 u2 =每單位測試時間所產生的價值 6-22

從對偶問題求得原始問題 (1/2) 原始問題與對偶問題的最佳目標函數值是相同的。倘若我們只有求解對偶問題，可否同時得到原始問題的最佳解？ 對偶問題的最終簡捷列表提供對偶變數的最佳值，則原始問題之變數應可在對偶問題最終簡捷列表中的zj列中找到。將此性質稱之為「性質二」。 6-23

從對偶問題求原始問題解(2/2) 性質二 給定對偶問題最終簡捷列表，則原始問題決策變數的最佳值可由表中剩餘變數所對應zj值得到。此外，原始問題寬裕變數最佳值為表中uj變數所對應cj-zj項的負值。 利用此性質，得到X 1 = 5，X 2 = 1，S1 = S2 = 0。 6-24