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

一、计算题

1． 设D=（W ，A ，C ）是一个网络。证明:如果D 中所有弧的容量c ij 都是整数，那么必存在一个最大流

初始号为:

。对于弧。 ，v j 的标号为:，因为c ij 均为整数，所以最终得至。调整量【答案】证明:将该问题转化为网络最大流的问题，并由寻求最大流的标号法进行求解。 ; 对于弧，v j 的标也为整数。故

标号最终结果，得最大流f 必为整数。

2． 证明如下序列不可能是某个简单图的次的序列:

（l ）7，6，5，4，3，2;

（2）6，6，5，4，3，2，l ;

（3）6，5，5，4，3，2，l 。

【答案】（1）由定理知，

能是图的次序列。

（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。

（3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。

； v 2与v 1之间存在边e 12:，而①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）

v 7的次为1，所以必不与v 1外的其他点相连。因而，v 2与除v 1，v 7外的四点之间各有一条连线。 至此，v l 、v 2与v 3、v 4、v 5和v 6中任意一个就组成了环，则G 不是简单图。

②假定G 中无环，则根据情形①的分析，v 1的关联边中必存在重复边。从而G 不是简单图。由上可知，该图中必有环或多重边，不可能是简单图的次的序列。

3． 己知运价表如表所示:

表 为偶数，而在此序列中，为奇数，所以此序列不可

求解总运费最小的最优解（注:求解方法不限，要求写出必要的计算过程）。

【答案】此问题是一个产销不平衡的运输问题，首先增加一个假想的产地戊，其产量为30，运价为0，化为产销平衡问题如表所示:

表

采用伏格尔法，求得初始解如下:

表

采用位势法检验，得下表:

表

表中还有负检验数，说明未得最优解，用闭回路法进行改进，如表所示:

表

确定调入量θ=min（50，20，30）=20。按闭回路上的正负号，加入和减去20，得到调整方案，如表所示:

表

对上表结果在采用位势法求各空格的检验数，如表所示:

表

此时所有检验数都非负，即达到最优，最小运费为:

40×2+30×2+20×4+60×3+30×5=580

4． 某工厂计划生产甲、乙、丙3种产品，各产品需要在设备A 、B 、C 上进行加工，其所需加工小时数、 设备的有效台时和单位产品的利润表所示。

表

请回答下面三个问题: