救灾物资调运最优化问题

0论文题目：救灾物资调运问题救灾物资调运问题摘要本题将救灾物资调运问题转化为求最短最优路径问题。在附件2的图中，将每个点看作图中的一个顶点，各点之间的公路看作图中对应节点相连的边，各条公路的长度与运输单价的乘积的值看作对应边的权，所给网就转化为加权网络图，所求问题就转化为图论问题。1根据Dijkstra算法，利用Matlab编程求出各企业、储备库到各发放点的最小费用路径及最小费用值。依次得出从企业1调物资到发放点1-8；从企业2调物资到发放点1-8；从企业3调物资到发放点1-8；储备库1，2到发放点1-8的各个最短最优路径。求出最优路径后，考虑时间第一位，计算出最短调运时间为8天，再以调运物资的花费最少为目标函数，附件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往发放点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百件。运费为7227600元，调运方案见第三问的解答。当灾害发生时，发生部分交通线路中断，故不能沿用原来的模型，需重新计算最优路径，但基本思想不变。再根据原有的细想及算法得出最优路线。具体调运方案见第四问的解答。最后按照就近原则提出分区模型，对模型进行简化，并根据实际情况，做出针对性建议。关键词：物资调运线性规划最短路一、问题重述我国地域辽阔，自然灾害频频发生，给国家和人民财产带来重大损失，建立应急预案是各级政府的一项重要工作。应急预案的一项重要内容是在灾害发生时应急物质的运输调度方案的制定。在某地区有生产某种救灾物质的企业有三家，设置物资发放点八个，储备仓库两个。在灾害发生时，已知企业、各物资发放地点、储备仓库的库存情况，及各发放点的最低需求和实际需求情况，还有企业、发放点、仓库及道路分布情况。设该种物资的运输成本为高等级公路20元/公里•百件，普通公路12元/公里•百件。研究以下问题：2（1）预案要求尽快满足各发放点对救灾物质的最低需求，并尽量使运输成本降低。建立数学模型，给出所需要的时间，物资的调运方案，包括调运量和调运路线。（2）在20天内，按均衡配给的原则，各发放点可以得到多少物资？给出相应的调运方案。（3）能否在25天内满足各发放点的实际需求？怎样才能满足各发放点的实际需求？并给出相应的调运方案。（4）在灾害发生时可能造成交通中断，以中断路段：为例，重新讨论上述三个问题。二、问题分析1.根据题目及附件2的数据信息加以分析，把曲线图转化为理想的纯数学图，每公里每百件的运费和路程数相乘的结果构成每条边上的权数，根据图论知识，将问题转化为最短路问题。第一问：要求尽快满足发放点对物资的最低需求，并且尽量使运输成本降低。这就有两个目标，一是时间最短，二是运费成本低，显然这两个目标是不能同时达到的。考虑到在灾害来临时，时间是第一位的，国家及各部门也会先考虑第一时间满足灾区人们的最低需求，再考虑运费成本问题，所以先考虑在满足最短时间满足各发放点最低需求的前提下，再考虑使运费最小的运输方案，这是一个线性规划问题。此外，为处理方便，将储备库看成没有生产能力的企业，这样储备库1和储备库2可分别看成企业4和企业5.2.第二问：求20天后各发放点收到物资的情况以及最佳运输方案，同样是线性规划的问题，让模型中的t=20，再对约束条件稍作修改，使“库存+生产=发放”，得出最优答案。3.第三问：25天之内能否满足各发放点的实际需求，经过计算25天各企业的生产量、所有库存量之和，与各发放点的实际需求总量进行比较，并没有达到需求。解决办法是让企业增产，使之满足各发放点的最高需求，再用线性规划模型求解最佳运输方案。4.第四问：假设指定路段中断后，以上所建立模型是否可用。对于该问题，只需要检验前面建立的模型中所得出的调运路线是否经过该路段，如果不经过，说明这些中断路线对我们的模型没有影响。如果有影响，可以将路段中断后的图采用第一步相同的处理程序重新进行计算，分别求解出最佳运输方案。三、基本假设1．假设道路的运输能力足够大，没有运输限制；2.假设企业的仓库和储备仓库的库存能力无限大；3.不考虑各点间的调运时间长短，假设物资调运瞬时到达；14--23，11--25，26---27，9---31，34.假设调运过程中没有衍生灾害，各个路段道路畅通，即调运过程不受阻；除第四问已知中断路径外，其他路径均不受影响。四、符号说明ijx：企业i调往发放点j的货物量，单位为百件ijc：货物从企业i到发放点j所经过路段的每百件费用之和，单位为元/百件ia：企业i的库存货物量，单位为百件ib：企业i的日产量，单位为百件，其中3b=4b=0jl：发放点j的最低需求，单位为百件ju：发放点j的最高需求，单位为百件jd：发放点j原来的库存，单位为百件q：公路区间调运每百件货物的运费，单位为元/百件w：公路区间调运货物每公里每百件的运费，高等级公路为20元/公里•百件，普通公路为12元/公里•百件r：公路区间距离，单位为公里t：生产的天数，单位为天i=1，2，3，4，5；j=1，2，3，4，5，6，，7，8五、模型的建立与求解5.1预处理将各个节点以及节点间的公路分别用点和直线表示，抽象成纯数学的图形，形成一个连通的无向图，记为(,)GVE。由于假设各点间的物资瞬时调运，故不关心各点间的路程长短，而是关心各点间的运费多少，所以将距离和每公里每百件的运费相乘得到该段公路上调运每百件货物的运费，即4*qwr将q作为各段公路上的权数，则题目附件2的生产企业，发放地点及储备库分布图就转化成如下的赋权图。5.2模型的建立由于灾害发生后时间的紧迫性，要在第一时间将货物调运到发放点，故只考虑企业发放点、储备库发放点之间的调运，不考虑企业储备库之间的调运。要使运费最小，可以建立线性规划模型。设ijx为企业i调往发放点j的货物量，ijc为货物从企业i到发放点j所经过路段的每百件费用之和，z所有运输费用的和，假设经过t天。目标是使所有运输费用最小，故目标函数为：8511min*ijijjizxc对于企业的运量有约束，从企业运出去的货物量不能大于该企业的储存量和5产量之和，即81*ijiijxabt，i=1，2，3，4，5；（1）对各发放点也有约束条件，运到每个发放点的货物量应大于或等于它们的最低需求，小于或等于它们的最高需求，即51jjijjjildxud，j=1，2，3，4，5，6，，7，8；（2）还有各调运量的非负约束，即0ijx,i=1，2，3，4，5；j=1，2，3，4，5，6，，7，8；5.3模型的求解5.3.1第一问：（1）利用求最短路的算法求各企业到各发放点的单位最少运费ijc这是求上述赋权图上两点间的最短路问题，将上述赋权图中第i个顶点到第j个顶点之间的权数写在矩阵的第i行第j列的位置上，对应成一个权数矩阵。利用Dijkstra算法对赋权图求最短路。Dijkstra算法是一种标号法，它的基本思想是从起点sv出发，逐步向外探寻最短路，执行过程中，给每一个顶点jv标号,jjw，其中j是正整数，表示获得此标号的前一点的下标；jw或表示起点到该点的最短路的权（记为P标号），或表示从起点到该点的最短路的权的上界（记为T标号）。方法的每一步是去修改T标号，并且把某一个具有T标号的点改变为具有P标号的点，从而使G中具有P标号的顶点数多一个。这样经过至多p-1步，就可以求得从起点到各点的最短路，再根据每个点标号的第一个数j反向追踪找出最短路。编写Dijkstra算法的程序(源程序见附录1)，在Matlab中实现，得到结果，整理出各个企业到各发放点的最小运费单价如下表所示：各业到各发放点的最小单位运费表（单位：元/百件）发放1发放2发放3发放4发放5发放6发放7发放8企业118481500408023041560344425683720企业26961884367218962472303614163312企业32688398414769004044174019681116储备122721980288011042040224421602520储备214643420210015244008267674417406（2）求时间t由于不考虑各点间的运输时间，故尽快达到各发放点最低需求的时间限制就是各企业的生产时间，要使这个时间最短，则所有的库存就要都被充分利用，这样需要生产的帐篷才会最少，生产时间也就最短。从这一原则出发，我们计算最短时间。由题目中附件1的数据可得:发放点的最低需求总和=500+600+300+350+400+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因为天数取整数，所以取最小时间t=8.（3）运输方案的求解将上面求出来的各企业到各发放点的单位最少运费ijC和最小时间t，还有题目附件1中的已知数据代入模型，编写Lingo程序，利用Lingo求解（源程序和运行结果见附录2），得到最优值为4579680元；最优解为：12140x；15300x；21300x；38240x42410x；44320x；46260x51160x；53280x；57470x；58290x运输方案如下：第一问运量表（单位：百件）发放1发放2发放3发放4发放5发放6发放7发放8企业1140300企业2300企业3240储备1410320260储备2160280470290运输路线如下：企业1○26○19○18发放点2；企业1○20发放点5；企业2○42发放点1；7企业2○42○28发放点7；企业3○32发放3；企业3○32发放4；企业3○1○33发放6；企业3○32发放8；储备1○26○19○18发放2；储备1○9发放4；储备1○26○19发放5；储备1○9○2○3发放6；储备2○29发放1；储备2○39○32发放点3；储备2发放点7；○1储备2○39○32发放点85.3.2第二问此问中t=20,由第一问可看出生产8天就可以满足各发放点的最低需求，现在生产20天，肯定能满足各发放点的最低需求，如果还采用上题的模型，目标是运费最少，货物越少运费就越少，那在上题的约束条件下求出来的解肯定是满足最低需求的最少运量，这让各发放点仅仅达到最低需求，而各企业还有库存不向发放点调配，这不符合实际。为了克服这个问题，让各企业在发放点没有达到实际需求时有库存就都要往发放点调运。根据这个原则，修改约束条件（1），将小于或等于改成等于，即81*ijiijxabt；i=1，2，3，4，5；同时修改L