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

一、简答题

1． 什么是可行流?

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

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

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

2． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。

【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。

（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。

二、计算题

3． 对于下列线性规划问题:

如果用表上作业法求解该问题，请写出相应的调运表，并用最小元素法求出其初始基可行解。【答案】相应的调运表为下表:

表

用最小元素法得打的初始基为

表

4． 利用单纯型法求解上题的线性规划问题。

【答案】在上述约束条件中加入x 6, x 7, x 8，用单纯形法求解得到表1至表4。

表

1

表

2

表

3

表4

由计算得到最优下料方案是:按l 方案下料30根; 2方案下料10根:4方案下料50根。即需90根原材料, 可以制造100套刚架。

5． 求图中所示的网络最大流。

图

【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为

）。

图

用标号算法求最大流 步骤一

，依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（l ）标号过程。先给v s 标号（0，+∞）（v 6，9）。

（2）调整过程。在网络上寻找增广链

=

，如图双箭头所示。