2017年西北工业大学机电学院951运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
二、计算题
3． 图中V s 表示仓库，V t 表示商店. 现要从仓库运10单位的物资到商店，应如何调运才能使运费，其中C ij ，表示交通线上运输能力限制，b ij 最省（图 中弧表示交通线，弧旁的数字为（C ij ，b ij ）表示单位运价）。
图
【答案】（l ）从f （）={0}开始，做L （f （））如图1，用Dijkastra 算法求得L （f （））网络中
最短路为调整，结果见
，在网络中相应的可增广链
，如图2所示:
上用最大流算法进行流的
图
1
图2
（2）作
2
如图1，找出最短路为，在网络内相应的可增广链上进行调整，得
， 如图2所示:
到流f （）
图1
图2
（3）作调整，得到流
与如图1，找出最短路为，如图2所示
，在网络内相应的可增广链上进行
图
1
图
2
即为所求的最小费用流。
相关内容
相关标签