《运筹学课后习题三.docx》由会员分享，可在线阅读，更多相关《运筹学课后习题三.docx（24页珍藏版）》请在三一文库上搜索。
1、习题三3.1某公司今后三年有五项工程可以考虑投资。每项工程的期望收入和年度费用3-10所示。（万元）如表表3-10工程费用收入第一年第二年第三年151830247240359620475215586930资金拥有量302530每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。【解】设Xj1投资j项目，模型为20x315x4 303025j0不投资j项目maxZ30x140x2花5x-i4x25x37x48x5X17x29x35x46x58x!2x26x32&9x530x尸0或1,j1,5最优解X=（1,1,1,0,1）,Z=110万元，即选择项目1、2、3、5时总收入最
2、大。3.2 址问题。以汉江、长江为界将市划分为汉口、汉阳和武昌三镇。某商业银行计划投资9000万元在市备选的12个点考虑设立支行，如图3-10所示。每个点的投资额与一年的收益见表3-10。计划汉口投资2?3个支行，汉阳投资1?2个支行，武昌投资3?4个支行。如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。图3-10表3-11地址i123456789101112投资额（万900120010007506808007201150120012508501000收出（万元）400500450350300400320460500510380400【解】设Xj为投资第j个点的
3、状态，x=1或0,j=1,2,-,12maxZ 400x 1500x2450x3400xi2900xi 1200X244Xj 2,Xjj ij i1000X 3r 1 r 73, Xj 1, j 5850x11 1000x12712Xj 2, Xj 3j 5j 8900012Xjj 8Xj1或0,j8920万元。最优解：x1=x5=x12=0,其余xj=1,总收益Z=3870万元，实际完成投资额3.3 一辆货车的有效载重量是20吨，载货有效空间是8X3.5X2m。现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-12。另外，在货物4和5中先运货物5,货物1和2不能混装，怎样安排货物
4、运输使收入最大，建立数学模型。表3-12货物号123456重量（T）653472体积（m）374562收入（百元）584673【解】设Xj为装载第j件货物的状态，Xj=1表示装载第j件货物，Xj=0表示不装载第j件货物，有maxZ5x18x24x36x47x53x66x15x23x34x47x52x6203x17x24X35x46X52x656x4x50为X21xj0或13.4 女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马及自由体操。（2）每个运动员最多只能参加3个项目弁且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，弁且总的参赛人次数等于10
5、；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表3-13所示。表3-13高低杠平衡木鞍马自由体操甲8.69.78.99.4乙9.28.38.58.1丙8.88.79.39.6丁8.57.89.57.9戊8.09.48.27.7怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。【解】设Xj（i=1,2,，5;j=1,2,3,4）为第i人参赛j项目的状态，即1第i人参赛j项目ij0第i人不参赛j项目记第i人参赛j项目的成绩为C,，目标函数54maxZCijXiji1j1每个运动员最多只能参加3个项目并
6、且每个项目只能参赛一次,约束条件:Xi1Xi2Xi3Xi43i1,2,5每个项目至少要有人参赛一次，并且总的参赛人次数等于10,约束条件：X1jX2jX3jX4jX5j1j1,2,3,454Xij10数学模型为maxZCijXjj1Xi1Xi2X3Xi41,2，|，5x1jX2jX3jX4jX5j1j1,2,3,454Xi10j1Xij1或0,i1,2,|,5;j1,2,3,43.5利用0-1变量对下列各题分别表示成一般线性约束条件(1) X1+2x210及2x1+6x25,则x210,否则X2W8X1取值2,4,6,8中的一个X12X28y1M4x(x210y2M【解】(1)2x6X218y
7、sMy1y2y210或1,1,2,36?考虑下列数学模型X5yM1X5(1y)M1X210yMX28(1y)My0或1X1(3)y1yj2y14y26y38y4yyy10或1,j1,2,3,4minf(xjgg)其中106%,若01510X2，若X20fx10,gg)(X1)0,0,若X20满足约束条件若X1(1) Xi8或X26(2) |Xi-X2|=0,4或8(3) Xi+2X220、2x计X220及x计X220三个约束中至少一个满足(4) X0,X20将此问题归结为混合整数规划的数学模型。mi nZ 10 y 1 6X115y210X2X1yM ;X2X1ysM条件(1)X2(1 y3)
8、MX1X20y44y54y68y7 8y8条件(2)【解】y4y5y6y7 y 1X12X220ygM条件(3)2x120y1 MX1X220yuMy9y10ynXi0,x0; yj0或1,1,2,1条件(4)min Z 2x 1 3x2x1 2x29(2)1 22x1 x210x1,x20且为整7.用分枝定界法求解下列IP问题maxZx-ix2minZX12X23为2x27/c、X1X210(1) 12(2)2x14x2510x12x250x1,x20且为整数X1,X2数0且为整【解】(1)X=(1,2),或X=(0,3)Z=3X=(5,0),Z=5&用割平面法求解下列IP问题maxZ2x1
9、3x2x12x29(2) 12x1x210x1,x20且为整数【解】(1)X=(3,3),Z=15(2)X=(5,2),Z=169.用隐枚举法求解下列BIP问题maxZ4xi3x2+X35xi2x2X364Xi2x2X37Xj0或1,j1,2,3【解】(1)X=(1,1,1),Z=8(2)X=(1,1,1,0),Z=4minZ4xx；x33xX11X24X35X43(3) 3X1X22x32X44X13X22x34X47Xj0或j123,410?用分枝定界-隐枚举法求解下列BIP问题maxZ4搭x2x33x4X1 X2 4X3(1) 3X1 X2 2X3X13X2 2X3Xj0 或 j【解】(
10、1)X=h,0,1,1),Z=85X48Z2X444X471,234(2)X=(1,1,0,0,0),Z=min3x1x22X36X4X5X-!5X2X32X4X582为2x23x32x4x54Xj0或1,j1,5一2习题四4.1工厂生产甲、乙两种产品，由A、E二组人员来生产。A组人员熟练工人比较多，工作效率高，成本也高；E组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示表4.21产品甲产品乙效率（件/小时）成本（元/件）效率（件/小时）成本（元/件）A组1050845B组845540产品售价（元/件）8075二组人员每天
11、正常工作时间都是8小时，每周5天。一周每组最多可以加班10小时，加班生产的产品每件增加成本5元。工厂根据市场需求、利润及生产能力确定了下列目标顺序:R：每周供应市场甲产品400件，乙产品300件P：每周利润指标不低于500元P3：两组都尽可能少加班，如必须加班由A组优先加班建立此生产计划的数学模型。【解】解法一：设X1,X2分别为A组一周正常时间生产产品甲、乙的产量，X3,X4分别为A组一周加班时间生产产品甲、乙的产量；X5,X6分别为B组一周正常时间生产产品甲、乙的产量，X7,X8分别为B组一周加班时间生产产品甲、乙的产量。总利润为80(X1 X3 X5 X7) (50 为75(X2 X4
12、X6 Xs) (45X230x1 30x2 25X3 25x455x3 45X5 50X7)50x4 40x6 45 禺)35x5 35x6 30x730x8生产时间为A组：O.lxi0.125X20.1x30.125X4B组：0.125/E0.2X60.125X7O.2xs数学模型为：minZp1(d1d2)X1X3X5X7X2X4X6X8d2P2d3P3(d4d5)P4(d6d1400d23002d7)30xi30X225x325x435x535x60.1X10.125X2d4d44030x730X8d3d35000.125x50.2x6d5d5400.1x30.125x4d6d6100.
13、125x70.2x8d7d710Xj0,di,di0,i|,7；j1,2,|3设X1,x2分别为A组？周生产产品乙的正常时间乙的加班时间；X5,X6界别为B组周生产产品解法二：产品甲、B组一周生产产品甲、乙的加班时一甲、X3,X4分别为A组？周生产乙的正常时间，XX8分别为间。总利润为10X180508X2(7545)10x380558X4(7550)8X5(8045)5X6(7540)8X7(8050)5八(7545)300x1240X2250X3200&280%175x6240x7150x8数学模型为minzP1?d?)P2d3P3(d4ds)P4(d62d?)10x110x38X58x7
14、d1d14008x28x45x65Xgd2d2300300x1240x2250x3200x4280x5x1x2d4d440X5X6d5d540X3X4d6d610X7X3d7d710Xj0,di,di0,i1,2,7;j1,24.2【解】设Xj为A到B的运量，数学模型为175x6240x7150x8d3d3500l,8minzRd1P2(ad3d4)f3d5f4d6P5(d7d7)f6d8X13X23X33didi480X11X21XOd31d2d2272B3保证供应需求的85%X12Xi4X22X24X32X34d3d4X33d5d5200X21deSt2冷2X22:2X324C.ijj1X
15、jd80d3d4AbBbXiiX12X13Xi4204323X13X23560B2需求的B4需求的X33d7d7衡运费最小85%85%0B与B3的平X21X31X22X32X23X33X24X34400750Xj(i1,2,3;j1,2,3,4)；di,di4.3双击下图,0(i1,2,.,8)；打开幻灯片。习题4.3(1)minZpidi8x,4x2d1d1X1d2d2X12x2d3d3X1,X2,di,diP2(2d2d3)2X20,i1604030401,2,3满意解在线段AB上30aA2,1)5-3,20/3)10304050(50/B(3Q6Kddi10 一.X2(2)2X.*d21
16、习题4.3(2)minzp(did?)p2d3X)x2dsd3Xi2x?chx,x2fdiFd.满意解X=(2t0)(3)3/飞3XL_.X122d3126(i1,2,3)习题4.3(3)60、(1)50-Xd240X川x30一心、2010-Xix2&Kx25Xd3x2d4ANd,(3)一y/4(4)售1。)d2)did2d3d4,diP2d3406050200(iP3d41,4)102030405060满意解：X=(50,10).1习题4.3(4)minZXi2X2XiX2di(3(0,3)d2d3did2di4.4已知某实际问题的线性规划模型为假定重新确定这个问题的目标为:Pi:z的值应不
17、低于i900P2:资源1必须全部利用将此问题转换为目标规划问题,m数学模型为4.5已知目标规划问题minz满意解:X=(0,3)maXzi00Xi50X2i0Xii6X2200iiXi3X225Xi,X2列出数学模型。minZi00XiiOAiiXiXj?Pidi50xi6x23X2pidiP2dP2(d2；did2250,jP3(5d3d2pi(2did2)P2d36Xi2X2X2d3d3Xi,X2,di,di（资源（%源2）dii,2di2d2d20,ii,2,3d2)i9002003d4)巳diXi2X2didiXi2X2d2d2Xi2X2d3d3X2d4d4Xi,X2,di,di0(i
18、1,4)5/4 )(中分析w、W2的比例变动)解的变化。 minz pdP2d2PA P4(5d33d4 )(1)分别用图解法和单纯形法求解；(2)分析目标函数分别变为、两种情况时P4diminzpGP2d2F3(w-d3w2d4)【解】(1)图解法(双击下图，打开幻灯片)习题4.5(1)minzP&B(5da3d4)时(2)*x24艰卜4)(ields*.已4ad2ad4did2d4x?1569420(3)(13/2,5/4)%2x?%2x23/45d3满意解：X=(13/2,5/4)(1)单纯形法G00P0P5P303P0bCb基X1X2d+dc+d2d3+c3d4+d4Rdi121_16
19、0d121_195P3d1-21一143P3cL11一12表(1)c-ZP一1-21F21R-5753P1Pd11一12220cb11一12255P3ds11_12-280X21112表GZP_112-2P1R-575一710R10Xi11/21/21/21/20013/2Pdi+一111一133Pd41/41/41/41/4113/40X211/41/41/45/4表G-ZP1P1R3/43/417/43/43R111(b)minzpidiP?d2F3(widaW2d4)Pqdi单纯形法，利用上表(5)的结果，引入参数w、W2进行灵敏度分析，得到下表。G00P0PwR00bCb基XiX2d1
20、+diCb+d2cb一+Cbd4+d40X111/21/21/2一1/20013/2d；_111一13W2Pd1/41/41/4一1/4113/40X211/41/41/45/4表(1)G-ZP1R1RW2/4w/4w-W2/4w/4wR1110X111一1-225Pd；一111一13wRc3一11114一430xT1112表G-ZP1巨1RW-Www4w4wR1_11(1)由表(1)知，当wW2/40,即w-(wi,W20)时，满意解为：X=(13/2,W24,w1(2)w2(3)1当一(wi,W20)时，表(1)和表都是满意解。4由表(2)知，当W24w0,即口W1(Wi,W20)时，满意解为：X=(5,2)w24