Chap. 7、解LP的其他演算法
7.1 Dual Simplex Method
是Mirror Image of Simplex Method.
See Table 6.10, 6.11 與 Fig.6.1 (p.210, 211)
Simplex Method 由Suboptimal basic solution開始求解，朝optimum 前進，
Dual Simplex Method 由 Superoptimal basic solution 開始求解，朝optimum 前進。
解題步驟：
For Maximization Problem
在Eq.0 的所有係數均為非負，如此the basic solution 才是 Superoptimal.
The basic solution 會是Infeasible 只有當有些變數為負數。Dual Simplex 法會逐步降低目標函數值，同時保持在Eq.0 的所有係數均為非負，並逐步去除其值為負數的變數，直到所有的變數最後均為非負。最後的basic solution 即為最優解。
Step 1. Initialization
Step 2. Feasibility test
Step 3. Iteration
|
|
Step 3.1 |
決定出基變數 (leaving basic variable): 由基變數中選取有最大絕對值的負數為出基變數。 |
|
|
Step 3.2 |
決定入基變數 (entering basic variable): 由非基變數中選取那個在eq. 0 中可透過與step 3.1中的出基變數列做高斯消去演算(Gaussian elimination)後最快變為0者為入基變數。 |
|
|
Step 3.3 |
求出新的basic solution: 目標在Set the nonbasic variables equal to 0之後，每個basic variable 與Z值即等於新的rhs的值。回Step 2 進行 Feasibility Test. |
範例：
Maximize Z = -4y1 – 12 y2 –18 y3,
s.t. y1 + 3 y3 >= 3
2 y2 + 2 y3 >= 5
y1, y2, y3 >=0
修改為
Minimize Z = 4y1 + 12 y2 +18 y3,
s.t. -y1 - 3 y3 <= -3
-2 y2 - 2 y3 <= -5
y1, y2, y3 >=0
此題為Wyndor Glass Co. (p.82) 問題之Dual Prblem
Table 7.1 Dual Simplex Method applied to Wyndor Glass Co. Dual Problem
|
Iteration |
Basic var. |
Eq. |
Coefficient of |
r.h.s |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
||||
|
|
Z |
(0) |
1 |
4 |
12 |
18 |
0 |
0 |
0 |
|
0 |
y4 |
(1) |
0 |
-1 |
0 |
-3 |
1 |
0 |
-3 |
|
|
y5 |
(2) |
0 |
0 |
-2 |
-2 |
0 |
1 |
-5 |
|
Iteration |
Basic var. |
Eq. |
Coefficient of |
r.h.s |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
||||
|
|
Z |
(0) |
1 |
4 |
0 |
6 |
0 |
6 |
-30 |
|
1 |
y4 |
(1) |
0 |
-1 |
0 |
-3 |
1 |
0 |
-3 |
|
|
y2 |
(2) |
0 |
0 |
1 |
1 |
0 |
-1/2 |
5/2 |
|
Iteration |
Basic var. |
Eq. |
Coefficient of |
r.h.s |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
||||
|
|
Z |
(0) |
1 |
2 |
0 |
0 |
2 |
6 |
-36 |
|
2 |
y3 |
(1) |
0 |
1/3 |
0 |
1 |
-1/3 |
0 |
1 |
|
|
y2 |
(2) |
0 |
-1/3 |
1 |
0 |
1/3 |
-1/2 |
3/2 |
The corresponding basic solution is (y1, y2, y3, y4, y5) = (0, 3/2, 1, 0, 0), Z = -36
The optimal solution for the dual of this problem is
(x1*, x2*, x3*, x4*, x5*)=(2,6,2,0,0)
比較 Table 7.1 與 Table 4.8. (p.99)
7.2 Parametric LP
Systematic changes in the Cj parameters
is replaced by 
代表relative rates at which the
coefficients are to be changed.
The values assigned to the 
may represent
………(p.267).
For any given value of, ……. (p.267)
always has this piecewise linear and convex form (Fig. 7.1 of
p.267)
Summary
1.
Solve the problem with 
=0 by the simplex method.
2.
Use the sensitivity analysis procedure
(case 2a and 3, sec. 6.7) to introduce the 
changes into Eq.(0).
3.
Increase 
until one of the
nonbasic variables has its coefficient in Eq.(0) go negative (or until 
has been
increased as far as desired).
4. Use this variable as the entering basic variable for an iteration of the simplex method to find the new optimal solution. Return to step 3.
Table 7.2 of p.269
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||||||||||||||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
|||||||||||||||||||
|
|
|
(0) |
1 |
0 |
0 |
0 |
|
|
36-2 |
x4=0 x5=0 |
||||||||||||||
|
x3 |
(1) |
0 |
0 |
0 |
1 |
1/3 |
-1/3 |
2 |
x3=2 |
|||||||||||||||
|
x2 |
(2) |
0 |
0 |
1 |
0 |
1/2 |
0 |
6 |
x2=6 |
|||||||||||||||
|
x1 |
(3) |
0 |
1 |
0 |
0 |
-1/3 |
1/3 |
2 |
x1=2 |
|||||||||||||||
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||||||||||||||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
|||||||||||||||||||
|
|
|
(0) |
1 |
0 |
0 |
|
0 |
|
27+5 |
x3=0 x5=0 |
||||||||||||||
|
x4 |
(1) |
0 |
0 |
0 |
3 |
1 |
-1 |
6 |
x4=6 |
|||||||||||||||
|
x2 |
(2) |
0 |
0 |
1 |
-3/2 |
0 |
1/2 |
3 |
x2=3 |
|||||||||||||||
|
x1 |
(3) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
x1=4 |
|||||||||||||||
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||||||||||||||||
|
Z |
x1 |
x2 |
x3 |
x4 |
x5 |
|||||||||||||||||||
|
|
|
(0) |
1 |
0 |
|
|
0 |
0 |
12+8 |
x2=0 x3=0 |
||||||||||||||
|
x4 |
(1) |
0 |
0 |
2 |
0 |
1 |
0 |
12 |
x4=12 |
|||||||||||||||
|
x5 |
(2) |
0 |
0 |
2 |
-3 |
0 |
1 |
6 |
x5=6 |
|||||||||||||||
|
x1 |
(3) |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
x1=4 |
|||||||||||||||
Systematic changes in the bj parameters
Maximize 
s.t.
for i = 1,2,….,
m
and 
for j = 1,2,…, n
The goal is to identify he optimal solution
as a function of 
.
Summary
1.
Solve the problem with 
=0 by the simplex method.
2.
Use the sensitivity analysis procedure
(case 1, sec. 6.7) to introduce the 
changes to the r.h.s. column.
3.
Increase 
until one of the
basic variables has its value in the r.h.s. column go negative (or until 
has been
increased as far as desired).
4. Use this variable as the leaving basic variable for an iteration of the dual simplex method to find the new optimal solution. Return to step 3.
Table 7.3 of p.271
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
|||||
|
|
|
(0) |
1 |
2 |
0 |
0 |
2 |
6 |
-36+2 |
y1=y4=y5=0 |
|
y3 |
(1) |
0 |
1/3 |
0 |
1 |
-1/3 |
0 |
(3+2 |
r.h.s =y3 |
|
|
y2 |
(2) |
0 |
-1/3 |
1 |
0 |
1/3 |
-1/2 |
(9-7 |
r.h.s =y2 |
|
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
|||||
|
|
|
(0) |
1 |
0 |
6 |
0 |
4 |
3 |
-27-5 |
y2=y4=y5=0 |
|
y3 |
(1) |
0 |
0 |
1 |
1 |
0 |
-1/2 |
(5- |
r.h.s =y3 |
|
|
y2 |
(2) |
0 |
1 |
-3 |
0 |
-1 |
3/2 |
(-9+7 |
r.h.s =y1 |
|
|
Range of
|
Basic Var. |
Eq. |
Coefficient of: |
r.h.s. |
Optimal solution |
|||||
|
Z |
y1 |
y2 |
y3 |
y4 |
y5 |
|||||
|
|
|
(0) |
1 |
0 |
12 |
6 |
4 |
0 |
-12-8 |
y2=y3=y4=0 |
|
y5 |
(1) |
0 |
0 |
-2 |
-2 |
0 |
1 |
-5+ |
r.h.s =y5 |
|
|
y1 |
(2) |
0 |
1 |
0 |
3 |
-1 |
0 |
3+2 |
r.h.s =y1 |
|
)/3
)/6
)/2
)/2
