管理運籌學(xué)：第4講 單純形法的進(jìn)一步討論

1、第第1頁頁第二章第二章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法Linear Programming （LP） 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 線性規(guī)劃的單純形法線性規(guī)劃的單純形法 線性規(guī)劃問題的應(yīng)用線性規(guī)劃問題的應(yīng)用 線性規(guī)劃問題的求解方法線性規(guī)劃問題的求解方法第第2頁頁 將線性規(guī)劃問題化成標(biāo)準(zhǔn)形式將線性規(guī)劃問題化成標(biāo)準(zhǔn)形式; 找出一個找出一個m階單位矩陣作初始可行基，得到初始基可行解階單位矩陣作初始可行基，得到初始基可行解; 計算各非基變量計算各非基變量xj的檢驗數(shù)的檢驗數(shù) j，若所有，若所有 j0，則問題已得，則問題已得到最優(yōu)解，停止計算，

2、否則轉(zhuǎn)入下步到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步; 若存在某個若存在某個 s0，且對應(yīng)的所有系數(shù)，且對應(yīng)的所有系數(shù)ais0，則此問題是無，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步界解，停止計算，否則轉(zhuǎn)入下步; 根據(jù)根據(jù)max j | j0 = k 原則，確定原則，確定xk為入基變量，再按為入基變量，再按 = min bi /aik | aik0 = bl /alk 規(guī)則，確定規(guī)則，確定xl為出基變量，為出基變量，得到改進(jìn)的基可行解。得到改進(jìn)的基可行解。 以以alk為主元素進(jìn)行迭代，利用初等行變換將為主元素進(jìn)行迭代，利用初等行變換將xk所在列化所在列化 為單位向量，即為單位向量，即alk化為化為1，

3、其它元素化為，其它元素化為0，得到改進(jìn)的，得到改進(jìn)的 可行基，轉(zhuǎn)入第步?？尚谢D(zhuǎn)入第步。單純形法計算步驟總結(jié)單純形法計算步驟總結(jié)（有可行解時）（有可行解時）第第3頁頁標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化1nijjija xb1 nijjsiija xxb系數(shù)矩陣系數(shù)矩陣1112121222121 000 100 01nnmmmnaaaaaaaaa( (五五) )單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論 用單純形法解題時，需要有個單位矩陣作為初始可行基用單純形法解題時，需要有個單位矩陣作為初始可行基 當(dāng)約束條件都是當(dāng)約束條件都是“”時，加入松弛變量就形成了初始基時，加入松弛變量就形成了初始基 但實際存在但實際存在“”

4、或或“”型的約束，沒有現(xiàn)成的單位矩陣型的約束，沒有現(xiàn)成的單位矩陣第第4頁頁 x1 x2 x3 x4 = 4max z = 3x1 + 0 x2 + x3 + 0 x4 + 0 x513max3zxx12312323123 42 1 3 9,0 xxxxxxxxx x xs.t.( (五五) )單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論 用單純形法解題時，需要有個單位矩陣作為初始可行基用單純形法解題時，需要有個單位矩陣作為初始可行基 當(dāng)約束條件都是當(dāng)約束條件都是“”時，加入松弛變量就形成了初始基時，加入松弛變量就形成了初始基2x1 x2 x3 x5 = 1解：解：引入變量引入變量40 x ，50

5、x ，從而得到標(biāo)準(zhǔn)形式從而得到標(biāo)準(zhǔn)形式s.t. x1, x2, x3, x4, x5 0 3x2 x3 = 9約束方程組的系數(shù)矩陣：約束方程組的系數(shù)矩陣：12345 111102 11 0103100 P PPP P 但實際存在但實際存在“”或或“”型的約束，沒有現(xiàn)成的單位矩陣型的約束，沒有現(xiàn)成的單位矩陣第第5頁頁max z = 3x1 + 0 x2 + x3 + 0 x4 + 0 x5( (五五) )單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論 采用采用添加人工變量添加人工變量的方法的方法 因是在等式中人為因是在等式中人為加的，為保證約束條件的意義，加的，為保證約束條件的意義，最優(yōu)解中人工變量只

6、能等于最優(yōu)解中人工變量只能等于0 0 在等式約束中加入若干人工變量，人為構(gòu)造一個單位矩陣在等式約束中加入若干人工變量，人為構(gòu)造一個單位矩陣 人工變量的添加不能影響最優(yōu)解的取值：人工變量的添加不能影響最優(yōu)解的取值：2x1 x2 x3 x5 = 1s.t. x1 x2 x3 x4 = 4 x1, x2, x3, x4, x5 0 3x2 x3 = 9約束方程組的系數(shù)矩陣：約束方程組的系數(shù)矩陣：12345 111102 11 0103100 P PPP P 兩種處理方法兩種處理方法 大大M M法法 兩階段法兩階段法60 10 P70 01 P x6 = 1 x7 = 9 = 4 , x6, x7 0

7、 如何如何 處理？處理？第第6頁頁1 1、大、大M M法法max z = 3x1 + 0 x2 + x3 + 0 x4 + 0 x52x1 x2 x3 x5 = 1s.t. x1 x2 x3 x4 = 4 x1, x2, x3, x4, x5 0 3x2 x3 = 9 x6 = 1 x7 = 9 = 4 , x6, x7 0M x6M x7 為保證最優(yōu)解中人工變量取值為為保證最優(yōu)解中人工變量取值為0，可令目標(biāo)函數(shù)中人工，可令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值，用變量的系數(shù)為足夠大的一個負(fù)值，用“M”代表。代表。 由于系數(shù)是一個足夠大的負(fù)值，因此，由于系數(shù)是一個足夠大的負(fù)值，因此，只要人

8、工變量的只要人工變量的取值不為零取值不為零，目標(biāo)函數(shù)就不可能實現(xiàn)最大化。，目標(biāo)函數(shù)就不可能實現(xiàn)最大化。 計算時，把計算時，把 M 看做一個代數(shù)符號直接參加單純形法求解?？醋鲆粋€代數(shù)符號直接參加單純形法求解。第第7頁頁2x1 x2 x3 x5 = 1s.t. x1 x2 x3 x4 = 4 x1, x2, x3, x4, x5 0 3x2 x3 = 9 x6 = 1 x7 = 9 = 4 , x6, x7 0jjczjc BC基bi0MM301004x6x7x4191201131111000103 2M 4M10M413MM010001001x2x3x4x5x6x7xmax z = 3x1 +

9、0 x2 + x3 + 0 x4 + 0 x5M x6M x71mjjiijjjicc acBC Pmax0kjjj min0ilikiiklkbbaaa第第8頁頁jjczjc BC基bi0MM301004x6x7x4191201131111000103 2M 4M10M413MM010001001x2x3x4x5x6x7x00M4x2x7x3636002410133 6M 1 4M03M111301211011014M0jjcz0使人工變量使人工變量盡快出基盡快出基第第9頁頁jjczjc BC基bi30100MM1x2x3x4x5x6x7x0034x2x1x01010002/3101/21/

10、20303/23/21/21/21/23011/30001/31/63/2M 1/2M jjcz000M4x2x7x3636002410133 6M 1 4M03M111301211011014M00第第10頁頁jjczjc BC基bi30100MM1x2x3x4x5x6x7x0034x2x1x01010002/3101/21/20303/23/21/21/21/23011/30001/31/63/2M 1/2M 00014x2x3x3/23/20103/49/2003/43/4000011/21/21/25/21/21001/41/4 1/41/43/4M 1/4M jjcz0此時所有檢驗數(shù)

11、此時所有檢驗數(shù) 0j ，得到最優(yōu)解得到最優(yōu)解 *5 3(0, , ,0,0,0,0) ,2 2TX 最優(yōu)值為最優(yōu)值為*3/2.z 第第11頁頁1 1、大、大M M法法 為保證最優(yōu)解中人工變量取值為為保證最優(yōu)解中人工變量取值為0，可令目標(biāo)函數(shù)中人工，可令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值，用變量的系數(shù)為足夠大的一個負(fù)值，用“M”代表。代表。 由于系數(shù)是一個足夠大的負(fù)值，因此，由于系數(shù)是一個足夠大的負(fù)值，因此，只要人工變量的只要人工變量的取值不為零取值不為零，目標(biāo)函數(shù)就不可能實現(xiàn)最大化。，目標(biāo)函數(shù)就不可能實現(xiàn)最大化。 計算時，把計算時，把 M 看做一個代數(shù)符號直接參加單純形法求解。看做一個

12、代數(shù)符號直接參加單純形法求解。 若若最終單純形表最終單純形表中，中，人工變量仍是基變量并且值不為零人工變量仍是基變量并且值不為零，則說明該問題求不到最優(yōu)解，即則說明該問題求不到最優(yōu)解，即無可行解無可行解。第第12頁頁2x1 x2 x3 x5 = 1s.t. x1 x2 x3 x4 = 4 x1, x2, x3, x4, x5 0 3x2 x3 = 9 x6 = 1 x7 = 9 = 4 , x6, x7 0max z = 3x1 + 0 x2 + x3 + 0 x4 + 0 x5 用大用大M法處理人工變量，用手工計算不會出現(xiàn)任何問題。法處理人工變量，用手工計算不會出現(xiàn)任何問題。 但用計算機(jī)求解

13、時，由于在程序中只能用很大的數(shù)代替但用計算機(jī)求解時，由于在程序中只能用很大的數(shù)代替M，有，有可能受計算機(jī)的誤差影響，導(dǎo)致結(jié)果發(fā)生錯誤，使大可能受計算機(jī)的誤差影響，導(dǎo)致結(jié)果發(fā)生錯誤，使大M法失效。法失效。2 2、兩階段法、兩階段法 第一階段：第一階段：構(gòu)造判斷是否存在可行解的模型構(gòu)造判斷是否存在可行解的模型 構(gòu)造構(gòu)造僅含人工變量僅含人工變量( (系數(shù)為系數(shù)為1)1)且且要求極小化要求極小化的目標(biāo)函數(shù)的目標(biāo)函數(shù) 用單純形法求解，若用單純形法求解，若min w=0，說明人工變量為，說明人工變量為0，問題存在，問題存在可行解，進(jìn)入第二個階段；可行解，進(jìn)入第二個階段； 若若min w0，說明，說明最優(yōu)解

14、中人工變量非零，無可行解，停止最優(yōu)解中人工變量非零，無可行解，停止。min w = x6 + x7 最優(yōu)解中人工變量最優(yōu)解中人工變量只能是只能是0 0第第13頁頁min w = x6 + x72 2、兩階段法、兩階段法2x1 x2 x3 x5 = 1s.t. x1 x2 x3 x4 = 4 x1, x2, x3, x4, x5 0 3x2 x3 = 9 x6 = 1 x7 = 9 = 4 , x6, x7 0jjczjc BC基bi011000004x6x7x4192400141311120113111100010010001001x2x3x4x5x6x7x第第14頁頁jjczjc BC基bi

15、0014x2x7x36360024101364031113012110110140jjcz0011000004x6x7x419413111201131111000100100011x2x3x4x5x6x7x2400100使人工變量使人工變量盡快出基盡快出基第第15頁頁00000jjczjc BC基bi1x2x3x4x5x6x7x2 2、兩階段法、兩階段法000000004x2x1x0311100101001/32/31001/201/21/211/21/21/31/61100000000 第一階段的最優(yōu)解達(dá)到時，人工變量為零，即第一階段的最優(yōu)解達(dá)到時，人工變量為零，即min w=0，說明，說明

16、問題存在可行解，問題存在可行解，進(jìn)入第二個階段進(jìn)入第二個階段； 否則，說明否則，說明無可行解，停止無可行解，停止。第第16頁頁00000jjczjc BC基bi1x2x3x4x5x6x7x2 2、兩階段法、兩階段法000000004x2x1x0311100101001/32/31001/201/21/211/21/21/31/611 第二階段：第二階段：從從上階段的最終單純形表上階段的最終單純形表出發(fā)，去掉人工變出發(fā)，去掉人工變量，引入量，引入原來的目標(biāo)函數(shù)原來的目標(biāo)函數(shù)，繼續(xù)迭代，找出問題的最終解，繼續(xù)迭代，找出問題的最終解max z = 3x1 + 0 x2 + x3 + 0 x4 + 0

17、 x53010000300303/2第第17頁頁人工變量法總結(jié)人工變量法總結(jié) 約束方程組約束方程組 在等式約束中加在等式約束中加人工變量人工變量，人為構(gòu)造單位矩陣作初始可行基，人為構(gòu)造單位矩陣作初始可行基 目標(biāo)函數(shù)目標(biāo)函數(shù) 為保證原約束條件的意義，最優(yōu)解中的人工變量只能是為保證原約束條件的意義，最優(yōu)解中的人工變量只能是0 0 大大M M法法 令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值令目標(biāo)函數(shù)中人工變量的系數(shù)為足夠大的一個負(fù)值“M” 兩階段法兩階段法1 1、構(gòu)造僅含人工變量且求極小化的目標(biāo)函數(shù)，單純形法求解；、構(gòu)造僅含人工變量且求極小化的目標(biāo)函數(shù)，單純形法求解；2 2、去掉上階段最終單純形表

18、中的人工變量，引入原目標(biāo)函數(shù)，、去掉上階段最終單純形表中的人工變量，引入原目標(biāo)函數(shù)，繼續(xù)迭代，找出問題的最終解。繼續(xù)迭代，找出問題的最終解。 若最終單純形表中，若最終單純形表中，人工變量仍是基變量且值不為零人工變量仍是基變量且值不為零，則說明該問題求不到最優(yōu)解，即則說明該問題求不到最優(yōu)解，即無可行解無可行解。第第18頁頁由單純形表判別解的類別由單純形表判別解的類別所有所有 0j 無界解（無最優(yōu)解）無界解（無最優(yōu)解）存在某個存在某個 ， 0s且且 所對應(yīng)的系數(shù)所對應(yīng)的系數(shù)0isa sx 最優(yōu)解最優(yōu)解 無可行解無可行解最終單純形表的基變量中仍有非零人工變量最終單純形表的基變量中仍有非零人工變量唯一

19、最優(yōu)解唯一最優(yōu)解無窮多最優(yōu)解無窮多最優(yōu)解1xjjcz4x2x203301001/53101/201/5400214/500101/5所有非基變量的檢驗數(shù)所有非基變量的檢驗數(shù)*0j第第19頁頁由單純形表判別解的類別由單純形表判別解的類別唯一最優(yōu)解唯一最優(yōu)解所有所有 0j無窮多最優(yōu)解無窮多最優(yōu)解 無界解（無最優(yōu)解）無界解（無最優(yōu)解）存在某個存在某個 ， 0s且且 所對應(yīng)的系數(shù)所對應(yīng)的系數(shù)0isa sx 最優(yōu)解最優(yōu)解所有非基變量的檢驗數(shù)所有非基變量的檢驗數(shù)*0j 無可行解無可行解最終單純形表的基變量中仍有非零人工變量最終單純形表的基變量中仍有非零人工變量第第20頁頁無窮多最優(yōu)解無窮多最優(yōu)解 示例：示

20、例：12max2zxx1212212 2 63212 2 ,0 xxxxxx xs.t.標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化12345max2000zxxxxx1231242512345 2 632 12 2 ,0 xxxxxxxxx x x x xs.t.1x2x3x4x5xjc BC基bjjczi000120003x4x5x612213022110001000112000362第第21頁頁1x2x3x4x5xjc BC基bjjczi000120003x4x5x612213022110001000112000362jjcz3x4x2x0022010012101028300121000228/3第第22頁頁1x2x3

21、x4x5x12000jjcz1x4x2x1022010012101022003140010021/23x4x2x0022010012101028300121000228/3jc BC基bjjczi此時所有檢驗數(shù)此時所有檢驗數(shù) 0j ，得到最優(yōu)解得到最優(yōu)解 *(2,2,0,2,0) ,TX 最優(yōu)值為最優(yōu)值為*6.z 第第23頁頁1x2x3x4x5x12000jjcz1x5x2x1023/2013/4 1/403101/21/2 01/2003/41/4100100jc BC基bjjczi*(2,2,0,2,0)TX *6z 1x4x2x1022010012101022003140010021/2

22、此時所有檢驗數(shù)此時所有檢驗數(shù) 0j ，得得另一最優(yōu)解另一最優(yōu)解 *31(3, ,0,0, ) ,22TX 最優(yōu)值為最優(yōu)值為*6.z 第第24頁頁單純形法小結(jié)單純形法小結(jié) 根據(jù)實際問題給出數(shù)學(xué)模型，首先化為標(biāo)準(zhǔn)形式，構(gòu)造出單根據(jù)實際問題給出數(shù)學(xué)模型，首先化為標(biāo)準(zhǔn)形式，構(gòu)造出單位矩陣作為基，列出初始單純形表位矩陣作為基，列出初始單純形表. .第第25頁頁單純形法計算框圖單純形法計算框圖唯一最優(yōu)解唯一最優(yōu)解添加松弛變量添加松弛變量、人工變量人工變量 列出初始單純形表列出初始單純形表計算非基變量計算非基變量檢驗數(shù)檢驗數(shù)j所有所有j 0基變量中基變量中有非零的有非零的人工變量人工變量 否否某非基變某非基

23、變量檢驗數(shù)量檢驗數(shù)為零為零 否否無可行解無可行解無窮多最優(yōu)解無窮多最優(yōu)解對任一對任一j0有有aik 0無界解無界解令令k=maxj xk為入基變量為入基變量 對所有對所有aik 0計算計算i=bi/aik 令令l=min=mini xl為出基變量為出基變量 alk為主元素為主元素迭代運算迭代運算1、用非基變量、用非基變量xk替換基變量替換基變量xl 2、對主元素行、對主元素行(第第l行行) 令令bl/alkbl；alj/alkajl3、對主元素列、對主元素列(第第k列列) 令令1alk;0;0其它元素其它元素4、表中其它行、表中其它行 令令rirl/alkaikri列出新的單純形表列出新的單純

24、形表否否否否是是是是 是是是是循循環(huán)環(huán)第第26頁頁補(bǔ)充說明補(bǔ)充說明單純形法在計算中可能出現(xiàn)以下兩種情況單純形法在計算中可能出現(xiàn)以下兩種情況： 同時出現(xiàn)多個相同的最大同時出現(xiàn)多個相同的最大 j值值 同時出現(xiàn)多個相同的最小同時出現(xiàn)多個相同的最小值值 理論上可能出現(xiàn)死循環(huán)，但實際很罕見，一般不需特理論上可能出現(xiàn)死循環(huán)，但實際很罕見，一般不需特殊處理，任選其中一個對應(yīng)的變量入基或出基即可。殊處理，任選其中一個對應(yīng)的變量入基或出基即可。 若遇到極端情況，可利用勃蘭特若遇到極端情況，可利用勃蘭特( (bland) )規(guī)則：規(guī)則： 當(dāng)存在多個當(dāng)存在多個 j0時，選取下標(biāo)值最小的變量入基；時，選取下標(biāo)值最小的變量入基； 當(dāng)出現(xiàn)多個相同最小當(dāng)出現(xiàn)多個相同最小時，選取下標(biāo)值最小的變量出基。時，選取下標(biāo)值最小的變量出基。第第27頁頁1 1、圖解法同單純形法雖然求解的形式不同，但從幾何上、圖解法同單純形法雖然求解的形式