2016年华中科技大学自动化学院828运筹学考研必备复习题库及答案
● 摘要
一、简答题
1． 简述对偶问题的“互补松弛性”。 【答案】互补松弛性:若仅当为
最优解。
分别是原问题和对偶问题的可行解。那么
，当且
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界域（称为分支）的方法，逐步减小和增大3． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
若
; 。分支定界法就是将B 的可行域分成子区
:， 最终求到z*。
二、证明题
4． 证明下列定理: （1）设有两个矩阵对策，
，L 为任一常数，则有
（2）设有两个矩阵对策
，
，
（3）设则
，
（定理8） 为矩阵对策，且 ，其中
）和，则
了为斜对称矩阵（亦称这种对策为对称对策）。分别为局中人I 和
的最优策略集。（定理9）
，
，其中
，
。（定理7）
，其中a>0
为任一常数。则
【答案】（1）设A l 的赢得函数是则
，A 2的赢得函数是
则所以，同理，有
，
和瓦
，则
①
。
。
故
（2）设A l 和A 2对应的赢得函数分别为
（3）
故即
由式②可知
，因此
故
。
。
是可控制的，试定
5． 称顾客为等待所费时间与服务时间之比为顾客损失率，用R 表示。 （l ）试证:对于M/M/1模型，（2）在上题中，设
不变而
。
使顾客损失率小于4。
证毕。
时，顾客损失率小于4。 和
是G 的解，
则
【答案】（l ）对于M/M/1模型, （2）由
，得
。由定义，有
，所以当
6． 设G 为2*2对策，且不存在鞍点。证明若
。
【答案】可利用反证法求证。 假设条件不成立，可设
。
又
。
，所以