2017年西北民族大学968运筹学(网络科学基础)考研复试核心题库
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。
二、计算题
3． 求下述线性规划问题目标函数z 的上界
其中
【答案】（l ）要求z 的上界
和下界
，则c 1，c 2，b l ，b 2应取其最大值; a ll ，a 12，a 21，a 22应取其最
小值，此时，得到的线性规划问题为
在上述问题的第一个约束条件中加入松弛变量x 3，第二个约束条件左右两边同时除以2再加入松弛变量x 4，得到该线性规划问题的标准型
单纯形法的计算过程如表所示。
表
解得最优解（2）要求z 的下界时，得到的线性规划问题为
，目标函数z 的上界=21。
，则c l ，c 2，b 1，b 2应取其最小值; a 11，a 12，a 21，a 22应取其最大值，此
在上述问题的第一个约束条件中加入松弛变量x 3，第二个约束条件左右两边同时除以2再加入松弛变量x 4，得到该线性规划问题的标准型
单纯形法的计算过程如表所示:
表
解得最优解
4． 求如图所示的中国邮递员问题。
，目标函数z 的下界
图
【答案】按最短路线连接各奇点，如图所示。
由图可知，在图的每一条边上至多有一条重复边; 图中每圈上重复边的总权不大于该圈总权的一半。 所以任一欧拉圈就是最优邮递路线。
5． 某厂每年需要某种元件5000个，每次订购费c 3=50元，保管费每件每年c 1=1元，不允许缺货，元件单价k 随采购数量的不同而变化，问公司每次应该订购多少? 总的采购成本是多少?
【答案】利用E.O.Q 公式计算
分别计算每次订购707个和1500个元件，平均单位元件所需费用: