2016年华东交通大学经济管理学院812运筹学考研导师圈定必考题汇编及答案
● 摘要
一、选择题
1． 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。 A. 非负的 B. 大于零 C. 无约束 D. 非零常数 【答案】A
【解析】系数矩阵中的系数表示的是费用、成本、时间等。 2． 用匈牙利法求解指派问题时，不可以进行的操作是（ ）。 A. 效益矩阵的每行同时乘以一个常数 B. 效益矩阵的每行同时加上一个常数 C. 效益矩阵的每行同时减去一个常数 D. 效益矩阵乘以一个常数 【答案】D
【解析】效益矩阵乘以一个常数相当于系数矩阵的某行或某列乘以一个常数，这相当于目标函数中的部分系 数乘以一个常数，而目标函数整体乘以一个系数，显然会影响求解结果。 3． 关于对偶问题，下列叙述错误的有（ ）
A. 根据对偶问题的性质, 当原问题为无解时, 其对偶问题无可行解; 反之当对偶问题无可行解, 其原问题具有无界解。
B. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解。
C. 己知y 飞为线性规划的对偶问题的最优解，若y*j>0，说明在最优生产计划中第j 种资源己完全耗尽
D. 若某种资源的影子价格等于k ，在其他条件不变的情况下，当种资源增加5个单位时，相应的目标函 数只讲增大sk 【答案】A
【解析】当原问题（对偶问题）无可行解时，对偶问题（原问题）或具有无界解或无可行解。 4． 在产销平衡运输问题中，设产地有m 个，销地有n 个。如果用最小元素法求最优解，那么基变量的个数 为（ ）。 A. 不能大于（m+n-1） B. 不能小于（m+n-l） C. 等于（m+n-l） D. 不确定
【答案】A
【解析】在运输问题中，其自变量的个数是m ×n ，约束方程有m+n个，但是对于产销平衡问题，有以下关系式存在:
。故，模型最多只有m+n﹣1个独立方程，由
此得运输问题最多有m+n﹣1个基变量。当出现退化解时，基变量小于m+n﹣1个。
二、填空题
5． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。 【答案】
，极大化
【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为6． 无向连通图G 是欧拉图的充要条件是___。 【答案】G 中无奇点
7． 决策问题的三个基本要素是:____和____。 【答案】策略、事件、事件的结果
8． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_。 【答案】
【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。
三、证明题
9． 现有一个线性规划问题（P 1）:
, 其对偶问题的最优解为Y*=（y1, y2, y3, …ym ）
另有一线性规划（P 2）:
【答案】问题（P 2）的对偶问题为:
问题（P 2）的对偶问题为:
其中，d=（d 1, d 2, ...d 3）T 。 求证:
易见，问题（P 1）的对偶问题与问题（P 2）的对偶问题具有相同的约束条件，从而，问题（P 1）的对偶问 题的最优解
一定是问题（P 2）的对偶问题的可行解。
令问题（P 2）的对偶问题的最优解为
，则:
。
因为原问题与对偶问题的最优值相等，所以
型， 试证:
【答案】由题设知
并说明上式左右两端的概率意义。
10．车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模
一个周期T c 等于发生故障的机器在系统中的逗留时间W s
加上机连续正常工作时间
为 服务台繁忙的概率。服务台繁忙的概率也为
11．设G=（V ，E ）是一个简单圈，令证明:（l ）若（2）若
，则G 必有圈； ，则G 必有包含至少
条边的圈。
，假设
，所以（称
。
为G 的最小次）。
，
则
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若的次至少为
，设与，也至少与
对应的点为v k ，则v k
必与个端点相连。如果v k 与v i
这
个端点相连。由（l ）的结论知，G
个端点不构成圈，那么在端
条边的圈。
v k 至少与这中必有圈（由于对圈中的连通图而言，点处必向外延伸（因为最小次为另一端点，对该圈而言，边数大于
个端点构成圈）。
， 不与其中某点相连，必与其外某点相连）经连通链而到
条，故G 必定 是包含不少于占
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
12．对于M/M/1/∞/∞模型，在先到先服务情况下，试证明:
顾客排队等待时间分布的概率密度是
，并根据该式求等待时间的期望值
为在统计平衡 下顾客的等待时间，则
由a n 的定义，得
，于是有
。
，【答案】令N ’为在统计平衡下一个顾客到达时刻看到系统中已有的顾客数（不包括此顾客）
由定理知，对任何一个输入为最简单流的单服务台或多服务台的等待制排队系统，恒有