2016年南京大学859系统分析与集成专业基础之《运筹学教程》考研导师圈定必考题汇编及答案
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 考虑两个企业的资源整合问题。如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生 产要素进行重组，然后再统筹生产带来的收益高。因此，资产重组，往往能够带来“双赢”的格局，企业自身也 希望通过合并，做大做强。问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。请谈谈你的设想，用以协调 其中可能出现的问题（不超过300字，可用符号表述你的想法）?
【答案】让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。如果z 1+z2≦z 成之，则将，按照z 1、z 2的比例进行分配。这样的分配方式，两个企业说真话，合作后的额外收益z-（z 1+z2）是一个均衡策略。
3． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
若
4． 试写出标准指派问题的线性规划问题。 【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
二、计算题
5． 某整数规划模型如下:
其最优解为x=（18/7，19/7）。试用分枝定界法写出后续的两个分枝模型。 【答案】选择x l =18/7进行分支，问题B
l
则得问题B l ，B 2
T
问题B
l
6． 某农场考虑是否提早种植某种作物的决策问题，如果提早种，又不遇霜冻，则收入为45元；如遇霜冻，则收入仅为10万元，遇霜冻的概率为0.4。如不提早种，又不遇霜冻，则收入为35万元；即使遇霜冻，受灾也轻，收入为25万元，遇霜冻的概率为0. 2，己知:
（1）该农场的决策者认为:“以50%的机会每45万元，50%的机会得10万元”和“稳获35万元”二者对其来说没有差别；
（2）该农场的决策者认为:“以50%的机会得45万元，50%的机会得35万元”和“稳获40万元”二者对其来说没有差别；
（3）该农场的决策者认为:“以50%的机会得35万元，50%的机会得10万元”和“稳获25万元”二者对其来说没有差别。 问题如下:
[1]说明该决策者对风险的态度，按期望效用最大的原则，该决策者应做何种决策? [2]期望收益最大的原则，该决策者又应做何种决策?
【答案】[1]将最高收益45万元的效用定为10，记为U （45）=10。把最低收益值10万元的效用定为0，记为U （10）=0。 则决策者对风险的态度可以表示为:
令提早种的期望效用为E 1，不提早种的期望效用为E 2。则
E 2 > E1，所以，决策者的决策应为不提早种。
[2]令提早种的期望收益为E 1，不提早种的期望收益为E 2 。
E 2 > E1，所以，决策者的决策应为不提早种。 7． 利用图解法求解下列矩阵对策，其中A 为
【答案】（l ）在矩阵中，由于第l 行优超于第2行，故可划去第2行，得到新的赢得矩阵为
设局中人‖的混合策略为别是局中人‖采取混合策略且对策的值显然为AB 。
了，由图可知，直线在任一点上的纵坐标分
时的支付。根据最不利当中选取最有利的原则，局中人‖的最
优选择，就是如何确定y ，以使三个纵坐标值中的最大值尽可能地小。由图可知，应选择y=OA，