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

一、简答题

1． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

可见，当Cr 变化成△Cr 后，最终表中的检验数是:

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

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

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

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

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

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

，即可求出目标规划的满意解。 解k 个线性规划（k 为优先级的个数）

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

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

二、计算题

5． 某厂计划连续生产B 产品，每月初开始生产。B 的生产成本费为每吨x 2千元，其中x 是B 产品当月的产量。仓库存货成本费是每月每吨1千元。估计3个月的需求量分别为5，10，15吨。现设开始时第l 个月的月初库存为零，第3个月月末存货为零。

试问:每月应生产多少吨B 产品，可使总的生产和存货费用最小? （用动态规划方法求出最优解，不必求最 优值）。

【答案】按月份将问题划分为三个阶段，设d k 为第k 阶段对产品的需求量，x k 为第k 阶段生产产品B 的吨数，V k 为第k 阶段结束时的产品库存量，

则有

生产产品B 为x k 吨时的成本，

动态规划的顺序递推关系式为

边界条件

6． 在图中，分别求v l 至v 6，v l 至V 4，v6至vZ 和vZ 至vs 的最短路和最短距离。

表示第k 阶段表示在第k 阶段结束时有库存量v k

所需的库存费用。

图

【答案】用Floyd 方法求解

令网络的权矩阵为

其中，

为到的距离 由表示从v i 到v j 点的或直接

有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得

表示从vi 到vj 点最多经v l ，v 2的最短路长，得以此类推，

所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1; v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3; v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3: v 2至v 5的最短路是v 2一v3一v 5，最短距离1;