2017年江南大学管理运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
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． 考虑一个平衡流水线的设计问题。一项工作可以分解分A 、…、K 项任务，完成每项工作需要的时间如表所示
表
彼此工序如图所示，需要在4个工作台上实现这11项任务。试问怎样在4个工作台上安排这些任务， 在满足工序要求的前提下，整个流水线的循环周期为最小
图
【答案】设流水线的一个周期时间为T ，C i 表示工作i 所需时间，另外
建立模型如下：
说明:模型不唯一，上述只是一个模型表述。
4． 随机型网络计划假设某项工程的关键路线为（1，3，5，7，9），共有4项关键活动，各项活动的a ，m ，b 值由下表给出（单位:天）。试求总工期T E 的期望值和方差以及在17天内完工的概率。（其中: a 为最乐观的时间; b 为最保守的时间; m 为最可能的时
间
表 各项活动的a ，m ，b 值
【答案】由题意可知，根据已知条件，可以求解总工期的期望和方差为:
易知总工期T 服从均值为T ，方差为v ’的正态分布，即总工期服从N （Tz ，v ’）的正态分布在17天内完工的概率为
即在17天内完工的概率为0.87.
5． 两家工厂x 1和x 2生产一种商品，商品通过如图所示的网络运送到市场y 1，y 2，y 3，试用标号法确定从工厂到市场所能运送的最大总量。
图
【答案】增加v s 和v t 令所有弧上可行流为零，同时给图中的中间点标上名称，如图所示。
图
用网络流的标号算法求该问题的最大流。 步骤一
相关内容
相关标签