資源描述：
《單純形法、大M法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、單純形法的計算步驟例1.10用單純形法求下列線性規(guī)劃的最優(yōu)解1）將問題化為標準型，加入松馳變量x3、x4則標準型為:10/5/2021單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicBXBbx1x2x3x40x34021100x4301301檢驗數(shù)003？10/5/2021單純形法的計算步驟3）進行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標值更大的基可行解，列出新的單純形表確定換入基的變量。選擇
2、，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ，選最小的θ對應(yīng)基變量作為換出變量。10/5/2021單純形法的計算步驟用換入變量Xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。數(shù)學(xué)解釋經(jīng)濟解釋檢驗數(shù)σj單位變量增加帶來目標函數(shù)變化值單位產(chǎn)品產(chǎn)量增加帶來的凈利潤變化值最小比值θj確保在迭代過程中所有變量的值非負
3、，即每步得到的解均為基可行解。確保在增加產(chǎn)品產(chǎn)量的過程中，不超過現(xiàn)在的資源限量。10/5/2021單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/5－2/5400－1－1最優(yōu)解：最優(yōu)值：10/5/2021單純形法的計算步驟例1.11用單純形法求解解：將數(shù)學(xué)模型化為標
4、準形式：不難看出x4、x5可作為初始基變量，列單純形表計算。10/5/2021單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最優(yōu)解：最優(yōu)值：10/5/2021單純形法的進一步討論－人工變量法一、人工變量法：前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基
5、可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。1、大M法通過引進人工變量，構(gòu)造一個輔助的線性規(guī)劃問題，然后由輔助的線性規(guī)劃問題找出原問題的第一個初始可行基，在此基礎(chǔ)上，利用單純形方法求出原問題的最優(yōu)解。10/5/2021單純形法的進一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標
6、準形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。10/5/2021單純形法的進一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。10/5/2021單純形法的進一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431－10104-Mx5101－1201005-Mx712－21000113－2M2+M
7、－1+2M↑－M0x63－650－1013/5-Mx58－3300108/3-1x312－21000——5-6M5M↑0－M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→10/5/20212、兩階段法在原來問題引入人工變量后分兩個階段求解線性規(guī)劃問題的方法。其中，第一階段在原來問題中引入人工變量，設(shè)法構(gòu)造一個單位陣的初始
8、可行基，另外在目標函數(shù)中令非人工變量的系數(shù)全部為0，人工變量的系數(shù)為1，構(gòu)造一個新的輔助目標函數(shù)。在此基礎(chǔ)上，建立輔助線性規(guī)劃問題。然后運用單純形方法求解，直到輔助目標函數(shù)值為0時為止。第二階段重新回到原來的問題，以第一階段得到的可行基為初始可行基，運用單純形方法以求出原來問題的解。10/5/20213)兩階段法的計算步驟（1）不考慮原問題是否存在基可行解，引進人工變量，
