2017年华中科技大学管理学院851运筹学(二)考研题库
● 摘要
一、简答题
1． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
2． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
3． 简述影子价格的经济含义。
【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。
4． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、证明题
5． 证明下列定理:
（1）设有两个矩阵对策，
，L 为任一常数，则有
（2）设有两个矩阵对策，
，
（3）设
（定理8） 为矩阵对策，且
了为斜对称矩阵（亦称这种对策为对称对策）。
，其中
，
。（定理7）
，其中a>0
为任一常数。则
则， ，其中）和分别为局中人I 和，
则
的最优策略集。（定理9）
，A 2
的赢得函数是
【答案】（1）设A l
的赢得函数是
，则
则所以，同理，有
故
，
和瓦
，则
①
。
。
（3）
故即由式②可知
，因此
故
。
。
（2）设A l 和A 2对应的赢得函数分别为
6． 对于M/M/1/∞/∞模型，在先到先服务情况下，试证明:
顾客排队等待时间分布的概率密度是
，并根据该式求等待时间的期望值
为在统计平衡 下顾客的等待时间，则
。
，【答案】令N ’为在统计平衡下一个顾客到达时刻看到系统中已有的顾客数（不包括此顾客）
由a n 的定义，得
，于是有
由定理知，对任何一个输入为最简单流的单服务台或多服务台的等待制排队系统，
恒有
，所以，
到达者遇到系统中顾客数不少于1个顾客，是需要等待的充要条件，因此
①
因为当系统中有n （n ≥l ）个顾客时，其中只有一个顾客正在接受服务，而其余n-1个顾客在排队等待，所以，新到顾客必须在服务台轮空n 次后，才能接受服务。于是，服务台轮空次数m （t ）
②
其次，因为服务时间服从负指数分布，故其输出流，即服务台轮空次数m （t ）是一最简单流，其参数为
因此
③
将③式代入②式，然后再将②式代入①式，得
，其中，
，有
所以，顾客在系统中的等待时间分布为
因为，
以正概率
取0值，而当t>0时，它又具有连续型随机变量的性质，其分布函
既不是连续型随机变量，又不是离散型随机变量。然而类似的密度函数为
数必在（0，+∞） 上连续。所以于连续型随机变量，可以定义
。