物资调运问题的优化模型

1、物资调运问题的优化模型肖凤莲涂礼才何三才摘要：在此问题中我们求各企业、物资仓库及国家级储备库之2 （生产企业，物资仓库及国家级储备库分布图）的分1），所得图是连通图，设为G V,E，各个边的权本题所说的是防洪抗涝物质调运问题。 间物资的运费每一百件最少的路线，把附件 布图转化为数学直观简图（见模型求解中图三、四、五。为相连两点每百件物资的运费。我们利用“破圈法”和“最短路”求任意企业、物资仓库及国家级 储备库两两之间及仓库与仓库之间的最优路线，显然我们建立的数学（简单图形）模型是可行的、 合理的。得出最优路线见表二、我们根据实际情况，在保证国家级储备库的情况下，采用就近原则，在此基础上建立线性

2、规划 模型（如下）：运用Lin go软件对我们所建立线性规划问题进行计算。再把天数为20带入上述线性规划，运用Lin go运用软件进行计算，可以得到 20天后各库的库 存量好下：仓库名仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库220天后库存量50060045035080030055060035502500由于汛期路段2627交通中断，中断路线改为企业1 2013储备库1,企业2640储 备库1,其他中断路段对物资运输的路线无影响。建立线性规划，运用 Lingo运用软件求解，其结 果见问题4的求解。此模型简单易懂，容易推广。运用了 LINGO数学软件，提高了计算的速度。解得的

3、结果符合实际。关键词：破圈法、最短路、线性规划模型、Lingo.、问题的重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经 常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要 工作。某地区为做好今年的防洪抗涝工作， 根据气象预报及历史经验，决定提前做好某种防洪抗涝 物资的储备。已知该地区有生产该物资的企业三家， 大小物资仓库八个，国家级储备库两个，各库库存及需 求情况见附件1,其分布情况见附件2。经核算该物资的运输成本为高等级公路 2元/公里？百件， 普通公路元/公里？百件，假设各企业、物资仓库及国家级储备库之间的物资可以

4、通过公路运输互相 调运。（1）请根据附件2提供的信息建立该地区公路交通网的数学模型。（2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家级储备库的情况 下，为给该地区有关部门做出科学决策提供依据。（3）根据你的调运方案，20天后各库的库存量是多少（4）如果汛期下列路段因洪水交通中断，能否用问题二的模型解决紧急调运的问题，如果不 能，请修改你的模型。中断路段：14 23，1125，2627，931二、模型的假设1、物资从各企业调运到每个仓库的运输时间不计，即运输能力足够大；2、在满足仓库和储备库的库存要求之下，我们可以任意的进行物资调运;3、调运过程无任何意外情况发生；4、企业之

5、间物资的生产互不影响；5、企业与企业不存在运输关系；6仓库与仓库、储备库与储备库之间权值相同；7、仓库与储备库之间可以相互运输。三、符号说明四、模型的分析和建立我们根据题目及附件1中的数据信息加以分析，把实际图形转化为数学图形，再根据图论知识， 将数学图放在图论中，进行假设与分析，从而建立了比较优化的数学模型。 我们分析得到：合理的 调运方案实际上就是在满足仓库、 储备库各自需求的前提下，要求总运费最少，因此建立了一个线 性规划模型。因为高等级公路和普通公路的路程价钱不同， 为了使计算过程简单化，我们结合高等 级公路和普通公路的路程价钱的比例关系将高等级公路路程转化为普通公路路程， 所以我们就

6、避免 了路程和价钱同时考虑的现象，从而我们就将价钱和里程的关系转化为单一的里程问题， 因此简化 了问题。所以我们需要求出企业与物资仓库之间的最短路 yj ,企业与国家级储备库之间的最短路yik，物资仓库与国家级储备库之间的最短路wik，物资仓库与物资仓库之间的最短路Wj，而最短路路线可以根据 附件2由图论中的“破圈法1”统计出来。我们的目的是在满足仓库、储备库各自的需求下，要求总运费最少，即可以转化为转移物资和路程的长度之积。首先我们只考虑的运输关系为：企业与物资仓库，企业与国家级储备库。建立目标函数1为:然后经过分析我们考虑到了物资仓库与国家级储备库还存在着运输关系，因此我们将目标函数1做了

7、进一步的修改，得到目标函数 2：综合上面的分析，最后我们得出了物资调运的线形规划模型：目标函数：约束条件：五、模型的求解我们由图论知识可以把题中给的 生产企业，物资仓库及国家级储备库分布图进行简化可以得以下的简图:结合上图，我们要找到 生产企业、 国家级储备库每两两之间的最短路， 用“破圈法”一一任取一个圈，从圈 权（图中为每两点间的距离）最大的 有两条或两条以上的边上的权都是最 任意的去掉其中一条）。在余下的图 个步骤，直至得到一个不含圈的图为 企业2到仓库1的方法如下：由图知：企业2到仓库1之间的路物资仓库及所以我们使 中去掉一条 边（但如果 大的边，则 中，重复这 止。我们求径有5条,此

8、图为连通图，但为了求他们之间的最短路，因此应去掉该图中的权（任意两点之间的距离） 的边，由“破圈法”得到最终图形为下图所以由最短路的相关知识可以得到企业最大1:2到仓库1的最短路程为：y2158，路径为:（见附件1:表二、表二、表四、表五）41 （企业 2） 42 28 （仓库 1）。同理得：yij , yik, Wij , Wik及相关路径根据以上算出的数据，由题意可得首先应该重点保证国家级储备库；再是考虑公路区间长短及 运输货物的费用，采用就近原则进行货物调运。又因为各处发生洪涝灾害的情况是突发的， 对时间 并没有限制，有附录表1中的数据得到各仓库和储备库的现有库存量都超过最底库存量，所以

9、假定仓库与仓库之间、仓库与储备库之间不进行货物的调运， 各个企业之间也不会相互联系的。 那么现 在只有企业与仓库，企业和储备库才有运输关系，因此我们根据图论中的最短路和破圈法可以得到 各个企业和仓库、储备库的调运关系，如下表所示：企业i运输目的地企业1仓库2仓库5储备库1企业2仓库1仓库7储备库1储备库2企业3仓库3仓库4仓库6仓库8储备库2由附录中的表1可知，从仓库1到仓库8和两个储备库的储量来看他们现有的库存都是介于最 低库存和预测库存之间，因此我们要从企业调运物资来使得他们的库存达到预测库存以上。对于企业1要使得他的库存来满足仓库2、仓库5和储备库1的预测库存，就必须的生产，那 么企业一

10、至少要生产多少天才可以达到仓库2、仓库5和储备库 1的预测库存呢。有（丫2X2） （丫5X5）（丫9X9） 40 18.25天，企业1至少要生产天才可以满足仓库2、仓库5和储备库1的存储量达到预测库存以上；同理可以得企业2要生产22天才可以满足仓库1、仓库7 和储备库2的存储量达到预测库存以上，企业 3要生产22天才可以满足仓库3、仓库4、仓库& 仓库8和储备库2的存储量达到预测库存以上。1、问题二的求解：有前面的模型和现在分析的情况可以得到一个新的模型： 目标函数：约束条件：企业1到仓库2、仓库5和储备库1的最短路程为：125，80，100公里；企业2到仓库1、仓库7、储备库1和储备库2的最

11、短路程为：58，118，148公里；企业3到仓库3、仓库4、仓库 &仓库8和储备库2的最短路程为：123, 75, 145, 93, 102公里。在附录表1中有丫k ,Xi ,Cmaxj ,Ci的值Ti的取值为22天。把数据和目标条件和约束条件放在 Lingo 解得最小费的最优解为：315876 最优解为： 即：企业企业企业 企业软件去解:1向仓库2运输330百件，企业2向仓库1运输300百件，企业3向仓库4运输120百件，企业3向仓库8运输100百件，企业1向储备库1运输1000百件; 2向仓库7运输110百件；3向仓库6运输20百件，3向储备库2运输700百件。2、问题三的求解：我们是规定

12、的20天完成，那么又可以得一个目标规划模型:mi nF （如 浙）（X2jy2j）（xsjysj） A 约束条件:j 1.5.9 j 1.5.9j 1,7.9.10 j 1.7.9.10j 3.4.6.8.10 j 3.4.6.8.10企业 1 到仓库 2、仓库 5和储备库 1 的最短路程为： 125，80，100公里；企业 2 到仓库 1、仓库 7、储备库 1和储备库 2的最短路程为： 58， 118， 148公里；企业 3到仓库 3、仓库4、仓库6仓库8和储备库2的最短路程为：123, 75, 145, 93, 102公里。在附录表1中有Y-XiCmaxj的值，T的值取20天。把数据和目标

13、条件和约束条件放在 Lingo 软件去解：那么最小费用的优解为： 302532 最优解为：即：企业 企业 企业 企业 企业1 向仓库 2运输 330百件,企业 1 向储备库 1 运输 1000百件； 2向仓库 1运输 300百件,企业 2向仓库 7运输 110百件, 2向储备库 1运输 550百件；企业 2向储备库 2运输 0百件； 3 向仓库 4 运输 120百件,企业3 向仓库 8 运输 100百件,企业3 向仓库 6运输 20 百件,3 向储备库 2 运输 700 百件。3、问题四的求解：931，因洪水交通中断， 2627影响到了企业 1 到由于汛期路段 1423, 1125, 2627

14、,企业1 到储备库的最短路：y11 234.6, 4201327；企业 2到储备库 1 的最短路：y29131.3, 4164027。现在根据题意可得，我们应该选者企业 2 到储备库 1 的路线即：y29131.3, 4164027，然后对我们先前的模型的数据进行改变可以的：储备库 1,企业 2到储备 1 的路线；我们把这条边去掉,然后在用破圈法和最短路进行计算可得：约束条件：这里的 T=20,那么最小费用的优解为： 最优解为： 即：企业 企业 企业 企业 企业用问题三的求解方法对问题四的求解得结果为；324234 1向仓库 2 运输 400百件，企业 1向仓库 5运输 200百件； 2向仓库

15、 1运输 300百件，企业 2向仓库 7运输 110百件，2 向储备库 1 运输 550 百件，企业 2 向储备库 2 运输 0 百件； 3向仓库 4运输 120百件，企业 3向仓库 6运输 20百件， 3向仓库 8运输 100百件，企业 3向储备库 2运输 700百件。六、模型的结果和分析我们在本问题的求解中没有考虑各个仓库之间的调运关系, 也没有考虑仓库和储备库之间的调 运关系, 而在实际生活当中它们的关系是存在的。 但在特殊的情况下有特殊的处理, 灾害具有突发 性,不是人们所能控制的, 所以我们在处理这道题的过程当中就没有必要去考虑各个仓库之间的调 运关系、仓库和储备库之间的调运关系。

16、在运输货物的时候是需要时间的, 然而我们在题中也没有 考虑时间的关系, 因此我们还可以增加货物调运过程中的时间因素, 并且为了预防某些路段因紧急 情况而不能使用,则应该设有预备方案,从而确保防洪工作做得更好。在现实生活中, 每一次运输的运输量会有一定的限制, 在某种情况还会因为运量的多少而改变 运费,例如运量过少, 负责运输单位会因运输过程中的物质耗费而亏本, 因此负责运输单位会为确 保其利益,增加本次运输费用, 故无形中就会增加单位货物的运输费用。 所以在模型的改进中, 应 该考虑这个因素,从而使该模型更具有现实性七、模型的评价及推广优点：我们利用图论有关知识把复杂的交通路线图简化为带权图，

17、再根据权的大小及“破圈法”和“最 短路”来判定欲求两点的最短路径，即为调运路线。根据实际情况（就近原则）来确定具体的调运 方案，既有理论依据，又符合实际要求。缺点：从而被迫此模型可以 商品的保鲜我们在运算中假设仓库与仓库之间没有调运，利用直观就近原则可能忽略了其它的调运路线， 使得我们的调运方案具有局限性，从而使总路费存在误差。我们考虑在调运过程中与时间无关的情 况，但是在实际情况中，如果遇到紧急情况时，可能使得防洪物质短缺或者路段被冲断， 我们必须得改变调运路线，导致运费改变。他不仅可以直接应用与解决本文是关于物资调运问题，在实际的社会当中涉及许多领域，就此模型进行推广。 推广到商品的发放问

18、题中。但还需要考虑更多的因素，如运输过程中商品的变质期限、 费用、市场变动情况等等。其中最短路问题是重要的最优化问题之一， 生产实际的许多问题，如：管道铺设、线路安排、厂区布局、设备更新、南水北调工程和西气东输 等问题。1234萧树铁, 李大潜, 许国志, 何聪，参考文献:数学实验，北京：高等教育出版社，2002, 2。中国大学生数学建模竞赛，北京：高等教育出版社，1998, &运筹学，北京：清华大学出版社，2005, 6。规划论，成都：四川大学出版社，2005, 9。附录附件1:存单位现有库存预测库存最低库存最大库存产量（/天）企业160080040企业236060030企业35006002

19、0仓库1200500100800仓库2270600200900仓库3450300200600仓库4230350100400仓库58004003001000仓库6280300200500仓库7390500300600仓库8500600400800储备库12000300010004000储备库21800250010003000表1、各企业到每个仓库的最短路最 仓7仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8企业11641253401928028728030826,2526,1920,27,26,27,26,19,26,27,26,27,26,27,18,239,3,329,312240,40,

20、9,15,42,28,359,2,3,6,4,2931,3236,38企业25815730615820625311827642,2842,15,186,40,96,40,942,15,186,40,942,28,6,40,299,2331,32,3119,222,3,3631,3235,38企业3224332123753371451649332,39,3032,31,9,32,3532,3132,31,9,1,33,332,39,32,3827,27,26,19630,29,2826,19,18,22292、各企业到每个储备库的最短路_最备库储备库1储备库2企业110026,2726,27,4

21、0,6,4,30企业21486,40,276,4,30企业316710232,31,9,2732,39,30表3、储备库与仓库之间的最短路最短储备仓库1 心仓库2仓库3仓库4仓库5仓库6仓库7仓库8储18916524092170187180210备40,6,4126,19,189,31,9,3126,4,19,9,2,3,40,6,49,31,32库)32,352236142,28232938储12228517512733424762145备29,2829,28,9,39,32,339,32,329,28,42,1539,32,342939,32,3库1518,23518218,19,221,

22、33,36表四,234、仓库与仓库之间的最短路仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8仓库11632972162123116026742,15,29,30,42,4142,15,1842,41,6,2929,30,18,2339,6,40,39,32,3540,9,19,229,2,3,3632,3831仓库216340525713935222337542,15,18,19,18,1918,19,2218,19,2618,15,18,19,18,2326,27,27,9,2,42,26,27,9,31,26,3,3628,299,31,32,3527,9,32,3831仓库329740

23、514841026823716629,30,3918,19,2632,3132,31,9,32,34,1,32,39,32,38),27,9,3127,33,3630,2932,35,32,3526,19,22仓库421625714826222018911842,41,6,18,19,2632,319,27,26,32,34,1,32,39,32,3840,9,3119,2233,3630,2927,9,31仓库521213941026235727238042,15,1818,19,2232,31,9,27,19,26,2719,18,19,26,)9,26,15,27,9,19,2227,26,19,229,2,3,3642,28,31,32,19,222938仓库631135226822035711342,41,6,18,19,2632,34,32,3419,26,273,2,9,33,37,40,27,9,2,1,1,40,389,2,3,363,3633,3