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

一、简答题

1． 什么是可行流?

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

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

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

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

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

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

:， 最终求到z*。

二、计算题

3． 某机场有一条专供飞机降落的跑道。假定飞机降落占用跑道的平均时间为2分钟（这里“占用”指不准 其他飞机使用）。设飞机在空中的平均耽误时间（wq ）不得超过10分钟，飞机的到达为泊松分布。

（l ）如果飞机占用跑道时间服从负指数分布，机场的最大允许载荷量（以每小时能到达的飞机平均数表示） 是多少?

（2）如果飞机占用跑道时间服从任意独立分布，并已知一架飞机占用跑道的标准差为1分钟，那么机场的 最大允许载荷量是多少?

（3）如果飞机占用跑道时间服从负指数分布，并另外规定:要求一架飞机从到达到降落时间大于20分钟的 概率小于0.05，这时机场的最大允许载荷量是多少? （计算过程中如有过数，不必求出，结果可用含对数的式子 表示）

【答案】

由

知，

知机场最大载荷来量：

飞机最大载花量为3ln20

4． 已知有六台机床x 1，x 2，…，x 6，六个零件y 1，y 2，…，y 6。机床x 1可加工零件y 1; x 2可加工零件y 1，y 2; x3可加工零件y 1，y 2，y 3，x 4可加工零件y 2; x 5可加工零件y 2，y 3，x 4; x 6可加工零件y 2，y 5，y 6。现在要求制订一个加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工。试把这个问题化为求网络最大流的问题，求出能满足上述条件的加工方案。

【答案】依题意，画出最大容量的网络图，并令（l ）标号过程。进行标号，并找出增广链:

因v t 已标号，转入调整过程。

，如图所示。

图

（2）调整过程。按点的第一个标号找到一条增广链整:

调整后得如图所示的可行流，对这个可行流进入重新标号，寻找增广链。

。按照

在

上调

图

反复标号过程和调整过程，最后得到如图所示的结果。

图

可知，最优加工方案为:机床x 1加工零件y 1，机床x 2加工零件y 2，机床x 3加工零件y 3，机床x 5加工零件y 4，机床x 6加工零件y 6，机床x 4不加工零件，零件y 5没有机床加工。

最大流量是V （f ）=5。

5． 试写出下述非线性规划问题的K-T 条件并进行求解：

【答案】（1）原非线性规划问题可改写成：

目标函数和约束函数的梯度为：

对第一、二个约束条件分别引入广义拉格朗日乘子条件:

和

，并令K-T 点为X*，则有K-T