运筹学-第三章

西安邮电学院试题库管理系统——试题表第1页共8页专业代码11专业名称信息管理与信息系统课程代码18课程名称运筹学试题类型代码08试题类型名称计算题出题人管理员出题日期2005-11-4知识点代码题干答案评分标准难度系数认知分类建议分数建议时间11180301某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表。仪器装置代号体积重量实验中的价值A1v1w1c1A2v2w2c2A3v3w3c3A4v4w4c4A5v5W5c5A6v6w6c6要求：（1）装入卫星的仪器装置总体积不超过V，总重量不超过W（2）A1与A3中最多安装一件；（3）A2与A4中至少安装一件；（4）A5与A6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。maxz=61jjjxcst.否则仪器安装,0A,111j6542316161jjjjjjjxxxxxxxWxwVxv中运用88现有一批每根长度为L的圆钢，需要截取n种不同长度的零件毛坯，长度为aj的毛坯需要有mj（1,2,….n）段。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少？设使用jx根L米长的圆钢来截取ja米长的毛坯（1,2,……n）。设sjjaL为每根L米长的圆钢用来截取ja米长毛坯时可以得到的最多段数。数学模型为），且为整数（njxmxsxzjjjjnjj.....210min1某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号要满足以下限制条件：（1）或选择s1和s7，或选择钻探s8；（2）选择了s3或s4就不能选择s5，或反过来也一样；（3）在s5，s6，s7，s8中最多只能选择两个；试建立这个问题的数学模型。minz=101jjjxcst.否则井位选择钻探第,0,1211115j876545873581101sxxxxxxxxxxxxxxjjj运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他n个城市去推销商品，规定每个城市均须到达而且只能到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试建立这个问题的数学模型。设xij=，否则直接去，旅行商贩从01ji由此可写出整数规划模型为minz=ninjijijxd11st.jinjiniunnxuunixnjxiijjinjijniij，，，也可取整数值为连续变量,,1),,1(1),,1(1),,1(111一种产品可分别在A，B，C，D4种设备的任一种上加工。已知每种设备启用时的准备结束费用，生产上述产品时的单件成本以及每种设备的最大加工能力如表所示。如需生产该产品2000件，如何使总的费用最少，试建立数学模型。设备准备结束费/元生产成本/（元·件1）最大加工能力/件A100020900B920241000C800161200D700281600设xj为在第j设备上加工的产品数（j=1，…，4）；yj=不启用，设备加工产品，启用设备jj01（j=1，…，4）由此可写出模型为minz=1000y1+20x1+920y2+24x2+800y3+16x3+700y4+28x4st.,4)1,(j10y01600x1200x1000y9002000j443322114321或jxyyxyxxxxx西安邮电学院试题库管理系统——试题表第2页共8页有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tij表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立这个问题的数学模型。用xij表示第i个产品在第j机床上开始加工的时刻，这个问题的数学模型为：minz=max{x13+t13,x23+t23,x33+t33}st.010;3,2,1;2,1)1()2,1;3,2,1(,1,1,11,ijiiijjijiijiijijjiijijxjiMxtxMMxtxjittx或在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。设地建厂表示在地不建厂表示在i1i0xi整数规划模型为1,0xrxLxLIxI.t.sxPzmaxiN1iiN1iiiN1iiiN1iii红豆服装厂利用三种专用设备分别生产衬衣,短袖衫和休闲服,已知上述三种产品的每件用工量,用料量,销售价及可变费用如表所示.产品名称单位用工单件用料销售价可变费用衬衣3412060短袖衫238040休闲服6618080已知该厂每周可用工量为150单位,可用料量为160单位,生产衬衣,短袖衫和休闲服三种专用设备的每周固定费用分别为2000,1500和1000.要求为该厂设计一个周的生产计划,使其获利为最大.设该厂生产衬衣x1件,短袖衫x2件,休闲服x3件设xj为在第j设备上加工的产品数（j=1，…，4）；yj=，否则种专用设备，启动相应的01j由此可写出模型为maxz=120x1-(2000y1+60x1)+80x2-(1500y2+40x2)+150x3-(1000y3+80x3)st.,3)21,(j10y025xy3540160634150623j332211321321或jxyxyxxxxxxx某大学运筹学专业硕士研究生要求课程计划中必须选修两门数学类,两门运筹学类和两门计算机类课程,课程中有些只归属某一类,如微积分归属数学类,计算机程序归属计算机类;但有些课程是跨类的,如运筹学可归为运筹学类和数学类,数据结构归属计算机类和数学类,管理统计归属数学和运筹学类,计算机模拟归属计算机类和运筹学类,预测归属运筹学类和数学类,凡归属两类的课程学后可认为两类中各学了一门课.此外,有些课程要求先学习先修课,如学计算机模拟或数据结构必须先修计算机程序,学管理统计必须先修微积分,学预测必须先修管理统计.问一个硕士研究生最少应学几门及哪几门,才能满足上述要求.对微积分,运筹学,数据结构,管理统计,计算机模拟,计算机程序,预测7门课程分别编号为1,2,3,4,5,6,7.设xj=，否则课程，选学第01j由此可写出模型为minz=x1+x2+…+x7st.10x222j74365641653754274321或xxxxxxxxxxxxxxxxxxxx红星塑料厂生产6种规格的塑料容器,每种容器的容量(cm3),需求量及可变费用(元/件)如表所示.容器代号123456容量(cm3)1500250040006000900012000需求量500550700900400300可变费用(元/件)5810121618每种容器分别用不同专用设备生产,其固定费用均为1200元.当某容器数量上不能满足需要时,可用容量大的代替.问在满足需求的情况下,如何组织生产,使总的费用为最小.设xj为j种容器生产的数量设yj=，否则种容器，生产01j由此可写出模型为minz=1200jjy+5x1+8x2+10x3+12x4+16x5+18x6st.6110y0x61yx2850230016007003003350jjjj654326543654656654321），，（或），，（jjMxxxxxxxxxxxxxxxxxxxxx西安邮电学院试题库管理系统——试题表第3页共8页要在长度为L的一根圆钢上截取不同长度的零件毛坯，毛坯长度分别有n种，分别为aj（j=1,2,…..,n）。每种毛坯应当各截取多少根，才能使圆钢残料最少？如果求毛坯的总根数最多，应当怎样截取毛坯？设截取长为aj的毛坯xj根（j=1，2……,n）。使圆钢残料最少的下料问题数学模型为n1,2,......j0x),...2,1(Lminj111且为整数njLxaxaznjjjnjjj由于z2=L-z1=njjjxa1是实际用料总长，故问题的目标函数等价于2maxznjjjxa1如果求毛坯总根数最多则可将目标函数改为3maxznjjx1某地准备投资D元建民用住宅。可以建住宅的地段有n处：A1，A2A3，….An，在Aj处每幢住宅的造价为dj，最多可造aj幢。应当在哪处建住宅，分别建几幢，才能使住宅总数最多？设在Aj处建住宅xj幢（j=1，2…..n）。数学模型为）是整数（njxaxDxdxzjjjnjjjnjj.....2,10max1111180302某公司今后三年内有五项工程可以考虑投资设项目，不投资项目投资jjxj0,112345123451234512345max30402015305457830795625826293001,1,,5jZxxxxxxxxxxxxxxxxxxxxxj＝或求最优解和投资的最大收益最优解X＝(1,1,1,0,1)，Z=110万元。用分枝定界法求解下列整数规划问题maxz=3x1+2x2st.且为整数0x,5.4x5.014x32212121xxx最优解z=14,x1=4,x2=1;用分枝定界法求解下列整数规划问题maxz=2x1+3x2st.且为整数0x,36x9435x75212121xxx最优解z=14,x1=4,x2=2;用分枝定界法求解下列整数规划问题maxz=x1+x2st.且为整数0x,30x5616x52212121xxx最优解z=5,x1=5,x2=0;或x1=4,x2=1用分枝定界法求下列整数规划。且为整数0,2126052max2121212121xxxxxxxxxxz最优解和最优值如下：7,)1,3(**zxT用分枝定界法解下列整数规划：且为整数0,1923188847232max2121212121xxxxxxxxxxz最优解和最优值如下：21,)5,3(**zxT用割平面法求解下列整数规划问题maxz=7x1+9x2st.且为整数0x,35x76x3212121xxx最优解z=55,x1=4,x2=3;西安邮电学院试题库管理系统——试题表第4页共8页用割平面法求解下列整数规划问题maxz=4x1+5x2st.且为整数0x,2x35x47x2321212121xxxx最优解z=13,x1=2,x2=1;用割平面法求解下列整数规划问题maxz=4x1+6x2+2x3st.且为整数0x,x,5xx5x65x443213212121xxxx最优解z=26,x1=2,x2=1,x3=6;用割平面法求解下列整数规划问题maxz=11x1+4x2st.且为整数0x,4x216x254x221212121xxxx最优解z=34,x1=2,x2=3;分别用割平面法求解以下整数规划问题且为整数0,521