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

一、简答题

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

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

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

2． 简述影子价格的经济含义。

【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。

二、计算题

3． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

第 2 页，共 60 页

故将节点2进行P 标号，

因为

（3）修改节点6，8的标号

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

因为

顶节点12已经进行了P 标号，且

故将点12进行P 标号，

于是得到节点1到节点12的最短路程为18，最故将点9进行P 标号，

故将点8进行P 标号，

故将点4进行P 标号，

故将点6进行P 标号，

故将点5进行P 标号，

短路线为1→2→5→8→11→12

4． 设有三种资源，每单位的成本分别为a ，b ，c ，给定的利润函数为ri （xi ，yi ，zi ）（i=1，2，…，n ），现有资金为，应购买各种资源多少单位分配给n 个行业才能使总利润最大，试给出动态规划的公式，并写出它的一维递推关系式。

【答案】由题意，可建立该问题的数学模型为:

按n 个行业划分为n 个阶段。阶段变量k=l，2，…，n ，第k 阶段为第k 个行业分配资源; 状态变量

为第1至第k 个行业的总金额; 决策变量（x k , y k , z k ）为第k 个行业所用三种资源的数

; 最优值函数

第 3 页，共 60 页

量; 状态转移方程为:

在状态下从第1

阶段至第k 阶段的最大利润。

动态规划的一维递推关系式为:

5． 甲、乙、丙三个铁矿石开采基地向A 、B 、C 、D 四个工厂供应原料，各供应地的供应量（万吨），各需 求地需求量（万吨）和相互之间的运价（百万元万吨）如表所示。由于外在的原因，工厂D 的原料只能由 铁矿石开采基地丙来供应。请求解满足这一要求的最优调运方案，要求采用最小元素法建立初始调运方案，采用位势法进行方案检验。

表

【答案】该问题属于运输平衡问题。因为工厂D 的原料只能由铁矿石开采基地丙来供应，所以这里规定甲、乙 和D 之间的运价为M ，M 表示足够大的正数。

采用最小元素法得初始调运方案如表所示:（因为基格个数=7-1=6个，故在一空格中填入0）

表

用位势法检验得各空格的检验数（括号内）如表所示:

在初始方案中，存在两个非基变量的检验数小于0，所以该方案不是此问题的最优方案，需进行进一步调整。 利用闭回路法进行解的改进。

在初始方案表中以（丙，A ）出发作一闭回路，利用闭回路进行调整，得到的结果如表所示:

表

第 4 页，共 60 页