2017年山东科技大学交通学院847运筹学考研题库
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
2． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
3． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）恰好是问题的最优解。
4． 考虑两个企业的资源整合问题。如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生 产要素进行重组，然后再统筹生产带来的收益高。因此，资产重组，往往能够带来“双赢”的格局，企业自身也 希望通过合并，做大做强。问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。请谈谈你的设想，用以协调 其中可能出现的问题（不超过300字，可用符号表述你的想法）?
【答案】让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。如果z 1+z2≦2成之，，按照z 1、z 2的比例进行分配。这样的分配方式，两个企业说真则将合作后的额外收益z-（z 1+z2）话，是一个均衡策略。
二、计算题
5． 用破圈法和避圈法求下列图中各图的最小树。
【答案】（l ）给图（a ）的点和边编号v i 和e j ，如图（al ）所示。
①采用避圈法。首先从图（al ）中选取最小边e l3=1，以后每一步从未选出的边中选出一个边上权最小的边，并使之与前面己选的边不构成圈（若在某一步中，有两条或两条以上的最小权的，直到不能选出为止。 边时，则从中任选取一条）
于是，以{el3，e 15，e 3，e 9，e 10，e 5，e l7}为边构成的图恰好就是一个支撑树，如图（a2）所示，其权为16。
，从中去掉权最大的边（此处②采用破圈法。在图（al ）中任取一个圈，例如（v 1，v 2，v 3）
，在 余下的图中，重复上述步骤，直到此图不再含圈为止。其具体过程如下: 去掉边e 2=8）
，去掉最大边e 2=8; ①取圈（v l ，v 2，v 3）
，，去掉最大边e l =7; ②取圈（v l ，v 2，v 3，v 4）
，去掉最大边e 8=2; ③取圈（v 2，v 3，v 7）
，去掉最大边e 7=7; ④取圈（v 2，v 4，v 6）
，去掉最大边e 11=3; ⑤取圈（v 3，v 7，v 8）
，去掉最大边e 4=6; ⑥取圈（v l ，v 4，v 5）
，去掉最大边e 12=5; ⑦取圈（v 6，v 7，v 8）
，去掉最大边e 16=4; ⑧取圈（v 2，v 4，v 6，v 8，v 7，v 3）
，去掉最大边e 6=4; ⑨取圈（v l ，v 4，v 5，v 6）
，去掉最大边e l4=6。 ⑩取圈v 5，v 6，v 8）
，这就是一个最小支撑树。
在图（al ）中通过10次破圈后留下来的图仍然还是（a2）
（2）给图（b ）中的顶点和边编号v i 和e j ，如图（bl ）所示。
①采用避圈法。类似于（l ）的避圈法，最后，由边集合{e3，e 2，e 5，e 7，e 9，e 8}构成的子图（见图（b2））是一个最小支撑树，其权为12。
②采用破圈法。与（l ）中的破圈思路相同，通过破去图中e l ，e 4，e 6，e l0和e 1l ; 这五条边以后余下的边集 {e2，e 3，e 5，e 7，e 9，e 8}构成的子图就是原图的一个最小支撑树，此最小支撑图正是先前的图（b2）。