应用运筹学11-12-1期末考试试卷.doc

年级：_ 专业：_ 班级：_ 学号：_ 姓名：_.装.订.线诚信应考 考出水平 考出风格浙江大学城市学院2011 2012学年第一学期期末考试试卷应用运筹学开课单位： 计算分院 ；考试形式：闭卷；考试时间： _2012_年_1_月_13_日；所需时间： 120 分钟题序一二三四五六七八九总 分得分评卷人（注：答案全部写在答卷上）得分一判断题 (本大题共10小题，每题1分，共10分。)在你认为正确的叙述后面打“”，错误的后面打“”。1 线性规划中“线性”的含义是指约束条件关于决策变量是线性等式或不等式，而对目标函数没有要求。 ( )2 线性规划求解的结果可能会有无穷多个最优解，但解相应的最优值都相等。 ( )3 若线性规划有最优解则其可行域一定有界。 ( )4 若线性规划无解，则其可行域是空集。 ( )5 影子价格为0时，表明该资源未得到充分利用。 ( )6 平衡运输问题的约束是资源约束。 ( )7 指派问题是运输问题的特例。 ( )8 匈牙利法是对运输问题求最小值的一种求解方法。 ( )9 点vi表示自来水厂及用户，vi与vj之间的边表示两点间可以铺设管道，权为vi与vj间铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5个用户并且使总的费用最小。这属于最短路问题。 ( )10邮递员从邮局vi出发要经过每一条边将邮件送到用户手中，最后回到邮局vi，如何安排路线使总路程最短。这属于运输问题。 ( )得分二填空题 (本题每行1分，共10分。)根据灵敏度报告进行分析，对下列情形能否得到相应的最优值和最优解？或是只能重新求解？在相应方格打“”。灵敏度报告最优值最优解重新求解单个目标函数系数变动且在变动范围内多个目标函数系数变动且在变动范围内单个约束右端值变动且在变动范围内多个约束右端值变动且在变动范围内约束条件系数变化增加一个新变量增加多个新变量增加一个约束条件增加多个约束条件同时增加变量和约束条件得分三分析解答题 (共10分。)某公司目前正在制造两种产品，产品I和产品II，现在产品I和产品II的每天产量分别为30个和120个，工资负责制造的副总经理希望了解是否可以通过改变这两种产品的数量来提高公司的利润。公司制造每个产品所需的加工工时和每个车间的加工能力（每天加工工时数）如下表产品I和产品II一所示：生产两种产品的有关数据车间产品I产品II车间能力12030020354032244041.21.5300每件产品利润（元）500400利用EXCEL进行线性规划建模求解后的表格（表格一）和敏感性性分析报告（表格二）如下：问：（1） 假设生产的全部产品都能销售出去，请确定最优产品组合，即确定使得总利润最大的产品I和产品II每天的产量。（2） 在问题（1）所求得的最优产品组合中，在1、2、3、4四个车间中哪些车间的能力还有剩余，剩余多少？（3） 1、2、3、4四个车间能力的影子价格各为多少？即1、2、3、4四个车间的能力分别增加一个加工工时数时能给公司带来多少的额外利润？ （4） 当产品I的单位利润不变，产品II的单位利润在什么范围内变化时，此最优解不变？ 分别讨论各个单位产品利润在什么范围内变化时，原生产计划不变。当产品II的单位利润不变，产品I的单位利润在什么范围内变化时，此最优解不变？（5） 当产品I的单位利润从500元降为450元，而产品II的单位利润从400元降为430元时，最优解是否改变？表格一、EXCEl建模表格表格二、第三题的敏感性分析报告得分四计算解答题 (共20分。)某公司铺设光导纤维网络问题（最小支撑树问题）。某公司的管理层已经决定铺设最先进的光导纤维网络，为它的主要中心之间提供高速通信（数据、声音和图像）。图一中的节点显示了该公司主要中心（包括公司的总部、巨型计算机、研究区、生产和配送中心等八个位置）的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。（分别用破圈法和避圈法、Prim算法和Sollion算法求解，给出算法步骤，不用建立模型。）图一、第三题的节点分布图22526752334CEHABFDGF6得分五计算解答题 (共10分。)指派问题。根据下面的费用矩阵，采用匈牙利算法给出最优的指派方案。（给出算法步骤，不用建立模型。） 得分六线性规划建模题(共10分。)解题要求：给出三要素，建立相应的规划模型。（生产与存储问题问题）。某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表三所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用1500元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。表格三、各季度的生产能力及生产每台柴油机的成本季度生产能力（台）单位成本（万元）12510.823511.133011.041011.3（1） 以各季度的产量及库存为决策变量，建立线性规划模型；（2） 以第i季度生产的第j季度交货的柴油机数为决策变量，建立产大于销的运输问题模型。 得分七优化建模题 (共10分。)解题要求：给出三要素，建立相应的规划模型。图二、第五题的城市网络图333333313232467910512244118224311441) 在进行货郎担问题试求解时，有回路“23652”，“4784”，“912”，给出货郎担问题的数学模型；2) 给出上图求解中国邮路问题的数学模型； 得分八最大流建模题(共10分。) 解题要求：给出三要素，建立相应的规划模型。计划编制问题。某市政工程公司在未来58月份内需完成4项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见表3。该公司共有劳动力120人，任一工程在一个月内的劳动力投入不能超过80人，问公司应如何分配劳动力完成所有工程，是否能按期完成？(1) 画出将该问题转化为最大流问题的网络图；(2) 给出求解最大流问题的数学模型；工程工期需要劳动力（人）A.地下通道57月100B.人行天桥67月80C.新建道路58月200D.道路维修 8月80 得分九整数规划建模题(共10分。)解题要求：给出三要素，建立相应的规划模型。某速递公司提供快递服务，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该地区的几辆卡车。因为快递行业的竞争加剧，为了减少平均的送货时间，必须将各包裹根据目的地的地理位置加以分类，并分装到不同的卡车上。假设每天有三辆卡车提供快递服务，卡车可行的路线有10条，如表格五所示（其中各列的数字表示送货的先后次序）。公司有特制软件，该软件第一步就是根据当天要送快递的地点，找出各卡车可能的路线。假设当天有9个快件需要送到9个地点，请根据各种可能的路线以及所需时间的估计值，建立相应的0-1整数规划模型，为每辆卡车选出一条路线，以最短的总时间完成各地的送货工作。表格五 某速递公司的路线选择的相关数据快递地点可行的路线12345678910A111B21222C3333D211E223F12G3123H131I342时间(小时)6475465376年级：_ 专业：_ 班级：_ 学号：_ 姓名：_.装.订.线诚信应考 考出水平 考出风格浙江大学城市学院2011 2012学年第一学期期中末考试试卷应用运筹学题序一二三四总 分得分评卷人得分一判断题(本大题共10小题，每题1分，共10分。) 题号12345678910得分二填空题(本大题共30空，每空1分，其中第一小题每行1分，共30分。) 灵敏度报告最优值最优解重新求解单个目标函数系数变动且在变动范围内多个目标函数系数变动且在变动范围内单个约束右端值变动且在变动范围内多个约束右端值变动且在变动范围内约束条件系数变化增加一个新变量增加多个新变量增加一个约束条件增加多个约束条件同时增加变量和约束条件得分三分析解答题 (共10分。)得分四计算解答题 (共20分。)得分五计算解答题 (共10分。)解题要求：给出三要素，建立