2016年厦门大学管理科学系809运筹学考研冲刺模拟题及答案
● 摘要
一、计算题
1． 绘制表所示的网络图，并用图上作业法计算时间参数，确定关键路线。
表
【答案】
图
表
关键工序为：A ，F ，I ，N ，O ，Q 关键路线是
2． 某银行正在为其全职和兼职出纳员制定一个有效的工作时间表，时间表必须满足包括足够顾客服务、职员体息等在内的银行运转条件。表给出的是每周一银行从9:00到17:00所需的出纳员人数。
表
全职员上从整点开始工作且连续工作4小时，随后是l 小时午餐时间，然后是2小时的班; 兼职员
，工从整点 开始做一个4小时班; 全职员工成本是每小时10元（60元/天）兼职员工成本是每小时
6元（24元/天）:银行要求，每时段至少要有一个全职员工:如何安排员工作息既满足要求又使成本最小。试建立该问题的数学模型。
【答案】根据题意，全职人员只有从时间编号为1、2的时间段开始工作，兼职人员可以从时间编号为1、2、3、 4、5的时间段开始工作。令从从时间编号为1、2的时间段开始工作的全职人员数分别为x ，、x :，从时间编号 为1、2、3、4、5的时间段开始工作的兼职人员数分别为y 1、y 2、y 3、y 4、y 5。则可建立如下数学模型:
二、证明题
3． 设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 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
4． 证明:矩阵对策G={S1，S 2; A}在混合策略意义下有解的充要条件是:存在
为函数以的一个鞍点，即对一切
【答案】（l ）先证明充分性
对任意X , Y 均有，故得出
，
使，有