2018年天津财经大学管理科学与工程809管理科学与工程综合之运筹学考研核心题库
● 摘要
一、选择题
1． 动态规划是解决（ ）的一种数学方法。
A. 单阶段决策过程最优化 B. 多目标决策过程最优化 C. 多阶段决策过程最优化 D. 位目标决策过程最优化
【答案】C
【解析】动态规则是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法 2． 如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ ）。
A.d 十>0; B.d 十=0; C.d 一=0; D.d 十>0且d 一>0
【答案】B
【解析】实际实现值不超过目标值，即. A. 效益矩阵的每行同时乘以一个常数 B. 效益矩阵的每行同时加上一个常数 C. 效益矩阵的每行同时减去一个常数 D. 效益矩阵乘以一个常数
【答案】D
【解析】效益矩阵乘以一个常数相当于系数矩阵的某行或某列乘以一个常数，这相当于目标函数中的部分系 数乘以一个常数，而目标函数整体乘以一个系数，显然会影响求解结果。 4． 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。
A. 非负的 B. 大于零 C. 无约束
第 2 页，共 28 页
，根据，可知
3． 用匈牙利法求解指派问题时，不可以进行的操作是（ ）。
D. 非零常数
【答案】A
【解析】系数矩阵中的系数表示的是费用、成本、时间等。
二、判断题
5． 如果线性规划问题有最优解，则它一定是基可行解。（ ）
【答案】√
【解析】基解且可行才有可能是最优解。 6． 对自由变量x k ，
通常令不可能同时出现
【答案】√
【解析】因为不可能同时出现
，其中
。（ ）
在用单纯型法求得的最优解中
，所以。
不能同时为基变量，则至少有一个为0。故最优解中
7． 如果线性规划问题无最优解，则它也一定没有基可行解。（ ）
【答案】×
【解析】当问题的解为为无界时，此时该规划问题无最优解，但存在基可行解。
8． 如果图T 是树，则T 中一定存在两个顶点，它们之间存在两条不同的链。（ ）
【答案】×
【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。
9． 对于一个有n 个变量，m 个约束方程的标准线性规划SLP ，其基可行解的数目恰好是个。（ ）
【答案】×
【解析】其基解的个数最多是个，且一般情况下，基可行解的数目小于基解的个数。
三、证明题
10．设G=（V ，E ）是一个简单圈，令
证明:（l ）若（2）若
，则G 必有圈； ，则G 必有包含至少
条边的圈。
（称
为G 的最小次）。
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。
【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若假设G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
第 3 页，共 28 页
，
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若
，设与
对应的点为v k ，则v k 必与
，也至少与
个端点相连。由（l ）的结论知，
个端点构成圈）
。
G 中必有圈（由于对圈中的连通图而言，v k 至少与
这
的次至少为
个端点不构成圈，那么在端点处必向外延伸（因为最小次为外某点相连）经连通链而到另一端点，对该圈而言，边数大于少于占
条边的圈。
个端点相连。如果v k 与v i 这
， 不与其中某点相连，必与其
条，故G 必定 是包含不
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
11．己知九个人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两两相连，即存在三人之间互相握过手。 12．设线性规划问题解。
【答案】其对偶问题为设
，
即可得
，由此得
，即是
1
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
是原问题的最优解，则其对应的基矩阵B
必存在，这时Y 是对偶问题的可行解，它使
由于原问题的最优解13．证明下列定理:
，使目标函数取值
对偶问题的最优解，因此单纯形乘子
（1）设有两个矩阵对策，
，是对偶问题的最优解。
，其中
，L 为任一常数，则有
（2）设有两个矩阵对策，
第 4 页，共 28 页
， 。（定理7）
，其中a>0为任一常数。则
相关内容
相关标签