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

一、计算题

1． 在有互相排斥的约束条件的问题中，如果约束条件是（≤）型的，我们可用加以y i M 项（y i 是0-1变量， M 是很大的常数）的方法统一在一个问题中。如果约束条件是（≥）型的，我们将怎样利用y i 和M 呢?

【答案】在互相排斥的约束条件问题中，如果约束条件是（≥）型，我们可以分别在m 个约束条件右端减去y i M ， 其中y i 是0-1变量，M 是充分大的正数，且。

2． 某产品从仓库A i （i=1， 2, 3）运往市场B j （j=1， 2, 3，4） 销售，已知各仓库的可供应量、各市场的需求量及从A 1仓库到B 1市场路径上的容量如表所示（表中数字0表示两点之间无直接通路），请制定一个调运方案使从各仓库调运产品总量最多。

表

【答案】该问题是求最大流问题，由题得网络图，其中S 、D 是虚拟开始和结束点，各路径最大

容量如图所示，初始流量为0:

图

（1）标号过程

①首先给S 标号（0,

，同理，）, 检查S , 在弧（S , A1）上，F SA1< CSA1，则给A 1标号（S , 20）

，A 3 （S , 100） 标号A 2（S , 20）

②任选一点A 1进行检查，在弧（A 1 , B1）上，F A1B1< CA1B1，则给B 1标号（A 1, 20）

③检查B 1 ，在弧（B l , D ）上，F B1D < CB1D ，则给D 标号（B l , 20），这样找到了一条增广链，S- A1- B 1-D

（2）调整过程，由（1）知，=20, 得新的可行流量图，如下图所示。

图

依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得最大流量图，如下图所示。

图

调运方案如表所示.

表

3． 求如图所示的网络最小费用最大流，每条弧旁的数字为 。

图

【答案】给网络中的中间点加上名称，如图所示。 （l ）取为初始可行流。

（2）依照下列方法构造有向赋权图，如图所示。

并求出从v s 到v t 的最短路（v s ，

v 2，v 4，v t ），如图所示（双箭头即为最短路）。