2016年华中科技大学管理学院851运筹学(二)考研内部复习题及答案
● 摘要
一、简答题
1． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流
（l ）容量限制条件:对每一弧（v i ，v j ）
对于起点Vs ，记
对于终点V t ，记 （2）平衡条件 对于中间点，流出量=流入量，即对每个
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
2． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?
【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。
3． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
二、证明题
4． 设线性规划问题1是
（）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证
【答案】问题1的矩阵表示为
第 2 页，共 17 页
其中
问题2的矩阵表示为
。 设X 1 为它的一个可行解，其对偶问题的最优解为
其中
问题1的对偶问题为
问题2的对偶问题为
=
由此可知，问题1的对偶问题与问题2的对偶问题有相同的约束条件，所以问题1的对偶问题的最优解一定是问题2的对偶问题的一个可行解。
。 设X 2 为它的一个可行解，其对偶问题的最优解为Y 2 又因为Y 2是问题2对偶问题的最优解，所以，
因为原问题与对偶问题的最优值相等，所以
5． 己知九个人v 1，v 2，…，v 9中v 1和两个人握过手，v 2和v 3各和四个人握过手，v 4，v 5，v 6，v 7各和五个人握过手，v 8，v 9各和六个人握过手，证明这九个人一定可以找出三人互相握过手。
【答案】该问题可表述为一个包含9个点（每个人代表一个点）的图的问题。依题意知 d （v l ）=2，d （v 2）=d（v 3）=4，d （v 4）=d（v 5）=d（v 6）=d（v 7）=5，d （v 8）=d（v 9）=6 其中，边v i ，v j 〕代表v i 和v j 握过手。对于v 9，因为d （v 9）=6，所以v 4，v 5，v 6，v 7中至少有两个点与v 9之间 存在连线，设该两点为v 4和v 5。假设与v 4和与v 9相连的其他五点之间无边，
则
，与已知的 d （v 4）=5相矛盾，故假设不成立。即v 4与上述五点间必存在至少
两条边，设其中一点为v k ，则v k ，v 4，v 9两两相连，即存在三人之间互相握过手。
第 3 页，共 17 页
相关内容
相关标签