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

第三章單形法SimplexMethod©

廖慶榮作業研究二版2009第三章單形法©廖慶榮作業研究二版2009p.2/45章節大綱前言單形法的幾何意義單形法的代數說明單形法的表形式

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

單形法的幾何意義典型範例的圖形

08108642642˙˙˙˙˙˙BCDEFA作業研究二版Ch.3單形法p.3/453.2單形法的幾何意義典型範例的圖形p.4/453.2

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

單形法的幾何意義範例3.1此三個變數問題的角點解是三個限制式邊界的交點

A、B、……、J等10點是CPFS˙˙CDE˙˙˙˙˙˙˙JIGHFBA˙作業研究二版Ch.3單形法p.5/453.2單形法的幾何意義範例3.1˙˙CDE˙作業研究二版Ch.3單形法p.6/45CPFS的重要性質性質3.1對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的CPFS性質3.2CPFS的個數是有限的性質3.3若一個CPFS無更佳的相鄰CPFS，則其為最佳解作業研究二版Ch.3單形法p.6/45CPFS的重作業研究二版Ch.3單形法p.7/45單形法的幾何程序根據CPFS的三個重要性質而來步驟（對於標準形式）以原點作為起始CPFS。測試是否各相鄰的CPFS具有更佳的Z值。若是，則至步驟3；否則停止，目前的CPFS即為最佳解。由目前的CPFS，沿著可行區域上Z值改進率最大的邊移動至相鄰的CPFS。返回步驟2。作業研究二版Ch.3單形法p.7/45單形法的幾何p.8/45典型範例之CPFS的搜尋順序搜尋順序（A-D-C）作業研究二版Ch.3單形法p.8/45典型範例之CPFS的搜尋順序搜尋順序（A-D-作業研究二版Ch.3單形法p.9/45範例3.3之CPFS的搜尋順序搜尋順序（A-D-F-I-J）˙˙CDE˙˙˙˙˙˙˙JIGHFBA˙作業研究二版Ch.3單形法p.9/45範例3.3之p.10/453.3

單形法的代數說明使用單純法前，須先將所有限制式轉換為等式若限制式為≦，加上寬鬆變數(slackvariable)若限制式為≧，減去剩餘變數(surplusvariable)典型例題之擴充形式：作業研究二版Ch.3單形法p.10/453.3單形法的代數說明使用單純法前，須先將作業研究二版Ch.3單形法p.11/45LP的擴充形式擴充形式（augmentedform）加上寬鬆變數或減去剩餘變數後的LP形式擴充解包含原始變數、寬鬆變數及剩餘變數擴充角點解擴充角點可行解作業研究二版Ch.3單形法p.11/45LP的擴充作業研究二版Ch.3單形法p.12/45基解基解（basicsolution）基解的幾何的意義即為擴充角點解基變數（basicvariable；BV）基底（basis）可行基解（basicfeasiblesolution；BFS）BFS的幾何意義即為擴充CPFS相鄰的（adjacent）作業研究二版Ch.3單形法p.12/45基解基解（作業研究二版Ch.3單形法p.13/45BFS的三個重要性質性質3.4對於一個具有最佳解的線性規劃問題，一定存在一個為最佳解的BFS性質3.5BFS的個數是有限的性質3.6若一個BFS沒有更佳的相鄰BFS，則其為最佳解作業研究二版Ch.3單形法p.13/45BFS的三p.14/45單形法代數程序求解典型範例作業研究二版Ch.3單形法p.14/45單形法代數程序求解典型範例作業研究二版p.15/453.4

單形法的表形式高斯消去法（Gaussianeliminationmethod）利用基本代數運算將原方程式系統轉換為常態形式常態形式（properform）：基變數僅出現在其所在的方程式，且係數為1，而不會出現在其他方程式內基本代數運算（elementaryalgebraicoperation）一列可乘以一個常數一列與常數的乘積可加到另一列或被另一列減去作業研究二版Ch.3單形法p.15/453.4單形法的表形式高斯消去法（Gauss作業研究二版Ch.3單形法p.16/45高斯消去法範例考慮以下方程式系統（即迭代0）：若進入、離開，則（即迭代1）：作業研究二版Ch.3單形法p.16/45高斯消去法作業研究二版Ch.3單形法p.17/45基本代數運算較有效率的計算方式：一律使用加法，而不用減法，以避免混淆視計算的難易，而決定使用原基準列（離開變數之列）或新基準列作業研究二版Ch.3單形法p.17/45基本代數運作業研究二版Ch.3單形法p.18/45單形法的表形式第二、三個單形表作業研究二版Ch.3單形法p.18/45單形法的表作業研究二版Ch.3單形法p.19/45單形法表形式的求解步驟起始步驟：加上寬鬆變數。在起始BFS中，讓寬鬆變數為該限制式的BV，並讓所有原始變數為NBV。最佳性測試：若所有Z列係數均為非負值，則停止；否則繼續。迭代步驟：決定進入變數：選擇具最負Z列係數的NBV為進入變數。決定離開變數：以最小比率測試，選擇比率最小的BV。產生新單形表：利用高斯消去法。

返回最佳性測試。作業研究二版Ch.3單形法p.19/45單形法表形範例範例20單形法的表形式單形法的表形式單形法的表形式(續)單形法的表形式(續)p.23/453.5

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

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

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

對於其他形式的調整

RHS為負值左右兩邊分別乘以等式限制式必須加上人工變數（artificialvariable）以此AV作為該等式的起始BV大於等於限制式先減去剩餘變數（surplusvariable）再加上AV以此AV作為該限制式的起始BV作業研究二版Ch.3單形法p.26/453.6對於其他形式的調整RHS為負值作業作業研究二版Ch.3單形法p.27/45人工問題的圖形當僅有兩個變數時：等式限制式由「一條線」擴充至「半個面」。大於等於限制式由「半個面」擴充至「全部面積」08108642642P的可行區域（一條線）P(A)的可行區域˙作業研究二版Ch.3單形法p.27/45人工問題的p.28/453.6

對於其他形式的調整變數允許為負值具有下限值

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

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

3.13作業研究二版Ch.3單形法p.30/45無下限值/p.31/453.7

大M法兩個處理人工變數的方法：大M法（big-Mmethod）雙階法（two-phasemethod）目的盡量讓人工變數為零，以使所得到的人工問題最佳解即為原問題的最佳解作業研究二版Ch.3單形法p.31/453.7大M法兩個處理人工變數的方法：作業研作業研究二版Ch.3單形法p.32/45大M法求解程序作法對人工變數(AV)在目標函數中給予極大的懲罰，以使得在單形法的運算過程中，盡可能降低AV之值（最好為零）對於max問題，讓AV的目標函數係數為-M對於min問題，讓AV的目標函數係數為M建立第一個單形表第一個單形表並不符合常態形式，而須以高斯消去法還原（restore）列，才能得到起始BFS。之後，即可完全依一般單形法處理作業研究二版Ch.3單形法p.32/45大M法求解作業研究二版Ch.3單形法p.33/45大M法結果的分析情況A：找到問題P(M)的最佳解若所有AV=0，則此解亦為問題P的最佳解若有任何AV≠0，則問題P無可行解情況B：問題P(M)是無窮解若所有AV=0，則問題P亦為無窮解若無窮解的條件來自最負的Z列係數（對max問題），且有任何AV≠0，則問題P無可行解若非來自最負的Z列係數，則仍無法判斷，須繼續求解作業研究二版Ch.3單形法p.33/45大M法結果p.34/45範例3.16

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

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

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

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

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

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

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

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

作業研究二版Ch.3單形法p.42/