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

Presentation on theme: "第三章 單形法 Simplex Method 作業研究 二版 2009 © 廖慶榮."— Presentation transcript:

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

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

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

4 3.2 單形法的幾何意義 限制式邊界（constraint boundary） 角點解（corner-point solution）
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 3.2 單形法的幾何意義 範例3.1 此三個變數問題的角點解是三個限制式邊界的交點 A、B、……、J等10點是CPFS ˙
3.2 單形法的幾何意義 範例3.1 此三個變數問題的角點解是三個限制式邊界的交點 A、B、……、J等10點是CPFS ˙ C D E J I G H F B A 作業研究 二版 Ch.3 單形法

6 CPFS的重要性質 性質3.1 性質3.2 性質3.3 對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的CPFS
作業研究 二版 Ch.3 單形法

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

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

9 範例3.3之CPFS的搜尋順序 搜尋順序（A-D-F-I-J） ˙ C D E J I G H F B A 作業研究 二版 Ch.3 單形法

10 3.3 單形法的代數說明 使用單純法前，須先將所有限制式轉換為等式 典型例題之擴充形式：
3.3 單形法的代數說明 使用單純法前，須先將所有限制式轉換為等式 若限制式為≦，加上寬鬆變數(slack variable) 若限制式為≧，減去剩餘變數(surplus variable) 典型例題之擴充形式： 作業研究 二版 Ch.3 單形法

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

12 基解 基解（basic solution） 基變數（basic variable；BV） 基底（basis）
基解的幾何的意義即為擴充角點解 基變數（basic variable；BV） 基底（basis） 可行基解（basic feasible solution；BFS） BFS的幾何意義即為擴充CPFS 相鄰的（adjacent） 作業研究 二版 Ch.3 單形法

13 BFS的三個重要性質 性質3.4 性質3.5 性質3.6 對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的BFS
作業研究 二版 Ch.3 單形法

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

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

16 高斯消去法範例 考慮以下方程式系統（即迭代0）： 若 進入、 離開，則（即迭代1）： 作業研究 二版 Ch.3 單形法

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

18 單形法的表形式 作業研究 二版 Ch.3 單形法 第二、三個單形表

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

20 範例

21 單形法的表形式

22 單形法的表形式(續)

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

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

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

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

27 人工問題的圖形 當僅有兩個變數時： 等式限制式由「一條線」擴充至「半個面」。 大於等於限制式由「半個面」擴充至「全部面積」 ˙
8 10 6 4 2 P的可行區域（一條線） P(A)的可行區域 ˙ 作業研究 二版 Ch.3 單形法

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

29 具有下限值/範例 3.12 作業研究 二版 Ch.3 單形法

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

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

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

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

34 範例3.16 作業研究 二版 Ch.3 單形法

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

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

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

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

39 範例3.18 作業研究 二版 Ch.3 單形法

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

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

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

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

44 範例3.19 作業研究 二版 Ch.3 單形法

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

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

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