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

一、简答题

1． 什么是关于可行流f 的增广链?

【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若

满足下列条件: （l ）在弧（2）在弧称

是关于可行流f 的一条增广链。

即即

中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。

是从v s 到v t ，的一条链，

2． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大

; 。分支定界法就是将B 的可行域分成

:， 最终求到z*。

二、计算题

3． 国内某电缆公司利用包括5个分销中心、8个客户区域的分销系统来销售其产品。配给每个客户区域一个专门的资源供应商，且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需求和雇员的工作量， 公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。如下表就是从5个分销中心到8个客户区域的供给成本（单位:1000美元）。求:

（1）使总成本最小的分销中心—客户区域的组合方式; （2）如果有，哪一分销中心没有任务分派;

（3）若进一步规定每个分销中心最多只能负责2个区域，那么新的分配方案又是什么? 【答案】 （1）由题意知该题为指派问题，添加虚拟的人，用匈牙利解法，具体过程如下：

（2）由上一小题可知，第二2、5、6、7没有任务 （3）

表

4． 已知线性规划问题

对偶变量

其对偶问题的最优解为对【答案】原问题的对偶问题为

，试应用对偶问题的性质，求原问题的最优解。

将补松弛性可知

分别代入对偶问题的各约束条件中，可知，式①和式②为严格不等式，由互

。又因为

，所以根据互补松弛性知，原问题的两个约束条件

应取等号，即

解得，

。于是原问题的最优解为

，最优目标函数值为z*=44。

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

表

【答案】按产品种类将问题分三个阶段，阶段变量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时，