第三章 單形法 Simplex Method © 廖慶榮 作業研究 二版 2009. p.2/45 章節大綱 1. 前言 2. 單形法的幾何意義 單形法的幾何意義 3. 單形法的代數說明 單形法的代數說明 4. 單形法的表形式 單形法的表形式 5. 特殊情況 特殊情況 6. 對於其他形式的調整 對於其他形式的調整.

Presentation on theme: "第三章 單形法 Simplex Method © 廖慶榮 作業研究 二版 2009. p.2/45 章節大綱 1. 前言 2. 單形法的幾何意義 單形法的幾何意義 3. 單形法的代數說明 單形法的代數說明 4. 單形法的表形式 單形法的表形式 5. 特殊情況 特殊情況 6. 對於其他形式的調整 對於其他形式的調整."— Presentation transcript:

1 第三章 單形法 Simplex Method © 廖慶榮 作業研究 二版 2009

2 p.2/45 章節大綱 1. 前言 2. 單形法的幾何意義 單形法的幾何意義 3. 單形法的代數說明 單形法的代數說明 4. 單形法的表形式 單形法的表形式 5. 特殊情況 特殊情況 6. 對於其他形式的調整 對於其他形式的調整 7. 大 M 法 大 M 法 8. 雙階法 雙階法 9. 單一人工變數技巧 單一人工變數技巧 10. 計算效率與電腦軟體 計算效率與電腦軟體  附錄 附錄 附錄 1. Excel 規劃求解 附錄 2. LINDO 軟體 作業研究 二版 Ch.3 單形法

3 p.3/45 3.2 單形法的幾何意義  典型範例的圖形 0 8 10 8 642 6 4 2 ˙ ˙ ˙ ˙ ˙ ˙ B C D E F A 作業研究 二版 Ch.3 單形法

4 p.4/45 3.2 單形法的幾何意義  限制式邊界（ constraint boundary ）  角點解（ corner-point solution ） 各限制式邊界所相交的點（圖中 A 、 B 、 C 、 D 、 E 、 F ） 角點可行解（ corner-point feasible solution ； CPFS ）： A 、 B 、 C 、 D 角點不可行解（ corner-point infeasible solution ）： E 、 F  相鄰的（ adjacent ） 若兩個 CPFS 有一個共同的限制式邊界，則彼此稱為相鄰 的。如 A 與 B 兩點是相鄰的  邊（ edge ） 相鄰兩 CPFS 的連接線段為此可行區域的邊。如 AB 、 BC 、 CD 、 DA 四個線段均為可行區域的邊。 作業研究 二版 Ch.3 單形法

5 p.5/45 3.2 單形法的幾何意義  範例 3.1 此三個變數問題的角點解是三個限制式邊界的交點 A 、 B 、 …… 、 J 等 10 點是 CPFS ˙ ˙ C D E ˙ ˙ ˙ ˙ ˙ ˙ ˙ J I G H F B A ˙ 作業研究 二版 Ch.3 單形法

6 p.6/45 CPFS 的重要性質  性質 3.1 對於一個具有最佳解的線性規劃問題，一定存 在一個為最佳解的 CPFS  性質 3.2 CPFS 的個數是有限的  性質 3.3 若一個 CPFS 無更佳的相鄰 CPFS ，則其為最佳解

7 作業研究 二版 Ch.3 單形法 p.7/45 單形法的幾何程序  根據 CPFS 的三個重要性質而來  步驟（對於標準形式） 1. 以原點作為起始 CPFS 。 2. 測試是否各相鄰的 CPFS 具有更佳的 Z 值。 若是，則至步驟 3 ； 否則停止，目前的 CPFS 即為最佳解。 3. 由目前的 CPFS ，沿著可行區域上 Z 值改進率最 大的邊移動至相鄰的 CPFS 。返回步驟 2 。

8 p.8/45 典型範例之 CPFS 的搜尋順序  搜尋順序（ A-D-C ） 作業研究 二版 Ch.3 單形法

9 p.9/45 範例 3.3 之 CPFS 的搜尋順序  搜尋順序（ A-D-F-I-J ） ˙ ˙ C D E ˙ ˙ ˙ ˙ ˙ ˙ ˙ J I G H F B A ˙

10 10 Questions to design the simplex algorithm  In algebra, How do we identify a CPFS ( 如何利用代數找到 一個 ( 幾何的 ) CPFS)? How to move from a CPFS to another ( 如何由 一個 CPFS 移動到另一個 CPFS)? Where is the move direction that improve Z( 如 何找到移動的方向 )?

11 p.11/45 3.3 單形法的代數說明  使用單純法前，須先將所有限制式轉換為等式 若限制式為≦，加上寬鬆變數 (slack variable) 若限制式為≧，減去剩餘變數 (surplus variable)  典型例題之擴充形式： 作業研究 二版 Ch.3 單形法 The augmented form of LP problem is equivalent to the original LP problem

12 12 Introducing slack variables to functional constraints

13 13 The augmented form of the LP problem

14 作業研究 二版 Ch.3 單形法 p.14/45 LP 的擴充形式  擴充形式（ augmented form ） 加上寬鬆變數或減去剩餘變數後的 LP 形式  擴充解 包含原始變數、寬鬆變數及剩餘變數  擴充角點解  擴充角點可行解

15 如何利用擴張問題找到 CPFS?  CPFS 是 n 個限制式邊界交會點  要先找到限制式邊界才能找到 CPFS  Q: 如何找到限制式邊界 ?  A: 利用原始變數、寬鬆變數 / 剩餘變數 作業研究 二版 Ch.3 單形法 p.15/45

16 16 Identify a boundary equation in the original model by using the augmented model  Case: the functional constraint  使用寬鬆變數 / 剩餘變數 找到限制式邊界

17 17 Identify a boundary equation in the original model by using the augmented model  Case: non-negative constraint  使用原始變數找到限制式邊界

18 作業研究 二版 Ch.3 單形法 p.18/45 基解  基解（ basic solution ） 擴充問題的代數解 基解的幾何的意義即為擴充角點解  基變數（ basic variable ； BV ） : 基解中不為 0 的變數  基底（ basis): 基解所有的基變數的集合  非基變數 (non-basic variable: NBV): 基解中為 0 的變數  可行基解（ basic feasible solution ； BFS ） BFS 的幾何意義即為擴充 CPFS  相鄰的（ adjacent ） BFS: 兩個 BFS 中只差一個非基變 數不同 (Q: 如何在代數中知道兩個 BFS 是相鄰 ?)

19 練習 : 利用擴張問題的代數解找到對應的 CPFS 作業研究 二版 Ch.3 單形法 p.19/45 0 8 10 8 642 6 4 2 ˙ ˙ ˙ ˙ ˙ ˙ B C D E F A (4,3) (0,5) (6,0) (0,0)

20 20 How do we identify a CPFS in Algebra

21 21 How do we identify a CPFS in Algebra

22 作業研究 二版 Ch.3 單形法 p.22/45 BFS 的三個重要性質  性質 3.4 對於一個具有最佳解的線性規劃問題，一定存 在一個為最佳解的 BFS  性質 3.5 BFS 的個數是有限的  性質 3.6 若一個 BFS 沒有更佳的相鄰 BFS ，則其為最佳解

23 p.23/45 單形法代數程序求解典型範例 作業研究 二版 Ch.3 單形法

24 p.24/45 3.4 單形法的表形式 (Tabular Form)  高斯消去法（ Gaussian elimination method ） 利用基本代數運算將原方程式系統轉換為常態形式 常態形式（ proper form ）：基變數僅出現在其所在 的方程式，且係數為 1 ，而不會出現在其他方程式內 基本代數運算（ elementary algebraic operation ）  一列可乘以一個常數  一列與常數的乘積可加到另一列或被另一列減去 作業研究 二版 Ch.3 單形法

25 p.25/45 高斯消去法範例 考慮以下方程式系統（即迭代 0 ）： 若 進入、 離開，則（即迭代 1 ）：

26 作業研究 二版 Ch.3 單形法 p.26/45 基本代數運算  較有效率的計算方式： 一律使用加法，而不用減法，以避免混淆 視計算的難易，而決定使用原基準列（離開變 數之列）或新基準列

27 作業研究 二版 Ch.3 單形法 p.27/45 單形法的表形式  首先將典型範例的擴充形式改寫如下：  第一個單形表

28 作業研究 二版 Ch.3 單形法 p.28/45 單形法的表形式  第二、三個單形表

29 作業研究 二版 Ch.3 單形法 p.29/45 單形法表形式的求解步驟  起始步驟： 加上寬鬆變數。 在起始 BFS 中，讓寬鬆變數為該限制式的 BV ，並讓所有 原始變數為 NBV 。  最佳性測試： 若所有 Z 列係數均為非負值，則停止；否則繼續。  迭代步驟： 決定進入變數：選擇具最負 Z 列係數的 NBV 為進入變數。 決定離開變數：以最小比率測試，選擇比率最小的 BV 。 產生新單形表：利用高斯消去法。 返回最佳性測試。

30 p.30/45 3.5 特殊情況 1. 進入變數平手 任選其一 2. 離開變數平手（退化解） 此時，在下一個單形表，未被選擇離開的 BV 必為零 退化基變數（ degenerate BV ） 退化可行基解（ degenerate BFS ）。 理論上，退化 BFS 有可能產生循環，使得 Z 值不變， 但實際運算時幾乎不可能發生。 作業研究 二版 Ch.3 單形法

31 p.31/45 3.5 特殊情況 3. 無離開變數（無窮解） 若任何單形表，其進入變數之欄無任何正值 實務上，若遇無窮解，則代表該 LP 模式有誤 4. 最佳單形表含 Z 列係數 =0 的 NBV （多重最佳解） 所得到兩個解的凸組合均為最佳解。 作業研究 二版 Ch.3 單形法

32 p.32/45 3.6 對於其他形式的調整 1. 極小化問題  轉換法 將原問題轉換為極大化的問題 使用轉換法時，單形表 Z 欄的 Z 列係數將是 -1 ，因此 原問題的 Z 值 = - （最佳單形表中的 Z 值）  直接法 直接改變最佳性測試和決定進入變數的規則： 最佳性測試：若所有 Z 列係數均為非正值，則停止；否則 則繼續。 迭代步驟：  決定進入變數：選擇具最大 Z 列係數的 NBV 為進入變數。 作業研究 二版 Ch.3 單形法

33 p.33/45 3.6 對於其他形式的調整 2. RHS 為負值 左右兩邊分別乘以 3. 等式限制式 必須加上人工變數（ artificial variable ） 以此 AV 作為該等式的起始 BV 4. 大於等於限制式 先減去剩餘變數（ surplus variable ）再加上 AV 以此 AV 作為該限制式的起始 BV 作業研究 二版 Ch.3 單形法

34 p.34/45 人工問題的圖形  當僅有兩個變數時： 等式限制式由「一條線」擴充至「半個面」。 大於等於限制式由「半個面」擴充至「全部面積」 0 8 10 8 642 6 4 2 P 的可行區域（一條線） P(A) 的可行區域 ˙

35 p.35/45 3.6 對於其他形式的調整 5. 變數允許為負值 具有下限值 其中下限值為負值。我們可讓 此方法亦適用於當下限值為正值時 作業研究 二版 Ch.3 單形法

36 p.36/45 具有下限值 / 範例 3.12

37 作業研究 二版 Ch.3 單形法 p.37/45 無下限值 / 範例 3.13

38 p.38/45 3.7 大 M 法  兩個處理人工變數的方法： 大 M 法（ big-M method ） 雙階法（ two-phase method ）  目的 盡量讓人工變數為零，以使所得到的人工問題 最佳解即為原問題的最佳解 作業研究 二版 Ch.3 單形法

39 p.39/45 大 M 法求解程序  作法 對人工變數 (AV) 在目標函數中給予極大的懲罰， 以使得在單形法的運算過程中，盡可能降低 AV 之值（最好為零） 對於 max 問題，讓 AV 的目標函數係數為 -M 對於 min 問題，讓 AV 的目標函數係數為 M  建立第一個單形表 第一個單形表並不符合常態形式，而須以高斯 消去法還原（ restore ）列，才能得到起始 BFS 。 之後，即可完全依一般單形法處理

40 作業研究 二版 Ch.3 單形法 p.40/45 大 M 法結果的分析  情況 A ：找到問題 P(M) 的最佳解 若所有 AV=0 ，則此解亦為問題 P 的最佳解 若有任何 AV≠0 ，則問題 P 無可行解  情況 B ：問題 P(M) 是無窮解 若所有 AV=0 ，則問題 P 亦為無窮解 若無窮解的條件來自最負的 Z 列係數（對 max 問 題），且有任何 AV≠0 ，則問題 P 無可行解 若非來自最負的 Z 列係數，則仍無法判斷，須繼 續求解

41 p.41/45 範例 3.16 作業研究 二版 Ch.3 單形法

42 p.42/45 範例 3.16 / 單形表 1-3 作業研究 二版 Ch.3 單形法

43 p.43/45 範例 3.16 / 單形表 4-5 作業研究 二版 Ch.3 單形法

44 p.44/45 3.8 雙階法  兩方法之差異 大 M 法：藉由大 M 的係數區分 AV 和其他變數 雙階法：以兩階段區分 AV 和其他變數（較易）  第一階段 僅考慮 AV ，因此僅需用係數 1 或 -1 即可 第一個單形表不符合常態形式，因此須以高斯 消去法還原 Z 列 第一階段問題 P(I) ：  一定會求得最佳解，不可能是無窮解或無可行解  當得到 P(I) 的最佳解時，若所有 AV=0 ，則至第二階 段；若有任何 AV≠0 ，則原問題無可行解 作業研究 二版 Ch.3 單形法

45 p.45/45 3.8 雙階法  第二階段 將 AV 全部刪除（若有 AV 仍為基變數（其值必為 零）時，則仍必須暫時保留該 AV ） 利用 P(I) 的最佳解作為 P(II) 的起始 BFS 回復原問題的目標函數係數，並還原 Z 列 作業研究 二版 Ch.3 單形法

46 p.46/45 範例 3.18

47 作業研究 二版 Ch.3 單形法 p.47/45 範例 3.18 P(I) 的單形表 1-2

48 作業研究 二版 Ch.3 單形法 p.48/45 範例 3.18 P(I) 的單形表 3-4

49 作業研究 二版 Ch.3 單形法 p.49/45 範例 3.18 P(II) 的單形表

50 p.50/45 3.9 單一人工變數技巧  步驟 1. 對於≧或≦限制式，分別減去一個各自的剩餘變 數，再分別加上一個共同的 AV ，然後於左右兩 邊分別乘以 -1 。 2. 目標函數與雙階法的第一階段問題相同。 3. 在 1st 單形表中，以 step 1 所加的剩餘變數為 BV ， 並讓 AV 為進入變數，然後選擇比率最大的變數 為離開變數，即可得到 P(A) 的一個 BFS 。 4. 以大 M 法或雙階法繼續求解該問題。 作業研究 二版 Ch.3 單形法

51 p.51/45 範例 3.19

52 作業研究 二版 Ch.3 單形法 p.52/45 範例 3.19 / 續

53 p.53/45 3.10 計算效率與電腦軟體  影響單形法計算時間的因素 功能限制式的個數 變數的個數 非零係數的比例  單形法（ LP ）的常用電腦軟體 LINDO （最普及） Excel 規劃求解功能 CPLEX （對於大型問題最有效率） 作業研究 二版 Ch.3 單形法

54 p.54/45 附錄  請參見書本： 附錄 3.1 Excel 的規劃求解 附錄 3.2 LINDO 軟體 作業研究 二版 Ch.3 單形法