單純形計算方法(SimplexMethod)是先求出一個初始基可行解并判斷它是否最優，若不是最優，再換一個基可行解并判斷，直到得出最優解或無最優解。它是一種逐步逼近最優解的迭代方法。當系數矩陣A中可以觀察得到一個可行基時（通常是一個單位矩陣或m個線性無關的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解。【例1.13】用單純形法求下列線性規劃的最優解4/8/2025【解】化為標準型，加入松馳變量x3、x4則標準型為系數矩陣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以上得到的一組基可行解是不是最優解，可以從目標函數中的系數看出。目標函數Z=3x1+4x2中x1的系數大于零，如果x1為一正數，則Z的值就會增大，同樣若x2不為零為一正數，也能使Z的值增大；因此只要目標函數中非基變量的系數大于零，那么目標函數就沒有達到最大值，即沒有找到最優解，判別線性規劃問題是否達到最優解的數稱為檢驗數，記作λj,j=1,2…,n。本例中λ1=3,λ2=4,λ3=0,λ4=0.參看表1-4（a）。最優解判斷標準當所有檢驗數λj≤0（j=1，…，n）時，基本可行解為最優解。當目標函數中有基變量xi時，利用約束條件將目標函數中的xi消去即可求出檢驗數。4/8/2025進基列出基行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.求初始基可行解，列出初始單純形表，求出檢驗數。其中基變量的檢驗數必為零；2.判斷：（a）若λj≤０（j＝１，２，…，n）得到最解；（b）某個λk>0且aik≤０（i=1，2,…,m）則線性規劃具有無界解。（c）若存在λk>0且aik(i=1,…,m)不全非正，則進行換基；4/8/20253.換基：（a）設λk>0,xk為進基變量，求最小比值：第Ｌ個比值最小，選最小比值對應行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素；(b）求新的基可行解：用初等行變換方法將aik

化為１,k列其它元素化為零（包括檢驗數行）得到新的可行基及基本可行解，再判斷是否得到最優解。4/8/2025【例1.14】用單純形法求解【解】將數學模型化為標準形式：不難看出x4、x5可作為初始基變量，單純法計算結果如表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單純形法的軟件演示作業