目標(biāo)規(guī)劃典型例題

1、§主要解題方法和典型例題分析題型I目標(biāo)規(guī)劃數(shù)學(xué)模型的建立當(dāng)線性規(guī)劃問(wèn)題有多個(gè)目標(biāo)需要滿足時(shí)，就可以通過(guò)建立目標(biāo)規(guī)劃數(shù)學(xué)模型來(lái)描述。目標(biāo)規(guī)劃數(shù)學(xué)模型的建立步驟為：第一步，確定決策變量；第二步，確定各目標(biāo)的優(yōu)先因子；第三步，寫(xiě)出硬約束和軟約束；第四步，確定目標(biāo)函數(shù)。例6-1某公司生產(chǎn)甲、乙兩種產(chǎn)品，分別經(jīng)由I、II兩個(gè)車間生產(chǎn)。已知除外購(gòu)?fù)?，生產(chǎn)一件甲產(chǎn)品需要I車間加工4小時(shí)，II車間裝配2小時(shí)，生產(chǎn)一件乙產(chǎn)品需I車間加工1小時(shí)，II車間裝配3小時(shí)，這兩種產(chǎn)品生產(chǎn)出來(lái)以后均需經(jīng)過(guò)檢驗(yàn)、銷售等環(huán)節(jié)。已知每件甲產(chǎn)品的檢驗(yàn)銷售費(fèi)用需40元，每件乙產(chǎn)品的檢驗(yàn)銷售費(fèi)用需50元。I車間每月可利用的工

2、時(shí)為150小時(shí)，每小時(shí)的費(fèi)用為80元；II車間每月可利用的工時(shí)為200小時(shí)，每小時(shí)的費(fèi)用為20元，估計(jì)下一年度平均每月可銷售甲產(chǎn)品100臺(tái)，乙產(chǎn)品80臺(tái)。公司根據(jù)這些實(shí)際情況定出月度計(jì)劃的目標(biāo)如下：P1:檢驗(yàn)和銷售費(fèi)用每月不超過(guò)6000元;P2：每月售出甲產(chǎn)品不少于100件；P3：I、II兩車間的生產(chǎn)工時(shí)應(yīng)該得到充分利用；P4：I車間加班時(shí)間不超過(guò)30小時(shí)；P5：每月乙產(chǎn)品的銷售不少于80件。試確定該公司為完成上述目標(biāo)應(yīng)制定的月度生產(chǎn)計(jì)劃，建立其目標(biāo)規(guī)劃模型。解：先建立目標(biāo)規(guī)劃的數(shù)學(xué)模型。設(shè)X1為每月計(jì)劃生產(chǎn)的甲產(chǎn)品件數(shù)，X2為每月生產(chǎn)的乙產(chǎn)品的件數(shù)。根據(jù)題目中給出的優(yōu)先等級(jí)條件，有以下目標(biāo)及

3、約束：(1)檢驗(yàn)及銷售費(fèi)用目標(biāo)及約束min(d1)40X1 50X2 d1d16000(2)每月甲產(chǎn)品的銷售目標(biāo)及約束min(d2)X1d2 d2100(3)I、II兩車間工時(shí)利用情況目標(biāo)及約束I車間min(d3), II 車間4x1 x2 d3 d3 150min(d4) x1 3x2 d4 d4200(4)I車間加班時(shí)間目標(biāo)及約束d3min(d5) d5 d530(5)每月乙產(chǎn)品銷售目標(biāo)及約束min(d6)x2 d6 d680根據(jù)優(yōu)先等級(jí)層次，確定優(yōu)先因子和權(quán)系數(shù)，得出目標(biāo)規(guī)劃的數(shù)學(xué)模型如下minZpap2d2P3(4d3d4)p4d5p5d640x150x2d1d16000x1d2d21

4、004x1x2d3d3150s.tx13x2d4d4200d3d5d530x2d6d680X,x20;di,di0;i1,L,6例6-2有三個(gè)產(chǎn)地向四個(gè)銷地供應(yīng)物資。產(chǎn)地Ai(i=1,2,3)的供應(yīng)量a、銷地Bj(j=1,2,3,4)的需要量bj、各產(chǎn)銷地之間的單位物資運(yùn)費(fèi)Cj如表5-1所示。表中，ai和bj的單位為噸，Cij的單位為元/噸。編制調(diào)運(yùn)方案時(shí)要求按照相應(yīng)的優(yōu)先級(jí)依次考慮下列六個(gè)目標(biāo)：P1:B4是重點(diǎn)保證單位，其需要量應(yīng)盡可能全部滿足；P2:A3向B1提供的物資不少于100噸；P3:每個(gè)銷地得到的物資數(shù)量不少于其需要量的80%;P4：實(shí)際的總運(yùn)費(fèi)不超過(guò)當(dāng)不考慮P1至P6各目標(biāo)時(shí)的最

5、小總運(yùn)費(fèi)的110%;P5:因路況原因，盡量避免安排A2的物資運(yùn)往B4；P6:XBB和B3的供應(yīng)率要盡可能相同；試建立該問(wèn)題的目標(biāo)規(guī)劃模型。表6-1AiBiB2B3B4aiA15267300A23546200A34523400bj200100450250解：設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量，首先求出當(dāng)不考慮P1至P6各目標(biāo)時(shí)的最小總運(yùn)費(fèi)為2950元。在各級(jí)目標(biāo)中沒(méi)有涉及到供應(yīng)量，因此供應(yīng)量構(gòu)成硬約束:XiiXi2Xi3Xi4300x21x22x23x24200x31x32x33x34400根據(jù)各優(yōu)先級(jí)目標(biāo)，可寫(xiě)出相應(yīng)的目標(biāo)及目標(biāo)約束。P1:B4是重點(diǎn)保證單位，其需要量應(yīng)盡可能全部滿足mind1x

6、14x24x34didi250P2:A3向Bi提供的物資不少于100噸mind2X3id2d2100P3:每個(gè)銷地得到的物資數(shù)量不少于其需要量的80%min( d3X11X21X12X22x13X23d4d5 )X31d3X32 d4X33 d5d3160d480d5360P4：實(shí)際的總運(yùn)費(fèi)不超過(guò)當(dāng)不考慮P1至P6各目標(biāo)時(shí)的最小總運(yùn)費(fèi)的110%。mind634Cjxjd6d62950110%i1j1P5：因路況原因，盡量避免安排A2的物資運(yùn)往B4mind7X24d7d70P6:對(duì)Bi和B3的供應(yīng)率要盡可能相同min(d8d8)X11 X21 X31200X13 X23 X33450d8d8綜上

7、所述，將該問(wèn)題列成優(yōu)先目標(biāo)規(guī)劃模型:minz1d1,minz2d2,minz3d3d4d5minz4d6,minz5d7,minz6d8d8Xiix12Xl3Xl4300X21X22X23X24200X31X32X33X34400X14X24X34didi250X31d2d2100XiiX21X31d3d3160x12X22X32d4d480Xi3X23X33d5d536034CijXijd6d63245i1j1X24d7d70200(XiiX21X31)(X13X23X33)d8d80300題型II目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法就是通過(guò)圖形來(lái)確定所給目標(biāo)規(guī)劃的滿意解，雖然比較直觀，但因?yàn)槭?/p>

8、平面圖，所以最多只能求解包含兩個(gè)決策變量的目標(biāo)規(guī)劃問(wèn)題。其解題步驟是：第一步，建立直角坐標(biāo)系，作出硬約束的限制區(qū)域；第二步，作出其他約束條件當(dāng)偏差變量為0時(shí)的圖形，確定其它各約束條件的限制區(qū)域；第三步，結(jié)合決策變量的可行范圍，按優(yōu)先因子考察各偏差變量的變化對(duì)目標(biāo)函數(shù)的影響，確定盡可能滿足目標(biāo)的滿意解。例6-3用圖解法找出以下目標(biāo)規(guī)劃問(wèn)題的滿意解。minZPi(didi)PzQd?da)X110x2d1d1503X15x2d2d220s.t8x16x2d3d3100Xi,X2,di,di0,i1,2,3解：第一步，因?yàn)楸绢}沒(méi)有硬約束，所以先作出偏差變量為0時(shí)，各目標(biāo)約束所確定的直線，如圖5-1所

9、示。第二步，按優(yōu)先因子考慮各偏差變量的變化對(duì)目標(biāo)函數(shù)的影響，確定約束條件所限定的X1,X2范圍。要滿足min(didi),只能在CD射線上取得滿意解；顯然，在CD射線上，5(&di)0o其次，在CD射線上使P2(2d2d3)達(dá)到極小點(diǎn)的只能是C點(diǎn)。第二步，確定滿意解。由圖6-1可知，滿意解為xi50,x208x1+6x2=100圖6-1例6-4用圖解法找出以下目標(biāo)規(guī)劃問(wèn)題的滿意解。minZp1d2p1d2Psd1x12x2d1d11010x112x2d2d262.4s.t24x28x1,x2,di,d20,i1,2解：第一步，首先作出硬約束等式直線AB:2x1x28第二步，再作出偏差變

10、量為0時(shí)，各目標(biāo)約束所確定的直線DI和CH,如圖6-2所示。第三步，按優(yōu)先因子考慮各偏差變量的變化對(duì)目標(biāo)函數(shù)的影響，確定約束條件所限定的x1,x2范圍。要滿足min(d2d?),并且滿足硬約束2x1x28所在范圍，只能在GC線段上取得滿意解；而要滿足mind1,滿意解又只能是在CE線段上。第三步，確定滿意解。由圖6-2可得滿意解為C(0,和E(,)連線上任一點(diǎn)圖6-2題型III目標(biāo)規(guī)劃的單純形法例6-5用單純形法求以下目標(biāo)規(guī)劃問(wèn)題的滿意解minZp1d2p1d2p2d1x12x2d1d11010x112x2d2s.t2x1x2d262.48x1,x2,di,di0,i1,2解：第一步，將原規(guī)劃

11、化為標(biāo)準(zhǔn)型minZp1(d2d2)p2d1x12x2d1d11010x112x2d2d262.4s.t2%x2x38x1,x2,x3,di,di0,i1,2第二步，取d1,d2,x3為初始基變量，列初始單純形表，如表6-2所示表6-2c000P20P1P1旦aikiCbXBbx1x2x3d1d1d2d2P2d1101201-10010/2P1d210120001-1120x3821100008/1Cj-zjPi-io-i200002P2-i-200i00第三步，取k=1,檢查檢驗(yàn)數(shù)的Pi行的負(fù)數(shù)，取最小者-12對(duì)應(yīng)的變量X2為換入變量，并用最小比值原則確定換出變量為di,見(jiàn)表6-3。表6-3C

12、j000P20PiPibiaikCbXbbxix2x3didid2d20x25I/2i0I/2-I/200-Pid2400-66i-i60x333/20i-I/2I/2003/(i/2)cj-ziPi-4006-602P2000i000第四步，還是取k=1,檢查檢驗(yàn)數(shù)的Pi行的負(fù)數(shù)，取最小值-6對(duì)應(yīng)的變量di為換入變量，并用最小比值規(guī)則確定換出變量d2,見(jiàn)表6-4。表6-4C000P20PiPibiaikCbXbbxix2x3didid2d20x25/6i000i/i2-i/i2-0di2/300-iiI/6-I/60x37/60i00-i/i2i/i2Cj-zjPi00000iiP2000i

13、000第五步，檢查檢驗(yàn)數(shù)的Pi行，P2行，都沒(méi)有負(fù)數(shù)了，故得到滿意解x*(0,5.2)T且因?yàn)榉腔兞縳i的檢驗(yàn)數(shù)為0,所以存在多重解。例6-6用單純形法求解下列目標(biāo)規(guī)劃問(wèn)題。minZpi(2di3d2)p2d4p3d3xix2didiI0xid2d24s.t5xi3x2d3d356xix2d4d4I2為？2<40,ii,2,3,4解：第一步：該問(wèn)題已經(jīng)化為標(biāo)準(zhǔn)形，以di,d2,d3,d4為基變量，建立初始單純形表，如表6-5所示。表6-5初始單純性表XBbXiX2d1d1d2d2d3d3d4d4di10111-1000000d2410001-10000d3565300001-100d4

14、12110000001-1Cj-ZjPi0002030000P20000000001P3-5-300000100第二步：在表6-5中，檢驗(yàn)數(shù)矩陣中第一列、第二列均有負(fù)數(shù)，因此此表對(duì)應(yīng)的解不是滿意解，需要進(jìn)行迭代。以為進(jìn)基變量，d2為出基變量，進(jìn)行基變換運(yùn)算，結(jié)果如表6-6所示。表6-6第一次迭代表XbbX1X2d1d1d2d2d3d3d4d4d16011-1-110000X1410001-10000d3360300-551-100d480100-11001-1Cj-zjP10002030000P20000000001P30-3005-50100第三步：在表5-6中，檢驗(yàn)數(shù)矩陣中第二列仍有負(fù)數(shù)，以X2為進(jìn)基變量，di為出基變量，進(jìn)行基變換運(yùn)算，結(jié)果如表6-7所示。表6-7第二次迭代表XBbX1X2d1d1d2d2d3d3d4d4X26011-1-110000Xi410001-1