2016年东南大学经济管理学院972运筹学考研内部复习题及答案
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
若
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 3． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
二、证明题
4． 对于M/M/c/∞/∞模型，（1）
【答案】（l
）因为以（2）
。
；（2）
，
其中
是每个服务台的平均服务率，试证:
，并给予直观解释。
为系统服务台的平均繁忙个数，
即为服务台的强度，所
即其中，
为系统服务台的平均空闲个数，
则为系统服务台的平均
繁忙个数，即为服务台的强度。
5． 车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模型， 试证:
【答案】由题设知
一个周期T c 等于发生故障的机器在系统中的逗留时间W s
加上机连续正常工作时间
为 服务台繁忙的概率。服务台繁忙的概率也为
6． 证明矩阵对策意i 和j ， 有
【答案】先证充分性，由
而
所以
另一方面，对任意i , j , 由
所以
且
由有
并说明上式左右两端的概率意义。
，
则
，所以。
，使的对任
在纯策略意义下有解的充要条件是:存在纯局势。
, 有
现在证明必要性，设有i*，j*，使得
相关内容
相关标签