2016年东华大学旭日工商管理学院802运筹学考研必备复习题库及答案
● 摘要
一、选择题
1． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。 A. 唯一的最优解 B. 一个以上的最优解 C. 目标函数无界 D. 没有可行解 【答案】AB
【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。 2． 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。 A. 非负的 B. 大于零 C. 无约束 D. 非零常数 【答案】A
【解析】系数矩阵中的系数表示的是费用、成本、时间等。
3． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。 A. 松弛变量 B. 多余变量 C. 闭回路 D. 圈 【答案】C
【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。
4． 网络计划中的某工序（i ，j ），估计的最乐观时间为a ，最可能时间为m ，最保守时间为b ，则该工序的 期望工时和方差可以按下面（ ）计算。
【答案】A
二、填空题
5． 若对偶问题为无界解，则原问题:_____。 【答案】无可行解
【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数有可行解。
6． 图G=（V ，E ）有生成树的充分必要条件是___。 【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。 7． 最速下降法的搜索方向_。 牛顿法的搜索方向为_。 拟牛顿法的搜索方向为_。 【答案】
【解析】最速下降法:
可
时，下降最快。
牛顿法：正定二次函
数
即搜索方向是
拟牛顿法
：
（单位阵）
8． 网络中如果树的节点个数为z ，则边的个数为___。 【答案】z-l
【解析】由树的性质可知，树的边数=数的节点数一1
若
是最优点，
则以得出
，
当
无界，即无限小，则z 无解，即没
三、证明题
9． 设线性规划问题解。
【答案】其对偶问题为
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
1
设是原问题的最优解，则其对应的基矩阵B 必存在
，由此得
，即可得，
这时Y 是对偶问题的可行解，它使由于原问题的最优解
，使目标函数取值
，即是对偶
问题的最优解，因此单纯形乘子证明:（l ）若（2）若
，是对偶问题的最优解。
（称
条边的圈。
，假设
为G 的最小次）。
10．设G=（V ，E ）是一个简单圈，令
，则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 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。 11．设
是正定二次函数
。试证:若
关于Q 共扼
分别
在两条平行
于方向P 的直线上的极小点，则方向p 与方向【答案】因为则有从而又由于
分别是f （x ）在两条平行于方向P 的直线上的极小点， ，
相关内容
相关标签