2016年哈尔滨工业大学深圳研究生院850运筹学考研冲刺密押卷及答案
● 摘要
一、简答题
1． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记
2． 简述常用的不确定型决策准则。
【答案】不确定性决策是指决策者对将发生结果的概率一无所知，只能凭决策者的主观倾向进行决策，适用于对 概率判断缺乏信心，对事情做出简单的估计。。不确定性决策由决策者的主观态度不同基本可分为四种准则:悲 观主义准则、乐观主义准则、等可能性准则、最小机会准则。 （l ）悲观主义决策准则:行中取min ，再取max 。 （2）乐观主义决策准则:行中取max ，再取max 。
（3）等可能性准则:先求各策略的收益期望值，再从中取max 。 （4）最小机会损失准则:
机会损失矩阵:每一列的值为列中最大的数分别减去其他的数（自己则变为0，其他的值全大于等，即
于0）
（5）折衷主义决策准则
其中a （收益值。 然后选择
3． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。 【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
（2）平衡条件 对于中间点，流出量=流入量，即对每个
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
。
）为乐观系数，，。分别表示第i 个策略可能得到的最大收益值与最小
4． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整 但增加线性约束条件数这一条件，（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是面（不见得一次就找到）问题的最优解。
二、计算题
5． 某工程公司在未来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人做第三项任务。
6． 求下述线性规划问题目标函数z 的上界
其中
【答案】（l ）要求z 的上界
和下界
，则c 1，c 2，b l ，b 2应取其最大值; all ，a 12，a 21，a 22应取其最小值，
此时，得到的线性规划问题为
在上述问题的第一个约束条件中加入松弛变量x 3，第二个约束条件左右两边同时除以2再加入松弛变量x 4，得到该线性规划问题的标准型
单纯形法的计算过程如表所示。
表
解得最优解（2）要求z 的下界得到的线性规划问题为
，目标函数z 的上界=21。
，则c l ，c 2，b 1，b 2应取其最小值; a 11，a 12，a 21，a 22应取其最大值，此时，
在上述问题的第一个约束条件中加入松弛变量x 3，第二个约束条件左右两边同时除以2再加入松