定義在 n 維空間之中,n 個獨立的等式可以決定一個點的座標, ( 注意是可以, 但不必然, 因為可能有平行或歪斜的情況 ) 則這 n 個等式稱為該點的定義方程式 (defining equation) 例典型例題限制式邊界方程式 x 1 4 2x x 1 + 2x 2 18 x

Size: px

Start display at page:

Download "定義在 n 維空間之中,n 個獨立的等式可以決定一個點的座標, ( 注意是可以, 但不必然, 因為可能有平行或歪斜的情況 ) 則這 n 個等式稱為該點的定義方程式 (defining equation) 例典型例題限制式邊界方程式 x 1 4 2x x 1 + 2x 2 18 x"

桶沙
5 years ago
Views:

1 Chapter 5 修訂單形法 (revised simplex method) 5.1 單形法的基礎本小節的前半段都是前面章節講過, 只是強調可以推廣到 n 變數的一般 LP 問題, 因此重覆的部份不再詳述, 請各位自行參閱教科書, 或者看第 3 與第 4 章定義任意限制式的邊界方程式 (boundary equation) 就是把限制式之中的 = 或者都換成等號 ( 等式是半平面的邊界 ) 例限制式 3x 1 + 2x 2 18 x 2 0 x 1 + 2x 2 5 邊界方程式定義在 n 維空間之中, 任意等式 a 1 x 1 + a 2 x a n x n = b 都可以稱為空間之中的超平面 (hyperplane) 超平面把 n 維空間分割成兩個部份, 一邊的點代入方程式得到的數值 b, 另一邊的點代入方程式得到的數值 b 1

2 定義在 n 維空間之中,n 個獨立的等式可以決定一個點的座標, ( 注意是可以, 但不必然, 因為可能有平行或歪斜的情況 ) 則這 n 個等式稱為該點的定義方程式 (defining equation) 例典型例題限制式邊界方程式 x 1 4 2x x 1 + 2x 2 18 x 1 0 x 2 0 角點定義方程式 2

3 定理在非退化之下, 相鄰角點只有一個定義方程式是不同的定理若 LP 是單一最佳解, 則它一定是可行角點 ; 若 LP 是多重最佳解, 則至少兩個相鄰角點是最佳解定理在有最佳解的 LP 問題之中, 若某可行角點旁邊沒有 Z 值較優的相鄰角點, 則它就是最佳解由於多個變數就無法圖解, 必需使用方程組求解, 因此加入差額變數成為等式系統一個 m 限制式 n 變數的標準式 LP 會變成 m 等式 n + m 變數的聯立方程組 : a 11 x 1 + a 12 x a 1n x n + x n+1 = b 1 a 21 x 1 + a 22 x a 2n x n + x n+2 = b a m1 x 1 + a m2 x a mn x n + x n+m = b m 圖形中的角點, 在擴充問題之中對應的解稱為基解, 基解就是角點的擴充解, 因此所有角點的性質與定理可以直接應用在擴充問題的基解 3

4 重要觀念以下定義是為了說明基解與角點之間的代數關係如前所述, 每個角點是 n 條邊界方程式的交點, 這 n 條方程式是角點的定義方程式, 問題是在擴充問題之中, 如何得知哪些方程式是角點的定義方程式? 定義在原始問題的每一個限制式與非負限制, 在擴充問題方程組之中, 都有一個對應的指標變數 (indicated variable), 使得 ( 重要!!) 限制式等式成立時 ( 即邊界 ), 擴充問題方程組某個變數 ( 對應的指標變數 ) 為 0 例典型例題限制式擴充問題限制式邊界方程式指標變數 x 1 4 2x x 1 + 2x 2 18 x 1 0 x 2 0 4

5 若是非標準的限制式, 說明如下 : 1. 限制式是等式, 指標變數是人工變數例如限制式 3x 1 + 2x 2 = 18, 擴充問題變成 3x 1 + 2x 2 + x 5 = 18, 限制式等式成立時 x 5 = 0 2. 限制式, 指標變數是加入的兩個變數的值合起來當作一個變數例如限制式 0.6x x 2 6, 擴充問題變成 0.6x x 2 x 5 + x 6 = 0, 限制式等式成立時 x 5 + x 6 = 0 ( 兩個正數加減之後仍然當作變數, 這概念在討論 x j 沒有非負限制時, 使用 x + j x j 道理完全一樣 ) 為了不混淆, 以下專心討論標準式 LP 的情況前一章已經談過,m 個方程式聯立, 一般情形可以設定求解某 m 個變數, 因此在全部 n + m 個變數之中, 可以令某 n 個變數為 0, 也就是非基變數, 再來求解 m 個變數的值, 也就是基變數數值非負就是可行基解, 否則不可行 5

6 現在我們可以把角點基解方程組可行性單形法這些概念整合起來說明如下 : 1. 在 n 維空間之中,n 個等式同時成立可以決定一個點的座標, 而這 n 個等式又各自有對應的指標變數, 限制式等式成立時指標變數為 0, 因此這個點的非基變數已知方程組求解其它 m 個變數可得出基變數的值, 由數值的正負可判斷這個角點所對應的基解可行或不可行 2. 相鄰角點只有一個定義方程式不同, 相當於只有一個非基變數不同, 而單形法每次轉軸是換一個非基變數, 因此的確是搜尋相鄰角點對應的基解 3. 角點其實相當多, 為了不盲目搜尋, 在聯立方程組之中, 單形法首先確保起始的基變數值都是正 ( 右手邊值為正值 ), 用 Z 列之中 x j 的係數保證下一個相鄰角點是更好的基解,Z 值上升, 同時轉軸之前使用最小比值測試, 保證所有的基變數還是維持正值, 最後高斯消去法求得 proper form 保證讀出來所有數值都是正確的 6

7 例典型例題, 先寫出擴充問題, 再練習以下, 尤其觀察 (0, 0) (0, 6) (2, 6) 此外特別注意最後每個基解的聯立方程組是如何寫出來的, 下一小節會用到角點定義方程式基解非基變數聯立方程組 7

8 5.2 單行法的矩陣表示與基本內涵要用電腦演算, 必需利用矩陣運算首先介紹 LP 的矩陣表示, 本小節以標準式說明一個 n 變數 m 限制式的標準式 LP 加入 m 個差額變數之後一般式如下 : Maximize Z = c 1 x 1 + c 2 x c n x n subject to a 11 x 1 + a 12 x a 1n x n + x n+1 = b 1 a 21 x 1 + a 22 x a 2n x n + x n+2 = b and a m1 x 1 + a m2 x a mn x n x j 0, j 我們可以令向量與矩陣如下 ( 注意維數 ):c = + x n+m = b m ] [ ] [c 1 c 2 c n, c s = 0 0 0, a 11 a 12 a 1n b 1 x 1 a A = 21 a 22 a 2n......, b = b 2., x = x 2., x s = a m1 a m2 a mn b m x n x n+1 x n+2. x n+m 8

9 則 LP 與它的擴充問題可以分別使用矩陣表達如下 : Maximize Z = cx Maximize Z = cx + c s x s subject to Ax b subject to Ax + I m x s = b and x 0 and x 0, x s 0 擴充問題之中, 將向量 c c s, 矩陣 A I 與向量 x x s 合併之後模式如下 : ] Maximize Z = [c c s x x s subject to and [ A ] I x = b x s x 0 x s 9

10 例將典型例題以矩陣表示 Maximize Z = 3x 1 + 5x 2 subject to x 1 4 2x x 1 + 2x 2 18 and x j 0, j 10

11 單形法的每一回合, 我們會從 n + m 個變數之中選定 m 個基變數,n 個非基變數, 基變數所組成的向量記為 x B, 非基變數的向量記為 x N, 以下圖幫助理解 : 原始變數 n 個差額變數 m 個 m 條 m + n 個變數求解等式 m 個基變數, 記為向量 x B n 個非基變數, 記為向量 x N 11

12 在 LP 之中, 把項次先後順序重新排列, 基變數 x B 排在前面, 非基變數 x N 排在後面, 這樣一來 Z 列係數 c 與 c s 也會依據這個順序重新排列 ( 標準式之中 c s = 0), 與基變數相乘的係數記為向量 c B, 與非基變數相乘的係數記為向量 c N, 原本是 Z = cx + c s x s, 排好之後變成 Z = c B x B + c N x N c 有 n 個係數 c s 有 m 個係數乘 x B 的 m + n 個係數乘 x N 的 m 個係數, 記為向量 c B n 個係數, 記為向量 c N 12

13 限制式方程組一樣的方式重新排列順序, 把矩陣 A 與 I 一行一行直的來看, 與基變數相乘的行組成矩陣 B, 與非基變數相乘的行組成矩陣 N, 原本是 Ax + Ix s = b, 排好之後變成 Bx B + Nx N = b A 有 n 行 I 有 m 行 m + n 個行乘 x B 的乘 x N 的 m 個行, 記為矩陣 B n 個行, 記為矩陣 N 例典型例題擴增之後, 若給定基變數是 (x 4, x 1, x 2 ), 將問題重新排序並以矩陣表示 13

14 重要觀念每一回合基變數選定之後, 將 LP 問題依基變數與非基變數重新排好, 方程組變成 Bx B + Nx N = b, 又因為非基變數 x N = 0, 此時方程組是 m 限制式 m 變數, 在單形法的設計之下, 方程組有唯一解, 且 B 1 存在, 因此基變數的值必然可以這樣計算得到 :x B = B 1 b 重要觀念目標函數重新排好之後變成 Z = c B x B + c N x N, 因為非基變數 x N = 0, 因此目標函數值必然可以這樣計算得到 :Z = c B x B = c B B 1 b 以上已經幾乎把電腦如何計算與運作講解完畢, 只差沒有講到如何選出基變數, 選的方式請見 5.3 小節單形法的每一回合基變數與非基變數互換一個, 因此 x B c B 與 B 的行, 都只有一個是不同的單形法在電腦之中計算瓶頸是每一回合的 B 1, 其餘的運算只是選出排序向量矩陣乘法, 這些運算對於電腦來說是很快的重要觀念有兩個地方很容易犯錯, 一定要注意!! 第一是 x B 的順序與 c B 還有 B 的行的順序要完全一致, 答案才正確第二是這邊的 Z = c B x B + c N x N 都沒有經過移項, 不要忘記例典型例題, 給定三個回合的基變數是 (x 3, x 4, x 5 ) (x 3, x 2, x 5 ) (x 3, x 2, x 1 ), 使用矩陣運算分別求出每一回合的基變數值與目標函數值 14

15 重要觀念以下說明單形法表格運算與矩陣運算之間的關係標準式的 LP 加入差額變數 x s 之後, 填入起始表格如下 : Z x x s RHS Z 1 c c s (= 0) 0 1 列 x B 0 A I b m 列 ( 由分割矩陣原理, 可以視為 1 列 ) 表格其實就是方程組求解的形式, 寫成矩陣是 [ ] Z [ ] 1 c 0 0 x = 0 A I b x s 15

16 由前述推導的一般式, 每一回合 x B 決定之後, 把 B 與 c B 選好, 則 x B = B 1 b, 且 Z = c B B 1 b, 填入表格得出 Z x x s RHS Z 1 c B B 1 b x B 0 B 1 b 重要關念因為所有的運算都是列運算, 觀察上下兩個表格, 可以得知 : 第一, 新的 x B 這一列必然是起始表格的 x B 列乘以 B 1 ( 只是每一回合 B 1 不同 ) 第二, 新的 Z 列必然是起始表格的 x B 列乘以 c B B 1 之後, 加過來的列運算要整列一起算, 因此得出空白的部份, 且方程組寫成矩陣是 : 例續上頁例題, 使用矩陣運算把典型例題最終表格完成 16

17 例給定以下的線性規劃問題, 假設對限制式加入差額變數 x 4 x 5 x 6 若已知最佳解的基變數是 (x 2, x 6, x 3 ), 使用矩陣乘法把最終表格完成, 並寫出最佳解的定義方程式 Maximize Z = x 1 x 2 + 2x 3 subject to 2x 1 2x 2 + 3x 3 5 x 1 + x 2 x 3 3 x 1 x 2 + x 3 2 and x j 0, j 17

18 以上的討論非標準式同樣可以應用, 首先特別注意到起始基變數是哪些, 它們在方程組的行組成矩陣 I, 起始的時候 I 並不像標準式起始時是連在一起的, 若是怕弄錯也可以先更換 x j 的順序, 讓它們一開始排成單位矩陣比較不會弄錯此外, 過去在大 M 法與兩階段法計算的時候, 若人工變數 x a 離開基底就不再計算, 沒有保留住 B 1 的資訊, 在使用矩陣計算的時候, 人工變數的計算不能省略重要觀念學會矩陣運算之後, 應該對於兩階段法在第二階段時只更換目標函數, 有進一步的理解, 因為 x B 這列的所有數值包括 B 1 A 與 B 1 都不需變動重要觀念以下介紹單形法表格運算的基本內涵 (fundamental insight) 18

19 觀察典型例題的表格運算過程之中最重要的部份 : x B Z x 1 x 2 x 3 x 4 x 5 RHS

20 定理 ( 基本內涵 ) 表格運算都是列運算, 觀察得知, 不論單形法運算多少回合, 所做的列運算都可以從起始基變數對應的 m 個行看出如何運算 ( 可推廣至非標準式, 但 x a 離開基底之後, 運算不能省略 ) 重要觀念 ( 這個觀念在第六章有非常大的幫助 ) 觀察起始表格, 尤其是 Z 列係數不論單形法運算多少回合, 每一回合都是限制式方程組的某些列乘以某些係數之後, 加過去 Z 列, 並維持 proper form, 一直加到 Z 列係數都沒有負值, 得到最佳解到底每一個方程式是乘以多少加到 Z 列呢? 一開始並不知道所以設為變數典型例題共有三個限制式, 假設這三個限制式各乘以 y 1 y 2 y 3 再加到 Z 列, 直到 Z 列係數非負為止, 上述的過程寫成數學模式是 : 20

21 5.3 修訂單形法 (revised simplex method) 大型的線性規劃問題就算是電腦也需要花許多時間運算, 本小節說明如何節省運算時間回顧單形法每一回合所需要的計算, 以矩陣表示如下 ( 標準式之中 c s = 0): Z x x s RHS Z 1 c B B 1 A c c B B 1 c s c B B 1 b x B 0 B 1 A B 1 B 1 b 如前所述, 給定 x B, 選好 B 與 c B, 首先計算 B 1, 接著是 x B = B 1 b 為了要判斷是否最佳, 所以 Z 列係數 c B B 1 與 c B B 1 A c 也要全部算出來, 假設不是最佳解, 選 Z 列係數負最大的 x k 為入基變數 Z 值等到最佳解再算即可 21

22 但是 B 1 A 呢? 想像一下有個原始變數的問題, 此時矩陣 B 1 A 有行, 假如 x k 是原始變數, 接下來要轉軸, 思考一下發現這行之中用得上的只有一行因此單形法的第一個修訂, 就是省略不必要的 B 1 A 計算, 選好入基變數 x k 之後, 只要計算這一行 B 1 A k 就可以進行最小比值測試 ; ( 假如入基變數 x k 是差額變數, 不用計算 B 1 A, 從 B 1 就可以進行最小比值測試 ) 單形法的演算之中, 最消耗演算時間的就是計算每一回合的 B 1 當然我們從 A 與 I 的行選定 B 之後, 利用擴充單位矩陣與高斯消去法可以算出 B 1, 但是大型的問題限制式很多條,B 矩陣相當大, 要用這樣的方式計算 B 1 很耗時間注意到, 每一回合的 B 矩陣跟上一回合只有一行不同, 其它行都相同因此單形法的第二個修訂, 就是使用列運算快速算出 B 1, 不需擴充矩陣從頭算到尾概念如下, 以典型例題演算過程的最後一回合舉例說明 22

23 1 0 0 第二回合基變數是 (x 3, x 2, x 5 ),B 1 1 = 0 0 2, 且 x B = x 3 x 2 x 5 4 = B 1 b = 6, 6 假設已經計算 Z 列發現 x 1 的係數 3 是負最大的係數接下來計算 B 1 1 A 1 = = 0, 就可以與比值測試 6 由最小比值測試 4/1 = 4 與 6/3 = 2 選最小, 得知第三限制式的基變數 x 5 是出基變數, 1 0 因此剛剛算的 B 1 A = 0 下一回合要變成 0 才會是 proper form 3 1 觀察數值得知, 第三列乘以 1 3, 第二列不用計算, 第三列乘以 1 3 加到第一列即可這樣就知道下一回合的基變數是 (x 3, x 2, x 1 ), 且新的 B 1 是 : 23

24 小型問題手算時, 以上述的方法就可以計算下一回合的 B 1, 但是電腦的演算必需使用矩陣乘法, 以下介紹電腦的記算方式定義單位矩陣配合所需的列運算更改數值之後, 所得出的矩陣稱為基本矩陣 (elementary matrix), 記為矩陣 E 例上述的演算說明之中, 第三列乘以 1 3, 第二列不用計算, 第三列乘以 1 3 加到第一列, 寫出矩陣 E 並計算 EB 1 定理基本矩陣乘以任何矩陣 ( 不限定方陣 ), 結果就是對該矩陣作列運算最後, 在計算 Z 列係數時, 因為只要是基變數, 它的 Z 列係數一定是 0, 因此單形法的第三個修訂, 就是計算 Z 列係數時只需計算非基變數 x N 的部份綜合上述三項修訂, 計算較少的 revised simplex method 演算法如下 : 24

25 演算法 revised simplex method 步驟 0 找出起始基變數 x B, 選出 B 與 c B, 起始 B 1 = I, 計算 x B 與 Z 值步驟 1 計算 x N 的 Z 列係數, 都是非負值就寫出最佳解與計算最佳值 Z, 否則步驟 2 進行一回合的演算 : 1. 選 Z 列係數負最大的為入基變數 x k 2. 計算 B 1 A k, 進行最小比值測試, 再判斷所需的列運算得出矩陣 E 3. 計算 EB 1 得出新的 B 1, 再計算新的 x B = B 1 b 更換基變數, 回步驟 1 重要觀念修訂單形法可以直接應用在非標準式 LP, 只要起始 x B 配合起始 B 1 = I, 而在兩階段法進入第二階段時, 只有目標函數改變此外容易犯錯的是, 此時 c s 不是零向量, 因此在算 Z 列時是 c B B 1 c s 重要觀念從修正單形法可得知, 計算 B 1 A 可以只計算某一行 B 1 A k, 可推廣至 Z 列係數, 只想知道某個係數時只需計算 c B B 1 A k c k 25

26 例使用 revised simplex method 求解典型例題 Maximize Z = 3x 1 + 5x 2 subject to x 1 4 2x x 1 + 2x 2 18 and x j 0, j 26

27 例使用 revised simplex method 配合兩階段法求解放射線治療問題 Minimize Z = 0.4x x 2 subject to 0.3x x x x 2 = 6 0.6x x 2 6 and x j 0, j 27

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0

定義在 n 維空間之中,n 個獨立的等式可以決定一個點的座標, ( 注意是 可以, 但不必然, 因為可能有平行或歪斜的情況 ) 則這 n 個等式稱為該點的定義方程式 (defining equation) 例典型例題 限制式 邊界方程式 x 1 4 2x x 1 + 2x 2 18 x

定義在 n 維空間之中,n 個獨立的等式可以決定一個點的座標, ( 注意是可以, 但不必然, 因為可能有平行或歪斜的情況 ) 則這 n 個等式稱為該點的定義方程式 (defining equation) 例典型例題限制式邊界方程式 x 1 4 2x x 1 + 2x 2 18 x