單形法代數(shù)程序求解典型范例課件

第三章單形法SimplexMethod?

廖慶榮作業(yè)研究二版2009p.2/45章節(jié)大綱前言單形法的幾何意義單形法的代數(shù)說明單形法的表形式

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

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

08108642642˙˙˙˙˙˙BCDEFA作業(yè)研究二版Ch.3單形法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的連接線段為此可行區(qū)域的邊。如AB、BC、CD、DA四個線段均為可行區(qū)域的邊。作業(yè)研究二版Ch.3單形法p.5/453.2

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

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

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

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

返回最佳性測試。範例單形法的表形式單形法的表形式(續(xù))p.23/453.5

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

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

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

對於其他形式的調整

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

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

其中下限值為負值。我們可讓此方法亦適用於當下限值為正值時作業(yè)研究二版Ch.3單形法作業(yè)研究二版Ch.3單形法p.29/45具有下限值/範例

3.12作業(yè)研究二版Ch.3單形法p.30/45無下限值/範例

3.13p.31/453.7

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

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

作業(yè)研究二版Ch.3單形法p.36/45範例3.16/單形表4-5

作業(yè)研究二版Ch.3單形法p.37/453.8

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

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

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

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

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

p.43/453.9

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