2017年南京农业大学1210运筹学复试实战预测五套卷
● 摘要
一、简答题
1． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
2． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、计算题
3． 求如图所示的网络最小费用最大流，每条弧旁的数字为
。
图
【答案】给网络中的中间点加上名称，如图所示。 （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 的最 短路，故
为网络的最小费用最大流。其最大流量为
，而最小费用为
（货币单位）。
图
4． 一辆货车的有效载重量是20吨，载货有效空间是7×2.5×2m 。现有六件货物可供选择运输，每件货物 的重量、体积及收入如表所示。
表
另外，在货物4和5中优先运货物4，货物2和3不能混装，怎样安排货物运输使收入最大，建立数学模型， 说明是什么模型，可用什么方法求解（注:不要求求解）。
【答案】由题意建立数字模型如下:
相关内容
相关标签