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

一、简答题

1． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若当且仅当为最优解。

2． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记

（2）平衡条件 对于中间点，流出量=流入量，即对每个

分别是原问题和对偶问题的可行解。那么

，

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。

二、计算题

3． 设有三个电视机厂生产同一种彩色电视机，日生产能力分别是:50，60，50（台），供应三个门市部，日销售量分别是:60，40，60（台），从各分厂运往个门市部的单位运费如表所示，试安排一个运费最低的运输计划。 若工厂1到门市部1的运价由9减为6，试寻求最优运输计划。

表

【答案】（l ）此问题是运输平衡问题。 第一步，用伏格尔法寻找得到初始基可行答:

表

第二步，用位势法计算各空格处的检验数为:

表

从所有非基变量的检验数可以看出都是非负数，其中存在一个0的检验数，说明该题有多重最优解。

（2）若工厂1到门市部1的运价由9减到6时，代入计算得第一步，用伏格尔法寻找得到初始基可行

表

第二步，用位势法计算各空格处的检验数为:

表

从所有非基变量的检验数可以看出都是非负数，其中存在两个0的检验数，说明该题有多重最优解。

4． 用分支定界法解以下问题。

【答案】在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，化为标准型

先不考虑模型中的整数约束，利用单纯形法求解，过程如表所示。

表

此时的最优解为记题:

，因为

为可行解，所以

。将原问题分解为两个子问

求得B 1的最优解x l =2，x 2=23/9，z 2=41/9。