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

一、简答题

1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

2． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?

【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。

先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求解k 个线性规划（k 为优先级的个数），即可求出目标规划的满意解。

二、计算题

3． 某一运输问题的初始基可行解如表所示，括号内数据为非基变量的检验数，试确定新的基可行解。

表

【答案】选择空格A 2B 3，对其所在回路进行调整，调整量为min （5，30）=5，得新的基可行解如下:

表

4． 已知世界六大城市:P e ，N ，P a ，L ，T ，M 。试在表所示交通网络的数据中确定最小树。

表

【答案】将表用图形的形式表示出来，如图所示。

图

（1）采用避圈法。从图中选取权数最小的边[L，P a ]; 从未选的边中，选取权最小的边[Pe ，T]:依次进行，并使得它们相互不构成圈，直到再也不能选取出边为止。经过五次选边，得到边集合 {[L，P a ]，[Pe ，T]，[M，N]，[L，N]，[Pe ，L]}构成了唯一的最小支撑树，如图所示，此最小支撑树的总权为119。

图

（2）采用破圈法。应用破圈法的原理，依次进行破圈，直到所有边构成的图中不含有圈为止。所得到的结 果与上述避圈法的相同。

5． 用单纯形法求解下列线性规划问题。

【答案】将上述线性规划问题化为标准型为:

用单纯形表计算如表所示，

表

所以，最优解为x*=（40，5，0，0，0，15），最优目标函数值为z*=750。

6． 用牛顿法求答解:

【答案】

，

取初始点

T

为对称正定矩阵 。