运筹学-第三章

1、专业代码11专业名称信息管理与信息系统课程代码18课程名称运筹学试题类型代码08试题类型名称计算题出题人管理员出题日期2005-11-4知识点代码题 干答 案评分标准难度系数认知分类建议分数建议时间某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表。仪器装置代号体积重量实验中的价值AvwcAvwcAvwcAvwcAvWcAvwc要求：（1） 装入卫星的仪器装置总体积不超过V，总重量不超过W（2） A与A中最多安装一件；（3） A与A中至少安装一件；（4） A与A或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。max z=

2、st.中运用88现有一批每根长度为L的圆钢，需要截取n种不同长度的零件毛坯，长度为a的毛坯需要 有m（1,2,.n）段。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少？设使用根L米长的圆钢来截取米长的毛坯（1,2,n）。设s为每根L 米长的圆钢用来截取米长毛坯时可以得到的最多段数。数学模型为某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号要满足以下限制条件：（1）或选择s和s，或选择钻探s；（2）选择了s或s就不能选择s，或反过来也一样；（3）在s，s，s，s中最多只能选择两个；试建立这个问题的数学模型。min z=

3、 st.运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他n个城市去推销商品，规定每个城市均须到达而且只能到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为d，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试建立这个问题的数学模型。 设x=由此可写出整数规划模型为min z=st.一种产品可分别在A，B，C，D4种设备的任一种上加工。已知每种设备启用时的准备结束费用，生产上述产品时的单件成本以及每种设备的最大加工能力如表所示。如需生产该产品2000件，如何使总的费用最少，试建立数学模型。设备准备结束费/元生产成本/（元件）最大加工能力/件A

4、1 00020900B920241 000C800161 200D700281 600设x为在第j设备上加工的产品数（j=1，4）；y=（j=1，4）由此可写出模型为 min z=1 000y+20x+920 y+24x+800 y+16x+700 y+28 xst.有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用t表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立这个问题的数学模型。 用x表示第i个产品在第j机床上开始加工的时刻，这个问题的数学模型为：min z

5、=maxx+t, x+t, x+tst.在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。设整数规划模型为红豆服装厂利用三种专用设备分别生产衬衣,短袖衫和休闲服,已知上述三种产品的每件用工量,用料量,销售价及可变费用如表所示.产品名称单位用工单件用料销售价可变费用衬衣3412060短袖衫238040休闲服6618080已知该厂每周可用工量为150单位,可用料量为160单位,生产衬衣,短袖衫和休闲服三种专用设备的每周固定费用分别为2000,1500和

6、1000.要求为该厂设计一个周的生产计划,使其获利为最大.设该厂生产衬衣x件,短袖衫x件,休闲服x件设x为在第j设备上加工的产品数（j=1，4）；y=由此可写出模型为 max z=120x-(2 000y+60x)+80x-(1500 y+40 x)+150x-(1000 y+80 x)st.某大学运筹学专业硕士研究生要求课程计划中必须选修两门数学类,两门运筹学类和两门计算机类课程,课程中有些只归属某一类,如微积分归属数学类,计算机程序归属计算机类;但有些课程是跨类的,如运筹学可归为运筹学类和数学类,数据结构归属计算机类和数学类,管理统计归属数学和运筹学类,计算机模拟归属计算机类和运筹学类,预

7、测归属运筹学类和数学类,凡归属两类的课程学后可认为两类中各学了一门课.此外,有些课程要求先学习先修课,如学计算机模拟或数据结构必须先修计算机程序,学管理统计必须先修微积分,学预测必须先修管理统计.问一个硕士研究生最少应学几门及哪几门,才能满足上述要求.对微积分,运筹学,数据结构,管理统计,计算机模拟,计算机程序,预测7门课程分别编号为1,2,3,4,5,6,7.设x=由此可写出模型为 min z=x+x+xst.红星塑料厂生产6种规格的塑料容器,每种容器的容量(cm),需求量及可变费用(元/件)如表所示.容器代号123456容量(cm)1500250040006000900012000需求量5

8、00550700900400300可变费用(元/件)5810121618每种容器分别用不同专用设备生产,其固定费用均为1200元.当某容器数量上不能满足需要时,可用容量大的代替.问在满足需求的情况下,如何组织生产,使总的费用为最小.设x为j种容器生产的数量设y=由此可写出模型为 min z=1200+5x+8x+10x+12 x+16 x+18xst.要在长度为L的一根圆钢上截取不同长度的零件毛坯，毛坯长度分别有n种，分别为a（j=1,2,.,n）。每种毛坯应当各截取多少根，才能使圆钢残料最少？如果求毛坯的总根数最多，应当怎样截取毛坯？设截取长为a的毛坯x根（j=1，2,n）。使圆钢残料最少的

9、下料问题数学模型为由于z=L-z= 是实际用料总长，故问题的目标函数等价于 如果求毛坯总根数最多则可将目标函数改为 某地准备投资D元建民用住宅。可以建住宅的地段有n处：A，A A，. A，在A处每幢住宅的造价为d，最多可造a幢。应当在哪处建住宅，分别建几幢，才能使住宅总数最多？设在A处建住宅x幢（j=1，2.n）。数学模型为某公司今后三年内有五项工程可以考虑投资设求最优解和投资的最大收益最优解X(1,1,1,0,1)，Z=110万元。用分枝定界法求解下列整数规划问题max z=3x+2 x st. 最优解z=14, x=4, x=1;用分枝定界法求解下列整数规划问题max z=2x+3 x s

10、t. 最优解z=14, x=4, x=2;用分枝定界法求解下列整数规划问题max z=x+ x st. 最优解z=5, x=5, x=0;或x=4, x=1用分枝定界法求下列整数规划。最优解和最优值如下：用分枝定界法解下列整数规划：最优解和最优值如下：用割平面法求解下列整数规划问题max z=7x+9 x st. 最优解z=55, x=4, x=3;用割平面法求解下列整数规划问题max z=4x+5 x st. 最优解z=13, x=2, x=1;用割平面法求解下列整数规划问题max z=4x+6 x+2 x st. 最优解z=26, x=2, x=1, x=6;用割平面法求解下列整数规划问题

11、max z=11x+4x st. 最优解z=34, x=2, x=3;分别用割平面法求解以下整数规划问题先求解相应的线性规划的最优解：zx1x2x3x4RHSz1-1-4000x30144210196x40-12015zx1x2x3x4RHSz1-300210x303501-2191x20-1/2101/25/2zx1x2x3x4RHSz1003/351/589/5x10101/35-3/513/5x20011/701/519/5线性规划的最优解为x1=13/5，x2=19/5，max z=89/5。对于x2=19/5，b2=19/5，I2=3，F2=4/5y23=1/70，I23=0，F23

12、=1/70；y24=1/5，I24=0，F24=1/5构造附加的切割约束：4/5-（1/70x3+1/5x4）0即1/70x3+1/5x44/5zx1x2x3x4x5RHSz1003/351/5089/5x10101/35-3/5013/5x20011/701/5019/5x5000-1/70-1/51-4/5zx1x2x3x4x5RHSz1001/140117x10103/350-35x20010013x40001/141-54得到整数解：x1=5，x2=3，x3=0，x4=4，x5=0，max z=17。用割平面法解下列整数规划：最优解和最优值如下：用割平面法求解以下整数规划先求相应的线性

13、规划问题，得到最优单纯形表zx1x2x3x4RHSz100-2/5-9/544/5x1010-2/51/54/5x20011/5-3/58/5选择一个非整数的基变量，例如x2=8/5，构造约束条件（3.4），其中b2=8/5=1+3/5，I2=1，F2=3/5y23=1/5=0+1/5，I23=0，F23=1/5y24=-3/5=-1+2/5，I24=-1，F24=2/5附加的约束条件为3/5-（1/3x3+2/5x4）0即1/5x3+2/5x43/5将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到zx1x2x3x4x5RHSz100-2/5-9/5044/5x1010-2

14、/51/504/5x20011/5-3/508/5x5000-1/5-2/51-3/5用对偶单纯形法，x5离基，x3进基已获得整数的最优解。zx1x2x3x4x5RHSz1000-1-210x101001-22x20010-111x300012-53用割平面法解下列整数规划：最优解和最优值如下：用割平面法解下列整数规划：最优解和最优值如下：用割平面法解下列整数规划：最优解和最优值如下：用分枝定界法求下列整数规划。最优解和最优值如下：用分枝定界法求下列整数规划。最优解和最优值如下：设xj为投资第j个点的状态，xj=1或0，j=1,2,12求最优解和总收益及实际完成的投资额。最优解：x1x5=x1

15、2=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元用隐枚举法求解01规划问题max z=3x+2 x-5 x-2 x+3 xst. 最优解x= x=1, x=x= x=0, z=5用隐枚举法求解01规划问题max z=2x- x+5 x-3 x+4xst. 最优解x= x=0, x=x= x=1, z=6用隐枚举法求解01规划问题max z=8x+2 x-4 x-7 x-5xst. 最优解x= x=1, x=x= x=0, z=4已知下列五名运动员各种姿势的游泳成绩(各为50m)如表所示,试问如何从中选拔一个参加200m混合泳的接力队,使预期比赛成绩为最好.单位:s游泳姿

16、势赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1由下列运动员组混合接力队:张仰泳,王蛙泳,钱蝶泳,赵自由泳,预期总成绩为126.2s.公司在各地有四项业务，选定了四位业务员去分别处理。由于业务能力、经验和其他情况不同，四位业务员处理这四项业务的费用各不相同，费用估算见表。应当怎样分派这四位业务员，才能使四项业务得到处理，同时总的业务费用又最少？（业务，业务员，费用） 业务业务员123411100800100070026005003008003400800

17、1000900411001000500700应当分派业务员1去处理业务4，业务员2去处理业务2，业务员3去处理业务1，业务员4去处理业务3有五项设计任务可供选择。各项设计任务的预题完成时间分别为3，8，4，10天，设计报酬分别为7，17，11，9，21千元。设计任务只能一项一项地进行，总的期限是20天。选择任务时必须 满足下面的要求：（1）至少完成三项设计任务 ;(2 )若选择任务1，必须同时选择任务2；（3）任务3和任务4不能同时选择。应当选择那些设计任务，才能使总的设计报酬最大 ？应当选择设计任务3，4，5便民超市准备在城市西北郊新建的居民小区中开设若干连锁店。为方便购物，规划任一居民小区

18、至其中一个连锁店的距离不超过800m。表给出了新建的居民小区及离该居民小区半径800m内的各个小区，问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内。小区代号该小区800m半径内的各小区AACEGHIBBHICACGHIDDJEAEGFFJKGACEGHABCHIIABCHIJDFJKLKFJKLLJKLx= x= x=1，其余x为0有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。设取第i种物品xi件（i=1，2，k），则规划问题可以写为maxz=v1x1+v2x2+vkx

19、ks.t.w1x1+w2x2+wkxkWx1,x2,xk0x1,x2,xk为整数这个问题如果用线性规划求解，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如以下一个背包问题maxz=17x1+72x2+35x3s.t.10x1+42x2+20x350x1,x2,x30x1,x2,x3为整数线性规划最优解为x1=0，x2=，x3=0而整数规划的最优解是x1=1，x2=0，x3=2。在最小成本问题中，设第j种设备运行的固定成本为dj，运行的变动成本为cj，则生产成本与设备运行时间的关系为设第j种设备运行每小时可

20、以生产第i种产品aij件，而第i种产品的定货为bi件。列出使要满足定货同时使设备运行的总成本最小的问题的线性规划模型并求最优解。这里M是一个很大的正数。当yj=0时，xj=0，即第j种设备不运行，相应的运行成本djyj+cjxj=0当yj0时，0xjM，实际上对xj没有限制，这时相应的运行成本为dj+cjxj 较难运用1010男球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见下表 队员身高（m）擅长位置 11.92中锋21.90中锋31.88前锋41.86前锋51.85前锋61.83后卫71.80后卫81.78后卫出现阵容应满足以下条件：（1）中锋只能有一个上场；（2）至少有一名后卫；（3）如1号和4号上场，则6号不出场 ；（4）2号和6号至少保留一个不出场。应当选择哪5名队员上场 ，才能使出场队员平均身高最高？设 (j=1,2.n)最优解为=1，=0 目标函数最优解为1.862用你认为合适的方法求解下述问题max z=x+2 x+5 x st. 将问题改写为max z=x+2 x+5 x st. 求的解x=0， x=0， x=10，y=1，z=50解下列0-1型整数规划：无可行解解下