2018年东北大学工商管理学院852运筹学考研基础五套测试题
● 摘要
一、简答题
1． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。 2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
3． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、证明题
4． 假设线性规划问题为:
其中
，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到
第 2 页，共 68 页
的最优解必定 是线性规划问题（l ）的准最优解。
【答案】一般情况下，经过迭代后解变为
再将上式代入目标函数式，整理后得到
令于是
再令则
时，此时的解就为最优解。
，并对上式给予直观的解释。
这样当所有非基变量的检验数即5． 对于M/M/1/N/∞模型，试证
【答案】若令
，
则有
所以
，即
此系统的等待空间有限制，即一旦顾客满N 个，新来的顾客就无法进入系统，此时到达率为零。故这里需 要求出实际进入系统的平均到达率
。由于正在被服务的顾客平均数为
另外，在单位时间内实际进入服务系统的顾客平均数
为
第 3 页，共 68 页
。因此，
。
6． 在M/M/1/N/∞模型中，如
，试证
应为，于是。
【答案】系统在t 时刻的顾客数N （t ）仍是一生灭过程，且有
当t=+∞时，由系统的稳定状态概率可得
7． 设线性规划问题1是
（
）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证
【答案】问题1的矩阵表示为
第 4 页，共 68 页