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

第三章單形法SimplexMethod?

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

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

單形法的幾何意義典型範(fàn)例的圖形

08108642642˙˙˙˙˙˙BCDEFA作業(yè)研究二版Ch.3單形法p.4/453.2

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

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

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

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

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

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

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

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

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

對(duì)於其他形式的調(diào)整

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

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

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

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

3.13p.31/453.7

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

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

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

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

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

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

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

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

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

p.43/453.9

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