2016年中国石油大学(华东)经济管理学院运筹学考研复试题库
● 摘要
一、计算题
1． 求如图所示的网络最小费用最大流，每条弧旁的数字为。
图
【答案】给网络中的中间点加上名称，如图所示。
（l ）取为初始可行流。
（2）依照下列方法构造有向赋权图，如图所示。
并求出从v s 到v t 的最短路（v s ，
v 2，v 4，v t ），如图所示（双箭头即为最短路）。
图
（3）在原网络D 中，与这条最短路相应的增广链为
（4），如图所示。 。
图
（5）构造有问赋权图，井求出从v s 到v t 的最短路
最短路）。
，如图所示（其双箭头即为
图
（6）在原网络中，与这条最短路相应的增广链为
（7）在上调整流量，令，得，如图所示。
。
图
（8）构造有向赋权图，并求出从v s 到v t 的最短路，如图所示。因为图己不存在从v s 到v t 的最 短路，故币单位）。 为网络的最小费用最大流。其最大流量为，而最小费用为（货
图
2． 有一种设备最长使用3年时间，现考虑它在3年内的更新问题。在每年年初要作出决策，是继续使用还 是更新。如果继续使用，己知每年需要支付的维修费用如下表所示（单位:百元）:
表
如果更新设备，已知在各年年初购置该种设备的价格如表所示（残值忽略不计）（单位:百元）:
表
己知开始时该设备已经使用了l 年，问每年年初应怎样作出决策，才能使3年内该项设备的购置和维修总费 用最少? （用动态规划方法求解）
【答案】由更新设备与维修设备费用表可知，三年时间仅需选购一次设备。s k 表示k 年购进设备，可知s k 为0.1; xk 为设备在第k 年的使用年限; 设c k （x k ）为设备在第k 年的维修费用; P k 为设备在k 年购进时价格; f k （s k ）为 k 年购进设备总费用。
知第二年购进设备费用最小。
3． 某一警卫部门共有12支巡逻队，负责4个要害部门的警卫巡逻。对每个部位可以考虑派出2~4支巡逻 队，并且由于派出巡逻队的数目不同，各部位可能造成的损失会有差别，具体数字如表所示:
表