2017年华中科技大学管理学院885运筹学(一)[专业硕士]考研冲刺密押题
● 摘要
一、简答题
1． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。
2． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点的割平面（不见得一次就找到）
恰好是问题的最优解。
3． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
第 2 页，共 25 页
按如下规则:
4． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐，即可求出目标规划的满意解。 次求解k 个线性规划（k 为优先级的个数）
二、证明题
5． 证明:（1）若
（2）若
和
和
是对策G 的两个解，则是对策G 的两个解，则是G 的解，所以
①
同理，因为
是G 的解，所以
②
由不等式①可知
③
由不等式②可知
由不等式③与不等式④可知
（2）由（1）证明过程中不等式③和不等式④可知即也是解。
6． 设G=（V ，E ）是一个简单圈，令
证明:（l ）若（2）若
，则G 必有圈； ，则G 必有包含至少
条边的圈。
，
（称
为G 的最小次）。 ，
故
④
，即可知
。
和
。
也是对策G 的解。
【答案】（1）因为
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若假设G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若
，设与
对应的点为v k ，则v k 必与
，也至少与
第 3 页，共 25 页
个端点相连。由（l ）的结论知，
个端点构成圈）
。
G 中必有圈（由于对圈中的连通图而言，v k 至少与
这
的次至少为
个端点相连。如果v k 与v i 这
个端点不构成圈，那么在端点处必向外延伸（因为最小次为外某点相连）经连通链而到另一端点，对该圈而言，边数大于少于占
条边的圈。
， 不与其中某点相连，必与其
条，故G 必定 是包含不
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
7． 称顾客为等待所费时间与服务时间之比为顾客损失率，用R 表示。
（l ）试证:对于M/M/1模型，（2）在上题中，设
不变而
。
是可控制的，试定
使顾客损失率小于4。
证毕。
时，顾客损失率小于4。
，
使
【答案】（l ）对于M/M/1模型, （2）由
，得
。由定义，有
，所以当
8． 证明:矩阵对策G={S1，S 2; A}在混合策略意义下有解的充要条件是:存在
为函数以
的一个鞍点，即对一切
【答案】（l ）先证明充分性 对任意X , Y 均有
，故得出
又所以，
另一方便，对任何X ，Y 有
②
由不等式①、②
，
（2）再证必要性。设有X*，Y*，使得
则由
，有
第 4 页，共 25 页
，有
① ，所以得
相关内容
相关标签