2016年五邑大学经济管理学院812运筹学考研强化班模拟试题及答案
● 摘要
一、证明题
1． 对于M/M/1/m/m模型，试证【答案】因为
，并给与直观解释。
。
若L s 表示系统中平均出故障的机器数，则系统外的机器平均数应为m 一L s 。于是，系统的有效到达率，即 m 台机器单位时间内实际发生故障的平均数为因此，有
2． 设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 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
3． 现有一个线性规划问题（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）的对偶问题的可行解。 ，则:
。
。试证:若
关于Q 共扼
分别
在两条平行
因为原问题与对偶问题的最优值相等，所以
4． 设
是正定二次函数
于方向P 的直线上的极小点，则方向p 与方向【答案】因为则有从而又由于则有
分别是f （x ）在两条平行于方向P 的直线上的极小点， ，
二、填空题
5． 无向连通图G 是欧拉图的充要条件是___。 【答案】G 中无奇点
6． 在灵敏度分析时, 当LP 某系数发生变化使原最优单纯形表中的解为该LP 的一个正侧解，但不是可行解, 为求新的最优解, 处理办法是:____。 【答案】对偶单纯形法
相关内容
相关标签