單純形計算方法(SimplexMethod)是先求出一個初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。當(dāng)系數(shù)矩陣A中可以觀察得到一個可行基時（通常是一個單位矩陣或m個線性無關(guān)的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解?！纠?.13】用單純形法求下列線性規(guī)劃的最優(yōu)解4/8/2025【解】化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為系數(shù)矩陣r（B1）=2，B1是一個初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

4/8/2025以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù)Z=3x1+4x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達(dá)到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達(dá)到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作λj,j=1,2…,n。本例中λ1=3,λ2=4,λ3=0,λ4=0.參看表1-4（a）。最優(yōu)解判斷標(biāo)準(zhǔn)當(dāng)所有檢驗數(shù)λj≤0（j=1，…，n）時，基本可行解為最優(yōu)解。當(dāng)目標(biāo)函數(shù)中有基變量xi時，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗數(shù)。4/8/2025進(jìn)基列出基行bi/ai2，ai2>0θi表1-4(a)XBx1x2x3x4bx3211040x4130130λj3400

(b)x3x4λj

(c)x1

x2

λj

基變量11018001/301/3105/31－1/330405/30－4/330103/5－1/51801－1/5－2/5400－1－1將3化為1乘以1/3后得到4/8/2025單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形表（表1-4）。計算說明：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零；2.判斷：（a）若λj≤０（j＝１，２，…，n）得到最解；（b）某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。（c）若存在λk>0且aik(i=1,…,m)不全非正，則進(jìn)行換基；4/8/20253.換基：（a）設(shè)λk>0,xk為進(jìn)基變量，求最小比值：第Ｌ個比值最小，選最小比值對應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素；(b）求新的基可行解：用初等行變換方法將aik

化為１,k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。4/8/2025【例1.14】用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計算結(jié)果如表1－５所示。4/8/2025Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表1－51/3150120301713751/30－90－2－2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/34/8/2025單純形法的軟件演示作業(yè)