2017年长春理工大学经济管理学院运筹学复试之管理运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?
【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。
当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。
二、计算题
3． 出从1节点到U 节点的最短路径
图
【答案】Dijkstra 算法，即标号法求解
（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为
而
（2）修改节点3、5的T 标号
故将节点2进行P 标号，
因为
（3）修改节点6，8的标号
因为
（4）修改节点9的标号
因为
（5）修改节点7的标号
因为
（6）修改节点9、11的标号
因为
（7）修改节点12的标号
故将点5进行P 标号，
故将点6进行P 标号，
故将点4进行P 标号，
故将点8进行P 标号，
故将点9进行P 标号，
因为
顶节点12已经进行了P 标号，且
故将点12进行P 标号，
于是得到节点1到节点12的最短路程为18，最
短路线为1→2→5→8→11→12
4． 建立数学模型一家汽车制造商有5家过时的工厂，管理层考虑更新这些工厂以生产一种新型轿车的发动机组、变速器和一种主要配件A 。更新每个工厂的成本和更新后的生产能力如表所示:
表
工厂可用于更新的资金为1300万元，工厂3和工厂4位于同一地区，最多只能更新一个工厂，此外，工厂1与工厂5具有相关性，工厂5所需要的某些零件必须由工厂1生产。现计划需要180万个发动机、150万个变速器及200万个配件A ，管理层应决定更新哪些工厂以达到计划生产需
要，并使总成本最小。试建立该问题的数学模型。
【答案】设x i =1表示更新工厂i ，x i =0表示不更新工厂i 。根据题意，可建立如下数学模型:
5． 有四项工作A 、B 、C 、D 分别由甲、乙、丙、丁四个人来完成，各人完成各项任务所花费的时间（单位: 天）如下。试求解每人都承担一项工作的最优分配方案
表
【答案】该问题是指派问题，且是求目标最小。因此用匈牙利方法计算如下:
初次分配，矩阵中。个数小于4，因此对矩阵找出最少覆盖O 元素直线
进行计算后得到另一矩阵
重新分配如下:乙一A ，丙一D ，丁一B 。
，的个数为4，因此指派成功，即最优的支配方案是:甲一C ，