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

Slides:



Advertisements
Similar presentations
Chap 3 微分的應用. 第三章 3.1 區間上的極值 3.2 Rolle 定理和均值定理 3.3 函數的遞增遞減以及一階導數的判定 3.4 凹面性和二階導數判定 3.5 無限遠處的極限 3.6 曲線繪圖概要 3.7 最佳化的問題 3.8 牛頓法 3.9 微分.
Advertisements

楊學成 老師 Chapter 1 First-order Differential Equation.
工職數學 第四冊 第一章 導 數 1 - 1 函數的極限與連續 1 - 2 導數及其基本性質 1 - 3 微分公式 1 - 4 高階導函數.
不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
王 子 坊 《洛陽伽藍記》 主講教師:張其昀.
圓的一般式 內容說明: 由圓的標準式展出圓的一般式.
2011年全国中等职业学校医药卫生类专业 “创新杯”教师说课比赛
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
重庆大学制造工程研究所副所长 博士 重庆大学制造工程研究所副所长 杨育 博士  2002 Introduction to Operation Research 4 ADAPTING TO OTHER MODEL FORMS Thus far we have presented the details.
LINGO.
實驗計畫資料分析作業解答 何正斌 國立屏東科技大學工業管理系.
Linear Programming: Introduction and Duality
优化模型 教学目的: 初步认识优化模型的基本形式及掌握线性规划模型的建模及求解。 通过实例建模并求解,熟练掌握一些数学软件的使用。
Chapter 2 線性規劃.
Chapter 17 投資決策經濟分析.
1.1 線性方程式系統簡介 1.2 高斯消去法與高斯-喬登消去法 1.3 線性方程式系統的應用
第三章 單形法 Simplex Method 作業研究 二版 2009 © 廖慶榮.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
Methods 靜宜大學資工系 蔡奇偉副教授 ©2011.
第6章 線性規劃:單形法 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
簡捷法 簡捷法可用來找尋端點,並評估何者為最佳解。先考慮所有決策變數值皆為零的基本解,再算出是否有其他解的目標函數值較此點為佳。
對偶理論 「敏感度分析」,研究數學規劃問題中參數值(如各類係數)的改變對於最佳解以及目標函數值的影響。
第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
第一章 直角坐標系 1-1 數系的發展.
作業研究 第二章 線性規劃 林吉仁 著 高立圖書公司出版.
THE CHINESE UNIVERSITY OF HONG KONG EDD 5161R
GHANGDONG VOCATIONAL COLLEGE OF INDUSTRY&COMMERCE
敏感度與參數分析 Sensitivity and Parametric Analyses
非線性規劃 Nonlinear Programming
整數規劃 Integer Programming
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
15.3 極大與極小 附加例題 5 附加例題 6 © 文達出版 (香港 )有限公司.
赵 彤 运筹学模型与软件实践 Models and Software Practice of the Operations Research 赵 彤
Definition of Trace Function
小學四年級數學科 8.最大公因數.
CH1 我的第一個App與變數宣告.
第八章 網路模式 Network Models 作業研究 二版 2009 © 廖慶榮.
線性規劃模式 Linear Programming Models
第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.
Transportation Problem
期末考.
大綱:加減法的化簡 乘除法的化簡 去括號法則 蘇奕君 台灣數位學習科技股份有限公司
微積分網路教學課程 應用統計學系 周 章.
挑戰C++程式語言 ──第8章 進一步談字元與字串
6.6 線性規劃的單體法 單體法 (simplex method)
圖解配方法 張美玲老師製作.
第一章 直 線 ‧1-3 二元一次方程式的圖形.
運輸與指派問題 Transportation and Assignment Problems
反矩陣與行列式 東海大學物理系‧數值分析.
Commando War ★★☆☆☆ 題組:Problem Set Archive with Online Judge
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
第五章 對偶理論 Duality Theory 作業研究 二版 2009 © 廖慶榮.
第一章 直角坐標系 1-3 函數及其圖形.
線性規劃的其他演算法 Special Simplex Method
4-1 變數與函數 第4章 一次函數及其圖形.
第十三章 彩色影像處理.
在直角坐標平面上兩點之間 的距離及平面圖形的面積
10791: Minimum Sum LCM ★★★☆☆ 題組:Problem Set Archive with Online Judge
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
17.1 相關係數 判定係數:迴歸平方和除以總平方和 相關係數 判定係數:迴歸平方和除以總平方和.
Chapter 16 動態規劃.
第十七講 重積分 應用統計資訊學系 網路教學課程 第十七講.
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

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

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

p.3/ 單形法的幾何意義  典型範例的圖形 ˙ ˙ ˙ ˙ ˙ ˙ B C D E F A 作業研究 二版 Ch.3 單形法

p.4/ 單形法的幾何意義  限制式邊界( 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 單形法

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

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

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

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

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

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( 如 何找到移動的方向 )?

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

12 Introducing slack variables to functional constraints

13 The augmented form of the LP problem

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

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

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

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

作業研究 二版 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 是相鄰 ?)

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

20 How do we identify a CPFS in Algebra

21 How do we identify a CPFS in Algebra

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作業研究 二版 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 列係數,則仍無法判斷,須繼 續求解

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

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

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

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

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

p.46/45 範例 3.18

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

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

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

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

p.51/45 範例 3.19

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

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

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