单形法代数程序求解典型范例课件.ppt

1、第三章第三章單形法單形法Simplex Method 廖慶榮作業研究 二版 2009p.2/45章節大綱章節大綱1.前言2.單形法的幾何意義3.單形法的代數說明4.單形法的表形式5.特殊情況6.對於其他形式的調整7.大M法8.雙階法9.單一人工變數技巧10.計算效率與電腦軟體o 附錄n附錄1.Excel規劃求解n附錄2.LINDO軟體作業研究作業研究 二版二版 Ch.3 單形法單形法 p.3/453.2 單形法的幾何意義單形法的幾何意義 o 典型範例的圖形 08108642642BCDEFA123218xx12210 xx52Z 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.4/45

2、3.2 單形法的幾何意義單形法的幾何意義o 限制式邊界（constraint boundary）o 角點解（corner-point solution）n各限制式邊界所相交的點（圖中A、B、C、D、E、F）n角點可行解（corner-point feasible solution；CPFS）：A、B、C、Dn角點不可行解（corner-point infeasible solution）：E、Fo 相鄰的（adjacent）n若兩個CPFS有一個共同的限制式邊界，則彼此稱為相鄰的。如A與B兩點是相鄰的o 邊（edge）n相鄰兩CPFS的連接線段為此可行區域的邊。如AB、BC、CD、DA四個線段

3、均為可行區域的邊。作業研究作業研究 二版二版 Ch.3 單形法單形法 p.5/453.2 單形法的幾何意義單形法的幾何意義o 範例範例3.1n 此三個變數問題的角點解是三個限制式邊界的交點n A、B、J等10點是CPFS CDEJIGHFBA1x3x2x作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.6/45CPFS的重要性質的重要性質o 性質性質3.1n 對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的CPFSo 性質性質3.2n CPFS的個數是有限的o 性質性質3.3n 若一個CPFS無更佳的相鄰CPFS，則其為最佳解作

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

5、CPFS的搜尋順序的搜尋順序o 搜尋順序（A-D-F-I-J）CDEJIGHFBAp.10/453.3 單形法的代數說明單形法的代數說明o 使用單純法前，須先將所有限制式轉換為等式n 若限制式為，加上寬鬆變數(slack variable)n 若限制式為，減去剩餘變數(surplus variable)o 典型例題之擴充形式：121231241234Max 78s.t.2 10 32 18 ,0Zxxxxxxxxx x x x作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.11/45LP的擴充形式的擴充形式o 擴充形式（augment

6、ed form）n 加上寬鬆變數或減去剩餘變數後的LP形式o 擴充解n 包含原始變數、寬鬆變數及剩餘變數o 擴充角點解o 擴充角點可行解作業研究作業研究 二版二版 Ch.3 單形法單形法 p.12/45基解基解o 基解（basic solution）n 基解的幾何的意義即為擴充角點解o 基變數（basic variable；BV）o 基底（basis）o 可行基解（basic feasible solution；BFS）n BFS的幾何意義即為擴充CPFSo 相鄰的（adjacent）作業研究作業研究 二版二版 Ch.3 單形法單形法 p.13/45BFS的三個重要性質的三個重要性質o 性質性

7、質3.4n 對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的BFSo 性質性質3.5n BFS的個數是有限的o 性質性質3.6n 若一個BFS沒有更佳的相鄰BFS，則其為最佳解p.14/45單形法代數程序求解典型範例單形法代數程序求解典型範例 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.15/453.4 單形法的表形式單形法的表形式o 高斯消去法（Gaussian elimination method）n 利用基本代數運算將原方程式系統轉換為常態形式n 常態形式（proper form）：基變數僅出現在其所在的方程式，且係數為1，而不會出現在其他方程式內n 基本代數運算（e

8、lementary algebraic operation）o 一列可乘以一個常數o 一列與常數的乘積可加到另一列或被另一列減去作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.16/45高斯消去法範例高斯消去法範例n 考慮以下方程式系統（即迭代0）：n 若 進入、離開，則（即迭代1）：121231247802103218Zxxxxxxxx2x1x1312313434401152228Zxxxxxxxx作業研究作業研究 二版二版 Ch.3 單形法單形法 p.17/45基本代數運算基本代數運算o 較有效率的計算方式：n 一律使用加法，而不

9、用減法，以避免混淆n 視計算的難易，而決定使用原基準列（離開變數之列）或新基準列作業研究作業研究 二版二版 Ch.3 單形法單形法 p.18/45單形法的表形式單形法的表形式o 第二、三個單形表 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.19/45單形法表形式的求解步驟單形法表形式的求解步驟o 起始步驟：起始步驟：n加上寬鬆變數。n在起始BFS中，讓寬鬆變數為該限制式的BV，並讓所有原始變數為NBV。o 最佳性測試：最佳性測試：n若所有Z列係數均為非負值，則停止；否則繼續。o 迭代步驟：迭代步驟：n決定進入變數：選擇具最負Z列係數的NBV為進入變數。n決定離開變數：以最小比率測試

10、，選擇比率最小的BV。n產生新單形表：利用高斯消去法。返回最佳性測試。範例範例0,1823122 4 .5321212121xxxxxxtsxxZMax0,182312 2 4 .5354321521423121xxxxxxxxxxxxtsxxZMax單形法的表形式單形法的表形式單形法的表形式單形法的表形式(續續)p.23/453.5 特殊情況特殊情況1.進入變數平手進入變數平手n 任選其一2.離開變數平手（退化解）離開變數平手（退化解）n 此時，在下一個單形表，未被選擇離開的BV必為零n 退化基變數（degenerate BV）n 退化可行基解（degenerate BFS）。n 理論上，退

11、化BFS有可能產生循環，使得Z值不變，但實際運算時幾乎不可能發生。作業研究作業研究 二版二版 Ch.3 單形法單形法 p.24/453.5 特殊情況特殊情況3.無離開變數（無窮解）無離開變數（無窮解）n若任何單形表，其進入變數之欄無任何正值n實務上，若遇無窮解，則代表該LP模式有誤4.最佳單形表含最佳單形表含Z列係數列係數=0的的NBV（多重最佳解）多重最佳解）n所得到兩個解的凸組合均為最佳解。作業研究作業研究 二版二版 Ch.3 單形法單形法 p.25/453.6 對於其他形式的調整對於其他形式的調整1.極小化問題極小化問題o 轉換法n將原問題轉換為極大化的問題n使用轉換法時，單形表Z欄的Z

12、列係數將是-1，因此 原問題的Z值=-（最佳單形表中的Z值）o 直接法n直接改變最佳性測試和決定進入變數的規則：n最佳性測試：若所有Z列係數均為非正值，則停止；否則則繼續。n迭代步驟：o 決定進入變數：選擇具最大Z列係數的NBV為進入變數。作業研究作業研究 二版二版 Ch.3 單形法單形法 p.26/453.6 對於其他形式的調整對於其他形式的調整2.RHS為負值為負值n 左右兩邊分別乘以3.等式限制式等式限制式n 必須加上人工變數（artificial variable）n 以此AV作為該等式的起始BV4.大於等於限制式大於等於限制式n 先減去剩餘變數（surplus variable）再加

13、上AVn 以此AV作為該限制式的起始BV作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.27/45人工問題的圖形人工問題的圖形o 當僅有兩個變數時：n 等式限制式由一條線擴充至半個面。n 大於等於限制式由半個面擴充至全部面積08108642642P的可行區域（一條線）P(A)的可行區域p.28/453.6 對於其他形式的調整對於其他形式的調整5.變數允許為負值變數允許為負值n 具有下限值具有下限值 其中下限值為負值。我們可讓 此方法亦適用於當下限值為正值時iixl 0iiiixxlx 作業研究作業研究 二版二版 Ch.3 單形法單形法

14、 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.29/45具有下限值具有下限值/範例範例 3.12作業研究作業研究 二版二版 Ch.3 單形法單形法 p.30/45無下限值無下限值/範例範例 3.13p.31/453.7 大大M法法o 兩個處理人工變數的方法：n 大M法（big-M method）n 雙階法（two-phase method）o 目的n 盡量讓人工變數為零，以使所得到的人工問題最佳解即為原問題的最佳解作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.32/45大大M法求解程序法求解程序o 作法作法n 對人工變數

15、(AV)在目標函數中給予極大的懲罰，以使得在單形法的運算過程中，盡可能降低AV之值（最好為零）n 對於max問題，讓AV的目標函數係數為-Mn 對於min問題，讓AV的目標函數係數為Mo 建立第一個單形表建立第一個單形表n 第一個單形表並不符合常態形式，而須以高斯消去法還原（restore）列，才能得到起始BFS。n 之後，即可完全依一般單形法處理作業研究作業研究 二版二版 Ch.3 單形法單形法 p.33/45大大M法結果的分析法結果的分析o 情況情況A：找到問題P(M)的最佳解n 若所有AV=0，則此解亦為問題P的最佳解n 若有任何AV0，則問題P無可行解o 情況情況B：問題P(M)是無窮

16、解n 若所有AV=0，則問題P亦為無窮解n 若無窮解的條件來自最負的Z列係數（對max問題），且有任何AV0，則問題P無可行解n 若非來自最負的Z列係數，則仍無法判斷，須繼續求解p.34/45範例範例3.16 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.35/45範例範例3.16/單形表單形表1-3 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.36/45範例範例3.16/單形表單形表4-5 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.37/453.8 雙階法雙階法o 兩方法之差異兩方法之差異n 大M法：藉由大M的係數區分AV和其他變數n 雙階法：以兩階段區分

17、AV和其他變數（較易）o 第一階段第一階段n 僅考慮AV，因此僅需用係數1或-1即可n 第一個單形表不符合常態形式，因此須以高斯消去法還原Z列n 第一階段問題P(I)：o 一定會求得最佳解，不可能是無窮解或無可行解o 當得到P(I)的最佳解時，若所有AV=0，則至第二階段；若有任何AV0，則原問題無可行解作業研究作業研究 二版二版 Ch.3 單形法單形法 p.38/453.8 雙階法雙階法o 第二階段第二階段n 將AV全部刪除（若有AV仍為基變數（其值必為零）時，則仍必須暫時保留該AV）n 利用P(I)的最佳解作為P(II)的起始BFSn 回復原問題的目標函數係數，並還原Z列 作業研究作業研究

18、 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.39/45範例範例3.18 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.40/45範例範例3.18 P(I)的單形表的單形表1-2 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.41/45範例範例3.18 P(I)的單形表的單形表3-4 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.42/45範例範例3.18 P(II)的單形表的單形表 p.43/453.9 單一人工變數技巧單一人工變數技巧o 步驟步驟1.對於或=限制式，分別減去一個各自的剩餘變數，再分別加上一個共同的A

19、V，然後於左右兩邊分別乘以-1。2.目標函數與雙階法的第一階段問題相同。3.在1st單形表中，以step 1所加的剩餘變數為BV，並讓AV為進入變數，然後選擇比率最大的變數為離開變數，即可得到P(A)的一個BFS。4.以大M法或雙階法繼續求解該問題。作業研究作業研究 二版二版 Ch.3 單形法單形法 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.44/45範例範例3.19 作業研究作業研究 二版二版 Ch.3 單形法單形法 p.45/45範例範例3.19/續續 p.46/453.10 計算效率與電腦軟體計算效率與電腦軟體o 影響單形法計算時間的因素影響單形法計算時間的因素n 功能限制式的個數n 變數的個數n 非零係數的比例o 單形法（LP）的常用電腦軟體n LINDO（最普及）n Excel規劃求解功能n CPLEX（對於大型問題最有效率）作業研究作業研究 二版二版 Ch.3 單形法單形法 p.47/45附錄附錄o 請參見書本：n 附錄3.1 Excel的規劃求解n 附錄3.2 LINDO軟體作業研究作業研究 二版二版 Ch.3 單形法單形法