2017年浙江财经大学运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
（2）平衡条件 对于中间点，流出量=流入量，即对每个
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
二、计算题
3． 有四个工件J 1，J 2，J 3，J 4，要求在三台设备A ，B ，C 上顺次加工，各工件在各设备上的加工时间示于表中，试构造一启发式算法，用于寻求使总加工时间最短的工件加工顺序。
表
【答案】可设计如下启发式算法:
利用该启发式算法求解，求解过程如表所示。
表
所以，最优加工顺序为，总加工时间为40。
4． 在图中，（l ）用Dijkstra 方法求从v l 到各点的最短路; （2）指出对v l 来说，哪些顶点是不可到达的。
图
【答案】（1）①v1已经获得P 标号，
计算从v l 到各点的最短路的步骤如下:
，修改v2，v5，v7的T 标号
因为
②v5已经获得P 标号，
，改写v6的T 标号为
，所以有
。
于是，有v 1到各点v 2，v 5，v 7，v 6，v 8的最短路为
，
因为
（2）v 1不能到达v 3及v 4。
5． 已知矩阵对策
的解为
对策的解，其赢得矩阵A 分别为
【答案】（l ）因为
所以可由定理7可知
（2）因为
，对策值为24/l3。求下列矩阵
所以。
6． 陈明是国内某电子玩具公司负责营销的副总裁，他正在为新系列的电子玩具设计广告。他希望这个广告项目能够在57天之内完成，以便能够在圣诞季节之前及时推出这个广告。陈明确认这个广告项目需要完成六个活动，分别记为A 、B 、C 、D 、E 和F 。这些活动的顺序和每项活动所需要的时间如表所示。
表
相关内容
相关标签