1、4 單單純純形形法法的的計計算算步步驟驟本節重點：本節重點：單純形表（特別是檢驗數行）單純形表（特別是檢驗數行）單純形法的計算步驟單純形法的計算步驟大大M法法兩階段法兩階段法解的存在情況判別解的存在情況判別cj c1 cm cm+1 cn CB XB b x1 xm xm+1 xn I c1 c2 cm x1 x2 xm b1 b2 bm 1 0 0 0 0 1 a1,m+1 a2,m+1 am,m+1 a1n a2n amn 1 2 m -z -z值 0 0 m+1 n XB列基變量， CB列基變量的價值系數(目標函數系數)cj行價值系數，b列方程組右側常數 列確定換入變量時的比率計算值下面

2、一行檢驗數， 中間主要部分約束方程系數41 單純形表單純形表 用表格法求解LP，規范的表格單純形表如下： (5).以 alk為主元素進行迭代(即用高斯消去法或稱為旋轉變換)，把 xk所對應的列向量變換為(0，0，1，0)T，將XB列中的第 l 個基變量換為 xk，得到新的單純形表，返回(2)。 計算步驟計算步驟(1).找出初始可行基，確定初始基可行解，建立初始單純形表。(2).檢驗各非基變量xj的檢驗數，若j 0，j=m+1，n；則已得到最優解，可停止計算，否則轉入下一步。 (3).在j 0，j=m+1，n中，若有某個k對應xk的系數列向量Pk 0，則此問題是無界解，停止計算。否則，轉入下一步

3、。(4).根據max(max( j 0) = k，確定xk為換入變量，按 規則計算 =minb =minbi i/a/aikikaaikik00可確定第l行的基變量為換出變量。轉入下一步。cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 1 的的初初始始單單純純形形表表：cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 - 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16

4、4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 -9 2 0 0 0 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T，

5、 z z1 1 =9=9cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2( )cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 4 1 0 0 1/4 0-14 0 0 -1.5 -1/8 0203x1x5x2 2 0 1 1/2 -1/8 0 4 0 0 -2 1/2 1 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T， z z2 2 =13=13 X X(3)(3)=(4=(4，2 2，0 0，4 4，

6、0)0)T T， z z3 3 =14=14例例8 min z =-3-3x1+x2+x3s.t. 01 2324112 32131321321x,x,xxxxxxxxx5 單純形法的進一步討論51 人工變量法人工變量法 解決初始基可行解的問題。當某個約束方程中沒有明 顯的基變量時，在該方程中加上人工變量。 標準型：標準型： max z =3 3x1- -x2- -x3 s.t. 01 23 2 411 2 513153214321x,xxxxxxxxxxx例例 8 m in z =- -3 3x1+x2+x3 s.t. 01 2324112 32131321321x,x,xxxxxxxxx其

7、中第其中第2、3個約束方程中無明顯基變量，分別加上人工變個約束方程中無明顯基變量，分別加上人工變x6, x7 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 這時，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來的約束條件。如何使得可從X(0)開始，經迭代逐步得到x6=0，x7=0 的基可行解，從而求得問題的最優解，有兩種方法： 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx反之，若加了人工變量的問題解后最優解中仍含人工變量為基變量，便說明原問題無可行解。例3的單純形表格為： 只要原問

8、題有可行解，隨著目標函數向最大化方向的改善，人工變量一定會逐步換出基，從而得到原問題的基可行解，進而得到基最優解。3.大大M法法在目標函數中加上懲罰項max =3 3x1- -x2- -x3- -Mx6- -Mx7其中M為充分大的正數。Cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 -M -M x4 x6 x7 1 13 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 j 3- -6M M- -13M- -1 0- -M 0 0 0 x4 10 3 -2 0 1 0 0 -

9、1 -M x6 1 0 1 0 0 -1 1 -2 1 -1 x3 1 -2 0 1 0 0 0 1 1 1 -1+M 0 0- -M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4 -1 x3 1 -2 0 1 0 0 1 0 0 0 -1 3 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 0 0 0 -1/3 -1/3X X* * = (4= (4，1 1，9 9，0 0，0), z0), z* * = 2= 2 只要原問題有可行解， 該最小化問題的最優目標函數值就

10、只要原問題有可行解， 該最小化問題的最優目標函數值就是是 0，解得的最優解，解得的最優解 x6=0，x7=0，對應原問題一個基可行解。，對應原問題一個基可行解。反之若該問題的最優解目標函數值大于零， 則說明原問題無可反之若該問題的最優解目標函數值大于零， 則說明原問題無可行解。行解。 2.兩階段法兩階段法第一階段第一階段：以人工變量之和最小化為目標函數：以人工變量之和最小化為目標函數 min min = = x6+x7 第二階段第二階段：以第一階段的最優解：以第一階段的最優解(不含人工變量不含人工變量)為初為初始解，以原目標函數為目標函數。始解，以原目標函數為目標函數。例8 試用兩階段法求解線

11、性規劃問題 min z =- -3 3x1+x2+x3 s.t. 01 23241123211321321x,x,xx xxxxxxx3解：先在上述線性規劃問題的約束方程中加入人工變量，給出第一階段的數學模型為： m mi in n = = x6+x7 x1- -2 2x2+x3+x4 =11 - -4 4 x1+ x2+2x3 - -x5 + x6 =3 - -2 2x1 + x3 + x7 =1 x1， x7 0第一階段的單純形表如下：cj0000011CBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-2101211000-10010001113/216-1-30

12、100010 x4x6x3101130-2-2100011000-10010-1-2110-100103000 x4x2x3121130-2010001100-2-10210-5-20400000111 第一階段求得的結果是 = 0,最優解是（0,1,1,12,0,0,0）T因人工變量 x6= x7=0，所以(0,1,1,12,0)T是原線性規劃問題的基可行解。第二階段運算:cj -3 1 1 0 0 CB XB b x1 x2 x3 x4 x5 0 1 1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 4 j -1 0 0 0 1 -3 1

13、 0 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 j 2 0 0 0 1/3 1/3 5. 2 線性規劃問題解的討論線性規劃問題解的討論一、無可行解一、無可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0 x1x2CBXBbX3 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -

14、1 0 Z0=-40Z1=-20二、二、 退化問題退化問題 有有基可行解的正分量個數小于約束條件個數基可行解的正分量個數小于約束條件個數 m 的的問題。問題。 右側常數中有零時，初始解就是退化解。單純形法右側常數中有零時，初始解就是退化解。單純形法計算中，計算計算中，計算 值時有兩個以上比值同為最小，這樣在值時有兩個以上比值同為最小，這樣在下一次迭代中就會出現零值的基變量，出現退化解。下一次迭代中就會出現零值的基變量，出現退化解。 一般，出現退化情況時，不必特殊處理，一般不會一般，出現退化情況時，不必特殊處理，一般不會出現由于死循環得不到最優解的情況。出現由于死循環得不到最優解的情況。 勃蘭特

15、規則勃蘭特規則(P35)可避免死循環。可避免死循環。 例例: max z=3x1+4x2 x1 +x2 40 2x1+x2 60 x1-x2 =0 x1 ,x2 0 x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj- cj 0 0 0 -7/3 zj- cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M C

16、B XB b x5 x1 x2 x3 x4 0 7 0 0 zj- cj 0 0 -3.5 0 zj- cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0 -3/2 1 3 x1 20 1 0 1/2 0 三、三、 有無窮多最優解的情況有無窮多最優解的情況 最優解中有最優解中有非基變量的檢驗數等于零非基變量的檢驗數等于零的的情況。以這種非基變量作為換入變量，迭代可情況。以這種非基變量作為換入變量，迭代可求得另一基最優解。求得另一基最優解。 任一最優解可表示為所有基最優解的凸任一最優解可表示為所有基最優解的凸組合組合。 例例 max z=3x1+5x2 3x1 +5x2 15 2x1

17、 + x2 5 2x1+2x2 11 x1 ,x2 0。CBXBbx3 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/5x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2四、無（有）界解四、無（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x2 3 x1 ,x2 0練習：寫出單純形表練習：寫出單純形表,分析檢驗

18、數分析檢驗數 與系數關系并畫圖驗證。與系數關系并畫圖驗證。 線性規劃解除有線性規劃解除有唯一最優解唯一最優解的情況外，還的情況外，還有如下幾種情況有如下幾種情況人工人工變量變量不能不能從基從基底中底中換出換出基可行基可行解中非解中非零元素零元素個數小個數小于基變于基變量數量數檢驗數檢驗數中零的中零的個數多個數多于基變于基變量的個量的個數數檢驗數大檢驗數大于零，但于零，但對應列元對應列元素小于等素小于等于零，無于零，無換出變量換出變量單純形法小結單純形法小結 根據實際問題給出數學模型根據實際問題給出數學模型,列出初始單純形表列出初始單純形表,進行標準化進行標準化,見表見表 變變量量 x xj j0 0 x xj j0 0 x xj j無約束無約束 不需要處理不需要處理 令令 xj=-xj; xj0 令令 xj=xj-xj; ;xj, ,xj0 約