北郵運籌學(xué)ch1-5 單純形法

1、 單純形計算方法(Simplex Method)是先求出一個初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。m【例1.13】用單純形法求下列線性規(guī)劃的最優(yōu)解 8/14/2022【解】化為標(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 8/14/2022以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。目標(biāo)函數(shù) Z=3x1+

2、4x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標(biāo)函數(shù)中非基變量的系數(shù)大于零，那么目標(biāo)函數(shù)就沒有達到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達到最優(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ù)j0（j=1，n）時，基本可行解為最優(yōu)解。 當(dāng)目標(biāo)函數(shù)中有基變量xi時，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗數(shù)。 8/14/2022進基列出基行bi /ai2，ai20i表1-4(a)XBx1x2x3x4bx3211040 x413

3、0130j3400(b)x3x4j(c)x1x2j基變量11018001/301/3105/311/330405/304/330103/51/518011/52/540011將3化為1乘以1/3后得到8/14/2022單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形表（表1-4）。計算說明：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零； 2.判斷： （a）若j（j，n）得到最解； （b）某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解。 （c）若存在k0且aik (i=1,m)不全非正，則進行換基；8/14/20223.換基：（a）設(shè)k

4、0,xk為進基變量，求最小比值：第個比值最小 ，選最小比值對應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素； (b）求新的基可行解：用初等行變換方法將aik 化為,k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。8/14/2022【例1.14】 用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，單純法計算結(jié)果如表 1所示 。 8/14/2022Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j表151/3150120301713751/309022025601017/31/31250128/91/92/335/30098/91/97/38/14/2022單純形法的軟件演示作業(yè)：用Excel求解 P45 T1.6