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

一、简答题

1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

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

【答案】互补松弛性:若当且仅当为

最优解。

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

，

二、计算题

3． 利用优超原则求解下列矩阵对策。

（1） （2）

【答案】（l ）由于第1列优超于第3列与第4列，故可划去第3、4列，得到新的赢得矩阵

在A l 中，第3行优超于第1行，第4行优超于第2行，故可划去第1、2行，得到新的赢得矩阵

在A 2中，第1列优超于第2列，故可划去第2列，得到新的赢得矩阵

。

在A 3中，第1行优超于第3列，故可划去第2行，得到新的赢得矩阵策的解为

，

。

，故原矩阵对

（2）由于第3行优超于第2行，第4行优超于第1行，故可划去第1、2行，得到新的赢得矩阵

在A l 中，由于第1列优超于第3列，第2列优超于第4、5列，故可划去第3、4、5列，得到新的赢得矩阵

在A 2中，由于第l 行优超于第3行，故可划去第3行，得到新的赢得矩阵

易知

没有鞍点，所以有

解得

又因为A 3是由A 的第3、4行和第1、2列组成的矩阵，所以，原矩阵对策的解为

4． 用单纯形法求解如下LP 问题:

【答案】将原问题标准化:

利用单纯形法，求解如表所示。

表

此时，，故己达最优，原问题的最优解为:

5． 如下线性规划问题:

当t l =t2=0时用单纯形法求解得最终单纯形表如下表所示: 试分析说明如下问题: （l ）确定

的值;