Chapter 3 線性規劃單形法

“眾裡尋他千百度， 驀然回首， 那人卻在燈火闌珊處。” —辛棄疾《青玉案‧元夕》 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

and that has made all the difference.” “森林內的兩條分叉路， 我選擇了人跡罕至的一條， 從此一切變得不一樣。” —佛羅斯特 “Two roads diverged in a wood, and I took the one less traveled by, and that has made all the difference.” —Robert Frost(1874 – 1963) “The Road Not Taken” 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

為什麼引用這兩首詩？ 辛棄疾的詩是尋找「那人」，Frost的詩是選擇「人跡」的路徑。 單形法是尋找「數量」的解答，是選擇「數學」的路徑。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

「數學」和「人」有什麼不同？ 「數學」沒有「驀然」、沒有「燈火闌珊」、沒有「罕至」、沒有「一切變得不一樣」。 「數量」是有些「畫意」，但是缺乏「詩情」。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

LP的一般模式如下: 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

標準型式(Standard form)： 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

LP的標準型式：第3章 以矩陣表示 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

LP的標準型式：第3章 X A b c d 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

LP的正規型式：第3章 以矩陣表示 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

正規型式(canonical form)： 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

LP標準型式 LP正規型式 LP的正規型式： Max/Min xN xB I Z 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

求極小(Min)的LP問題如下： 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

肥料生產問題圖形1/2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

肥料生產問題圖形2/2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

基解 Basic Solution * x1 4 A F (0,6) (4,6) 2x2  12 D (4,3) B (0,0) C (2,6) E A (0,6) F (4,6) 2x2  12 D (4,3) 基解 B (0,0) C (4,0) 3x1 + 2x2  18 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

基可行解 Basic Feasible Solution x1 4 (2,6) E A (0,6) F (4,6) * 2x2  12 D (4,3) 基可行解 B (0,0) C (4,0) 3x1 + 2x2  18 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

3.3 單形演算法 首先是求極小LP 問題 Min cTx 的單形演算法： 找到一個基可行解(正規型式且 ≧0)。 找到一個基可行解(正規型式且 ≧0)。 檢查是否最佳解：若 ≧0，則最佳解為xB = ，xN = 0，為最佳目標函數值，結束。 從非基變數 xN 當中選擇一個進入變數 如果 xt 行的係數 均為零或負數，則本題是無界的，結束。否則，從基變數xB中選擇一個退出變數，利用比值檢定找 將xt行的係數 中正數除右手常數 ，取其比值最小的，其對應的基變數xk即為退出變數。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

軸運算(pivot)：以為軸元素，利用基本列運算： 新基變數xB，及新的 xN、 。回到第2步。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

例題1 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答1/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答2/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答3/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

圖3.2 求極大LP問題單形法 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

例題2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答1/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答2/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答3/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答4/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答5/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答6/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

例題3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答1/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答2/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答3/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答4/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答5/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答6/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

修正單形演算法(矩陣運算) x A b c d 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

例題4 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答1/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答2/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答3/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答4/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

解答5/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】

求極大的LP問題的的修正單形演算法步驟： 決定基變數 xB，並檢查 是否大於等於0。 計算 ，若 ，則為最佳解，停止。 找 中最大者，令為進入變數 xt。 計算 。若 ，則問題無界，停止。 計算 ，利用比值檢定找退出變數 xr。 令xB=xB-{xr}+{xt}，到第1步。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】