2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案
● 摘要
目录
2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案（一） ... 2
2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案（二） ... 9 2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案（三） . 17 2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案（四） . 23 2016年首都经济贸易大学903管理学综合之《运筹学教程》考研内部复习题及答案（五） . 32
第 1 页，共 39 页
一、计算题
1． 某公司在某地区采矿，拟建采矿点共有五个K 1、K 2、K 3、K 4和K 5，其相互之间距离如图所示。 该公司拟建四个冶炼车间F I 、F 2、F 3和F 4，其相互之间距离如图所示。所有采矿点所采的矿石都要通过公路运 往冶炼车间。采矿点K5与主干公路相连。其到两个公路连接点G l 和G 2的距离分别为15公里、8公里。冶炼车间F 4与主干公路相连，其到两个连接点G 3和G 4的距离分别为5公里、4公里。四个公路连接点G I 、G 2、G 3和 G 4之间都己经有公司相连，其距离如图所示。由于修建公路的费用非常巨大，所以公路建设方案必须保证建设 线路最短。同时，为了节省运费，矿石运距要尽可能缩短。请用图论的方法找出五个拟建采矿点之间的公路线路 建设最优方案，找出四个拟建冶炼车间之间的公路线建设最优方案，并指出矿石如何进行调运。
图
【答案】五个拟建采矿点之间，寻找最优建设方案，即寻求各点至ks 的最短距离。 采用逐次逼近法计算根据方程
开始令
则有：
第 2 页，共 39 页 ，即k 5与k j 无点时即直接连接时的距离。
所以最优建设方案如图所示
图
最短建设路线1.1km.
同理，可得四个拟建冶炼车间之间的公路线建设最优方案是:
图
建设最短公路线0.8+0.6+0.7=2.1km 同理可知，从K5到F4的最短距离为K5一一G2一一G4一一F4 L=8+90+8=l06km
2． 某产品从仓库A i （i=1， 2, 3）运往市场B j （j=1， 2, 3，4） 销售，已知各仓库的可供应量、各市场的需求量及从A 1仓库到B 1市场路径上的容量如表所示（表中数字0表示两点之
，请制定一个调运方案使从各仓库调运产品总量最多。 间无直接通路）
表
【答案】该问题是求最大流问题，由题得网络图，其中S 、D 是虚拟开始和结束点，各路径最大容量如图所示，初始流量为0:
第 3 页，共 39 页
图
（1）标号过程
①首先给S 标号（0,
，同理，）, 检查S , 在弧（S , A1）上，F SA1< CSA1，则给A 1标号（S , 20）
，A 3 （S , 100） 标号A 2（S , 20）
②任选一点A 1进行检查，在弧（A 1 , B1）上，F A1B1< CA1B1，则给B 1标号（A 1, 20）
，这样找到了一条增广链，S- A1- ③检查B 1 ，在弧（B l , D ）上，F B1D < CB1D ，则给D 标号（B l , 20）
B 1-D
（2）调整过程，由（1）知，=20, 得新的可行流量图，如下图所示。
图
依据上述方法，重复标号及调整过程，直到不存在增广链为止，最终得最大流量图，如下图所示。
第 4 页，共 39 页