2018年沈阳理工大学经济管理学院818运筹学考研基础五套测试题
● 摘要
一、简答题
1． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。
二、计算题
2． 已知矩阵对策
的解为
对策的解，其赢得矩阵A 分别为
【答案】（l ）因为
所以可由定理7可知
（2）因为
，对策值为24/l3。求下列矩阵
所以。
3． 某人在未来四年中需要一辆汽车代步，一辆新车的购买价格为36000元，每年的使用和维护费用如表所示。在每年末，他可选择继续使用现有汽车或再买新车，若再买新车，他可将现有旧车折价出售，出售价格如 表所示。
（l ）试建立求解此四年间最佳购车计划的图论模型;
（2）试用图论方法确定什么样的购车策略（每年末继续使用旧车还是购买新车）才能使总费用最少? 该费 用为多少?
表 购车数据（单位：元）
【答案】
（1）构建图论模型，如图所示。
图
（2）最优方案为第二年末换新车，这样费用最少，具体为31500x2=63000元。
4． 某工程公司在未来L4月份内需完成三项工程:第一项工程的工期为1-3月份，总计需劳动力80人月; 第二项工程的工期为1-4月份，总计需劳动力100人月; 第三项工程的工期为3一4月份，总计需劳动力120人月。 该公司每月可用劳力为80人，但任一项工程上投入的劳动力任一月内不准超过印人。问该工程公司能否按期完 成上述三项工程任务，应如何安排劳力? （请将该问题归结为网络最大流问题求解）
【答案】可以构建图所示的网络图（弧上数字为最大流量）。
图
其中，结点1、2、3、4分别代表l 、2、3、4月份，结点5、6、7分别代表第一、二、三项工程。通过标号与调整，得到的最大流如图所示。
图
该最大流问题有多重最优解，上图仅给出一种。
所以该公司能按期完成上述三项工程任务，安排劳力的方案可以为:1月份，安排60人做第一项任务、20 人做第二项任务; 2月份，安排60人做第二项任务; 3月份，安排60人做第三项任务、20人做第一项任务; 4 月份，安排60人做第四项任务、20人做第三项任务。
5． 解下列0- 1规划问题。
（2）
T 【答案】 （1）通过观察可知（0, 0, 1）为可行解，相应的z=2, 故增加约束条件