2016年西安邮电大学理学院812运筹学考研内部复习题及答案
● 摘要
一、选择题
1． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。 A. 唯一的最优解 B. 一个以上的最优解 C. 目标函数无界 D. 没有可行解 【答案】AB
【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。 2． 根据对偶解的经济含义，若天然气资源是我国的一种稀缺能源资源，其影子价格必然是（ ）。 A. 不能确定 B.<0 C.=0 D.>0
【答案】D
【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系 统内越稀缺，增加该资源的供应量对系统目标函数值贡献也越大。天然气是资源是一种稀缺能源资源，其影子价 格必然大于0。
3． 在产销平衡运输问题中，设产地有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个。
二、填空题
4． 现有m 个约束条件
，若某模型要求在这m 个条件中取”个条件作为约束，用，1
变量来实现 该问题的约束条件组为:_。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
5． 图G=（V ，E ）有生成树的充分必要条件是___。 【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。 6． 流f 为可行流必须满足___条件和___条件。 【答案】容量限制条件和平衡条件
【解析】在运输网络的实际问题中可以看出，对于流有两个明显的要求:一是每个弧上的流量不能超过该弧 的最大通过能力（即弧的容量）; 二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运进这点的 产品总量之差，是这点的净输出量，简称为是这一点的流量; 由于中间点只起转运作用，所以中间点的流量必为 零。易而发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。
7． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。 【答案】
，极大化
【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为
三、证明题
8． 设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 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
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）的对偶问题的最优解为10．设线性规划问题1是
一定是问题（P 2）的对偶问题的可行解。 ，则:
。
因为原问题与对偶问题的最优值相等，所以
（
）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证【答案】问题1的矩阵表示为