2017年云南财经大学运筹学复试实战预测五套卷
● 摘要
一、简答题
1． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界; 。分支定界法就是将B 的可行域分成子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。
2． 说明本书所述货运车辆优化调度算法的原理和求解步骤，并绘出求解过程框图。请简要回答以下问题。
（1）若有两种车型的车可用，书中提出的模型应怎样修改? 在书中所提算法的启发下，试拟定出一套求解的迭代步骤。
（2）你认为应如何将书中提出的模型和算法推广到多目标的情形。
【答案】①货运车辆优化调度算法的原理:最小费用最大流原理。求解步骤为:a. 仅考虑重载点，运用表上作业法求出最优解作为原问题的可行解; b. 进行解的扩展和解的收缩，直至得到可接受的可行解; c. 以该可接受的可行解为依据确定初始行车线路; d. 根据具体约束条件进行调整，直至得到最优行车路线。求解过程框图如图所示。
图
（2）修改后的迭代算法即神经网络（neural networks）算法。
①建立结合矩阵:将车辆经过的点包括源点看成神经网络的结点，即神经元，令神经元数目为Ni 神经元 和j 神经元的结合权值为，j 神经元的输出为r j 。
②将车辆调度的各种约束条件转化为约束能量函数为E 约。
③神经网络计算:令时刻t 神经元i 的输出为r i （t ），且r i （t ）只能取0或1，令神经元i 的阈值为Q i ，则输出能量
为
，其中，因此总的能量函数
为，则该网络相对处于稳定状态。由于如
果，且E 有界，系统必
趋向一个比较好的稳定状态，再把此稳定状态时r i （t ） 形成换位阵中元素为l 的结点连接起来，形成所求的最满意车辆调度线路。
④根据所形成的最满意线路来选择车辆调度方案。
（3）推广到多目标情形:车辆优化的目标函数可以有很多个，如总运费最小，司机总的驾驶时间最短，车 辆满载行驶的时间最长等; 而约束条件，如路径的最大输入输出流、车载量、发车和收车约束等。也可以加入惩 罚算子将约束条件转化为惩罚函数，利用多目标方法进行求解。
二、计算题
3． 某城市的消防总部将全市划分为11个防火区，设有4个消防（救火）站。图表示各防火区域与消防 站的位置，其中①②③④表示消防站，1、2、…、11表示防火区域。根据历史资料证实，各消防站可在事先规定的允许时间内对所负责的地区的火灾予以消灭。图中虚线即表示各地区由哪个消防站负责（没有虚线连接，就 表示不负责）。现在总部提出:可否减少消防站的数目，仍能同样负责各地区的防火任务? 如果可以，应当关闭哪个?
图
提示:对每个防火站定义一个0-1变量x j ，令
然后对每个防火区域列一个约束条件。
【答案】定义：
于是，可建立如下数学模型：
由条件②，④，⑨可判定x l =x3=x4=1，分析可知（l ，0，1，1）为问题的一个可行解，此时z=3。假设可以减少一个消防站，即增加约束条件
T 有（l ，0，1，1）为可 行解，所以可关闭消防站②。 T 。通过单纯形法计算可知，只