運(yùn)籌學(xué)單純形法的計(jì)算步驟.PPT

1、14 單單純純形形法法的的計(jì)計(jì)算算步步驟驟本節(jié)重點(diǎn)：本節(jié)重點(diǎn)：?jiǎn)渭冃伪恚ㄌ貏e是檢驗(yàn)數(shù)行）單純形表（特別是檢驗(yàn)數(shù)行）單純形法的計(jì)算步驟單純形法的計(jì)算步驟大大M法法兩階段法兩階段法解的存在情況判別解的存在情況判別2cj 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列基變量的價(jià)值系數(shù)(目標(biāo)函數(shù)系數(shù))cj行價(jià)值系數(shù)，b列方程組右側(cè)常數(shù) 列確定換入變量時(shí)的比率計(jì)算值

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

3、下一步。(4).根據(jù)max(max( j 0) = k，確定xk為換入變量，按 規(guī)則計(jì)算 =minb =minbi i/a/aikikaaikik00可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步。4cjCB 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

4、 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=05cjCB 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

5、)T T， z z1 1 =9=96cjCB 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

6、0，4 4，0)0)T T， z z3 3 =14=147例例8 min z =-3-3x1+x2+x3s.t. 01 2324112 32131321321x,x,xxxxxxxxx5 單純形法的進(jìn)一步討論51 人工變量法人工變量法 解決初始基可行解的問(wèn)題。當(dāng)某個(gè)約束方程中沒有明 顯的基變量時(shí)，在該方程中加上人工變量。8 標(biāo)準(zhǔn)型：標(biāo)準(zhǔn)型： 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,xx

7、xxxxxxx其中第其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6, x79 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來(lái)的約束條件。如何使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0 的基可行解，從而求得問(wèn)題的最優(yōu)解，有兩種方法：10 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx反之，若加了人工變量的問(wèn)題解后最優(yōu)解中仍含人工變量為基變量，便說(shuō)明原問(wèn)題無(wú)可行解。例3的單

8、純形表格為： 只要原問(wèn)題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善，人工變量一定會(huì)逐步換出基，從而得到原問(wèn)題的基可行解，進(jìn)而得到基最優(yōu)解。3.大大M法法在目標(biāo)函數(shù)中加上懲罰項(xiàng)max =3 3x1- -x2- -x3- -Mx6- -Mx7其中M為充分大的正數(shù)。11Cj 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

9、 -2 0 1 0 0 -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= 212 只要原問(wèn)題有可行解，

10、該最小化問(wèn)題的最優(yōu)目標(biāo)函數(shù)值就只要原問(wèn)題有可行解， 該最小化問(wèn)題的最優(yōu)目標(biāo)函數(shù)值就是是 0，解得的最優(yōu)解，解得的最優(yōu)解 x6=0，x7=0，對(duì)應(yīng)原問(wèn)題一個(gè)基可行解。，對(duì)應(yīng)原問(wèn)題一個(gè)基可行解。反之若該問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值大于零， 則說(shuō)明原問(wèn)題無(wú)可反之若該問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值大于零， 則說(shuō)明原問(wèn)題無(wú)可行解。行解。 2.兩階段法兩階段法第一階段第一階段：以人工變量之和最小化為目標(biāo)函數(shù)：以人工變量之和最小化為目標(biāo)函數(shù) min min = = x6+x7 第二階段第二階段：以第一階段的最優(yōu)解：以第一階段的最優(yōu)解(不含人工變量不含人工變量)為初為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。始解，以原目標(biāo)函數(shù)為目標(biāo)

11、函數(shù)。13例8 試用兩階段法求解線性規(guī)劃問(wèn)題 min z =-3-3x1+x2+x3 s.t. 01 23241123211321321x,x,xx xxxxxxx3解：先在上述線性規(guī)劃問(wèn)題的約束方程中加入人工變量，給出第一階段的數(shù)學(xué)模型為： min min = = x6+x7 x1-2-2x2+x3+x4 =11 -4-4 x1+ x2+2x3 - -x5 + x6 =3 -2-2x1 + x3 + x7 =1 x1， x7 014第一階段的單純形表如下：cj0000011CBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-2101211000-10010001113

12、/216-1-30100010 x4x6x3101130-2-2100011000-10010-1-2110-100103000 x4x2x3121130-2010001100-2-10210-5-20400000111 第一階段求得的結(jié)果是 = 0,最優(yōu)解是（0,1,1,12,0,0,0）T因人工變量 x6= x7=0，所以(0,1,1,12,0)T是原線性規(guī)劃問(wèn)題的基可行解。15第二階段運(yùn)算: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

13、 0 0 1 -3 1 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 165. 2 線性規(guī)劃問(wèn)題解的討論線性規(guī)劃問(wèn)題解的討論一、無(wú)可行解一、無(wú)可行解 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

14、0cj-zj2 1 0 -1 0 Z0=-40Z1=-2017二、二、 退化問(wèn)題退化問(wèn)題 有有基可行解的正分量個(gè)數(shù)小于約束條件個(gè)數(shù)基可行解的正分量個(gè)數(shù)小于約束條件個(gè)數(shù) m 的的問(wèn)題。問(wèn)題。 右側(cè)常數(shù)中有零時(shí)，初始解就是退化解。單純形法右側(cè)常數(shù)中有零時(shí)，初始解就是退化解。單純形法計(jì)算中，計(jì)算計(jì)算中，計(jì)算 值時(shí)有兩個(gè)以上比值同為最小，這樣在值時(shí)有兩個(gè)以上比值同為最小，這樣在下一次迭代中就會(huì)出現(xiàn)零值的基變量，出現(xiàn)退化解。下一次迭代中就會(huì)出現(xiàn)零值的基變量，出現(xiàn)退化解。 一般，出現(xiàn)退化情況時(shí)，不必特殊處理，一般不會(huì)一般，出現(xiàn)退化情況時(shí)，不必特殊處理，一般不會(huì)出現(xiàn)由于死循環(huán)得不到最優(yōu)解的情況。出現(xiàn)由于死循

15、環(huán)得不到最優(yōu)解的情況。 勃蘭特規(guī)則勃蘭特規(guī)則(P35)可避免死循環(huán)。可避免死循環(huán)。 18例例: 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/

16、3 cj 3 4 0 0 -M CB 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 19三、三、 有無(wú)窮多最優(yōu)解的情況有無(wú)窮多最優(yōu)解的情況 最優(yōu)解中有最優(yōu)解中有非基變量的檢驗(yàn)數(shù)等于零非基變量的檢驗(yàn)數(shù)等于零的的情況。以這種非基變量作為換入變量，迭代可情況。以這種非基變量作為換入變量，迭代可求得另一基最優(yōu)解。求得另一基最優(yōu)解。 任一最優(yōu)解可表示為所有基最優(yōu)解的凸任一最優(yōu)解可表示為所有基最優(yōu)解的凸組合組合。 20 例例 max z=3

17、x1+5x2 3x1 +5x2 15 2x1 + 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=15x1x221四、無(wú)（有）界解四、無(wú)（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x2 3 x1 ,x2

18、0練習(xí)：寫出單純形表練習(xí)：寫出單純形表,分析檢驗(yàn)數(shù)分析檢驗(yàn)數(shù) 與系數(shù)關(guān)系并畫圖驗(yàn)證。與系數(shù)關(guān)系并畫圖驗(yàn)證。22 線性規(guī)劃解除有線性規(guī)劃解除有唯一最優(yōu)解唯一最優(yōu)解的情況外，還的情況外，還有如下幾種情況有如下幾種情況人工人工變量變量不能不能從基從基底中底中換出換出基可行基可行解中非解中非零元素零元素個(gè)數(shù)小個(gè)數(shù)小于基變于基變量數(shù)量數(shù)檢驗(yàn)數(shù)檢驗(yàn)數(shù)中零的中零的個(gè)數(shù)多個(gè)數(shù)多于基變于基變量的個(gè)量的個(gè)數(shù)數(shù)檢驗(yàn)數(shù)大檢驗(yàn)數(shù)大于零，但于零，但對(duì)應(yīng)列元對(duì)應(yīng)列元素小于等素小于等于零，無(wú)于零，無(wú)換出變量換出變量23單純形法小結(jié)單純形法小結(jié) 根據(jù)實(shí)際問(wèn)題給出數(shù)學(xué)模型根據(jù)實(shí)際問(wèn)題給出數(shù)學(xué)模型,列出初始單純形表列出初始單純形表,進(jìn)行標(biāo)準(zhǔn)化進(jìn)行標(biāo)準(zhǔn)化,見表見表 變變量量 x xj j0 0 x xj j0 0 x xj j無(wú)約束無(wú)約束 不需要處理不需要處理 令令 xj=-xj; xj0 令令 xj=xj-xj; ;xj, ,xj0