运筹学课后习题三

1、习题三某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用（万元）如表3-10所示。【解】设xj1投资j项目0不投资j项目模型为表 3-10工程费用收入A年第二年第三年151830247240359620475215586930资金拥有量302530每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。图 3-10maxZ 30x1 40x2 20x3 15x4 30%5x14x25x37x48x530x1 7x2 9x3 5x4 6x5258x12x26x32x49x530xj=0或 1,j 1,L ,5最优解X=(1,1,1,0,1), Z=110万元，

2、即选择项目1、2、3、5时总收入最大。址问题。以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。某商业银行计划投资 9000万元 在武汉市备选的12个点考虑设立支行，如图3-10 所示。每个点的投资额与一年的收益见表 3-10o 计划汉口投资 23个支行，汉阳投资 12个支 行，武昌投资34个支行。如何投资使总收益最大，建立该问题的数学模型， 说明是什么模型，可以用什么方法求解。表 3-11地址i123456789101112投资额（力兀）900120010007506808007201150120012508501000收益（万元）40050045035030040032046050051

3、0380400【解】设xj为投资第j个点的斗犬态,xj=1或0, j =1,2,12maxZ 400xi 500X2 450X3 L 400x12900x1 1200x2 1000x3 L 850x11 1000x12 900044771212xj 2, xj 3, xj 1, xj 2, xj 3, xj 4j 1j 1j 5j 5j 8j 8xj 1 或 0, j 1,L ,12最优解：x1 = x5=x12=0,其余xj=1,总收益Z=3870万元，实际完成投资额 8920万元。一辆货车的有效载重量是20吨，载货有效空间是 8XX 2 m）现有六件货物可供选择运输，每件货物的重量、体积及

4、收入如表表3-12。另外，在货物4和5中先运货物5,货物1和2不能混装，怎样安排货物运输使收入最大，建立数学模型。表 3-12货物号123456重量（T）653472体积（品）374562收入（百元）584673【解】设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装载第j件 货物，有maxZ5x18x24x36x47x53x66x15x23x34x47x52x6203x17x24x35x46x52x656x4 x5 0 x1 x2 1 xj 0或 1 女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马及自由体操。（2）每个运动员最多只

5、能参加 3个项目并且每个项目只能参赛一次； （3） 每个项目至少要有人参赛一次，并且总的参赛人次数等于10; （4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表 3-13所示。表 3-13?高低杠平衡木鞍马自由体操甲乙丙丁戊怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。【解】设xj （i =1 , 2,，5; j = 1 , 2, 3, 4）为第i人参赛j项目的状态，即1 第i人参赛j项目xijj 0 第i人不参赛j项目记第 i 人参赛 j 项目的成绩为Cij , ，目标函数54maxZCij x

6、iji1j1每个运动员最多只能参加3 个项目并且每个项目只能参赛一次xi1 xi2xi 3xi43 i每个项目至少要有人参赛一次，并且总的参赛人次数等于1,2,10，约束条件：, 约束条件：,5约束条件：x1 jx2 jx3 jx4 j x5 j 1 j 1, 2,3, 454xij10i1j1数学模型为54maxZCij xiji1j1xi1 xi 2 xi3 xi4x1 j x2j x3 j x4 j54xij 10i1j1xij1或 0,i 1,2,L3 i 1,2,L ,5 x5j1 j 1,2,3, 4,5; j 1,2,3,4利用0 1 变量对下列各题分别表示成一般线性约束条件(1

7、) xi+2x2W8、4xi+X2R10及2xi+6x2W 18三个约束中至少两个满足(2)若 xi>5,则 X2>10,否则 X2<83) x1 取值2， 4， 6， 8 中的一个2y1 4y2 6y3 8y4y2y3 y4 10或 1， j 1,2,3,4x1 2x2 8 y1M4x1 x2 10 y2 M 解 】 (1) 2x1 6x2 18 y3My1 y2 y21y j 0或 1， j 1,2,3x15yMx15(1y)Mx1(2) x2 10 yM (3) y1x28(1y)Myjy 0或 16考虑下列数学模型min Z f (x1) g (x2)其中f (x1)

8、10 6x1，若 015 10X2，若 X2 0, g(x2 )0, 若 x1 00, 若 x2 0满足约束条件(1) XiR8 或 X2>6（ 2） | x1 x2|=0 ， 4 或 8（3） Xi+2X2>20> 2Xi+X2R20及X1+X2A20三个约束中至少一个满足（4） Xi>0, X2>0将此问题归结为混合整数规划的数学模型。min Z i0yi 6Xi i5y2 i0X2解】XiyiM ; X2y2 MXi 8 y3MX26 (i y3)MXi X2 0y4 4y5 4y6 8y7 8y8 y4 y5 y6 y7 y8 iXi 2X220 y9M2

9、Xi X220yi0MXi X220 yiiMy9 yi0 yii 2Xi 0,X20;yj 0或 i， j i,2, ，ii条件（i）条件（2）条件（3）条件（4）7用分枝定界法求解下列IP 问题maXZ Xi X2i）3Xi 2X2 72Xi 4X2 5Xi, X2 0且为整数min Z Xi 2X2Xi X2 i0i0Xi 2X250Xi ,X2 0且为整数【解】(1)X=(1,2),或*= (0,3) Z=3 X=(5,0),Z=58用割平面法求解下列IP 问题maXZ2Xi 3X2Xi2X29( i)i 22Xi X2i0Xi ,X20且为整数【 解 】 (i)X=(3,3),Z=i

10、5 (2)X=(5,2),Z=i6min Z 2Xi 3X22）Xi 2X2 92Xi X2 i0Xi,X2 0且为整数9用隐枚举法求解下列BIP 问题(1)maxZ 4x1 3x2+ x35x14x12x2 x32x2 x3xj0或 1, j 1,2,3min Z4x1 x2! x33x4x1x2 4x35x43(2)3x1x2 2x32x44x13 x2 2x34x47xj0 或 1, j1,2,3,4【解】(1)X=(1,1,1),Z=8 (2)X=(1,1,1,0),Z=410.用分枝定界隐枚举法求解下列BIP问题(1)max Z 4x1 x2 x3 3x4x1 x2 4x3 5x48

11、3x1x2 2x3 2x44(2)min Zx13x1x2 2x3 6x4 x55x2 x3 2x4 x5 8x1xj3x2 2x 3 4x47 0或 1, j 1,2,3,42x12x2 3x3 2x4 x5 4xj0或 1, j 1, ,5-2【解】(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z二习题四工厂生产甲、乙两种产品，由A、B二组人员来生产。A组人员熟练工人比较多，工作效率高，成本也高；B组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表所示。表产品甲产品乙效率（件/小时）成本（元/件）效率（件/

12、小时）成本（元/件）A组1050845B组845540产品售价（元/件）8075二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成本 5元。工厂根据市场需求、利润及生产能力确定了下列目标顺序：Pi：每周供应市场甲产品 400件，乙产品300件P2：每周利润指标不低于 500元两组都尽可能少加班，如必须加班由A组优先加班建立此生产计划的数学模型。【解】 解法一：设xi, x2分别为A组一周内正常时间生产产品甲、乙的产量，x3, x4分别为A组一周内加班时间生产产品甲、乙的产量；x5, x6分别为B组一周内正常时间生产产品甲、乙的产量，x7, x

13、8分别为B组一周内加班时间生产产品甲、乙的产量。总利润为80(x1乂3x5乂7)(50% 55x3 45x550x7)75(x2x4x6%)(45x2 50x4 40x645x8)30x130x225x325x4 35x5 35x630x7 30x8生产时间为A组：0.1xi 0.125x2 0.1x3 0.125x4B组：0.125x5 0.2x6 0.125x7 0.2x8数学模型为：min Zp1(d1d2 ) p2d3p3(d4d5) p4(d6 2d7)x1 x3 x5 x7 d1 d1400x2 x4 x6 x8 d2d2 30030x1 30x225x3 25x4 35x5 35

14、x6 30x7 30x8 d3d35000.1x1 0.125x20.125x5 0.2x60.1x3 0.125x40.125x7 0.2x8d4 d440d5 d540d6 d610d7 d710xj0,di ,di0,i 1,2,L ,7; j 1,2,L ,8解法二：设x1, x2分别为A组一周内生产产品甲、乙的正常时间，x3, x4分别为A组一周内生产产品甲、乙的加班时间；x5, x6分别为B组一周内生产产品甲、乙的正常时间，x7, x8分别为 B 组一周内生产产品甲、乙的加班时间。总利润为10x1 80 508x2(75 45) 10x3 80 558x4(75 50)8x5(80

15、 45) 5x6 (75 40) 8x7 (80 50) 5x8 (75 45)300x1 240x2 250x3 200x4 280x5 175x6 240x7 150x8数学模型为minz p1(d1 d2) p2d3p3(d4 d5 ) p4(d6 2d7)10x1 10x3 8x5 8x7 d1 d14008x2 8x4 5x6 5x8 d2 d2300300x1 240x2 250x3 200x4 280x5 175x6 240x7 150x8 d3 d3 500x1x2d4d440x5x6d5d540x3x4d6d610x7x8d7d710xj 0,di ,di 0,i 1,2,L

16、 ,7; j 1,2,L ,8解 】设 xij 为Ai到Bj 的运量，数学模型为min zRd1P2(d2d3d4) P3d5 P4d6 P5(d7 d7) P6d8X13X23X33xiix2ix31X12X22x32X14X33X24d5X34d5d1 d2 d3 d4200d1 d2 d3 d4480272204323B3保证供应B1需求的85%B2需求的85%B4需求的85%X21st 2x123d612X222X32A3 对 B3A对BiX13X23X33d7 d70 B2 与 B3 的干衡4cij Xijd81运费最小X11X21X12X22X13X23X14X24560400X3

17、1XijX320X33X34750(i 1,2,3; j 1,2,3,4);di ,di0(i 1,2,8);双击下图，打开幻灯片。习题4.3(1)P2(2d1min Z p&I2 d 3)16030401,2,3习题4.3(3)min zpi(did2)p2d33126(i 1,2,3)习题4.3(3)P2d3406050200 (iP3d41, ,4)满意解：X=(50,10)习题4.4(4)min Zpi (2di d2 ) p2d3x1 2x2640,i 1,2,3di 2d2 d22已知某实际问题的线性规划模型为max z 100x150x210x1 16x2 200（资源

18、1）11xi 3x225（资源 2）x1，x20假定重新确定这个问题的目标为： P1 : Z的值应不低于 1900 P2：资源1必须全部利用将此问题转换为目标规划问题，列出数学模型。【解】数学模型为min Z p1d1P2（d2 d2）100x1 50x2 d1 d1190010x1 16x2 d2 d220011x1 3x225xj,dj,dj 0, j 1,2已知目标规划问题min zp1dlP2d2P3(5d3 3d4 ) P4d169420 (i i, ,4) min zpi diP2 d2P3diP4(5d3 3d4 )xi2x2didixi2x2d2d2xi2x2d3d 3x2d4

19、d4x1，x2,di ,di(i)分别用图解法和单纯形法求解；(2)分析目标函数分别变为、两种情况时(中分析 w、w2的比例变动)解的 变化。min z pidiP2 d2P3(5d3 3d4 ) F4dix, 2x2 di di xi 2x2 d2 d2 xi 2x2 d3 d3 x2 d4 d4 xi,x2,di ,di69420 (i i,L ,4)d4,di (4)4j(3)(i3/2,5/4)d2 min z pi diP2d2P3(w1d3w2d4) P4di【解】(i)图解法(双击下图，打开幻灯片)习题4.5(i)d2i 23456d3'd3满意解：X= (i3/2,5/4)(i)单纯形法G00PR0P5 P303 P0bCB基xix2di+dCb+d2d3+d3d+d4Rdii2i-i60di2i-i95 P3di-2i-i43 P3dii-i2表CZR-i-2