Chap. 5 簡算法之理論
5.1解釋名詞
Constraint boundary equation: 限制式的邊界方程式
以等號取代限制式中之不等號所形成之方程式。
Ai1 X1 + Ai2 X2 + .... + Ain Xn = bi, i = 1,2,...,m
此種方程式定義了n 度空間之幾何圖形。
|
n |
超面(HyperPlane) |
|
2 |
線 |
|
3 |
面 |
|
Max Z = 3 X1 + 5 X2 |
|
|
s.t. |
|
|
|
X1 <= 4 2X2 <=12 3X1 + 2 X2 <=18 X1>=0, X2>=0 |
依上例，#
of functional constraints = m =3
# of non-negativity = n=2, # of decision variables = n = 3
|
可行解 Feasible Solution |
滿足所有限制式之一組解。 |
|
可行域 Feasible Domain |
所有可行解所形成之集合。 |
|
邊界 Boundary |
滿足一個或多個邊界方程式的可行解稱之為可行域之邊界。 |
|
角點 Corner Point |
在 n 度空間中 m+n 組 Boundary Eq.裏任選 n組聯立所求得之解稱之。 |
附帶學習用 Excel 解聯立式，請下載 Excel6.zip
|
角點可行解 Corner Point Feasible Solution |
由角點引申的定義：並非所有角點皆為可行解，只有在可行域的邊界上的角點才是角點可行解。 由可行解引申的定義：不位於任何可連接其他兩個可行解的線段上的可行解。 A feasible
solution that does not lie on any line segment connecting two other feasible
solutions. |
|
相鄰角點可行解 Adjacent Corner Point Feasible Solution |
若兩角點被稱為相鄰，則連接該二點之'線'必須位於可行域之邊界。二相鄰角點之間只有一邊界方程式不同 |
|
定義方程式 Defining
Equation |
決定CP
的邊界方程式。 Refer
to p.156 Table 5.1
and Table
5.2 |
通則1a：
|
若 Optimum Solution 只有一組，則必為角點可行解。 |
通則1b：
|
若 Optimum Solution 有多組，則其中至少有二組為相鄰角點可行解。 |
證明：see p.159 of Text Book
假設存在一個最優解，且其非角點可行解。
由角點可行解的定義可知其為「不位於任何可連接其他兩個可行解的線段上的可行解」。
若非為角點可行解，則其可位於任何可連接其他兩個可行解的線段上。
如上所述，Z*若非等於Z1且等於Z2 ，則Z* 不可能為最優解。
通則2：
|
角點可行解之數目有限。 |
證明：see p.160 of Text Book
假設在 n 度空間的問題中有 m+n 個限制式，則有 m+n 個邊界方程式。
|
任取 n 個方程式聯立求解。 |
最多可有 |
|
|
角點之數目，Ncp |
Ncp < |
8 < 10 |
|
角點可行解之數目，Ncpfs |
Ncpfs < Ncp |
5 < 8 |
通則3：
|
一角點可行解若優於所有的相鄰角點可行解，則必優於其他角點可行解。 （凸集合） |
m = 50， n = 50，
=
=
組解
以簡算法去解，只須求約 100 個角點可行解。
證明：see p.161 of Text Book
Fig.5.3
加入Slack variables (擴張)之後的相關定義：
|
Augmented CP solutions擴張角點解= basic solutions基解 |
加入Slack
variables and/or Artificial variables 之後的角點解 |
|
|
基解：包括m個基變數，其餘的非基變數之值為0，m為功能限制式的個數 |
||
|
指示變數 Indicating
variable |
可代表某一邊界方程式的變數。 Refer
to p.162 Table 5.3
and p.164 Table 5.4 |
|
|
Augmented CPF solutions 擴張角點可行解 = Basic Feasible solutions基本可行解 |
加入Slack variables and/or Artificial variables 之後的角點可行解 |
|
基本可行解：是所有的m個基變數都
>=0 的一組基解，若任一基變數之值為0，此基本可行解被稱為退化 (degenerate)。 |
|
Table 5.5 BF solutions for the Wyndor Glass Co. Problem (p.164)
Table 5 .6 Basic infeasible solutions for
the Wyndor Glass Co. Problem (p.164)
Table
5.7 Sequence obtained by the Simplex method for the Wyndor Glass Co. Problem
|
Iteration |
CPF solution 角點可行解 |
Defining Eq. 定義方程式 |
Nonbasic Var. 非基變數 |
|
0 |
(0,0) |
X1=0 X2=0 |
X1=0, X2=0 |
|
1 |
(0,6) |
X1=0 2X2=12 |
X1=0, X4=0 |
|
2 |
(2,6) |
2X2=12 3X1+2X2=18 |
X4=0, X5=0 |
5.2 修正簡算法
矩陣表示
|
一般模式 Max: Z = 3 X1 + 5 X2 |
s.t. X1 <= 4 2 X2 <= 12 3 X1 + 2 X2 <= 18 X1 >= 0 X2 >= 0 |
|
通式 |
矩陣表示法 |
|
Max: Z =C1 X1 + C2 X2 + ..+Cn Xn s.t.
i = 1, 2, ..., m Xj >= 0, j = 1, 2, ..., n |
Z = C X A X <= b X >= 0 其中，C = [ C1, C2, C3, ... , Cn ]
|
上例有n 個變數，n 度空間，n + m 個限制式，需要 m 個 slack variables，
加上 m個 slack variables 之後的模式如下所示：
|
一般模式 Max Z Z-3X1-5X2+0S1+ 0S2+0S3 = 0 s.t. X1 + 1 S1+ 0 S2+ 0 S3 = 4 2 X2+ 0 S1+ 1 S2+ 0 S3 = 12 3 X1+2 X2+ 0 S1+ 0 S2+ 1 S3 = 18 |
矩陣表示法 Ｃ = [ C, 0 ] s.t. [A, I] 其中 |
|
|
|
|
限制式 [ A, I ] 求解： ＸB= Ｂ-1 * b 定義 ＣB= [C, 0] 中去掉非基變數之對應項，再重新排列以配合ＸB 之順序 Ｚ = ＣB ＸB = ＣB（Ｂ-1 * b ） |
|
>=0 且 [Xs]= 
= b，可簡化為
範例：
|
Max: Z = 3 X1 + 5 X2 |
Max: Z = [3, 5] |
|
s.t. X1 <= 4 2 X2 <= 12 3 X1 + 2 X2 <= 18 X1 >= 0 X2 >= 0 |
s.t.
A X <= B X = |
>= 
加上 slack variables 之後
|
Max Z Z - 3 X1 - 5 X2 + 0 S1 + 0 S2 + 0 S3 = 0 s.t. X1 + S1 = 4 2 X2 + S2 + = 12 3 X1 + 2 X2 + S3 = 18 |
|
矩陣表示法 |
|
|
以矩陣表示簡算法求解
|
iter 0 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
基陣B = 由[ A,I ] 去掉非基變數之對應行 = |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
ＣB = 由[ C, 0 ] 去掉非基變數之對應項 = [ 0 0 0 ] |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
ＸB =Ｂ-1 b
= |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Z = CBＸB = [0 0 0] |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
iter 1 |
X2 進入基底， S2 離開 |
||||||||||||||||||||||||||||||||||||||||||
|
ＸB = |
B = |
ＣB = [ 0 5 0 ] |
|||||||||||||||||||||||||||||||||||||||||
|
(a) Ｂ-1= |
(b) Ｂ-1Ａ = Ｂ-1 |
||||||||||||||||||||||||||||||||||||||||||
|
(c) ＣB Ｂ-1 = [ 0 5 0] |
|||||||||||||||||||||||||||||||||||||||||||
|
(d) ＣB Ｂ-1Ａ -Ｃ = [0 5/2 0] |
|||||||||||||||||||||||||||||||||||||||||||
|
(e) ＸB= Ｂ-1 b = Ｂ-1 |
|||||||||||||||||||||||||||||||||||||||||||
|
(f) Ｚ =ＣB ＸB = [ 0 5 0 ] |
|||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||
- [3 5] = [-3 0]
= 30
|
iter 2 |
X1 進入基底，S3 離開基底 |
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
ＣB = [0 5 3] |
||||||||||||||||||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||
修正矩陣表示簡算法
|
||||||||||||||||||||||||||||||||||||||||
|
矩陣表示 (iteration 0) |
||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||
|
0* 視 I 之 dimension (m x m) 而決定其為 m x 1 之 零矩陣， 0# 視 I 之 dimension (m x m) 而決定其為 1 x m 之 零矩陣， C 為 1 x n 之矩陣， A 為 m x n 之矩陣。 |
|
式(1)兩邊同乘
|
可導出下式
仍以上例做說明，iter. 0 及 1 略，僅以 iter. 2 做示範。
|
由前例已知 Ｂ矩陣 = |
(a) |
||||
|
(b) |
(c) ＣBＢ-1 = [0 5 3] Ｂ-1 = [0 3/2 1] |
||||
|
(d) ＣBＢ-1Ａ - Ｃ = [ 0 3/2 1 ] = [0 0] |
(e) ＣBＢ-1 b = [ 0 3/2 1 ] |
||||
|
(f) |
|
||||
|
|
|||||
|
最後之最佳測試: row 0 ( O.F.) 中非基變數之係數無負數則其解為最佳解。 |
|
||||
-[3
附帶學習以 Excel 做矩陣的運算，請下載 Excel6.zip
5.3 簡算法之基本內涵
假設有某一 LP 模式如原題所示，其經過幾次的 iteration之後，最終得到下方右側所示之最終解。在原題與最終解之間存在著一些關係，本節即在說明此些隱涵之特殊意義。
|
原題 |
最終解 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
其中
|
Ｋ* =ＣBＢ-1 A = y*A |
Ａ* =Ｂ-1 A |
Ｓ* =Ｂ-1 |
|
b* =Ｂ-1 b |
y* =ＣBＢ-1 |
Ｚ*=ＣBＢ-1 b = y* b |
可觀察出以下兩個關係式：
|
ｔ*= t + y* T = [ -C 0 0 ] + [y*A y*I y*b] = [y*A-C y*I y*b] |
|
Ｔ*= Ｓ*T = Ｂ-1 T = [Ｂ-1A Ｂ-1I Ｂ-1b] |
結論：只要求得 y* 與 Ｓ* ，即可由
求出 
|
|
在原始矩陣中之 row j * |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
範例： |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
範例：
|
原始矩陣 |
最終矩陣 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
驗證
|
row 1: 原始矩陣 (row 1)*1 + (row 2)*1/3 + (row 3)*(-1/3) |
|||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||
|
row 2: 原始矩陣 (row 1)*0 +(row 2)*1/2 +(row 3)*0 |
|||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||
|
row 3: 原始矩陣 (row 1)*0 + (row 2)*(-1/3) + (row 3)*(1/3) |
|||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||
進一步觀察原題與最終解之列 ０(即 O.F.)
|
|
|
|
[t] = [-C 0 0] |
[t*] = [K*-C y* Z*] = [ y*A-C y* y*b] |
簡算法之精神即在找尋一組基變數及其相對應之可行解，使得列０之係數皆為非負實數。（max problem）
|
Ｚ*= y*ｂ |
───>>>>──── |
Ｙo = yｂ |
|
s.t. y*Ａ - C >= 0 y* >= 0 |
去掉 *，改 Ｚ 為 Ｙo 常數項移至 rhs ───>>>>──── |
s.t. yＡ >= C y >= 0 |
|
|
此為原題偶題關係之由來 |
|
