2016年西安邮电大学理学院812运筹学考研冲刺密押卷及答案
● 摘要
一、选择题
1． 在产销平衡运输问题中，设产地有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个。
2． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。
A. 在最后的解中，松弛变量必须为0，人工变量不必为0
B. 在最后的解中，松弛变量不必为0，人工变量必须为0
C. 在最后的解中，松弛变量和人工变量都必须为0
D. 在最后的解中，松弛变量和人工变量都不必为0
【答案】B
【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有解，所有最后的解中人工变量必须为0。
3． 若是否采用j 项目的0--1变量为x ，那么j 个项目中至多只能选择一个项目的约束方程为（ ）。
D. 无法表示
【答案】C
【解析】A 表示的是至少选择一个项目，不符合; B 表示的是只能选择一个项目。
二、填空题
4． 若x 为某极大化线性规划问题的一个基可行解，用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。 【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
5． 现有m 个约束条件，若某模型要求在这m 个条件中取”个条件作为约束，用，1变量来实现 该问题的约束条件组为:_。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
6． 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12，则该问题的第1个约束条件的右端常数项的对偶价格为:_____。
【答案】-12
【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。
7． 流f 为可行流必须满足___条件和___条件。
【答案】容量限制条件和平衡条件
【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。
三、证明题
8． 己知九个人v 1，v 2，…，v 9中v 1和两个人握过手，v 2和v 3各和四个人握过手，v 4，v 5，v 6，v 7各和五个人握过手，v 8，v 9各和六个人握过手，证明这九个人一定可以找出三人互相握过手。
【答案】该问题可表述为一个包含9个点（每个人代表一个点）的图的问题。依题意知 d （v l ）=2，d （v 2）=d（v 3）=4，d （v 4）=d（v 5）=d（v 6）=d（v 7）=5，d （v 8）=d（v 9）=6 其中，边v i ，v j 〕代表v i 和v j 握过手。对于v 9，因为d （v 9）=6，所以v 4，v 5，v 6，v 7中至少有两
个点与v 9之间 存在连线，设该两点为v 4和v 5。假设与v 4和与v 9相连的其他五点之间无边，
则
，与已知的 d （v 4）=5相矛盾，故假设不成立。即v 4与上述五点间必存在至少
两条边，设其中一点为v k ，则v k ，v 4，v 9两两相连，即存在三人之间互相握过手。
9． . 令
试证
【答案
】为一组A 共轭向量，它们必线性无关。
则，A 为为一组A 共轭向量（假定为列向量）对称正定矩阵，
使得。 用左乘上式，并且由共轭关系可知：
令
由
知BA=E，所以。
故得证。
10．设线性规划问题1是
（）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证
【答案】问题1的矩阵表示为
相关内容
相关标签