Download presentation
Presentation is loading. Please wait.
1
對偶理論 「敏感度分析」，研究數學規劃問題中參數值(如各類係數)的改變對於最佳解以及目標函數值的影響。
「對偶理論」(duality)；瞭解每一個線性規劃問題都會有一個「對偶問題」(dual)與其對應，而此對偶問題在經濟上具有相當有趣的含意。 6-1
2
敏感度分析—運用簡捷列表 目標函數係數 敏感度分析中，我們常見到對於目標函數係數值有一個限制範圍，我們稱之為「最佳化範圍」。
當我們一次只改變一個目標函數係數時，只要改變後的目標函數係數落在此限制範圍內，則改變前的最佳解仍然是改變後問題的最佳解。 6-2
3
LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 9.000000
1) VARIABLE VALUE REDUCED COST X X ROW SLACK OR SURPLUS DUAL PRICES 2) 3) NO. ITERATIONS= RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X X RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 6-3
4
範例說明(1/4) 在考慮弘光問題--題目請見課本p130 運用簡捷法，最後可得簡捷列表：
X1 X2 S1 S2 Basis CB X /2 -1/4 1 X /2 5/4 5 zj /2 1/4 9 cj - zj /2 -1/4 得基本可行解X1 = 5、X2 = 1、S1 = 0、S2 = 0 目標函數值為: Z = X1 + 4X2 = 1(5) + 4(1) = 9 6-4
5
範例說明(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
6
範例說明(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
7
範例說明(4/4) 6-7
8
限制式右側值 在許多線性規劃問題中，限制式的右側值是代表可以運用的資源數量。 對偶價(dual price)：
是提供決策者有關於取得額外資源(即增加右側值)，所必須額外支出的資訊。每條限制式都有一對應的對偶價，其意義為該限制式的右側值每增加一單位，目標函數值的「改善」量。 6-8
9
範例說明(1/2) 以弘光為例，最終簡捷列表如下： X1 X2 S1 S2
Basis CB X /2 -1/4 1 X /2 5/4 5 zj /2 1/4 9 cj - zj /2 -1/4 S1與S2所對應zj值分別為1/2與1/4，表示第一條與第二條限制式的對偶價分別為0.50與0.25 6-9
10
範例說明(2/2) 最大化問題中，當限制式為 時，則對偶價為0或負數。因為，當右側值增加時，則限制式更難滿足，對於利潤可能沒幫助，甚或損及利潤，故對偶價不會是個正數。因此， 限制式的對偶價，可由簡捷列表內，剩餘變數欄所對應的zj值變號而得，亦即 –zj 值。 6-10
11
可行性範圍 簡捷列表中的zj列可以決定對偶價，以預測當右側值bi改變一單位時，目標函數值的改變量。然而，此結論只有當bi改變量不大時，即不足以使目前的可行解變成不可行解時，方能適用。 「可行性範圍」 算出維持可行解右側值bi可能改變的範圍。 6-11
12
範例說明(1/4) 最終簡捷列表如下： X1 X2 S1 S2 過程說明請見課本p135 。 Basis CB 1 4 0 0
zj /2 1/4 10 cj - zj /2 -1/4 6-12
13
範例說明(2/4) 原先解 b1改變量 S1欄 新解 新解 = + 2 =
新解 = = S1欄內的每個值亦可以表示當右側值b1增加一單位時，基本變數值的改變量。新的解則等於原來的解加上此改變量。 6-13
14
範例說明(3/4) 若b1改變b1，則弘光問題之新基本解，如下 = + b1 =
6-14
15
範例說明(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
16
對偶理論(1/5) 每一個線性規劃問題都會有一個「對偶問題」與其對應，而原來的問題則稱之為「原始問題」。
有關於原始對偶間的關係，一個最基本的性質，那就是原始與對偶問題兩者有相同的最佳目標函數值，此特性稱之為「對偶理論」 6-16
17
對偶理論(2/5) (Primal) Max X1 + 4X2 s.t. X1 + 5X2 10 2X1 + 6X2 16
(Dual) Min 10u u2 1u 1 + 2u 2 1 5u 1 + 6u 2 4 u 1, u 2 0 6-17
18
對偶理論(3/5) 目標函數轉變為：Max -10u 1 - 16u2 則最初簡捷列表如下： u1 u 2 S1 S2 a1 a2
Basis CB M M a1 -M a2 -M zj -6M -8M M M -M -M -5M cj – zj M –16+8M -M -M 6-18
19
對偶理論(4/5) 將過三次的基底變換，可以得到最終簡捷列表如下： u1 u2 S1 S2 Basis CB u / / /4 u / / /2 zj cj - zj 對偶問題的最佳解為： u1 = 1/2， u2 = 1/4， S1 = S2 = 0。因為我們將對偶問題的目標函數變號後來求解，故其最佳目標函數值應為：- (- 9) = 9。 6-19
20
對偶理論(5/5) 可以驗證原始與對偶問題具有相同最佳目標值(=9)。任何一組原始與對偶問題，皆存在此種關係，我們稱此為「性質一」。 性質一
若原始問題有最佳解，則其對偶問題亦有最佳解反之亦然。此外，原始問題與對偶問題的最佳目標函數值是相同的。 6-20
21
對偶變數在經濟上的涵義(1/2) 原始問題與對偶問題有相同最佳目標值。 原始目標函數為： X1 + 4X2 = 9 (6.1)
對偶目標函數為： 10u1 + 16u2 = 9 (6.2) 由(6.1)式，X1與X2分別表示，A產品與B產品的產量，則(每單位A產品價值)(A產品產量) + (每單位B產品價值)(B產品產量) = 總產值 6-21
22
對偶變數在經濟上的涵義(2/2) 由(6.2)式，對偶問題目標函數係數(10與16)可解釋為可以運用的資源數。 (可運用資源一之數量) u1 + (可運用資源二之數量) u2 = 總產值 對偶變數，乃代表單位資源所產生的價值。以弘光而言， u1 =每單位組裝時間所產生的價值 u2 =每單位測試時間所產生的價值 6-22
23
從對偶問題求得原始問題 (1/2) 原始問題與對偶問題的最佳目標函數值是相同的。倘若我們只有求解對偶問題，可否同時得到原始問題的最佳解？
對偶問題的最終簡捷列表提供對偶變數的最佳值，則原始問題之變數應可在對偶問題最終簡捷列表中的zj列中找到。將此性質稱之為「性質二」。 6-23
24
從對偶問題求原始問題解(2/2) 性質二 給定對偶問題最終簡捷列表，則原始問題決策變數的最佳值可由表中剩餘變數所對應zj值得到。此外，原始問題寬裕變數最佳值為表中uj變數所對應cj-zj項的負值。 利用此性質，得到X 1 = 5，X 2 = 1，S1 = S2 = 0。 6-24
Similar presentations
