Chap.6. 對偶理論與敏感度分析
6.1 對偶理論的本質
原題偶題之關係 Primal-Dual relations
|
原題 Primal Problem |
偶題 Dual Problem |
|
|
|
|
s.t.
|
s.t.
|
|
計算複雜度=m2n |
計算複雜度= n2m （當m較大時有利） |
矩陣表示法
|
Max Z ＝ C X s.t. A X <= b X >= 0 |
Min Yo ＝ Y b s.t. Y A >= C Y >= 0 |
|
亦可表示如下： |
|
|
Min ＣTＸ s.t. ＡＸ <= ｂ Ｘ >= ０ |
Max ｂTＹ s.t. ＡT Ｙ >= C Ｙ >= ０ |
|
Ex: p.198 Table 6.1 |
|
|
s.t.
|
s.t.
|
原題偶題練習
Ex1:
|
原題 |
偶題 |
|
MAX 20 A + 30 C SUBJECT TO A <= 60 C <= 50 A + 2 C <= 120 END |
MIN 60 X + 50 Y + 120 Z SUBJECT TO 1 X + 1 Z >= 20 1 Y + 2 Z >= 30 END |
|
O.F.V. 2100.00
VARIABLE VALUE Reduced Cost A 60 0 C 30 0
ROW SLACK Dual Prices 2) 0 5 3) 20 0 4) 0 15 |
O.F.V. 2100.00
VARIABLE VALUE Reduced Cost X 5 0 Y 0 20 Z 15 0 ROW SLACK 2) 0 -60 3) 0 -30 |
Ex2:
|
原題 MAX 4 X - 2 Y SUBJECT TO 2 X + 6 Y <= 12 3 X - 2 Y ＝ 1 4 X + 2 Y >= 5 END |
原題之變型 MAX 4 X - 2 Y SUBJECT TO 2 X + 6 Y <= 12 ① 3 X - 2 Y <= 1 ① -3 X + 2 Y <= -1 ① -4 X - 2 Y <= -5 END |
|
觀念： 3 X - 2 Y ＝1 可視為 3 X - 2 Y >= 1與 3 X - 2 Y <=1兩式同時成立，又>=式兩邊同乘以-1可改為<=之不等式。 |
|
|
偶題 |
|
|
MIN 12 R + S - T - 5 U SUBJECT TO 2 R + 3 S - 3 T - 4 U >= 4 6 R - 2 S + 2 T - 2 U >= -2 END |
|
Table 6.2 Primal-Dual Table for LP, illustrated by the Wyndor Glass Co. Example.
Table 6.3 Correspondence between Entitties in Primal and Dual Problems
|
One Problem |
|
Other Problem |
|
Constraint i |
ßà |
Variable i |
|
Objective func. |
ßà |
Right Sides |
簡算法的精神在找尋一組基變數與相對應的BF Solution, 使得row 0 的所有係數均為非負。
Condition
for Optimality：
Zj - Cj >= 0,
for j = 1, 2, 3,…., n,
Yi >= 0, for I = 1,
2,3,….., m.
Table 6.4 Notation for Entries in row 0 of a simplex Tableau
|
|
|
|
Coefficient of: |
|
||||||||
|
Iteration |
Basic Var. |
Eq. |
Z |
X1 |
X2 |
…. |
Xn |
Xn+1 |
Xn+2 |
…. |
Xn+m |
Right side1 |
|
any |
Z |
0 |
1 |
Z1-C1 |
Z2-C2 |
…. |
Zn-Cn |
y1 |
y2 |
…. |
ym |
y0 |
Table 6.5 Row 0 and corresponding dual solution for each iteration for the Wyndor glass Co. example.
|
iteration |
Primal Problem |
Dual Problem |
y0 |
|||||||||
|
Row 0 |
y1 |
y2 |
y3 |
Z1- C1 |
Z2- C2 |
|||||||
|
0 |
-3 |
-5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-3 |
-5 |
0 |
|
1 |
-3 |
0 |
0 |
5/2 |
0 |
30 |
0 |
5/2 |
0 |
-3 |
0 |
30 |
|
2 |
0 |
0 |
0 |
3/2 |
1 |
36 |
0 |
3/2 |
1 |
0 |
0 |
36 |
Z* = 36 = y0*
弱對偶性，強對偶性，互補性，及對稱性
弱對偶性：X為原題之可行解，Y為偶題之可行解，則C X <= Y b
強對偶性：X*為原題之最優解，Y*為偶題之最優解，則C X*=Y* b
Note that：
原題為Max 問題，存在C X <= C X*
偶題為Min 問題，存在Y b >= Y* b
互補性：在簡算法的每次反覆計算中，可求得原題的可行解與偶題的互補解
(在列0中，為差額變數的係數)，其中 C X=Y b。若X不是原題的最優解，則Y亦不是偶題的可行解。
互補最優性：在最後一次的反覆計算時，簡算法可同時求出原題的最優解X*與偶題的互補最優解Y*，其中
C X*=Y* b，Y*由Yi*組成，即為影價。
對稱性：偶題的偶題為原題
Duality Theorem：
1.
若某原題或偶題有可行解且有有界的目標函數，換言之，會有最佳解時，則其對應的偶題或原題也會有最佳解，且弱對稱性與強對稱性均適用。
2.
若某原題或偶題有可行解但目標函數為無界時，換言之，沒有最佳解時，則其對應的偶題或原題將找不到可行解。
3.
若某原題或偶題無可行解時，則其對應的偶題或原題不是沒有可行解，就是其目標函數為無界，總之，將找不到最佳解。
Table 6.7 Association between variables in Primal and Dual problems
|
Primal variable |
Associated Dual variable |
|
Original vari. Xi |
Zj - Cj (surplus vari.) j = 1,2,…,n |
|
Slack vari. Xn+1 |
yi (original vari.) i=1,2,..,m |
Table 6.10 Classification of Basic solutions (p.210)
|
|
Satisfies Condition for Optimality |
||
|
Yes |
No |
||
|
Feasible ? |
Yes |
Optimal |
Suboptimal |
|
No |
Superoptimal |
Neither feasible Nor Superoptimal |
|
Basic solutions 可用兩種方式來分類，分別為是否可行 (condition for feasibility) 與是否為最佳 (condition for optimality)。前者透過擴充解中的所有變數是否為非負(0或正數)來判斷，後者透過在列0的係數是否全為非負數來判斷。
Table 6.11
|
Primal basic solution |
Complementary Dual basic solution |
|
Suboptimal |
Superoptimal |
|
Optimal |
Optimal |
|
Superoptimal |
Suboptimal |
|
Neither feasible not superoptimal |
Neither feasible not superoptimal |
Table 6.13 Constructing the Dual of the Dual Problem
|
Dual Problem |
|
Converted to standard Form |
|
Minimize yo= y b s.t. y A >= c and y >= 0 |
à |
Maximize (-yo)= -y b s.t. -y A <= - c and y >= 0 |
|
|
||
|
Converted to standard Form |
|
Its Dual Problem |
|
Maximize Z = c X s.t. A X <= b and X >= 0 |
ß |
Minimize (-Z) = -c X s.t. -A X >= - b and X >= 0 |
Table 6.14 Corresponding Primal-Dual forms
|
Primal Problem (or Dual Problem) |
Dual Problem (or Primal Problem) |
||
|
Maximize Z (or yo) |
Minimize yo (or Z) |
||
|
限制式 i： |
變數 yi
(or Xi)： |
||
|
<= |
Form |
|
yi >= 0 |
|
= |
Form |
|
unconstrainted |
|
>= |
Form |
|
yi
'<= 0 |
|
變數 Xj (or yj)： |
限制式 j： |
||
|
|
Xj >= 0 |
>= |
Form |
|
|
unconstrainted |
= |
Form |
|
|
Xj
'<= 0 |
<= |
Form |
Table 6.15 One Primal-Dual Form for the Radiation Therapy Example
|
Primal Problem |
|
Dual Problem |
|
Maximize -Z=-0.4X1-0.5X2 s.t. 0.3X1+0.1X2<=2.7 0.5X1+0.5X2=6 0.6X1+0.4X2>=6 and X1>=0 X2>=0 |
|
Minimize yo=2.7y1+6y2+6y3' s.t. y1>=0 y2 unconstrainted in sign y3'<=0 and 0.3y1+0.5y2+0.6y3'>=-0.4 0.1y1+0.5y2+0.4y3'>=-0.5 |
6.6 敏感度分析 Sensitivity analysis
Table 6.18
|
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
|||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
||||
|
New initial tableau |
Z |
(0) |
1 |
-4 |
-5 |
0 |
0 |
0 |
0 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
|
|
x4 |
(2) |
0 |
0 |
2 |
0 |
1 |
0 |
24 |
|
|
x5 |
(3) |
0 |
2 |
2 |
0 |
0 |
1 |
18 |
|
此新表格係在c1, a31, b2 做了更正。
原題的最末表格
|
Final tableau for original model |
Z |
(0) |
1 |
0 |
0 |
0 |
3/2 |
1 |
36 |
|
x3 |
(1) |
0 |
0 |
0 |
1 |
1/3 |
-1/3 |
2 |
|
|
x2 |
(2) |
0 |
0 |
1 |
0 |
1/2 |
0 |
6 |
|
|
x1 |
(3) |
0 |
1 |
0 |
0 |
-1/3 |
1/3 |
2 |
最佳解為 (2, 6), Z = 36
Table 6.17 (p.219)
|
Revised final tableau |
Z |
(0) |
1 |
z*- |
y* |
Z* |
|
x3 |
(1) |
0 |
A* |
S* |
b* |
|
|
x2 |
(2) |
0 |
||||
|
x1 |
(3) |
0 |
修正題的最末表格
|
Revised final tableau |
Z |
(0) |
1 |
-2 |
0 |
0 |
3/2 |
1 |
54 |
|
x3 |
(1) |
0 |
1/3 |
0 |
1 |
1/3 |
-1/3 |
6 |
|
|
x2 |
(2) |
0 |
0 |
1 |
0 |
1/2 |
0 |
12 |
|
|
x1 |
(3) |
0 |
2/3 |
0 |
0 |
-1/3 |
1/3 |
-2 |
Table 6.19修正題的最末表格透過Gaussian elimination 再予以修正
|
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
|||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
||||
|
Converted to proper form |
Z |
(0) |
1 |
0 |
0 |
0 |
1/2 |
2 |
48 |
|
x3 |
(1) |
0 |
0 |
0 |
1 |
1/2 |
-1/2 |
7 |
|
|
x2 |
(2) |
0 |
0 |
1 |
0 |
1/2 |
0 |
12 |
|
|
x1 |
(3) |
0 |
1 |
0 |
0 |
-1/2 |
1/2 |
-3 |
|
在c1, a31, b2 做了更正之後，上列表格告訴我們最佳解由原來的 (2, 6) 改為 (-3, 12)，而後者由於在基變數中的x1 為負數，所以該解變為 non-feasible，但由於列0 的所有係數均為非負，所以其滿足optimality test。由Table 6.10 可知此basic solution 屬Superoptimal。可進一步在用Dual simplex method 求解。
Summary of procedure for Sensitivity Analysis
1. Revision of model
2. Revision of final tableau
3. Conversion to proper form from Gaussian elimination
4. Feasibility test
5. Optimality test
6. Reoptimization
6.7 Applying Sensitivity Analysis
(補充內容)
分三方面來探討：有關1.目標函數的係數值的變動，2.有關限制式的係數值的變動，3.其它有關限制式的 rhs 值的變動 (包括邊際資訊、與其它)。
目標函數的係數值的變動
|
100 % Rule by Bradley, Hax and Magnanti (1977): Any combination of change will not change the basis（基底）if the sum of the percentages of slack used sums to less than 100%. |
|
the % of slack =目標函數的係數的變動量/allowable decrease or increase |
|
範例： MAX 20 A + 30 C -----> 17 A + 20 C SUBJECT TO 2) A <= 65 3) C <= 50 4) A + 2 C <= 120 END |
|
O.F.V. = 2100 且 A = 60， C = 30 |
以 LINDO 作敏感度分析之部份結果如下表：
|
VARIABLE |
CURRENT COEF. |
ALLOWABLE INCREASE |
ALLOWABLE DECREASE |
|
A |
20 |
INFINITY |
5 |
|
C |
30 |
10 |
30 |
|
100 % Rule： (20-17)/5 + (30-20)/30 = 0.6 + 0.333 = 0.933 < 100 % |
|
Basis 不變， A = 60， C = 30 --> new O.F.V. = 2100 - 60 * 3 - 30 * 10 = 2100 - 480 = 1620 |
限制式的係數值的變動
|
O.F.V.改善量 =(value of variable j) x (dual price of row i) x e 其中， e 為 row i 中 variable j 的係數的減少的微小值 |
|
範例： |
|
MAX 20 A + 30 C SUBJECT TO 2) A <= 65 3) C <= 50 4) A + 2 C <= 115 -->更改為A + 2.01 C <= 115 END O.F.V. = 2050.00 |
|
VARIABLE VALUE REDUCED COST A 65 0 C 25* 0 ROW SLACK DUAL PRICES 2) 0 5 3) 25 0 4) 0 15* |
|
預測之 O.F.V. = 2050 + (25*15*(-0.01)) = 2050 - 3.75 = 2046.25 真正之 O.F.V. = 2046.269, O.F.V. decrease by 3.731 |
邊際資訊（Marginal Information）
|
邊際資訊包括：邊際成本（Marginal Cost）與邊際價值（Marginal Value），此二名詞分別與 LINDO 中使用的Reduced Cost及Dual Prices 相通。 |
|
※有關 Reduced Cost 與 Dual Prices 之探討，請參考『LP補充教材』中之 LINDO 進階。 |
有關限制式的 rhs 值的變動
增加 '<=限制式'的 rhs 值表示放鬆限制範圍，「可行域」（feasible
domain）將擴大，目標函數值（O.F.V.）可望增加。
減少 '<=限制式'的 rhs 值， 目標函數值可望減少。
增加 '>=限制式'的 rhs 值表示加大限制範圍，「可行域」將縮小，目標函數值可望減小。
減少 '>=限制式'的 rhs 值，目標函數值可望增加。
增加 '=限制式'的 rhs 值表示移動邊界（Boundary），目標函數值可能加大可能減小。
減少 '=限制式'的 rhs 值， 目標函數值可能加大可能減小。
與 Dual Prices 的觀念結合：
|
當 Dual Prices 之值 ≠ 0 時，其相對應之 SLACK or SURPLUS 為 0，表示該限制式已用到極點（口語化說法），若能增加 rhs 之值，則 O.F.V. 可增加與 Dual Price 相同之量。 |
加入新變數或新限制式
加入新變數或新限制式有時是必要的考量，
新變數：需放置於所有相關之處，包括目標函數及各限制式，新變數在目標函數及各限制式中涉及之係數亦需加以考量。
新限制式：可能是原來故意不加或忽略未加，敏感度分析有時涉及新限制式，當問題為無限多解（unbounded）時，常常是因某一重要限制式被忽略了。
(教科書內容)
Case 1 changes in bi (p.224)
One or more of the ‘right hand side’ values have been changed.
Right side of final row 0:
Right side of final rows 1,2,…,m: 
例：將b = [4 12 18]T 改為 à 
[4 24 18]T
例：b2 由12 改為24
|
Max. |
3X1 + 5 X2 |
|
|
s.t. |
X1 <=4 2X2<=24 3X1+2X2 <=18 X1, X2 >=0 |
|
Table 6.20 Revised data for Wyndor glass Co. problem after just b2 is changed.
|
|
BasicVar. |
Eq. |
Coefficient of: |
r.h.s. |
|||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
||||
|
Final tableau after reoptimization |
Z |
(0) |
1 |
9/2 |
0 |
0 |
0 |
5/2 |
45 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
3/2 |
1 |
0 |
0 |
1/2 |
9 |
|
|
x4 |
(3) |
0 |
-3 |
0 |
0 |
1 |
-1 |
6 |
|
另法：只考慮有更改的限制式(2nd
column of S*)與涉及的變數(2nd component of y*)，
所以Z = 原值36+18=54
|
|
à |
|
|
|
à |
|
|
|
à |
|
This range of values for b2 is referred to allowable range to stay feasible.
Case 2a. Changes in the coefficients of a Nonbasic variables
Refer to Table 6.20 of p.226, x3, x2, x4 為基變數，x1與 x5為非基變數。
由於非基變數之值在basic solution 中其值為0，修改各係數其實不會對最佳值有影響，只需確認該值是否仍為最佳解。
例：
|
Max. |
3X1 + 5 X2 修正為 |
4X1 + 5 X2 |
|
s.t. |
X1 <=4 2X2<=24 3X1+2X2 <=18 X1, X2 >=0 |
X1 <=4 2X2<=24 2 X1 + 2 X2 <=18 X1, X2 >=0 |
|
原題 |
Max Z = CX s.t. A X <= b |
|
|
偶題 |
Min y0=y b s.t. yA >= C |
|
|
|
Min y0=[y1* y2* y3*]T [4 24 18] s.t. [y1* y2* y3*]T [1 0 3] >=3 [y1* y2* y3*]T [0 2 2] >=5 |
|
|
修正後限制式 |
s.t. [y1* y2* y3*]T [1 0 2] >=4 |
|
由上表可知，更改原題中非基變數的係數相對於其偶題而言，只對一個限制式有影響，所以若原題 y* 滿足新的限制式，則原題的最佳解在修正後仍為最佳解。
The allowable range to stay optimal
滿足 Cj <= y* Aj
Case 2b. Introduction of a New variable
假設原題中多了一個非基變數，其係數皆為0，再採Case 2a 的方式去修正係數。
Case 3. Changes in the Coefficients of a Basic variable
例：
|
Max. |
3X1 + 5 X2 修正為 |
3X1 + 3 X2 |
|
s.t. |
X1 <=4 2X2<=24 3X1+2X2 <=18 X1, X2 >=0 |
X1<=4 3X2 <=24 3X1 + 4 X2 <=18 X1, X2 >=0 |
Table 6.21
|
|
BasicVar. |
Eq. |
Coefficient of: |
r.h.s. |
|||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
||||
|
Revised final tableau |
Z |
(0) |
1 |
9/2 |
7 |
0 |
0 |
5/2 |
45 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
3/2 |
2 |
0 |
0 |
1/2 |
9 |
|
|
x4 |
(3) |
0 |
-3 |
-1 |
0 |
1 |
-1 |
6 |
|
|
Converted to proper form |
Z |
(0) |
1 |
-3/4 |
0 |
0 |
0 |
3/4 |
27/2 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
3/4 |
1 |
0 |
0 |
1/4 |
9/2 |
|
|
x4 |
(3) |
0 |
-9/4 |
0 |
0 |
1 |
-3/4 |
21/2 |
|
|
After reoptimization (0ne iteration of the simplex method) |
Z |
(0) |
1 |
0 |
0 |
3/4 |
0 |
3/4 |
33/2 |
|
x1 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
0 |
1 |
-3/4 |
0 |
1/4 |
3/2 |
|
|
x4 |
(3) |
0 |
0 |
0 |
9/4 |
1 |
-3/4 |
39/2 |
|
Case 4. Introduction of a New constraint
|
Step 1. |
在原Simplex Method 的最末表格中加入新的限制式，使用新的Slack or Artificial variable. |
|
Step 2. |
轉換為適當的格式 |
|
Step 3. |
當原最佳解變為Superoptimal 時，使用Dual Simplex Method 來重新最佳化求解。 |
例：
加入 2X1 + 3 X2 <=24
Table 6.22
|
|
BasicVar. |
Eq. |
Coefficient of: |
r.h.s. |
||||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||
|
Revised final tableau |
Z |
(0) |
1 |
9/2 |
0 |
0 |
0 |
5/2 |
0 |
45 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
3/2 |
1 |
0 |
0 |
1/2 |
0 |
9 |
|
|
x4 |
(3) |
0 |
-3 |
0 |
0 |
1 |
-1 |
0 |
6 |
|
|
x6 |
New |
0 |
2 |
3 |
0 |
0 |
0 |
1 |
24 |
|
上表紅框區為不適當，Eq(2) x (–3) + New Eq. 可改善，結果如下表：
|
Converted to proper form |
Z |
(0) |
1 |
9/2 |
0 |
0 |
0 |
5/2 |
0 |
45 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
3/2 |
1 |
0 |
0 |
1/2 |
0 |
9 |
|
|
x4 |
(3) |
0 |
-3 |
0 |
0 |
1 |
-1 |
0 |
6 |
|
|
x6 |
New |
0 |
-5/2 |
0 |
0 |
0 |
-3/2 |
1 |
-3 |
x6為負數，所以 (0,9) 的解為 non-feasible, 但因為 Row 0 的係數均為非負，所以屬 Superoptimal, 可再透過 Dual Simplex Method 求解並得出下表：
|
Reoptimzation after one iteration of Dual simplex Method |
Z |
(0) |
1 |
1/3 |
0 |
0 |
0 |
0 |
5/3 |
40 |
|
x3 |
(1) |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
4 |
|
|
x2 |
(2) |
0 |
2/3 |
1 |
0 |
0 |
0 |
1/3 |
8 |
|
|
x4 |
(3) |
0 |
-4/3 |
0 |
0 |
1 |
0 |
-2/3 |
8 |
|
|
x5 |
New |
0 |
-5/3 |
0 |
0 |
0 |
1 |
-2/3 |
2 |
(0, 8) 為新的最佳解，且Z = 40 為新的 O.F.V.
有系統的敏感度分析－參數規劃
假設想瞭解一個或多個變數在某一區間內連續變動時，其對最佳解之變動
影響如何，此時可採參數規劃方式進行。
假設第二限制式之 rhs 值 b2 之值在 12 與 24 間連續變動，
則將 b2 定義為 12 + θ，其中 θ = 0 至 12
以 簡算法進行求解，可得出以下類似結果：
Ｚ = 36 + 3/2 * θ
Ｘ1 = 2 - 1/3 * θ
Ｘ2 = 6 + 1/2 * θ
Ｘ3 = 2 + 1/3 * θ
Ｘ4 = 0
Ｘ5 = 0
此法同時適用於 O.F.V. 或限制式中某變數之係數。
亦可同時分析數個變數之係數之變動或數個限制式之 rhs 值之變動。
作業
1. 請以實例闡述線性規劃之原題－偶題（Primal-Dual）關係中之弱對偶性，強對偶性，互補性，及對稱性。
2. 請以實例闡述線性規劃之「後最佳化分析」，包括：
一般的敏感度分析：⑴ O.F.V. 中 某變數係數改變
⑵ 某一限制式中 某變數係數改變
⑶ 某一限制式中 rhs 之值改變
及參數規劃