救灾物资调运最优化问题 .doc

1、论文题目：救灾物资调运问题 救灾物资调运问题摘 要 本题将救灾物资调运问题转化为求最短最优路径问题。在附件2的图中，将每个点看作图中的一个顶点，各点之间的公路看作图中对应节点相连的边，各条公路的长度与运输单价的乘积的值看作对应边的权，所给网就转化为加权网络图，所求问题就转化为图论问题。 根据Dijkstra算法，利用Matlab编程求出各企业、储备库到各发放点的最小费用路径及最小费用值。依次得出从企业1调物资到发放点1-8；从企业2调物资到发放点1-8；从企业3调物资到发放点1-8；储备库1，2到发放点1-8的各个最短最优路径。求出最优路径后，考虑时间第一位，计算出最短调运时间为8天，再以调运

2、物资的花费最少为目标函数，附件1中的各个条件为约束条件，利用线性规划方法，利用LINGO软件求得结果，得到最佳调运方案。即：企业1往发放点2调运140百件，往发放点5调运300百件；企业2往发放点1调运300百件；企业3往发放点8调运240百件；储备库1往发放点2调运410百件，往发放点4调运320百件，往发放点6调运260百件；储备库2往发放点1调运160百件，往发放点3调运280百件，往发放点7调运470百件，往发放点8调运290百件。运费为4579680元，最优运输路线见第一问的解答。再根据目标函数，把天数改为20天，修改约束条件，利用LINGO软件求得结果，得到最优调运方案。即：企业1

3、往发放点2调运480百件，往发放点5调运440百件；企业2往发放点1调运660百件；企业3往发放点3调运280百件，往发放点8调运200百件；储备库1往发放点2调运370百件，往发放点4调运370百件，往发放点6调运260百件；储备库2往发放点1调运100百件，往发放点7调运570百件，往发放点8调运530百件。运费为5719440元，最优运输路线见第二问的解答。经过计算25天各企业的产量，无法满足各发放点的实际需求。给出的解决方案是让企业增产，增设三个企业日产量为变量，增加约束条件，利用LINGO软件求得结果，得到解决方案和最优调运方案。解决方案为企业3的日产量增至40.4百件。运费为722

4、7600元，调运方案见第三问的解答。当灾害发生时，发生部分交通线路中断，故不能沿用原来的模型，需重新计算最优路径，但基本思想不变。再根据原有的细想及算法得出最优路线。具体调运方案见第四问的解答。 最后按照就近原则提出分区模型，对模型进行简化，并根据实际情况，做出针对性建议。关键词：物资调运 线性规划 最短路 一、 问题重述我国地域辽阔，自然灾害频频发生，给国家和人民财产带来重大损失，建立应急预案是各级政府的一项重要工作。应急预案的一项重要内容是在灾害发生时应急物质的运输调度方案的制定。在某地区有生产某种救灾物质的企业有三家，设置物资发放点八个，储备仓库两个。在灾害发生时，已知企业、各物资发放地

5、点、储备仓库的库存情况，及各发放点的最低需求和实际需求情况，还有企业、发放点、仓库及道路分布情况。设该种物资的运输成本为高等级公路20元/公里百件，普通公路12元/公里百件。研究以下问题：（1）预案要求尽快满足各发放点对救灾物质的最低需求，并尽量使运输成本降低。建立数学模型，给出所需要的时间，物资的调运方案，包括调运量和调运路线。（2）在20天内，按均衡配给的原则，各发放点可以得到多少物资？给出相应的调运方案。（3）能否在25天内满足各发放点的实际需求？怎样才能满足各发放点的实际需求？并给出相应的调运方案。31 ，9 -27 ，26-23 ，25 ，11 -14 -（4）在灾害发生时可能造成交

6、通中断，以中断路段：为例，重新讨论上述三个问题。二、问题分析1. 根据题目及附件2的数据信息加以分析，把曲线图转化为理想的纯数学图，每公里每百件的运费和路程数相乘的结果构成每条边上的权数，根据图论知识，将问题转化为最短路问题。第一问：要求尽快满足发放点对物资的最低需求，并且尽量使运输成本降低。这就有两个目标，一是时间最短，二是运费成本低，显然这两个目标是不能同时达到的。考虑到在灾害来临时，时间是第一位的，国家及各部门也会先考虑第一时间满足灾区人们的最低需求，再考虑运费成本问题，所以先考虑在满足最短时间满足各发放点最低需求的前提下，再考虑使运费最小的运输方案，这是一个线性规划问题。此外，为处理方

7、便，将储备库看成没有生产能力的企业，这样储备库1和储备库2可分别看成企业4和企业5.2.第二问：求20天后各发放点收到物资的情况以及最佳运输方案，同样是线性规划的问题，让模型中的t=20，再对约束条件稍作修改，使“库存+生产=发放”，得出最优答案。3.第三问：25天之内能否满足各发放点的实际需求，经过计算25天各企业的生产量、所有库存量之和，与各发放点的实际需求总量进行比较，并没有达到需求。解决办法是让企业增产，使之满足各发放点的最高需求，再用线性规划模型求解最佳运输方案。4.第四问：假设指定路段中断后，以上所建立模型是否可用。对于该问题，只需要检验前面建立的模型中所得出的调运路线是否经过该路

8、段，如果不经过，说明这些中断路线对我们的模型没有影响。如果有影响，可以将路段中断后的图采用第一步相同的处理程序重新进行计算，分别求解出最佳运输方案。三、基本假设1假设道路的运输能力足够大，没有运输限制；2. 假设企业的仓库和储备仓库的库存能力无限大；3. 不考虑各点间的调运时间长短，假设物资调运瞬时到达；4. 假设调运过程中没有衍生灾害，各个路段道路畅通，即调运过程不受阻；除第四问已知中断路径外，其他路径均不受影响。四、符号说明：企业调往发放点的货物量，单位为百件：货物从企业到发放点所经过路段的每百件费用之和，单位为元/百件：企业的库存货物量，单位为百件：企业的日产量，单位为百件，其中=0：发

9、放点的最低需求，单位为百件：发放点的最高需求，单位为百件：发放点原来的库存，单位为百件：公路区间调运每百件货物的运费，单位为元/百件：公路区间调运货物每公里每百件的运费，高等级公路为20元/公里百件，普通公路为12元/公里百件：公路区间距离，单位为公里：生产的天数，单位为天=1，2，3，4，5 ； =1，2，3，4，5，6，7，8五、模型的建立与求解5.1 预处理将各个节点以及节点间的公路分别用点和直线表示，抽象成纯数学的图形，形成一个连通的无向图，记为。由于假设各点间的物资瞬时调运，故不关心各点间的路程长短，而是关心各点间的运费多少，所以将距离和每公里每百件的运费相乘得到该段公路上调运每百件

10、货物的运费，即将作为各段公路上的权数 ，则题目附件2的生产企业，发放地点及储备库分布图就转化成如下的赋权图。5.2模型的建立由于灾害发生后时间的紧迫性，要在第一时间将货物调运到发放点，故只考虑企业发放点、储备库发放点之间的调运，不考虑企业储备库之间的调运。要使运费最小，可以建立线性规划模型。设为企业调往发放点的货物量，为货物从企业到发放点所经过路段的每百件费用之和，所有运输费用的和，假设经过天。目标是使所有运输费用最小，故目标函数为： 对于企业的运量有约束，从企业运出去的货物量不能大于该企业的储存量和产量之和，即 ， =1，2，3，4，5 ； （1）对各发放点也有约束条件，运到每个发放点的货物

11、量应大于或等于它们的最低需求，小于或等于它们的最高需求，即， =1，2，3，4，5，6，7，8； （2）还有各调运量的非负约束，即, =1，2，3，4，5 ； =1，2，3，4，5，6，7，8；5.3模型的求解5.3.1第一问：（1）利用求最短路的算法求各企业到各发放点的单位最少运费这是求上述赋权图上两点间的最短路问题，将上述赋权图中第个顶点到第个顶点之间的权数写在矩阵的第行第列的位置上，对应成一个权数矩阵。利用Dijkstra算法对赋权图求最短路。Dijkstra算法是一种标号法，它的基本思想是从起点出发，逐步向外探寻最短路，执行过程中，给每一个顶点标号，其中是正整数，表示获得此标号的前一点

12、的下标；或表示起点到该点的最短路的权（记为P标号），或表示从起点到该点的最短路的权的上界（记为T标号）。方法的每一步是去修改T标号，并且把某一个具有T标号的点改变为具有P标号的点，从而使G中具有P标号的顶点数多一个。这样经过至多p-1步，就可以求得从起点到各点的最短路，再根据每个点标号的第一个数反向追踪找出最短路。编写Dijkstra算法的程序(源程序见附录1)，在Matlab中实现，得到结果，整理出各个企业到各发放点的最小运费单价如下表所示：各业到各发放点的最小单位运费表（单位：元/百件）发放1发放2发放3发放4发放5发放6发放7发放8企业11848150040802304156034442

13、5683720企业26961884367218962472303614163312企业32688398414769004044174019681116储备122721980288011042040224421602520储备21464342021001524400826767441740（2）求时间由于不考虑各点间的运输时间，故尽快达到各发放点最低需求的时间限制就是各企业的生产时间，要使这个时间最短，则所有的库存就要都被充分利用，这样需要生产的帐篷才会最少，生产时间也就最短。从这一原则出发，我们计算最短时间。由题目中附件1的数据可得:发放点的最低需求总和=500+600+300+350+400

14、+300+500+600=3550；所有库存量= 120+60+80+40+50+20+30+100+40+30+70+1000+1200=2840；故需要企业耗时间生产的帐篷数量=3550-2840=710三企业每天的总日产量=40+30+20=90最小天数=710/90=7.9因为天数取整数，所以取最小时间=8.（3）运输方案的求解 将上面求出来的各企业到各发放点的单位最少运费和最小时间，还有题目附件1中的已知数据代入模型，编写Lingo程序，利用Lingo求解（源程序和运行结果见附录2），得到最优值为4579680元；最优解为：； ； ； ； ； ； ； 运输方案如下：第一问运量表（单位

15、：百件）发放1发放2发放3发放4发放5发放6发放7发放8企业1140300企业2300企业3240储备1410320260储备2160280470290运输路线如下：企业1发放点2；企业1发放点5；企业2发放点1；企业2发放点7；企业3发放3；企业3发放4；企业3发放6；企业3发放8；储备1发放2；储备1发放4；储备1发放5；储备1发放6；储备2发放1；储备2发放点3；储备2发放点7；储备2发放点85.3.2 第二问 此问中t=20, 由第一问可看出生产8天就可以满足各发放点的最低需求，现在生产20天，肯定能满足各发放点的最低需求，如果还采用上题的模型，目标是运费最少，货物越少运费就越少，那在

16、上题的约束条件下求出来的解肯定是满足最低需求的最少运量，这让各发放点仅仅达到最低需求，而各企业还有库存不向发放点调配，这不符合实际。 为了克服这个问题，让各企业在发放点没有达到实际需求时有库存就都要往发放点调运。根据这个原则，修改约束条件（1），将小于或等于改成等于，即； =1，2，3，4，5 ；同时修改Lingo程序，利用Lingo10.0重新求解（源程序和运行结果见附录3），得到最优值为5719440元；最优解为：； ； ； ； ； ； ； 最优调运方案如下：第二问运量表（单位：百件）发放1发放2发放3发放4发放5发放6发放7发放8企业1480440企业2660企业3280200储备137

17、0370260储备2100570530运输路线：企业1发放点2；企业1发放点5；企业2发放点1；企业3发放3；企业3发放8；储备1发放2；储备1发放4；储备1发放6；储备2发放1；储备2发放点7；储备2发放点85.3.3 第三问问题三研究的是能否在25天内满足各发放点的实际需求，通过计算，25天各企业生产总量=90*25=2250各发放点总的实际需求=800+900+600+400+1000+500+600+800=5600总储备量=2840总产量+总储备量=2250+2840=5090l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j; end;end;endlz附录2

18、：第一问Lingo程序方法1：model:!5发点8收点运输问题;sets: warehouses/wh1.wh5/: capacity; vendors/v1.v8/: demand; links(warehouses,vendors): cost, volume;endsets!目标函数; min=sum(links: cost*volume);!需求约束; for(vendors(J): sum(warehouses(I): volume(I,J)=demand(J);!产量约束; for(warehouses(I): sum(vendors(J): volume(I,J)=capaci

19、ty(I); !这里是数据;data: capacity=440 300 240 1000 1200; demand=460 550 280 320 300 260 470 530; cost=1848 1500 4080 2304 1560 3444 2568 3720 696 1884 3672 1896 2472 3036 1416 3312 2688 3984 1476 900 4044 1740 1968 1116 2272 1980 2880 1104 2040 2244 2160 2520 1464 3420 2100 1524 4008 2676 744 1740;enddat

20、aend方法2：min=1848*x11+1500*x12+4080*x13+2304*x14+1560*x15+3444*x16+2568*x17+3720*x18+696*x21+1884*x22+3672*x23+1896*x24+2472*x25+3036*x26+1416*x27+3312*x28+2688*x31+3984*x32+1476*x33+900*x34+4044*x35+1740*x36+1968*x37+1116*x38+2272*x41+1980*x42+2880*x43+1104*x44+2040*x45+2244*x46+2160*x47+2520*x48+14

21、64*x51+3420*x52+2100*x53+1524*x54+4008*x55+2964*x56+744*x57+1740*x58;t=8;x11+x12+x13+x14+x15+x16+x17+x18=120+40*t;x21+x22+x23+x24+x25+x26+x27+x28=60+30*t;x31+x32+x33+x34+x35+x36+x37+x38=80+20*t;x41+x42+x43+x44+x45+x46+x47+x48=1000;x51+x52+x53+x54+x55+x56+x57+x58=500-40;x12+x22+x32+x42+x52=600-50;x13

22、+x23+x33+x43+x53=300-20;x14+x24+x34+x44+x54=350-30;x15+x25+x35+x45+x55=400-100;x16+x26+x36+x46+x56=300-40;x17+x27+x37+x47+x57=500-30;x18+x28+x38+x48+x58=600-70;x11+x21+x31+x41+x51=800-40;x12+x22+x32+x42+x52=900-50;x13+x23+x33+x43+x53=600-20;x14+x24+x34+x44+x54=400-30;x15+x25+x35+x45+x55=1000-100;x16

23、+x26+x36+x46+x56=500-40;x17+x27+x37+x47+x57=600-30;x18+x28+x38+x48+x58=500-40;x12+x22+x32+x42+x52=600-50;x13+x23+x33+x43+x53=300-20;x14+x24+x34+x44+x54=350-30;x15+x25+x35+x45+x55=400-100;x16+x26+x36+x46+x56=300-40;x17+x27+x37+x47+x57=500-30;x18+x28+x38+x48+x58=600-70;x11+x21+x31+x41+x51=800-40;x12+x

24、22+x32+x42+x52=900-50;x13+x23+x33+x43+x53=600-20;x14+x24+x34+x44+x54=400-30;x15+x25+x35+x45+x55=1000-100;x16+x26+x36+x46+x56=500-40;x17+x27+x37+x47+x57=600-30;x18+x28+x38+x48+x58=800-70;运行结果：Global optimal solution found. Objective value: 5719440. Total solver iterations: 17 Variable Value Reduced C

25、ost X11 0.000000 564.0000 X12 480.0000 0.000000 X13 0.000000 2160.000 X14 0.000000 1680.000 X15 440.0000 0.000000 X16 0.000000 1680.000 X17 0.000000 2004.000 X18 0.000000 2160.000 X21 660.0000 0.000000 X22 0.000000 972.0000 X23 0.000000 2340.000 X24 0.000000 1860.000 X25 0.000000 1500.000 X26 0.0000

26、00 1860.000 X27 0.000000 1440.000 X28 0.000000 2340.000 X31 0.000000 1848.000 X32 0.000000 2928.000 X33 280.0000 0.000000 X34 0.000000 720.0000 X35 0.000000 2928.000 X36 0.000000 420.0000 X37 0.000000 1848.000 X38 200.0000 0.000000 X41 0.000000 508.0000 X42 370.0000 0.000000 X43 0.000000 480.0000 X44 370.0000 0.000000 X45 0.000000 0.000000 X46 260.0000 0.000000 X47 0.000000 1116.000 X48 0.000000 480.0000 X51 100.0000 0.000000