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

一、简答题

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

【答案】互补松弛性:若

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

，

当且仅当为最优解。

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

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

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

二、计算题

3． 用大M 法（极小化为标准形式）求解得某极小化线性规划问题的最优单纯形表如表所示。

表

表中x 4为松弛变量、x 5为剩余变量、x 6和x 7为人工变量。试回答如下问题: （l ）计算C 1和C 2的数值;

（2）求使最优基不变的C 1、C 2的关系; （3）求原问题的三个右端常数。

【答案】（l ）由最优单纯形表得到下列关系式为:

（2）若最优基不变，则有下列关系式:

（3）

解得原问题的三个右端常数为

4． 考虑如下线性规划问题:

其中α, β为参数，要求:

（l ）组成两个新的约束（l ）’=（l ）+（2），（2）’=（2）-2（l ），根据（l ）’，以X 1，X 2为基变量列出初始单纯形表;

（2）假定β=0，则α取什么值时，X 1，X 2为问题的最优基变量; （3）假定α=3，则β取什么值时，X 1，X 2为问题的最优基变量。 【答案】（l ）新的规划问题为:

初始单纯形表如表所示。

表

（2）若β=0，代入上述初始单纯形表中，得表

表

2）’（

若使最优解仍为x 1和x 2，则需满足

（3）将β=3，代入初始单纯形表中，得到表

表

若x 1，x 2为问题的最优基变量。则需满足

5． 某公司初步选定6个人去完成4项任务，由于个人和技术专长的不同，他们完成4项任务所获得的收益 如表所示，且规定每个人只能完成一项任务，一项任务只能由一个人来完成，具体完成任务的收益如表 所示，求使总收益最大的指派方案

表