2016年南京大学859系统分析与集成专业基础之《运筹学教程》考研内部复习题及答案
● 摘要
一、简答题
1． 简述割平面法的基本思想。
【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整
但增加线性约束条件数这一条件，（用几何术语，称为割平面）使得由原可行域中切割掉一部分，
这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平
，使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是面（不见得一次就找到）
问题的最优解。
2． 试写出标准指派问题的线性规划问题。 【答案】
A ij 表示工作人员i 做工作j 时的工作效益
则得线性规划模型为:
二、计算题
3． 某厂考虑生产甲、乙两种产品，根据过去市场需求统计数据如表所示。（1）用最大可能性法进行决策。（2）用期望值法进行决策并进行灵敏度分析，求出转折概率。
表
【答案】（1），即出现旺季的可能性最大，在旺季情况下，生产乙产品
比生产甲产品的收益大， 所以采用最大可能性法进行决策的结果为生产乙产品。
（2）①采用期望值法进行决策。生产甲产品的期望收益为4*0.7+3*0.3=3.7; 生产乙产品的期望收益为 7*0.7+2*0.3=5.5。因为生产乙产品比生产甲产品的期望收益大，所以按期望值法进行决策为乙方案。
②灵敏度分析。设出现旺季的概率为a ，相应的，出现淡季的概率为1-α，当生产甲、乙两种产品的 期望值相等时，
即
能达到最优。
4． 求如图所示的网络最小费用最大流，每条弧旁的数字为。
。求得转折概率为α=0.25。即当α>0.25时，生产乙产品是最优方案; 当α<0.25时，生产甲产品是最优方案; 当α=0.25时，生产任何一种产品都
图
【答案】给网络中的中间点加上名称，如图所示。
（l ）取为初始可行流。
（2）依照下列方法构造有向赋权图，如图所示。
并求出从v s 到v t 的最短路（v s ，
v 2，v 4，v t ），如图所示（双箭头即为最短路）。
图
（3）在原网络D 中，与这条最短路相应的增广链为
（4），如图所示。
。
图
（5）构造有问赋权图，井求出从v s 到v t 的最短路最短路）。
，如图所示（其双箭头即为
图
（6）在原网络中，与这条最短路相应的增广链为
（7）在上调整流量，令，得，如图所示。
。
图
（8）构造有向赋权图，并求出从v s 到v t 的最短路，如图所示。因为图己不存在从v s 到v t 的最 短路，故币单位）。 为网络的最小费用最大流。其最大流量为，而最小费用为（货