4.3用單純形法求解目標(biāo)規(guī)劃ppt課件

1、1;.2目標(biāo)規(guī)劃單純形法的求解步驟例 * 題3目標(biāo)規(guī)劃求解問(wèn)題過(guò)程目標(biāo)規(guī)劃求解問(wèn)題過(guò)程明確問(wèn)題，列出明確問(wèn)題，列出( (或修改或修改) )目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)目標(biāo)的優(yōu)先級(jí)和權(quán)系數(shù)構(gòu)造目標(biāo)構(gòu)造目標(biāo)規(guī)劃的模型規(guī)劃的模型求出求出滿(mǎn)意解滿(mǎn)意解滿(mǎn)意否？滿(mǎn)意否？分析各項(xiàng)目分析各項(xiàng)目表完成情況表完成情況據(jù)此制定出據(jù)此制定出決策方案決策方案是是否否4 由目標(biāo)規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型可看出，它實(shí)質(zhì)上是由目標(biāo)規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型可看出，它實(shí)質(zhì)上是 最小化的線(xiàn)性規(guī)劃，所以可用單純形法求解最小化的線(xiàn)性規(guī)劃，所以可用單純形法求解 這時(shí)，我們應(yīng)該把目標(biāo)優(yōu)先等級(jí)系數(shù)這時(shí)，我們應(yīng)該把目標(biāo)優(yōu)先等級(jí)系數(shù)P Pi i（i i = 1,

2、 2, = 1, 2, , , k k）理解為一種特殊的正）理解為一種特殊的正常數(shù)，且注意到各等級(jí)系數(shù)之間的關(guān)系：常數(shù)，且注意到各等級(jí)系數(shù)之間的關(guān)系：P P1 1P P2 2 P Pk k 而檢驗(yàn)數(shù)就是各優(yōu)先因子而檢驗(yàn)數(shù)就是各優(yōu)先因子P P1 1, , P P2 2 , , , P Pk k的線(xiàn)性組合。的線(xiàn)性組合。0jjjCcz當(dāng)所有檢驗(yàn)數(shù)都滿(mǎn)足最優(yōu)性條件（當(dāng)所有檢驗(yàn)數(shù)都滿(mǎn)足最優(yōu)性條件（ ）時(shí)，從最終表上即可得出）時(shí)，從最終表上即可得出目標(biāo)規(guī)劃的解目標(biāo)規(guī)劃的解ci - zj = kj Pk ,j=1,2,n ; k=1,2,KP Pk k是指不同數(shù)量的很大的數(shù)是指不同數(shù)量的很大的數(shù) d d-

3、-是松弛變量是松弛變量 d d+ +是剩余變量是剩余變量P Pk kMPMPk+1 k+1 (M(M是任意大的正數(shù)）是任意大的正數(shù)）5 用單純形法求解下面目標(biāo)規(guī)劃問(wèn)題用單純形法求解下面目標(biāo)規(guī)劃問(wèn)題: : 11223312112112122231233412Min 51060 2 0 s.t4 4 36 68 48 001 2 3( )()( )(),(, , )iiZPdP dP dxxlxxddlxxddlxxddlxxddi引入松馳變量引入松馳變量 x x3 3 , , 將它們化為標(biāo)準(zhǔn)型：將它們化為標(biāo)準(zhǔn)型：1122331231211122212331235106004366848001 2

4、 3Min 2 s.t. 4 ,(, , )iiZP dP dP dxxxxxddxxddxxddxxxddi6 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1 -2 0 1 -1 0 0 0 0 0 36 4 4 0 0 0 1 -1 0 0 P3 48 6 8 0 0 0 0 0 1 -1 P1 -1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 -6 -8 0 0 0 0 0 0 1 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0

5、1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 020 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 11d1d2d3d2d3d1d2d3d2d3djjjzc jjjzc 60166415000321313111PPPPPPPC1122331231211122212331235106004366848001 2 3Min 2 s.t. 4 ,(, , )iiZP dP dP dxxxxxddxxddxxddxxxddi7 cj

6、0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 020 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5 -2/5 0 01/10-1/10 036/5 0 0 0 -2/5 2/5 1 -1-

7、3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2d3djjjzc 2djjjzc 全部檢驗(yàn)數(shù)非負(fù)，全部檢驗(yàn)數(shù)非負(fù)，計(jì)算結(jié)束。計(jì)算結(jié)束。8 1 1、建立初始單純形表。、建立初始單純形表。 一般假定初始解在原點(diǎn)，一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量， 按目標(biāo)優(yōu)先等級(jí)從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，按目標(biāo)優(yōu)先等級(jí)從左至

8、右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表的下半部填入表的下半部 ，得檢驗(yàn)數(shù)矩陣。，得檢驗(yàn)數(shù)矩陣。9（2 2）若檢驗(yàn)數(shù)矩陣的）若檢驗(yàn)數(shù)矩陣的P Pi i 中有負(fù)系數(shù)，且負(fù)系數(shù)所在列的中有負(fù)系數(shù)，且負(fù)系數(shù)所在列的前前i i-1 -1行優(yōu)先因子的系數(shù)全為行優(yōu)先因子的系數(shù)全為0 ( 0 ( 例如例如 ) ) ，可判定該檢驗(yàn)數(shù)為負(fù)，可判定該檢驗(yàn)數(shù)為負(fù)，則選該系數(shù)（若此類(lèi)負(fù)系數(shù)有多個(gè)，則可選絕對(duì)值最大者）所在列對(duì)應(yīng)的非基則選該系數(shù)（若此類(lèi)負(fù)系數(shù)有多個(gè)，則可選絕對(duì)值最大者）所在列對(duì)應(yīng)的非基變量為入基變量，繼續(xù)進(jìn)行基變換變量為入基變量，繼續(xù)進(jìn)行基變換 （3 3）若檢驗(yàn)數(shù)矩陣的）若檢驗(yàn)數(shù)矩陣的P Pi i行中有負(fù)系數(shù)，

9、但負(fù)系數(shù)所在列的前行中有負(fù)系數(shù)，但負(fù)系數(shù)所在列的前i i-1 -1行優(yōu)先因行優(yōu)先因子的系數(shù)有子的系數(shù)有0 0，也有正數(shù)，也有正數(shù)，（例如（例如 ），即整個(gè)檢驗(yàn)數(shù)的值可判為正（因），即整個(gè)檢驗(yàn)數(shù)的值可判為正（因P Pi i-1 -1P Pi i ），故也應(yīng)），故也應(yīng)轉(zhuǎn)入對(duì)轉(zhuǎn)入對(duì)P Pi i+1+1級(jí)目標(biāo)的尋優(yōu)，否則會(huì)使高優(yōu)先級(jí)別的目標(biāo)函數(shù)值劣化級(jí)目標(biāo)的尋優(yōu)，否則會(huì)使高優(yōu)先級(jí)別的目標(biāo)函數(shù)值劣化 10 入基變量的確定：在入基變量的確定：在P Pk k行，從那些上面沒(méi)有行，從那些上面沒(méi)有 正檢驗(yàn)數(shù)正檢驗(yàn)數(shù) 的負(fù)檢驗(yàn)數(shù)中，選絕的負(fù)檢驗(yàn)數(shù)中，選絕對(duì)值最大者，對(duì)應(yīng)的變量對(duì)值最大者，對(duì)應(yīng)的變量x xs s就是

10、進(jìn)基變量。就是進(jìn)基變量。若若P Pk k行中有幾個(gè)相同的絕對(duì)值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其行中有幾個(gè)相同的絕對(duì)值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列的絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)的所在列的x xs s為進(jìn)基變量。為進(jìn)基變量。假如仍無(wú)法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。假如仍無(wú)法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。11 出基變量的確定：出基變量的確定：按最小非負(fù)比值規(guī)則確定出基變量，當(dāng)存在兩個(gè)或兩個(gè)按最小非負(fù)比值規(guī)則確定出基變量，當(dāng)存在兩個(gè)或兩個(gè) 以上相同的最小比值以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量

11、。時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。 主元素的確定：主元素的確定：出基變量與入基變量在系數(shù)矩陣中對(duì)應(yīng)的交叉點(diǎn)上的元素即為主元素出基變量與入基變量在系數(shù)矩陣中對(duì)應(yīng)的交叉點(diǎn)上的元素即為主元素 迭代變換：迭代變換：同線(xiàn)性規(guī)劃的單純形法得到新的單純形表，獲得一組新解同線(xiàn)性規(guī)劃的單純形法得到新的單純形表，獲得一組新解對(duì)求得的解進(jìn)行分析：對(duì)求得的解進(jìn)行分析： 若計(jì)算結(jié)果滿(mǎn)意，停止運(yùn)算；若計(jì)算結(jié)果滿(mǎn)意，停止運(yùn)算； 若不滿(mǎn)意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級(jí)和權(quán)系數(shù)，若不滿(mǎn)意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級(jí)和權(quán)系數(shù)， 或者改變目標(biāo)值，重新進(jìn)行第或者改變目標(biāo)值，重新進(jìn)行第1 1步。步。12 4 4 每個(gè)單

12、純形表每個(gè)單純形表中常數(shù)列中常數(shù)列b b，即為各基變量的相應(yīng)取值，即為各基變量的相應(yīng)取值本題最后一個(gè)單純形表已為最優(yōu)，它對(duì)應(yīng)的基本可行解：本題最后一個(gè)單純形表已為最優(yōu)，它對(duì)應(yīng)的基本可行解：x x1 1=24/5, =24/5, x x2 2=12/5, =12/5, x x3 3=12, d=12, d2 2- -=36/5=36/5，即為最優(yōu)解這與圖解法得到結(jié)果一致，即為最優(yōu)解這與圖解法得到結(jié)果一致 在最優(yōu)單純形表中非基變量在最優(yōu)單純形表中非基變量d d1 1+ +和和d d3 3+ +的檢驗(yàn)數(shù)都是零，故知本題有多個(gè)最的檢驗(yàn)數(shù)都是零，故知本題有多個(gè)最優(yōu)解優(yōu)解 如以如以 d d1 1+ +為入

13、基變量繼續(xù)迭代，可得單純形表為入基變量繼續(xù)迭代，可得單純形表2 2，如以如以d d3 3+ +為入基變量繼續(xù)迭代，可得單純形表為入基變量繼續(xù)迭代，可得單純形表3 313 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 020 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 0

14、x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5 -2/5 0 01/10-1/10 036/5 0 0 0 -2/5 2/5 1 -1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2d3djjjzc 2djjjzc 14 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 20 010/3 1 0 0 0 0 -5/6 5

15、/6 0 x1 8 1 4/3 0 0 0 0 0 1/6-1/6 0 4 0 -4/3 0 0 0 1 -1 -2/3 2/3 0 8 010/3 0 -1 1 0 0 1/6-1/6 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2djjjzc 1d15 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 12 0 0 1 1 -1 0 0 -1 1 0 x1 6 1 0 1/10 1/2 -1/2 0 0 0 0 0 0 0 0 -3/5 -1 1 1

16、-1 0 0 0 x2 3 0 1 1/20 -1/4 1/4 0 0 0 0 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2djjjzc 3d16 )3,2,1i( 0d ,d,0 x,x11 x x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii21213321222111213322211 )3,2,1i ( 0d ,d,0 x,x11 xx x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii21321332122

17、211121332221117Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 -10120002000P3 -568100000010 1d 1d 2d 2d 3d 3d 1d 2d 3d )3,2,1i( 0d ,d,0 x,x11 xx x256ddx10 x810ddx2 x 0ddx x dP)dd(PdPZminii21321332122211121332221118Cj 000P1 P2 P2P3 00CBXBbx1x2

18、 x3 053/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 -630005-5010 1d 1d 2d 2d 3d 3d 1d 3d= min10/3,10,6/3,12/3= 2,故故 為換出變量。為換出變量。 3d19Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002

19、-2-1/21/21kjP1 0000100000P2 0000011000P3 0000000100 1d 1d 2d 2d 3d 3d 1d 最優(yōu)解為最優(yōu)解為x12 2， x2 4 4。 但非基變量但非基變量 的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。= min4 , 24 , 6= 4,故故 為換出變量。為換出變量。 1d 3d20Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-110

20、01kjP1 0000100000P2 0000011000P3 000000100 1d 1d 2d 2d 3d 3d 3d 最優(yōu)解為最優(yōu)解為x110/3,，x2 =10/3。則這兩個(gè)解得凸組合都是本例的滿(mǎn)意解。則這兩個(gè)解得凸組合都是本例的滿(mǎn)意解。21例例 : : 用單純形法求解下述目標(biāo)規(guī)劃問(wèn)題：用單純形法求解下述目標(biāo)規(guī)劃問(wèn)題： )3 , 2 , 1i (0d,d,x,x100ddx2x340ddxx210ddx. t . sdPddPzminii213321222111132111解解 : : 第一步：列出初始單純形表第一步：列出初始單純形表cj 0 0 P1 0 0 P1 P2 0 CB

21、 基基 b x1 x2 d1- d1+ d2- d2+ d3- d3+ P1 d1- 10 1 0 1 -1 0 d2- 40 2 1 1 -1 P2 d3- 100 3 2 1 -1 P1 -1 1 1 cj-zj P2 -3 -2 1 第二步：確定換入變量第二步：確定換入變量 第三步：確定換出變量第三步：確定換出變量22第四步：用換入變量替換基變量中的換出變量第四步：用換入變量替換基變量中的換出變量cj 0 0 P1 0 0 P1 P2 0 CB 基基 b x1 x2 d1- d1+ d2- d2+ d3- d3+ 0 x1 10 1 0 1 -1 0 d2- 20 1 -2 2 1 -1

22、 P2 d3- 70 2 -3 3 1 -1 P1 1 1 cj-zj P2 -2 3 -3 1 2324已知一個(gè)生產(chǎn)計(jì)劃的線(xiàn)性規(guī)劃模型為已知一個(gè)生產(chǎn)計(jì)劃的線(xiàn)性規(guī)劃模型為 0 x)( 100 x )( 60 x )( 140 xx2x12x30Zmax21212121丙丙資資源源乙乙資資源源甲甲資資源源 其中目標(biāo)函數(shù)為總利潤(rùn)，其中目標(biāo)函數(shù)為總利潤(rùn)，x x1 1,x ,x2 2 為產(chǎn)品為產(chǎn)品A A、B B產(chǎn)量?，F(xiàn)有下列目標(biāo)：產(chǎn)量。現(xiàn)有下列目標(biāo)： 1 1、要求總利潤(rùn)必須超過(guò)、要求總利潤(rùn)必須超過(guò) 2500 2500 元；元； 2 2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，

23、A A、B B的生產(chǎn)量不超過(guò)的生產(chǎn)量不超過(guò) 60 60 件和件和 100 100 件；件； 3 3、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量140140。試建立目標(biāo)規(guī)劃模型，并用單純形法求解。試建立目標(biāo)規(guī)劃模型，并用單純形法求解。25 )4.3.2.1l ( 0d,d,0 x100dd x 60dd x 140dd x x2 2500ddx12x30dPdPdP5.2dPZminll214423312221112123423211 1 1、要求總利潤(rùn)必須超過(guò)、要求總利潤(rùn)必須超過(guò) 2500 2500 元；元； 2 2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，、考慮產(chǎn)

24、品受市場(chǎng)影響，為避免積壓，A A、B B的生產(chǎn)量不超過(guò)的生產(chǎn)量不超過(guò) 60 60 件件和和 100 100 件；件； 3 3、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量、由于甲資源供應(yīng)比較緊張，不要超過(guò)現(xiàn)有量140140。26Cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1=60

25、 ,故故 為換出變量。為換出變量。3d27Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10 ,故故 為換出變量。為換出變量。2d28Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-1100

26、0 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故故 為換出變量。為換出變量。3d1d29Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 000100000

27、00P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 為換出變量。為換出變量。2d3d3d30Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中P P3 3檢驗(yàn)數(shù)為負(fù)，說(shuō)明檢驗(yàn)數(shù)為負(fù)，說(shuō)明P3 優(yōu)先等級(jí)目標(biāo)沒(méi)有實(shí)現(xiàn)，但已無(wú)法改進(jìn)，得到滿(mǎn)意解優(yōu)先等級(jí)目標(biāo)沒(méi)有實(shí)現(xiàn)，但已無(wú)法改進(jìn)，得到滿(mǎn)意解 x1 60， x2 175/3， 115/3， 125/3。4d2d31 結(jié)果分析：計(jì)算結(jié)果表明，工廠(chǎng)應(yīng)生產(chǎn)結(jié)果分析：計(jì)算結(jié)果表明，工廠(chǎng)應(yīng)生產(chǎn)A A產(chǎn)品產(chǎn)品6060件，件，B B產(chǎn)