2017年南京大学软件学院859系统分析与集成专业基础(运筹学、管理信息系统)考研冲刺密押题
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域;
（3）某枝所得数据不优于当前最优解时。
二、计算题
3． 用标号法求点V 1到点v 7的最大流，弧旁数字分别表示流量和容量。
图
【答案】（l ）标号过程:
①首先给v l 标上（0，+∞）
②检查v 1在弧（v 1，v 5）上，v 5的标号为（v l ，7）
③检查v 5，在弧（v 5，v 7）上，v 7的标号为（v 5，6）
因v 7有了标号，故转入调整过程。
（2）调整过程 按点的第一个标号找到一条增广链，按可行流:
在上调整f. 调整后得如图所示的
图
（3）对得到的可行流人进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v 1，v 3）上，v 3的标号为（v l ，2）
③检查v 3，在弧（v 3，v 6）上，v 6的标号为（v 3，2）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（4）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（5）对得到的可行流几进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 2）上，v 2的标号为（v l ，2）
③检查v 2，在弧（v 2，v 5）上，v 5的标号为（v 5，2）
④检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，2）
⑤检查v 6，在弧（v 6，v 7）上，v 7的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（6）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（7）对得到的可行流进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 5）上，v 5的标号为（v l ，l ）
③检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，l ）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，l ）
因v 7有了标号，故转入调整过程。
（8）调整过程
按点的第一个标号找到一条增广链，按在上调整调整后得如图所示的可行流
图
标号过程无法继续进行下去，算法结束。最大流量为:3+6+7=16。
4． 计算分析与讨论一一考虑线性规划问题:
试用单纯形方法讨论p 在什么取值范围时，下列问题成立:
（l ）线性规划有唯一最优解;
（2）线性规划有无穷多最优解;
相关内容
相关标签