運(yùn)籌學(xué)習(xí)題集

1、數(shù)學(xué)建模1、某織帶廠生產(chǎn)A、B兩種紗線(xiàn)和C、D兩種紗帶，紗帶由專(zhuān)門(mén)紗線(xiàn)加工而成。這四種產(chǎn)品的產(chǎn)值、成本、加工工時(shí)等資料列表如下： 產(chǎn)品 項(xiàng)目ABCD單位產(chǎn)值 (元)1681401050406單位成本 (元)4228350140單位紡紗用時(shí) (h)32104單位織帶用時(shí) (h)0020.5工廠有供紡紗的總工時(shí)7200h，織帶的總工時(shí)1200h，列出線(xiàn)性規(guī)劃模型。解：設(shè)A的產(chǎn)量為x1，B的產(chǎn)量為x2，C的產(chǎn)量為x3，D的產(chǎn)量為x4，則有線(xiàn)性規(guī)劃模型如下：max f(x)=(168-42)x1 +(140-28)x2 +(1050-350)x3 +(406-140)x4=126 x1 +112 x2

2、 +700 x3 +266 x4s.t. 工廠1工廠2200萬(wàn)m3500萬(wàn)m32、靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，在兩個(gè)工廠之間有一條流量為200萬(wàn)m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬(wàn)m3和1.4萬(wàn)m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。現(xiàn)在要問(wèn)在滿(mǎn)足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠處理工業(yè)污水的總費(fèi)用最小。列出線(xiàn)性規(guī)劃模型。解：設(shè)x1、x2分別代表工廠1和工廠2處

3、理污水的數(shù)量(萬(wàn)m3)。則問(wèn)題的目標(biāo)可描述為min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x203、紅旗商場(chǎng)是個(gè)中型的百貨商場(chǎng)，它對(duì)售貨人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如表所示。為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問(wèn)應(yīng)該如何安排售貨人員的作息，既滿(mǎn)足了工作需要又使配備的售貨人員的人數(shù)最少？（只建模型，不求解）時(shí) 間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：設(shè)x1為星期一開(kāi)始上班的人數(shù)，x2為星期二開(kāi)始上班的人數(shù)，x7星期日開(kāi)始上班的人數(shù)。 min

4、x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x728x4+x5+x6+x7+x115x5+x6+x7+x1+x224x6+x7+x1+x2+x325x7+x1+x2+x3+ x419x1+x2+x3+x4+x531x2+x3+x4+x5+x628x1、x2、x3、x4、x5、x6、x704、一個(gè)登山隊(duì)員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等，每種物品的重量及重要性系數(shù)見(jiàn)表所示，能攜帶的最大重量為25 kg，試選擇該隊(duì)員所應(yīng)攜帶的物品。序號(hào)1234567物品食品氧氣冰鎬繩索帳篷照相器材通信設(shè)備重量kg55251023重要性系數(shù)2解：引入01變

5、量xi （i1，7）則01規(guī)劃模型為：max z20x115x216x314x48x514x69x7s.t. 5x15x22x35x410x52x63x725xi0或1，i1，0，7標(biāo)準(zhǔn)化問(wèn)題1、將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)形式 2、化下列線(xiàn)性規(guī)劃為標(biāo)準(zhǔn)形max z=2x1+2x24x3x1 + 3x23x3 30x1 + 2x24x380x1、x20，x3無(wú)限制解：按照上述方法處理，得該線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形為 max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30x1 + 2x24x31 + 4x32 + x5 = 80x1、x2，x31，x32，x4，x

6、5 0圖解法111z=42z=6OA圖131、用圖解法求解下面線(xiàn)性規(guī)劃。 max z=2x1+2x2x1x2 1x1 + 2x2 0x1、x2 0解：圖13中陰影部分就是該問(wèn)題的可行域，顯然該問(wèn)題的可行域是無(wú)界的。兩條虛線(xiàn)為目標(biāo)函數(shù)等值線(xiàn)，它們對(duì)應(yīng)的目標(biāo)值分別為2和4，可以看出，目標(biāo)函數(shù)等值線(xiàn)向右移動(dòng)，問(wèn)題的目標(biāo)值會(huì)增大。但由于可行域無(wú)界，目標(biāo)函數(shù)可以增大到無(wú)窮。稱(chēng)這種情況為無(wú)界解或無(wú)最優(yōu)解。2、用圖解法求解下述LP問(wèn)題。解： 可知，目標(biāo)函數(shù)在B(4, 2)處取得最大值，故原問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)最大值為。3、 用圖解法求解以下線(xiàn)性規(guī)劃問(wèn)題：（1）maxz=x1+3x2s.t.x1+x210

7、-2x1+2x212x1 7x1,x20 x2 10 (2,8) 6 x1 -6 0 7 10最優(yōu)解為（x1,x2）=（2,8），max z=26(2)minz=x1-3x2s.t.2x1-x24x1+x23x25x14x1,x20 x2 5 3 x1 0 2 3 4最優(yōu)解為 （x1，x2）=（0，5），min z=-15（3）maxz=x1+2x2s.t.x1-x21x1+2x24x13x1,x20 x2 2 x1 0 1 2 3 4多個(gè)最優(yōu)解，兩個(gè)最優(yōu)極點(diǎn)為（x1，x2）=（2，1），和(x1，x2)=(0，2)，max z=5（4）minz=x1+3x2s.t.x1+2x242x1+x2

8、4x1,x20 x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最優(yōu)解為（x1，x2）=（4，0），min z=4單純形法1、用單純形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20解：首先將問(wèn)題化為標(biāo)準(zhǔn)形式，然后將整個(gè)計(jì)算過(guò)程列在一個(gè)表中Cj50100000b CBXB x1 x2x3x4x5 0x311100300 0x421010400 0x501001250z501000000 0x31010-150 0x42001-1150 100x201001250z50000-10025000 50x11010-150

9、 0x400-21150 100x201001250z00-500-5027500由于j0（j=1，5），故X*=（50，250，0，50，0）T， Z*=275002、用單純形法求解max z=2x1+x2x1 + x252x15x210x1、x20解：用單純形表實(shí)現(xiàn)如表110 表110Cj2100b CBXB x1x2x3x4 0x3-11105 0x42-5011010/4(min)z21000 0x30-3/211/210 2x11-5/201/25z060-1102=6 0，且p20，故該線(xiàn)性規(guī)劃有無(wú)界解（無(wú)最優(yōu)解）。3、用單純形法（大M法）求解下列線(xiàn)性規(guī)劃max z=3x12x2x

10、3x12x2 + x3 114x1 + x2 + 2x3 32x1 + x3 = 1x1、x2、x30解：化為標(biāo)準(zhǔn)形式 max z=3x12x2x3x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 = 32x1 +x3 = 1x1、x2、x3 、x4、x50在第二、三個(gè)約束方程中分別加入人工變量x6、x7，構(gòu)造如下線(xiàn)性規(guī)劃問(wèn)題max z=3x12x2x3Mx6Mx7x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70用單純形進(jìn)行計(jì)算，計(jì)算過(guò)程見(jiàn)表Cj3-1-1

11、00-M-Mb CBXB x1 x2x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M004M0x43-20100-110-Mx60100-11-21-1x3-20100011z1-1+M00-M0-3M+1M+10x43001-22-512-1x20100-11-21-1x3-20100011z1000-1-M+1-M-123x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3-M+1/3-M+2/32由于j0（j=1，7），且

12、基變量中不含人工變量，故X*=（4，1，9）T， z*=24、用單純形法（大M法）求解下列線(xiàn)性規(guī)劃max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x20解: 化為標(biāo)準(zhǔn)形式后引入人工變量x5得到 max z=3x1+2x2Mx52x1+ x2 +x3 = 23x1 +4 x2 x4+x5 =12x1、x50用單純形法計(jì)算，過(guò)程列于表中。從表中可以看出，雖然檢驗(yàn)數(shù)均小于或等于零，但基變量中含有非零的人工變量x5=4，所以原問(wèn)題無(wú)可行解。 3200-MbCBxBx1x2x3x4x50-Mx3x52314100-101212-z3+3M2+4M0-M012M2-Mx2x52-

13、5101-40-10124-z-1-5M0-2-4M-M0-4+4M2、用單純形法求解下述LP問(wèn)題。解：首先將原問(wèn)題轉(zhuǎn)化為線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型，引入松弛變量x3, x4,x5，可得：構(gòu)造單純形表，計(jì)算如下：230000812100401640010012040013230000210101/220164001043301001/420003/42210101/2080041243301001/41200201/4241001/40040021/2132011/21/80003/21/80原問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)最大值為。3、用單純形法求解下述LP問(wèn)題。解：首先將原問(wèn)題轉(zhuǎn)化為線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型，引入

14、松弛變量、，可得：構(gòu)造單純形表，計(jì)算如下：340004021104003013011034000305/301-1/3184101/3101/3305/300-4/3318103/5-1/54401-1/52/500-1-1由此可得，最優(yōu)解為，目標(biāo)函數(shù)值為。4、用單純形法求解下述LP問(wèn)題。解：引入松弛變量、，化為標(biāo)準(zhǔn)形式：構(gòu)造單純形表，計(jì)算如下：2.510001535105010520122.510009019/513/545/192.5212/501/550001/2145/19015/193/192.520/19102/195/190001/2由單純形表，可得兩個(gè)最優(yōu)解、，所以?xún)牲c(diǎn)之間的所

15、有解都是最優(yōu)解，即最優(yōu)解集合為：，其中。5、用單純形法求解下述線(xiàn)性規(guī)劃解：引入松弛變量、和，列單純形表計(jì)算如下：1230000821810010413100101/308114001123000024/5-14/517/501-4/5032/51/10-3/10101/1004048/57/5-11/5002/5148/77/10-11/1000-3/1000160-528120141-3100100402-140-1101-70-1002600-71-1/25/211010-110-1/23/22201-70-1/21/20000-1/2-1/2故，原問(wèn)題的最優(yōu)解為， ，其中。7、用單純形法

16、求解下述LP問(wèn)題。解：構(gòu)造單純形表計(jì)算如下：340004021104003013011034000305/3011/3184101/3101/3305/3004/3318103/51/544011/52/50011故，最優(yōu)解為，目標(biāo)函數(shù)值為。8、用大M法求解下述LP問(wèn)題解：先將原問(wèn)題化為標(biāo)準(zhǔn)型，引入松弛變量，得：再引入人工變量、，得：構(gòu)造單純形表計(jì)算如下：2350MMM71110107M1025110153M+23-4M2M-5-M00M207/21/21/211/24/72515/21/21/201/207M/2+8M/2-6M/2+10-3M/2-134/7011/71/72/7-1/72

17、45/7106/7-1/75/71/700-50/7-1/7-M-16/7-M+1/7由此得，原問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)最優(yōu)值為102/7。9、用兩階段法求解下述LP問(wèn)題解：先將原問(wèn)題化為標(biāo)準(zhǔn)型，引入松弛變量，得：再引入人工變量、，得第一階段的模型為：構(gòu)造單純形表，計(jì)算如下：00001117111010711025110153421001207/21/21/211/24/70515/21/21/201/207/21/21/203/234/7011/71/72/7-1/7245/7106/7-1/75/71/7000011由此可得第一階段的最優(yōu)解，轉(zhuǎn)入第二階段，單純形表如下：235034/701

18、1/71/7245/7106/7-1/700-50/7-1/7由此得，原問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)最優(yōu)值為102/7。10、求解下述LP問(wèn)題 解：用大M法求解。將原問(wèn)題化為標(biāo)準(zhǔn)型，可得：在第三個(gè)等式約束中引入一個(gè)人工變量，可得：用單純形表求解，可得：101512000M0953110009/501556150100-M521100-115/22M+10M+15M+1200-M0109/513/51/51/50009024091611003/2M7/50-1/53/5-2/50-117/309-M/53M/5+10-2M/5-20-M0103/2139/8003/16-1/8000123/209/

19、1611/161/1600-M1/20-43/800-7/16-3/80-11027/8-43M/800-21/8-7M/16-5/8-3M/8-M0所有變量的檢驗(yàn)數(shù)均為負(fù)數(shù)或零，單純形表計(jì)算完畢，但人工變量仍在基變量中，故原問(wèn)題無(wú)可行解。寫(xiě)對(duì)偶問(wèn)題1、寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30解：其對(duì)偶問(wèn)題為min w=30y1+ 80y2y1+ 4y2 23y1 + 2y2 23y1 + 4y2 4y1、y202、寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 min z=2x1+8x24x3x1

20、+ 3x23x3 30x1 + 5x2 + 4x3 = 804x1 + 2x24x350x10、x20，x3無(wú)限制解：其對(duì)偶問(wèn)題為max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 23y1+5y2 + 2y3 83y1 + 4y24y3 =4y10，y2無(wú)限制，y30對(duì)偶的性質(zhì)1、已知線(xiàn)性規(guī)劃問(wèn)題 max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 + 3x3 +2x420x1、x2，x3，x40其對(duì)偶問(wèn)題的最優(yōu)解為y1*=6/5，y2*=1/5。試用互補(bǔ)松弛定理求該線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解。解：其對(duì)偶問(wèn)題為min w=20y1

21、+ 20y2y1 + 2y2 1 （1）2y1 + y2 2 （2）2y1 +3y2 3 （3）3y1 +2y2 4 （4）y1、y20將y1*=6/5，y2*=1/5代入上述約束條件，得（1）、（2）為嚴(yán)格不等式；由互補(bǔ)松弛定理可以推得x1*=0，x2*=0。又因y1*0，y2*0，故原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，所以2x3* +3x4* = 203x3* +2x4* = 20解得x3* = x4* = 4。故原問(wèn)題的最優(yōu)解為 X*=（0，0，4，4）T2、已知線(xiàn)性規(guī)劃的最優(yōu)解為，試?yán)没パa(bǔ)松弛定理，求對(duì)偶問(wèn)題的最優(yōu)解。解：原問(wèn)題的對(duì)偶問(wèn)題為：將代入原問(wèn)題的約束條件，可得： （1）又由 （2

22、）將結(jié)論（1）和（2）結(jié)合起來(lái)，可解得。3、已知線(xiàn)性規(guī)劃問(wèn)題其對(duì)偶問(wèn)題的最優(yōu)解為、，試用對(duì)偶理論求解原問(wèn)題的最優(yōu)解。解：原問(wèn)題的對(duì)偶問(wèn)題為：將對(duì)偶問(wèn)題的最優(yōu)解代入約束條件，可得： （1）又由 （2）將結(jié)論（1）和（2）結(jié)合起來(lái)，可得： ，解得 即原問(wèn)題的最優(yōu)解為。對(duì)偶單純形法1、用對(duì)偶單純形法求下面問(wèn)題解：Cj 4600min( zj - cj)/ai*jCBXBbx1x2x3x4ai*j022 =c22（u2+v2）=4（1+1）= 2023 =c23（u2+v3）=3（1+6）= 2034 =c34（u3+v4）=9（2+4）= 30由于23 =20，故表中基可行解不是最優(yōu)解，并以x23為

23、第一個(gè)頂點(diǎn)作閉回路，如下銷(xiāo) 地產(chǎn)地B1B2B3B4產(chǎn)量A120525503764A220x23202433A32010308389銷(xiāo)量40201525該閉回路上，偶數(shù)頂點(diǎn)上的基變量最小值為5，以該調(diào)整量進(jìn)行調(diào)整得到如表銷(xiāo) 地產(chǎn)地B1B2B3B4產(chǎn)量A12525503764A2155202433A32010308389銷(xiāo)量402015254、用最小元素法給出運(yùn)輸問(wèn)題的初始可行解，檢驗(yàn)解的最優(yōu)性，如果不是最優(yōu)解，改進(jìn)成最優(yōu)解。甲乙丙丁產(chǎn)量A1067124B1610599C5410104銷(xiāo)量5246解： 用最小元素法求得初始解：甲乙丙丁產(chǎn)量A314B459C224銷(xiāo)量5246用位勢(shì)法計(jì)算u和v：甲乙丙丁uiA(10)(12)0B(5)(9)-3C(5)(4)-5vj109812計(jì)算非基本變量的檢驗(yàn)數(shù)：甲乙丙丁uiA-3(6)-1(7)0B9(16)4(10)-3C7(10)3(10)-5vj109812以(A乙)作為調(diào)入格，用閉回路調(diào)整法計(jì)算(A乙)的新運(yùn)量：甲乙丙丁產(chǎn)量A1214B459C44銷(xiāo)量5246用位勢(shì)法計(jì)算非基變量的檢驗(yàn)數(shù)：甲乙丙丁uiA(10)(6)-1(7)(12)0B9(16)7(10)(5)(9