运筹学 第三章

1、试题类型 V W装入卫星的仪器装置总体积不超过V,总重量不超过W(2)（3）（4）试题类 型名称知识点 代码A 2与A4中至少安装一件;A1 与 A3中最多安装一件;A 5与A 6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发 挥最大的实验价值。试建立这个问题的数学模型。仪器装置代号体积重量实验中的价值Avw 1c1111Avwc2222Avwc3333Avwc4444AvWc5555Avwc6666要求:（1）j=1 w xj=1x + x 124x = x5611，x =5j 1,安装A.仪器 否则J出题日期难 度 系 数中2005-11-4认 知 分 类建 议 分 数建

2、 议 时 间现有一批每根长度为L的圆钢，需要截取n种不同长度的零件毛坯，长度为a j的毛坯需要有m j（1,2, .n）段。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能 使动用的圆钢数目最少？设使用%根l米长的圆钢来截取七米长的毛坯（1，2,n）。L设s =为每根L米长的圆钢用来截取a米长毛坯时可以得到的最多段数。a.j -1数学模型为-寸min z =乙 xjj=1SjXj mjx 0且为整数(j = 1，2.n)某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10 个井位的代号要满足以下限制条件：（1）（2）（3）或选择s 1和s 7，或选择钻探

3、s8选择了 s_或s.就不能选择s 5，或反过来也一样;s 8中最多只能选择两个；试建立这个问题的数学模型。z= exj jj=10 x = 5jj=1x+ x =18x+ x =78x+ x +561,x=5j|0,st. 5minx + x 153X + X 1+ x 28X7选择钻探第S井位j否则运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到 其他n个城市去推销商品，规定每个城市均须到达而且只能到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为d，问该商贩应选择一条什么样的路线顺序旅行， 使总的旅程为最短。试建立这个问题的数学模型。1，旅行商贩从

4、，直接去j0,否则由此可写出整数规划模型为min z= dxij iji=1 j =1x = 1( j = 1,., n)i=1x = 1( i = 1,., n)j=1u - u + nx n -1为连续变量(i = 1,n)，也可取整数值ii，j = 1,，n，i j一种产品可分别在A，B，C，D4种设备的任一种上加工。已知每种设备启用时的准备结束 费用，生产上述产品时的单件成本以及每种设备的最大加工能力如表所示。如需生产该产设备准备结束费/元生产成本/（元件-1 ）最大加工能力/件A1 00020900B920241 000C800161 200D700281 600设x j为在第j设备

5、上加工的产品数（j=1，4）；1，启用设备j加工产品.0,设备j不启用（j=1，4）由此可写出模型为min z=1 000y 1 +20 x920 y 2 +24x 2 +800 y 3 +16x 3 +700 y 4 +28 x 4st. 5x + x + x + x = 20001234x 900y x 1000yx 1200yx 0 y. = 0或1 (j = 1,4)有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用七表示在第j机 床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为

6、最短。试建立这 个问题的数学模型。用x表示第i个产品在第j机床上开始加工的时刻，这个问题的数学模型为:min z=maxx 粉 +t 粉，x 23 +t 23, x 33 +t 33x +1 t (i = 1,2,3; j = 1,2)ijiji,j+ix +1 - x M Mbijiji+1, jix +1 一x 0在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为 Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应 如何选择厂址，使建成后总生产能力最大。火 _0表示在i地不建厂 设Xi=i1表示在i地建厂整数规划模型为max z

7、= P xs.t.玖i iAx rix1 = 0,1设该厂生产衬衣x 1件，短袖衫x 2件，休闲服x 3件产品名称单位用工单件用料销售价可变费用衬衣3412060短袖衫238040休闲服6618080红豆服装厂利用三种专用设备分别生产衬衣，短袖衫和休闲服，已知上述三种产品的每件用 工量,用料量，销售价及可变费用如表所示.已知该厂每周可用工量为150单位，可用料量为160单位，生产衬衣，短袖衫和休闲服三种专 用设备的每周固定费用分别为2000,1500和1000.要求为该厂设计一个周的生产计划，使其 获利为最大.某大学运筹学专业硕士研究生要求课程计划中必须选修两门数学类，两门运筹学类和两门 计算

8、机类课程,课程中有些只归属某一类，如微积分归属数学类，计算机程序归属计算机类； 但有些课程是跨类的，如运筹学可归为运筹学类和数学类，数据结构归属计算机类和数学 类，管理统计归属数学和运筹学类，计算机模拟归属计算机类和运筹学类，预测归属运筹学 类和数学类，凡归属两类的课程学后可认为两类中各学了一门课.此外，有些课程要求先学 习先修课，如学计算机模拟或数据结构必须先修计算机程序，学管理统计必须先修微积分， 学预测必须先修管理统计.问一个硕士研究生最少应学几门及哪几门,才能满足上述要求.红星塑料厂生产6种规格的塑料容器，每种容器的容量（cm3），需求量及可变费用（元/件）如容器代号123456容量(

9、cm3)1500250040006000900012000需求量500550700900400300可变费用（元/810121618件）5表所示.每种容器分别用不同专用设备生产，其固定费用均为1200元.当某容器数量上不能满足需要 时,可用容量大的代替.问在满足需求的情况下，如何组织生产,使总的费用为最小.设x j为在第j设备上加工的产品数（j=1，4）；1，启动相应的j种专用设备 y J0,否则由此可写出模型为max z=120 x -(2 000y 1 +60 x+80 x2 -(1500 y2+40 x2)+150 x3-(1000 y3+80 x3) 150 x + 2 x + 6 x

10、x + 3x + 6 x123x 40 yx 53y2 2x3 0 y . = 0或1 (j = 1,2,3) 2356x x14x x65x x63x x47x=0或1jst.设Xj为j种容器生产的数量1，生产种容器 设y，=否则由此可写出模型为min z=1200 y +5x 1 +8x 2 +10 x 3 +12 x 4 +16 x 5 +18x 6 jx + x + x + x + x + x = 335023456x 300 x + x 70056x + x + x 1600 x + x + x + x 2300 x + x + x + x + x 28503456x 0y = 0或

11、 1(j = 1，. . .，6)j要在长度为L的一根圆钢上截取不同长度的零件毛坯，毛坯长度分别有n种，分别为aj(j=1,2,.，n)。每种毛坯应当各截取多少根，才能使圆钢残料最少？如果求毛坯的 总根数最多，应当怎样截取毛坯？I4EI女I殳截取长为a j的毛坯x 了根(j=1，2,n)。吏圆钢残料最少的下料问题数学模型为ninz = L -Ea xj=1Eax 0 且为整数 j = 1,2,.ni j白于z2 =L-z 1 =是实际用料总长，故问题的目标函数等价于j=1nax z = E a xj=1口果求毛坯总根数最多则可将目标函数改为nax z = E xj=1某地准备投资D元建民用住宅

12、。可以建住宅的地段有n处：A1，A2 A3，.A，在A ,处 每幢住宅的造价为dj，最多可造a童。应当在哪处建住宅，分别建几幢，才能使住宅总 数最多？ti殳在A .处建住宅x .幢(j=1，2.n)。攵学模型为nax z = E xjj=1Ed x Dj=10 x ajjx 是整数(j = 1,2.n)1118030214耗公司今后三年内有五项工程可以考虑投资几1,投资/项目殳尤=j 0,不投资项目nax Z = 30 x + 40 x + 20 x +15x + 30 x123455x + 4x + 5x + 7x + 8x 3012345x + 7 x + 9x + 5 x + 6x 25

13、123458x + 2x + 6x + 2x + 9x 30 x =0或1, j = 1, ,5R最优解和投资的最大收益最优解 X= (1,1,1,0,1)，Z=110 万元。用分木max zst. 4支定界法求解下列整数规划问题=3x 1+2 x2Ze 14x + 0.5x 0且为整数12最优解 z=14, x 1=4, x 2 =1;用分木max z4 st.支定界法求解下列整数规划问题=2x 1+3 x 25x1 + 7x2 354x + 9x 0且为整数最优解 z=14, x 1=4, x 2 =2;用分木max zst. 4支定界法求解下列整数规划问题=x 1+ x2气 + 5x2

14、166x + 5x 0且为整数12最优解 z=5, x 1=5, x 2 =0;或 x 1=4, x 2 =11I4目分枝定界法求下列整数规划。nax z = 2 x + xx + x 5-x +x 0126 x + 2 x 0且为整数最优解和最优值如下：x* = (3,1)广,z * = 7i4目分枝定界法解下列整数规划：nax z = 2 x + 3 x 12-x + x 247x + 8x 188123 x + 2 x 0且为整数最优解和最优值如下：x* = (3,5)广,z * = 21用割max zst. 4F面法求解下列整数规划问题=7x 1+9 x-x1+ 3x2 67x + x

15、 20且为整数12最优解 z=55, x 1=4, x 2 =3;用割平面法求解下列整数规划问题max z=4x ；5 x3x + 2x 7x 1+ 4x 5123x + x 212、xx2 0且为整数用割平面法求解下列整数规划问题max z=4x i+6 x +2 x 34x 4x 5-x + 6x2 512x + x + x 0且为整数用割平面法求解下列整数规划问题max z=11x+4xx + 2x 45x 1+ 2x 2 16122 x x 0且为整数分别用割平面法求解以下整数规划问题max z = x + 4 x1214x1 + 42x2 196s.t. x + 2x 0且为整数2先

16、求解相应的线性规划的最优解:1-1-400001442101960-12015zx1x2x3x4RHS1-30021003501-21910-1/2101/25/2zx1x2x3x4RHS1003/351/589/50101/35-3/513/50011/701/519/5RHSzzzzx3x2x3x4x1x2x 2.x 2.x Ix 1线性规划的最优解为x1=13/5, x2=19/5, max z=89/5。对于 x2=19/5,b2=19/5,y23=1/70I2=3, F2=4/5I23=0, %=1/70； y =1/5 构造附加的切割约束：4/5- (1/70 x3+1/5x4)1

17、/70 x3+1/5x44/5z x12324I24=0F24=1/5x1x2x4得到整数解:W01003/351/5089/50101/35-3/5013/50011/701/5019/5000-1/70-1/51-4/5RHSzx5x1x2x 2x 3x 4x 5.1001/1401170103/350-3500100130001/141-54RHSzx 2x 3x 4x 5.x 1乂=5, x2=3, x3=0, x4=4, x5=0, max z=17。用割平面法解下列整数规划:max z = x + x2Xi + X 64x + 5x 0且为整数2最优解和最优值如下:用割平面法求解以

18、下整数规划min z = 3x + 4 x123x + x 4s.t. 4x , x 0且为整数1 12先求相应的线性规划问题，得到最优单纯形表zxxxx,RHSzx1x100-2/5-9/544/50010-2/51/5011/5-3/54/58/5选择一个非整数的基变量，例如x2=8/5，构造约束条件(3.4)，其中b8/5=1+3/5，12=1，F2=3/5y23=1/5=0+1/5，I23=0， F23=1/5y24=-3/5=-1+2/5，I24=-1，F24=2/5附加的约束条件F -乎七己0为j=m+13/5- (1/3x3+2/5x4)W0即1/5x3+2/5x4N3/5将这个

19、约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5,得到 zxxxxxRHSzx1x2x100-2/5-9/5044/500010-2/51/50011/5-3/5000-1/5-2/514/58/5-3/5用对偶单纯形法，x5离基，x3进基 已获得整数的最优解。zxxxnxxRHSz1000-1-210 x01001-22x20010-111x 300012-53F i1 :目割平面法解下列整数规划：nax z = 4 x + 3xl4气+ 4x2 17 22 x 0且为整数I 12最优解和最优值如下：x* = (3,1)t , z * = 15i1:目割平面法解下列整数规划： nax

20、 z = 2 x + xx1 + x 2 6x - 4 x 20且为整数* 12最优解和最优值如下：x* = (5,1)t , z * = 11i1目割平面法解下列整数规划：nax z = 4 x + 5 x123气 + 2x2 10 x + 4 x 0且为整数l 12最优解和最优值如下：x* = (2,2)t , z * = 18i:目分枝定界法求下列整数规划。nax z = -5 x + x - 2 xC：72 x + x x + x1 2 3 4 22 x x + x + x = 21235x , x , x , x , x 012345x3和x5为整数最优解和最优值如下：x* = (0

21、,2,0,1.5,0)t , z * = 2i目分枝定界法求下列整数规划。nax z = 5 x + x 2 x3x +10 x 507x 2x 0、气为整数最优解和最优值如下：x* = (4.857,3)t , z * = 18.7142911180303设X.为投资第j个点的状态，x=1或0, j=1,2,，12Jmax Z = 400气 + 500 x2 + 450 x3 + + 400。|900 x +1200 x +1000 x + + 850 x +1000 x 2, x 1,x 3,月 x 4jjjjjjj=1j=1j=5j=5j=8j=8x = 1 或 0, j = 1, ,1

22、2i j求最优解和总收益及实际完成的投资额。最优解：x1=x5=x12=0，其余xj=1，总收益Z=3870万元，实际完成投资额8920万元用隐龙max zst. j攵举法求解01规划问题=3x 1 +2 x 2 -5 x 3 -2 x 4 +3 x 5x + x + x + 2 x + x 47x + 3x 4x + 3x 3、xj = 0或1( j = 1：.,5最优解 x 1 = x 2 =1, x 3 =x 4 = x 5 =0, z=5用隐龙max zt st. j攵举法求解01规划问题=2x 1 - x 2 +5 x 3 -3 x 4 +4x 53x 2x + 7x 5x + 4x

23、 6x x + 2x 4x + 2x 0 x = 0 或 1( j = 1,.：5)5I j最优解 x 1 = x 2 =0, x 3 =x 4 = x 5 =1, z=6用隐龙max zst. 攵举法求解01规划问题=8x 1 +2 x 2 -4 x 3 -7 x 4 -5x 53x + 3x + x + 2x + 3x 45x + 3x - 2x - x + x 0设第j种设备运行每小时可以生产第i种产品aij件，而第i种产品的定货为件。列出使 要满足定货同时使设备运行的总成本最小的问题的线性规划模型并求最优解。min z = d y + c x j j j j j=ist.Eax bi

24、= 1,2,，mj=1x. 0, y, = 0,1这里M是一个很大的正数。当y.=0时，x,=0，即第j种设备不运行，相应的运行成本dy+c,x =0当yj0时，0WxjWM，实际上对x.没有限制，这时相应的运行成本为 d +c x较难运 用1010男球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见下表、0队员不出场 .设xj =1队员出场(j=1,2max z = 1(1.92x +1.90 x +1.88x +1.86x +1.85x +1.86x +1.80 x +1.78x ) 812345678队员身高（m）擅长位置11.92中锋21.90中锋31.88前锋41.

25、86前锋 1678x + x + x 214 一6x2 + x6 15st. 2气 + x2 + x3 0123将问题改写为max z=x 1+2 x +5 x 3x + 10 x 3x 15 + (1 y)Mx 10 x + 3x 15 + Myst. E； + x 2+ x 0, y = 0或 1求的解 x 1=0， x =0， x3=10，y=1， z=50解下列0-1型整数规划：min x = 5 x + 7 x +10 x + 3 x + xx 一 3x + 5x + x 一 4x 2一 2 x + 6 x 一 3 x 一 2 x + 2 x 0 12345x. = 0 或 1( j

26、 = 1,2,3,4,5)无可行解解下列0-1型整数规划max z = 2 x + x xx + 3 x + x 24x2 + 3 5 x + 2 x x 2x + 4 x x 4123、x , x , x = 0或1最优解和最优值如下：x* = （1,0,0）t , z * = 211180304用匈牙利法求解下791012-13 12 16 1715 16 141511121516述指派问题,已知效率矩阵如下：最优指派方案为x 13 = x 22 = x 34 = x 41 =1,最优值为48;用匈牙利法求解下述 382103-8729764275842359106910过指派问题,已知效率矩阵如下：最优指派方案为x 15 = x 23= x 32 = x 44= x 51 = 1,最优值为21;分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务 多与人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花 费时间为最少的指派方案。最优分配方案为甲-B乙-D、C丙-E丁-A任务 人ABCDE甲乙丙丁2539342429382742312628364220402337333245需要分派五人去