当前位置：问答库＞考研试题

一、简答题

1． 考虑两个企业的资源整合问题。如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生 产要素进行重组，然后再统筹生产带来的收益高。因此，资产重组，往往能够带来“双赢”的格局，企业自身也 希望通过合并，做大做强。问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。请谈谈你的设想，用以协调 其中可能出现的问题（不超过300字，可用符号表述你的想法）?

【答案】让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。如果z 1+z2≦2成之，则将合作后的额外收益z-（z 1+z2），按照z 1、z 2的比例进行分配。这样的分配方式，两个企业说真话，是一个均衡策略。

2． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?

【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。

当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。

二、计算题

3． 用破圈法和避圈法求下列图中各图的最小树。

【答案】（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），在 余下的图中，重复上述步骤，直到此图不再含圈为止。其具体过程如下:

①取圈（v l ，v 2，v 3），去掉最大边e 2=8;

②取圈（v l ，v 2，v 3，v 4），，去掉最大边e l =7;

③取圈（v 2，v 3，v 7），去掉最大边e 8=2;

④取圈（v 2，v 4，v 6），去掉最大边e 7=7;

⑤取圈（v 3，v 7，v 8），去掉最大边e 11=3;

⑥取圈（v l ，v 4，v 5），去掉最大边e 4=6;

⑦取圈（v 6，v 7，v 8），去掉最大边e 12=5;

⑧取圈（v 2，v 4，v 6，v 8，v 7，v 3），去掉最大边e 16=4;

⑨取圈（v l ，v 4，v 5，v 6），去掉最大边e 6=4;

⑩取圈v 5，v 6，v 8），去掉最大边e l4=6。

在图（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）。

（3）给图（c ）中的顶点和边编号v i 和e j ，如图（cl ）所示。

①采用避圈法。按照图中的边的权的大小，依次从小到大逐步选取边，并使之不构成圈，直到不能选取时， 经过九次选取后，得到的边集合{e1，e 2，e 5，e 6，e 8，e 9，e 10，e 11，e 15}构成的图即为图c 的一个最小支撑树，如图（c2）所示，此支撑树的权为19。

②采用破圈法。应用破圈原理，经过七次破圈，去掉了权数较大的七条边:e 3，e 4，e 13，e 9，e 14，e 12和e 16。而余下的边集合{e1，e 2，e 5，e 6，e 7，e 8，e 10，e 11，e 15}构成了一个无圈的图即为图4（c ）的另一个最小支撑树，如图（c3）所示。此支撑树的权仍然为19，这说明，图（c ）的最小支撑树不惟一，但其总权均为19。