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

论文题目：救灾物资调运问题 救灾物资调运问题 摘 要 本题将调运问题转化为求最短最优路径问题。在附件2的图中，将每个点看作图中的一个点，各点之间的公路看作图中对应节点相连的边，各条公路的长度与运输的乘积的值看作对应边的权，所给网就转化为加权网络图，所求问题就转化为图论问题。 Dijkstra算法，利用Matlab编程求出各企业、储备库到各发放点的最小费用路径及最小费用值。从企业1调物资到1-8；从企业2调物资到1-8；从企业3调物资到1-8；储备库1，2的各个最短最优路径。求出最优路径后，计算最调运时间为天，再以调运物资的花费最少为目标函数，附件1中的各个条件为约束条件，利用线性规划方法，，利用LINGO软件求得结果，得到最佳调运方案。即：企业往。4579680元，最优运输路线见第一问的解答。 再根据目标函数，把天数改为20天LINGO软件求得结果企业往。5719440元，最优运输路线见第二问的解答。 经过计算25天各企业的产量，无法满足各发放点的实际需求。给出的解决方案是让企业增产，增设三个企业日产量为变量，增加约束条件，利用LINGO软件求得结果7227600元，调运方案见第三问的解答。 当不能原来的模型，需重新计算最优路径，但基本思想不变。再根据原有的得出最优路线。（4）在灾害发生时可能造成交通中断，以中断路段： 为例，重新讨论上述三个问题。 二、问题分析 1. 根据题目及附件2的数据信息加以分析，把曲线图转化为理想的纯数学图，每公里每百件的运费和路程数相乘的结果构成每条边上的权数，根据图论知识，将问题转化为最短路问题。 第一问：要求尽快满足发放点对物资的最低需求，并且尽量使运输成本降低。这就有两个目标，一是时间最短，二是运费成本低，显然这两个目标是不能同时达到的。考虑到在灾害来临时，时间是第一位的，国家及各部门也会先考虑第一时间满足灾区人们的最低需求，再考虑运费成本问题，所以先考虑在满足最短时间满足各发放点最低需求的前提下，再考虑使运费最小的运输方案，这是一个线性规划问题。此外，为处理方便，将储备库看成没有生产能力的企业，这样储备库1和储备库2可分别看成企业4和企业5. 2.第二问：求20天后各发放点收到物资的情况以及最佳运输方案，同样是线性规划的问题，让模型中的t=20，再对约束条件稍作修改，使“库存+生产=发放”，得出最优答案。 3.第三问：25天之内能否满足各发放点的实际需求，经过计算25天各企业的生产量、所有库存量之和，与各发放点的实际需求总量进行比较，并没有达到需求。解决办法是让企业增产，使之满足各发放点的最高需求，再用线性规划模型求解最佳运输方案。 4.第四问：假设指定路段中断后，模型是否可用。对于该问题，只需要检验前面建立的模型中所得出的调运路线是否经过该路段，如果不经过，说明这些中断路线对我们的模型没有影响。如果有影响，可以将路段中断后的图采用相同的程序：企业调往发放点的货物量，单位为百件 ：货物从企业到发放点所经过路段的每百件费用之和，单位为元/百件 ：企业的库存货物量，单位为百件 ：企业的日产量，单位为百件，其中==0 ：发放点的最低需求，单位为百件 ：发放点的最高需求，单位为百件 ：发放点原来的库存，单位为百件 ：公路区间调运每百件货物的运费，单位为元/百件 ：公路区间调运货物每公里每百件的运费，高等级公路为20元/公里?百件，普通公路为12元/公里?百件 ：公路区间距离，单位为公里 ：生产的天数，单位为天 =1，2，3，4，5 ； =1，2，3，4，5，6，，7，8 五、模型的建立与求解 5.1 预处理 将各个节点以及节点间的公路分别用点和直线表示，抽象成纯数学的图形，形成一个连通的无向图，记为。 由于假设各点间的物资瞬时调运，故不关心各点间的路程长短，而是关心各点间的运费多少，所以将距离和每公里每百件的运费相乘得到该段公路上调运每百件货物的运费，即 将作为各段公路上的权数 ，则题目附件2的生产企业，发放地点及储备库分布图就转化成如下的赋权图。 5.2模型的建立 由于灾害发生后时间的紧迫性，要在第一时间将货物调运到发放点，故只考虑企业发放点、储备库发放点之间的调运，不考虑企业储备库之间的调运。要使运费最小，可以建立线性规划模型。 设为企业调往发放点的货物量，为货物从企业到发放点所经过路段的每百件费用之和，所有运输费用的和，假设经过天。 目标是使所有运输费用最小，故目标函数为： 对于企业的运量有约束，从企业运出去的货物量不能大于该企业的储存量和产量之和，即 ， =1，2，3，4，5 ； （1） 对各发放点也有约束条件，运到每个发放点的货