2017年山东科技大学运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 试写出求解最短径路的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）。
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、计算题
3． （1）每月需要某种机械零件2000件，每件成本150元，每年的存储费用为成本的16%，每次订购费100 元，求E.O.Q 及最小费用。
（2）在题（1）中如允许缺货，求存储量s ，及最大缺货量，设缺货费为C 2=200元。 【答案】（1）用“不允许缺货，生产时间很短”的模型求解。
E.O.Q 为最小费用为
所以，最佳批量为447件，最小费用约为10733元。 （2）用“允许缺货，生产时间很短”的模型求解。
最大缺货量为
所以库存量S 为423件，最大缺货量为50件。
第 2 页，共 53 页
4． 求图中所示的网络最大流。
图
【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为
）。
图
用标号算法求最大流 步骤一
（l ）标号过程。先给v s 标号（0，+∞），依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（v 6，9）。
（2）调整过程。在网络上寻找增广链
=
，如图双箭头所示。
图
第 3 页，共 53 页
由此得到新的可行流
，如图所示。对新的可行流，重复标号与调整过程。
图
步骤二
（l ）标号过程。先给v s 标号（0，+∞），再依次给v 3标号（v s ，10），v s 标号（v 3，9），v 7
标号（v 5，9），v 8标号（v 7，9），v t 标号（v 8，9）。v t 己得到标号，因此转入调整过程。
（2）调整过程。在图所示网络上，寻找新的增广
链
，如图中双箭头所示。
，即
图
其他的保持
与调整过程。
不变。调整后得新的可行流
，如图所示。对此可行流继续标号
第 4 页，共 53 页