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

一、简答题

1． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记

（2）平衡条件 对于中间点，流出量=流入量，即对每个

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。

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

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

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

二、计算题

3． 试求解下列线性规划问题:

将本问题的目标变成maxz=-xl +x2，约束条件不变，何为其解? 【答案】（1）用图解法可得图

由图形可知，在（0，l ）处，-x 1+x2取得最大值为1。 故最优解为x 1=0，x 2=1，目标函数值为z=1。 （2

）当目标函数变为故最优解为x 1+x2=1

4． 试用SUMT 内点法求解

【答案】原问题可改写为:

构造障碍函数由于

所以，最优解为

。

即

，由于约束条件不变，即为上图中所示的阴影部分，

故目标函数值为下z=l。

由x 1+x2=0可 得，目标函数与边界直线x 1+x2=0平行。

5． 某罐头制造公司需要在近五周内必须采购一批原料，估计在未来五周内价格有波动，其浮动价格和概 率如表所示。试求各周以什么价格购入，使采购价格的数学期望值最小。

表

【答案】按采购期限将该问题分为5个阶段，将每周的价格看作该阶段的状态。

--状态变量，表示第k 周的实际价格。

--决策变量，

=1，表示第k 周决定采购;

=0，表示第k 周决定等待。

--第k 周决定等待，而在以后采取最优决策时采购价格的期望值。

第k 周实际价格为

可写出逆序递推关系式为:

其中：由

和

的定义可知：

并且得出最优决策为：

从最后一周开始，逆序递推计算，具体过程如下: 当k=5时，当k=4时，由

于是

可知

即在第5周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。

时，从第k 周至第5周采取最优决策时的最小期望值。 因而

所以，第4周的最优决策为同理求得

所以

所以