第十届大学生科技活动周 “数学建模竞赛”（理科组）论文
参赛试题 A B √ （在所选题目上打勾） 参赛编号 （竞赛组委会填写）
题 目： 企业和仓库的调运问题 二级学院： 数学与信息科学学院 专 业： 信息与计算科学 班 级： 2010级4班 姓 名： **** ** ** 学 号：*********** ************ ********** 联系电话： ***********
二〇一二年四月
企业和仓库的物资调运问题
摘 要
如今物资调运问题普遍存在于生活的每个角落，利用有效的方法解决该问题会给企业带来许多便利和可观的利益。本文根据题中所给数据确定了物资需求点和各地点的需求量，首先作出了该地区公路交通网的数学模型[1]，然后根据图论的知识求权值最小的调运路线，再运用LINDO软件求出了最优的调运方案，并得到20天后各仓库的库存量。最后在问题四中将中断路段的权值改为路程得到改进模型，这对突遇自然灾害时的物资急运十分有意义。
针对问题一，本文将附件2中的交通网络图抽象为数学中的无向图，把公路交汇点作为无向图的顶点，把每条路的运费作为无向图每条边的权值，这样就得到一个带权值的交通网状图。
针对问题二，在问题一得到的交通网基础上我们运用破圈法将得到任意两个顶点之间的最优路线，本题要求重点保护国家级储备库，因此模型的建立分为三个阶段：第一阶段，从3个企业和仓库3，5向储备库1，2调运物资，以运输费用最小为目标，达到各储备库的预测库存；第二阶段，从3个企业向仓库1，2，4，6，7，8调运该物资，以时间最少、费用最低为目标得到各企业每天的调运量，达到各仓库的预测库存；第三阶段，从3个企业继续向10个仓库调运物资，达到各仓库的最大库存。在LINDO软件中建立目标函数和约束条件，求出最优解，即为本题最佳的调运方案。最后求得达到预测库存时的运输总费用为353296元，总时间为13天。达到最大库存的运输总费用为765676元。
针对问题三，在问题二中我们求得达到预测库存的天数为13天，剩下的7天利用线性规划模型得到物资的调运方案，求出20天后各仓库的库存量分别为710百件、600百件、300百件、400百件、710百件、300百件、500百件、710百件，两个储备库的库存量为3470百件和2500百件。
针对问题四，遇到自然灾害造成紧急调运情况时，我们将问题二中以运费为权值改为以时间为权值，把总时间最少作为衡量标准建立模型，由于本文假设高等级公路和普通公路的运输速度相同，所以用路程代替时间作为权值，最后用类似问题二的模型建立目标函数和约束条件，运用LINDO软件求出最优的调运方案。
关键词: 图论 破圈法 LINDO 物资调运 线性规划模型
一、问题重述
物资调运不仅要合理选择运输工具还包括路线选择、特殊事项处理、最佳载重量等很多事项。我国地域辽阔、地形复杂、气候多变，各种自然灾害频频发生，所以建立一个合理实用的物资调运模型十分重要。
现已知某地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，各库库存及需求情况见附件1，其分布情况见附件2 。经核算该物资的运输成本为高等级公路2元/公里·百件，普通公路1.2元/公里·百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运。
现通过数学建模来完成以下问题：
（1）根据附件2提供的信息建立该地区公路交通网的数学模型。
（2）设计该物资合理的调运方案，包括调运量及调运路线，在重点保证国家级储备库的情况下，为给该地区有关部门作出科学决策提供依据。
（3）根据你的调运方案，20天后各库的库存量是多少？
（4）因山体滑坡等自然灾害下列路段交通中断，能否用问题二的模型解决紧急调运的问题，如果不能，请修改你的模型。
二、问题分析
2.1对问题一的分析
通过对附件2提供的交通网络结构的分析，要得到该地区公路交通网的数学模型，我们可以利用离散数学中图论[2]的知识把交通网络图抽象转化为数学中的无向图，本题有高等级公路和普通公路两种公路，题中告诉了每条公路的距离和两种公路单位距离的运费，因此我们可以算出每条公路的运费做为无向图中每条边的权值，把公路交汇点当做无向图的顶点。这样得到一个带权值的无向图，在选取路线时只需求出权值最小的边就是两个点之间运费最小的路线。 2.2对问题二的分析
本题要求设计该物资合理的调运方案，并且重点保证国家级储备库，即首先满足国家级储备库的预测库存。因此我们可以把物资调运分为三个阶段：
首先从企业1、2、3和仓库3、5向储备库1、2调运该物资，达到储备库的预测库存；然后再满足其他仓库的预测库存，3家企业边生产边向剩余各仓库运输物资；最后3家企业继续向10个仓库调运该物资，达到各库最大库存。
由问题一中得到的交通网根据图论知识中的破圈法得到权值和最小的调运线路。最后建立目标函数和约束条件，用LINDO软件求出最优解，即为最佳的调运方案。 2.3对问题三的分析
由于第二问中求出了调运模型，因此本题我们可以运用第二问中的模型得到20天后各仓库的库存量。 2.4对问题四的分析
山体滑坡导致路段中断时，运输物资不能从中断路段通过。因此在用破圈法求得每条最佳调运路线时我们首先要去掉中断路段，可以把本题中中断路段的权值改为无穷大，那么再利用问题二的模型就可以得出新的模型。
1
三、模型假设
1、假设运输时间不考虑，运输能力足够大；
2、假设公路交汇点27为储备库1，交汇点30为储备库2； 3、假设高等级公路和普通公路的运输速度相同； 4、假设不考虑除运输费用以外的其他费用； 5、假设无影响调运方案的意外情况出现；
6、在本文中我们没有考虑运输的限制及运输量对运费的影响
四、符号说明
符号 A，b，c 1，2…8
9 10 i j Cij Xij n MinZ Nj Pj Mj
符号的意义 企业1，企业2，企业3 仓库1，仓库2…仓库8
储备库1 储备库2 调出物资地 调入物资地 从i地运到j地的运费 从i地到j地的运输量
生产天数 最小总费用 各库的现有库存 各库的预测库存 各库的最大库存
2
Ri 企业每天的生产量
五、模型的建立与求解
5.1问题一
在附件2中一共有42个地点，因此我们构建一个由42个顶点组成的带权值的无向图，如图5-1，每条边的权值为Cij，Cij表示从i地运到j地的运费。
图5-1交通网1
其中，各顶点为公路交汇点，红色路线为高级公路，蓝色路线为普通公路，绿色数字为各边权值，权值表示该两点间运输每百件货物的费用。 各顶点与企业、物资仓库、储备库的关系如下三个表： 表5.1.1 储备库编号 储备库1 储备库2 交点编号 表5.1.2 企业编号 企业1 企业2 企业3 3
27 30