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

一、简答题

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

【答案】互补松弛性:若

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

，

当且仅当为最优解。

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

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

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

二、计算题

3． 某公司现拥有资金3万元。现做今后3年的投资计划每年允许投资额不能超过5万元. 若某年投资x 元，当年有l/3可能性损失x 元，而有2/3可能性增收x 元。现要确定能使3年后将拥有资金超过5万元的可能性最大的投资力案

试结合题中说明，当用动态规划方法求解时的下列基本概念（不必计算）: （l ）阶段变量:

（2）状态变量、状态集台: （3）决策变量、允许决策范围 （4）状态转移关系: （5）递推方程。

【答案】（l ）阶段变量k :按三年的投资计划，分为3个阶段; （2）状态变量s k :表示第k 年初投资时剩余的全部资金金额 状态集合为:s 1=3

（3）决策变量x k :表示第k 年初用于投资的金额（4）状态转移关系为:

（5）递推方程:

第 2 页，共 36 页

4． 用表上作业法求表1至表4中给出的运输问题的最优解（表中数字M 为任意大正数）。

表1 表

2

表3 表

4

【答案】（l ） 解表1

，求得的初始解如表5所第一步:用伏格尔法求初始可行解（过程类似于上一题，不再赘述）示。

表

5

第二步:用位势法进行最优解的判断。在对应于表5的数字格处填入单位运价，并增加一行一列，在行中填入v j ，在列中填入

，。令v 1=0，并按照

求出所有的

和v j ，

如表6所示。对于表16中的空格，依据

计算其检验数，如表7所示。

表6 表7

第 3 页，共 36 页

由表7可知，所有空格处的检验数均为非负。所以，表5中的运输方案，即为此问题的最优 最小运价为32。调运方案，由于非基变量的检验数中

（2）解表2

第一步:用伏格尔法求初始可行解，求得的初始解，如表8所示。

表

8

，所以该运输问题有无穷多最优解。

第二步:用位势法进行最优解的判断。在对应于表8的数字格处填入单位运价，并增加一行一列，在行 中填入v j ，在列中填入

。令u 1=0，按照

表9

求出所有的

和v j ，

并依据

计算所 有空格处的检验数，计算结果如表9所示。

由表9可知，所有空格处的检验数均为非负。所以，表8中的运输方案即为此问题的最优调运方案， 最小运价为118。

（3）解表3

，其运价为0，其销量为2，如表由于表3中产大于销，因此需要增添一个假想的销地“己”10所示。

第 4 页，共 36 页