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

一、简答题

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

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

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

2． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;

【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，

则

最优方案不发生变化。

二、计算题

3． 用单纯形法求解以下目标规划问题的满意解。

（2）

（3）

+

【答案】 （1）在第三个约束条件中加入松弛变量x 3，该目标规划的标准型为:

建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行进一步迭代，如表所示。

表

由表可知，为该目标规划的满意解。由于非基变量

。

的检验数为。，所以该

问题有多重解。进一步迭代得另一满意解为进一步迭代，如表所示。

（2）建立初始单纯形表，在表中将检验数列按优先因子个数排成4行，并采用单纯形法进行

表

由表可知，

进一步迭代，如 表所示。

为该目标规划的满意解。

（3）建立初始单纯形表，在表中将检验数列按优先因子个数排成两行，并采用单纯形法进行

表

由表可知，

为该目标规划的满意解。