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

一、简答题

1． 简述求解最小费用最大流的赋权网络设置方法。

，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权

②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令

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

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

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

按如下规则:

二、计算题

3． 求解下列矩阵对策，其中赢得矩阵A 分别为

【答案】（l ）令矩阵对策为G={S1，S 2; A}，

其中A 中表示在策略

，与策略

下的赢得值，则

，矩阵

4． 甲、乙两个儿童玩游戏，双方可分别出拳头（代表石头）、手掌（代表布）、两个手指（代表，规则是: 剪刀赢布，布赢石头，石头赢剪刀，赢者得1分。若双方所出相同算和局，均不剪刀）

得分。试列出儿童甲的赢得矩阵。

【答案】由题意知，儿童甲的赢得矩阵为:

5． 用表上作业法求表1至表4中给出的运输问题的最优解（表中数字M 为任意大正数）。

表1 表

2

表3 表4

【答案】（l ） 解表1

，求得的初始解如表5所第一步:用伏格尔法求初始可行解（过程类似于上一题，不再赘述）示。

表

5

第二步:用位势法进行最优解的判断。在对应于表5的数字格处填入单位运价，并增加一行一列，在行中填入v j ，在列中填入

，。令v 1=0，并按照

求出所有的

和v j ，

如表6所示。对于表16中的空格，依据

计算其检验数，如表7所示。

表6 表

7

由表7可知，所有空格处的检验数均为非负。所以，表5中的运输方案，即为此问题的最优 最小运价为32。调运方案，由于非基变量的检验数中

（2）解表2

第一步:用伏格尔法求初始可行解，求得的初始解，如表8所示。

表8

，所以该运输问题有无穷多最优解。