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

一、简答题

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

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

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

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

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因

，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

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

二、计算题

3． 设有线性规划

在第一二约束电分别加入松弛变量x 3、x 4

所示。

表

，并用单纯形法求解，得到最优单纯形表如表

（1）求出原规划LP 。

（2）写出LP 的对偶规划LD 。 （3）求LD 的最优解和最优目标值。 【答案】（l ）

（2）

（3）L p 的最优解为（3，l ），最优目标值为4x3+5xl=17 由强对偶性

4． 某工厂一年要进行A ，B ，C 三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功 的概率分别为0.4，0.6，0.8，因而都研制不成功的概率为0.4xo.6x0.8=0.192。为了促进三种新产品的研制，决定增拨2万元的研制费，并要求资金集中使用，以万元为单位进行分配。其增拨研制费与新产品不成功的概率如表所示。试问如何分配费用，使三种新产品都研制不成功的概率为最小。

表

T

【答案】按产品种类将问题分三个阶段，阶段变量k=1，2，3；设状态变量s k 为从第k 种产品至第3种产品增拨的研制费用; x k 为第k 种产品增拨的研制费用。状态转移方程为:

，p k （x k ）表示给k 种产品补加研制费x k 后的不成功概率，由题意知，动态规划

的逆推关系式为:

边界条件f 4（s 4）=1 当k=3时，

其数值计算如表所示。

表

当k=2时，

其数值计算如表所示。

表

当k=1时，

其计算结果如表所示。

表

所以，三种产品研制都不成功的概率最小为0.06。按计算表格的顺序反推式x 1*=1，x 2*=0，x 3*=1。即产品 A 、C 分别增配资金1万元，B 产品不分配资金。