2017年黑龙江科技大学管理学院820运筹学考研导师圈点必考题汇编
● 摘要
一、判断题
1． 在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。， （ ）
【答案】×
【解析】连通且不含圈的无向图称为树。
2． 对自由变量x k ，
通常令不可能同时出现
【答案】√ 【解析】因为
，所以
不能同时为基变量，则至少有一个为0。故最优解中
不可能同时出现。
3． 已知y i *为线性规划问题的对偶问题的最优解，若y i *>0，则说明在最优生产计划中第i 种资源己经完全耗尽。（ ）
【答案】√
【解析】对偶问题互补松弛性质中
，表明在最优生产计划
。（ ）
，其中
在用单纯型法求得的最优解中
中第i 种资源已经完全耗尽。
4． 运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现四种情况之一:有惟一最优解，有无穷多最优解，无界解，无可行解。（ ）
【答案】×
【解析】运输问题是一种特殊的线性规划模型，它总存在可行解，或是存在惟一最优解，或是有无穷最优解。
二、简答题
5． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
6． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?
【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。
三、计算题
7． 某工厂生产某种零件，每年需要量为18000个，该厂每月可生产3000个，每次生产后的装配费为5000元，每个零件的存储费为1.5元，求每次生产的最佳批量。
，已知C 3=500，C l =1.5，P= 【答案】由题意知，该题模型为“不允许缺货，生产需一定时间”3000, R=18000/12=1500。
最佳批量是
所以，每次生产的最佳批量为科72个。
8． 考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题），其中变量x 1，x 2取整数。该 问题的求解由子问题1开始，如图所示。
图
请回答，
（1）在当前状态下，如何对整数规划的最优解进行定界。
（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束? 附加的两个约束分别是什么?
【答案】（l ）设整数规划的最优目标值为Z*，则对其定界范围为:
（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为:
9． 对于下列线性规划问题:
如果用表上作业法求解该问题，请写出相应的调运表，并用最小元素法求出其初始基可行解。【答案】相应的调运表为下表:
表
用最小元素法得打的初始基为
表
10．求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程最短。
表
相关内容
相关标签