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． 已知下列资料，如表所示。
要求:（1）绘制网络图;
（2）计算各项时间参数;
（3）确定关键路线。
【答案】（1）由题意绘制网络图如图所示。
（2）事项最早时间见图“口”中的数字，事项最迟时间见图中“△”中的数字。
图
（3）总时差为零的工序为关键工序，
所以关键路线为
如图所示。
，