2017年河北大学管理学院868运筹学考研冲刺密押题
● 摘要
一、简答题
1． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;
【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，
则
2． 试写出求解最短径路的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）。
3． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。
（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不
使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，
行流水作业，同时消耗人、机、材等资源也合理。
4． 简述影子价格的经济含义。
【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场
第 2 页，共 60 页 最优方案不发生变化。
价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。
二、计算题
5． 解下列0- 1规划问题。
（2）
T 【答案】 （1）通过观察可知（0, 0, 1）为可行解，相应的z=2, 故增加约束条件
进行枚举及选择，如表所示。
表
由表可判定，最优解为
进行枚举及选择，如表所示。 T （2）通过观察可知（0，0，0，l ）为可行解，相应的z=4，故增加约束条件，
表
第 3 页，共 60 页
由表可判定最优解为
6． 有10个城市，它们在坐标系中的位置如表所示，试完成以下工作。
（l ）用C 一W 节约算法求出经过每个城市一次且仅一次的一条最短线路。
（2）用Norback 和Love 提出的几何法，求出经过上述每个城市一次且仅一次的最短线路。
（3）比较上述两种方法得出的结果，并设计一种启发式方法，对上述较差的结果进行改进。
表
【答案】（l ）计算各点对之间的欧氏距离c ij ，计算结果如表所示。
表
取城市1为基点，利用公式如表所示。 。计算将弧插入线路中的节约值，
第 4 页，共 60 页