1、線 性 規 劃(Linear Programming)單純形法小結 一、無窮多最優解例1、用單純形法表求解下面的線性規劃問題。幾種特殊情況 解：用單純形表來求解。填入單純形表計算得：迭代次數基變量CBx1 x2 s1 s2 s3b比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1j50 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 01150/2j50 0 0 0 0125002x1s2x2500501 0 1 0 -10 0

2、 -2 1 10 1 0 0 1505025050/1250/1j0 0 -50 0 015000 非基變量s3的檢驗數等于零，這樣我們可以斷定此線性規劃問題有無窮多最優解。求得另一個基本可行解，如下表所示：迭代次數基變量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200j0 0 -50 0 015000不妨用向量Z1，Z2表示上述兩個最優解即Z1 =（50，250，0，50，0）t， Z2 =（100，200，0，0，50）t，則無窮多最優解可表示為Z1+（1- ）Z2，其中01。 二、

3、無界解 例2、用單純形表求解下面線性規劃問題。 幾種特殊情況 迭代次數基變量CBx1 x2 s1 s2b比值1 1 0 00s1s2001 -1 1 0-3 2 0 1161j 1 1 0 01x1s2101 -1 1 0 0 -1 3 119j 0 2 -1 0填入單純形表計算得：解：在上述問題的約束條件中加入松馳變量，得標準型如下： 三、無可行解 例3、用單純形表求解下列線性規劃問題解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到： 填入單純形表計算得：幾種特殊情況迭代次數基變量CBx1 x2 s1 s2 s3 a1b比值20 30 0 0 0 -M0s1s2a100-M3

4、10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1j20+M 30+M 0 0 -M 01x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)j11+7/10M 0 -3-M/10 0 -M 0 2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304j0 0 -3-M/10 -11-7M/10 -M 0780-4M只要最優解有人工變量大于零，則原

5、線性規劃無可行解。 有初始可行基的情況下：唯一最優解、無窮多最優解、無界解； 無初始可行基的情況下會怎樣？決策變量右端常數項約束方程是等式或不等式目標函數是極大或極小新加變量價值系數xj0 xj無約束xj 0 bi 0bi 0=maxZminZxs xa不處理令xj = xj - xj xj 0 xj 0令 xj =- xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z=- ZminZ=max z0-M標準化后列出初始單純形表 A線性規劃問題單純型方法求解的第一步是標準化A 四、退化問題 如果一個基本可行解的基變量中至少有一個為0，則稱此基本可行解為退化的

6、基本可行解。例4.用單純形表，求解下列線性規劃問題。幾種特殊情況幾種特殊情況解：加上松馳變量s1,s2,s3化為標準形式，填入單純形表計算：迭代次數基變量CBx1 x2 x3 s1 s2 s3b比值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1j2 0 3/2 0 0 0Z=01x1s2s32001 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 12010/21/2j0 2 3/2 -2 0 0Z=42x1x2s32001 0 1/2 0 1/2 00 1 1/2 - 1 1/2

7、00 0 0 1 -1 1 2012/(1/2)0/(1/2)j0 0 1/2 0 -1 0Z=4迭代次數基變量CBx1 x2 x3 s1 s2 s3b比值2 0 3/2 0 0 03x1x3s323/201 -1 0 1 0 00 2 1 - 2 1 00 0 0 1 -1 1 2012/11/1j0 -1 0 1 -3/2 0Z=44x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221j0 -1 0 0 -1/2 -1Z=5 在以上的計算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2為最小比值，導致在第1次迭代中出現了退化，基變量s2=0。又由于在第1次迭代出現了退化，導致第2次迭代所取得的目標函數值并沒有得到改善，仍然與第1次迭代的一樣都等于4。像這樣繼續迭代而得不到目標函數的改善，當然減低了單純形算法的效率，但一般來說還是可以得到最優解的。當本題繼續計算下去最后得到了最優解（1，0，2，1，0，0）T，其最優值為5。 但有些特殊情況下當出現退化時，即使存在最優解，而迭代過程總是重復解的某一部分迭代過程，出現了計算過程的循環，目標函數值總是不變，永遠達不到最優解 為了避免這種現象，我們介紹勃蘭特法則。 首先我們把松弛變量（剩余變量）、人工變量都用xj表示，一般松弛變量（剩余變量）的下標號列在決策變