2017年南京师范大学F049管理运筹学之运筹学教程复试仿真模拟三套题
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、计算题
3． 某项目由8项作业组成，相关参数如表所示。
表
试回答下述问题。 （l ）绘制网络图;
（2）计算作业C ，D ，G 的最早开工、最早完工、最迟开工、最迟完工时间、单时差和总时差;
（3）如果项目组共有工人27人，试问如何安排项目的开工时间。 【答案】（l ）绘制网络图为: （2）
图
图
如上图中的菱形所示，上半部分是最早开工时间，下半部分是最迟开工时间，
总时差为:
单时差为:
（3） ①→③与①→②同时开工，②→④在第七天开工，一直到15天， ③→⑥第16天开工，③→⑤第9天开工，⑥→⑦第22天开工， ⑦→⑧第27天开工，⑧→⑨第31天开工
4． 用分支定界法解以下问题。
【答案】在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，化为标准型
先不考虑模型中的整数约束，利用单纯形法求解，过程如表所示。
表
此时的最优解为记题:
，因为
为可行解，所以
。将原问题分解为两个子问