2017年浙江海洋学院运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧
这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?
【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。
当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。
二、计算题
3． 考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题），其中变量x 1，x 2取整数。该 问题的求解由子问题1开始，如图所示。
图
请回答，
（1）在当前状态下，如何对整数规划的最优解进行定界。
（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束? 附加的两个约束分别是什么?
【答案】（l ）设整数规划的最优目标值为Z*，则对其定界范围为:
（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为:
4． 用单纯形法求解如下LP 问题:
【答案】将原问题标准化:
利用单纯形法，求解如表所示。
表
此时，，故己达最优，原问题的最优解为:
5． 某城市的消防总部将全市划分为11个防火区，设有4个消防（救火）站。图表示各防火区域与消防 站的位置，其中①②③④表示消防站，1、2、…、11表示防火区域。根据历史资料证实，各消防站可在事先规定的允许时间内对所负责的地区的火灾予以消灭。图中虚线即表示各地区由哪个消防站负责（没有虚线连接，就 表示不负责）。现在总部提出:可否减少消防站的数目，仍能同样负责各地区的防火任务? 如果可以，应当关闭哪个?
图
提示:对每个防火站定义一个0-1变量x j ，令