2017年江苏科技大学经济管理学院821运筹学考研题库
● 摘要
一、填空题
1． 现有m 个约束条件
，若某模型要求在这m 个条件中取”个条件作为约束，用，1
变量来实现 该问题的约束条件组为:_____。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
2． 决策问题的三个基本要素是:_____和_____。
【答案】策略、事件、事件的结果
3． 图G=（V ，E ）有生成树的充分必要条件是_____。
【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。
4． 流f 为可行流必须满足_____条件和_____条件。
【答案】容量限制条件和平衡条件
【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。
二、证明题
5． 对于M/M/c/∞/∞模型，
（1）
【答案】（l ）因为
是每个服务台的平均服务率，试证:
，并给予直观解释。
为系统服务台的平均繁忙个数，即为服务台的强度，
；（2）
，其中
所以
（2）
。
即其中，
为系统服务台的平均空闲个数，
则为系统服务台的
平均繁忙个数，即为服务台的强度。
6． 设线性规划问题1是
（
）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证【答案】问题1的矩阵表示为
其中
问题2的矩阵表示为
。
设X 1 为它的一个可行解，其对偶问题的最优解为
其中
。
设X 2 为它的一个可行解，其对偶问题的最优解为Y 2 问题1的对偶问题为
问题2的对偶问题为
=
由此可知，问题1的对偶问题与问题2的对偶问题有相同的约束条件，所以问题1的对偶问题的最优解
一定是问题2的对偶问题的一个可行解。
又因为Y 2是问题2对偶问题的最优解，所以，因为原问题与对偶问题的最优值相等，所以
7． 证明:r （x ）二x12+x22是严格凸函数。
【答案】首先求导为（2x l ，2x 2:） 求海塞矩阵
为正定矩阵，所以f （x ）为严格凸函数
三、计算题
8． 对下列整数规划问题，问用先解相应的线性规划然后凑整的办法能否得到最优整数解?
（1）
（2）
【答案】 （1）在该线性规划问题的约束条件中分别加入松弛变量
，化为标准型
相关内容
相关标签