救灾物资调运最优化问题

/论文题目：救灾物资调运问题救灾物资调运问题摘要本题将救灾物资调运问题转化为求最短最优路径问题。在附件2的图中，将每个点看作图中的一个顶点,各点之间的公路看作图中对应节点相连的边,各条公路的长度与运输单价的乘积的值看作对应边的权，所给网就转化为加权网络图，所求问题就转化为图论问题。根据Dijkｓtra算法，利用Ｍatlaｂ编程求出各企业、储备库到各发放点的最小费用路径及最小费用值。依次得出从企业1调物资到发放点1—8;从企业２调物资到发放点1—8;从企业3调物资到发放点1-８；储备库1,2到发放点1—8的各个最短最优路径。求出最优路径后,考虑时间第一位，计算出最短调运时间为8天，再以调运物资的花费最少为目标函数,附件1中的各个条件为约束条件，利用线性规划方法，，利用LINＧO软件求得结果，得到最佳调运方案。即：企业１往发放点2调运１４0百件，往发放点5调运300百件；企业2往发放点１调运300百件;企业3往发放点８调运２40百件；储备库1往发放点2调运41０百件，往发放点4调运3２0百件,往发放点６调运２60百件；储备库２往发放点1调运16０百件，往发放点3调运280百件，往发放点7调运4７０百件，往发放点８调运290百件.运费为元,最优运输路线见第一问的解答。再根据目标函数，把天数改为20天，修改约束条件，利用LIＮＧO软件求得结果，得到最优调运方案。即:企业1往发放点2调运４8０百件，往发放点5调运440百件；企业2往发放点1调运6６0百件;企业3往发放点３调运2８0百件，往发放点８调运２０0百件；储备库1往发放点2调运3７0百件,往发放点4调运370百件，往发放点6调运260百件;储备库2往发放点1调运1００百件,往发放点7调运570百件，往发放点8调运5３０百件。运费为元，最优运输路线见第二问的解答。经过计算２5天各企业的产量，无法满足各发放点的实际需求。给出的解决方案是让企业增产，增设三个企业日产量为变量,增加约束条件,利用ＬINＧO软件求得结果,得到解决方案和最优调运方案。解决方案为企业3的日产量增至4０．４百件。运费为元，调运方案见第三问的解答。当灾害发生时，发生部分交通线路中断,故不能沿用原来的模型，需重新计算最优路径，但基本思想不变。再根据原有的细想及算法得出最优路线。具体调运方案见第四问的解答.最后按照就近原则提出分区模型,对模型进行简化，并根据实际情况,做出针对性建议。关键词:物资调运线性规划最短路问题重述我国地域辽阔，自然灾害频频发生,给国家和人民财产带来重大损失，建立应急预案是各级政府的一项重要工作。应急预案的一项重要内容是在灾害发生时应急物质的运输调度方案的制定。在某地区有生产某种救灾物质的企业有三家，设置物资发放点八个，储备仓库两个.在灾害发生时，已知企业、各物资发放地点、储备仓库的库存情况，及各发放点的最低需求和实际需求情况，还有企业、发放点、仓库及道路分布情况.设该种物资的运输成本为高等级公路２0元/公里•百件，普通公路1２元/公里•百件。研究以下问题:（1）预案要求尽快满足各发放点对救灾物质的最低需求,并尽量使运输成本降低。建立数学模型，给出所需要的时间，物资的调运方案,包括调运量和调运路线.（２）在２0天内,按均衡配给的原则,各发放点可以得到多少物资?给出相应的调运方案。（3）能否在25天内满足各发放点的实际需求?怎样才能满足各发放点的实际需求？并给出相应的调运方案。31，927，2623，25，11--14--（4）在灾害发生时可能造成交通中断，以中断路段：31，927，2623，25，11--14--为例,重新讨论上述三个问题。二、问题分析1。根据题目及附件2的数据信息加以分析，把曲线图转化为理想的纯数学图，每公里每百件的运费和路程数相乘的结果构成每条边上的权数，根据图论知识,将问题转化为最短路问题。第一问:要求尽快满足发放点对物资的最低需求，并且尽量使运输成本降低.这就有两个目标,一是时间最短，二是运费成本低，显然这两个目标是不能同时达到的.考虑到在灾害来临时，时间是第一位的，国家及各部门也会先考虑第一时间满足灾区人们的最低需求，再考虑运费成本问题,所以先考虑在满足最短时间满足各发放点最低需求的前提下，再考虑使运费最小的运输方案,这是一个线性规划问题。此外,为处理方便,将储备库看成没有生产能力的企业,这样储备库１和储备库２可分别看成企业４和企业5.2。第二问：求2０天后各发放点收到物资的情况以及最佳运输方案,同样是线性规划的问题，让模型中的t=20,再对约束条件稍作修改，使“库存+生产＝发放”,得出最优答案.3.第三问:25天之内能否满足各发放点的实际需求,经过计算２5天各企业的生产量、所有库存量之和，与各发放点的实际需求总量进行比较，并没有达到需求。解决办法是让企业增产,使之满足各发放点的最高需求,再用线性规划模型求解最佳运输方案。4.第四问：假设指定路段中断后,以上所建立模型是否可用。对于该问题，只需要检验前面建立的模型中所得出的调运路线是否经过该路段,如果不经过,说明这些中断路线对我们的模型没有影响。如果有影响，可以将路段中断后的图采用第一步相同的处理程序重新进行计算，分别求解出最佳运输方案。三、基本假设1．假设道路的运输能力足够大，没有运输限制；2.假设企业的仓库和储备仓库的库存能力无限大；3．不考虑各点间的调运时间长短,假设物资调运瞬时到达；4．假设调运过程中没有衍生灾害，各个路段道路畅通，即调运过程不受阻；除第四问已知中断路径外,其他路径均不受影响.四、符号说明SKＩPIＦ1〈0：企业SKIＰＩF1<0调往发放点SKＩPIF1<0的货物量,单位为百件SKIPＩF1〈0:货物从企业SＫIPIF1<０到发放点SKＩPIＦ1＜0所经过路段的每百件费用之和，单位为元/百件SＫIPＩF1〈0：企业SKＩPIF１〈０的库存货物量，单位为百件SKＩＰＩF１〈0：企业SKＩPIF１〈0的日产量,单位为百件，其中SKIPIF１〈0＝SＫＩPＩF1〈0=0SＫIPIF1<0：发放点SKIPIF1<0的最低需求，单位为百件SKＩPIF1〈０:发放点SＫＩPＩF１<０的最高需求，单位为百件SKIＰIF１〈0:发放点SKIPＩF1<0原来的库存，单位为百件SKIPIF１＜0：公路区间调运每百件货物的运费，单位为元/百件SKIPIF1〈0：公路区间调运货物每公里每百件的运费，高等级公路为２0元/公里•百件，普通公路为12元/公里•百件SKIPIF1<0：公路区间距离,单位为公里SＫIPＩF1<０：生产的天数，单位为天SＫＩPＩＦ1<0=1，2，３，4，５;SＫIPIF1〈０=1，2，3，４,5，6，，7，8五、模型的建立与求解5。1预处理将各个节点以及节点间的公路分别用点和直线表示,抽象成纯数学的图形,形成一个连通的无向图，记为SKIPＩF1<０。由于假设各点间的物资瞬时调运，故不关心各点间的路程长短，而是关心各点间的运费多少,所以将距离和每公里每百件的运费相乘得到该段公路上调运每百件货物的运费，即SＫIPIＦ1<0将SKIPIF１＜0作为各段公路上的权数,则题目附件2的生产企业,发放地点及储备库分布图就转化成如下的赋权图。5.2模型的建立由于灾害发生后时间的紧迫性,要在第一时间将货物调运到发放点，故只考虑企业ＳKＩPIF1<0发放点、储备库SKIＰIF1〈0发放点之间的调运，不考虑企业SKIPＩF１<０储备库之间的调运。要使运费最小，可以建立线性规划模型。设ＳKIPIF1＜0为企业ＳＫＩＰIF1〈0调往发放点ＳKIＰIＦ1〈0的货物量，SKIPIＦ1〈0为货物从企业ＳKIPIF1<0到发放点SKIPIF１＜0所经过路段的每百件费用之和，SKIPIＦ1<0所有运输费用的和,假设经过ＳKＩPIF1＜0天.目标是使所有运输费用最小，故目标函数为：SKIPIF1<０对于企业的运量有约束，从企业运出去的货物量不能大于该企业的储存量和产量之和，即SKＩPIF1<0，SKIPIF1〈0=1，2,3,4，5；(1）对各发放点也有约束条件，运到每个发放点的货物量应大于或等于它们的最低需求，小于或等于它们的最高需求,即SKＩPIF1<０，SＫIPIF1<０=1，2,3，4，5，6，,7,8；（2）还有各调运量的非负约束，即SKIＰIF１〈0，SKIPIＦ1<0=１,2，3，4,5;SKIPＩF1＜0=1,2,3，4,5，6，,7,8;5.3模型的求解５.３。1第一问：(1）利用求最短路的算法求各企业到各发放点的单位最少运费SＫIＰＩF１<0这是求上述赋权图上两点间的最短路问题，将上述赋权图中第SKＩPIF1〈０个顶点到第SKIPIF1〈0个顶点之间的权数写在矩阵的第SKIＰIF１＜0行第SＫIＰIF1<０列的位置上，对应成一个权数矩阵。利用Dijｋstｒa算法对赋权图求最短路。Ｄijkstrａ算法是一种标号法,它的基本思想是从起点SＫＩＰＩF1＜０出发，逐步向外探寻最短路，执行过程中,给每一个顶点SＫIPIF1〈0标号SＫIPIF1〈０,其中SKIＰIF1＜0是正整数，表示获得此标号的前一点的下标；ＳKＩPIF１〈0或表示起点到该点的最短路的权（记为P标号)，或表示从起点到该点的最短路的权的上界（记为T标号）。方法的每一步是去修改T标号,并且把某一个具有Ｔ标号的点改变为具有P标号的点,从而使G中具有P标号的顶点数多一个.这样经过至多p-1步,就可以求得从起点到各点的最短路,再根据每个点标号的第一个数ＳKIＰIＦ1〈0反向追踪找出最短路。编写Dｉjｋstｒa算法的程序（源程序见附录1），在Matlab中实现，得到结果,整理出各个企业到各发放点的最小运费单价如下表所示：各业到各发放点的最小单位运费表（单位：元/百件）发放1发放2发放3发放４发放5发放6发放７发放8企业１18481５00408０23０4156034４42568372０企业2６９6188４３６72１８962４７2３０３6１4１６３312企业326８83９84１４76900４04４174０１9681116储备１22７219８02８8０1１0420402２４42１６025２0储备２146434202１0015２４400826７6７44１7４０（2)求时间SＫＩＰIＦ1＜０由于不考虑各点间的运输时间,故尽快达到各发放点最低需求的时间限制就是各企业的生产时间，要使这个时间最短，则所有的库存就要都被充分利用,这样需要生产的帐篷才会最少,生产时间也就最短。从这一原则出发,我们计算最短时间。由题目中附件１的数据可得:发放点的最低需求总和=50０＋60０+３00＋350+4０0＋300＋５00＋600＝3５50；所有库存量＝120+60+８0+40+50+20+３0+100+40+３0＋7０+1０00+1２00=28４0；故需要企业耗时间生产的帐篷数量=3550—2８40=７１0三企业每天的总日产量＝40+3０+20＝90最小天数=71０／90=７.9因为天数取整数，所以取最小时间SKIPIF1〈0＝8。（3)运输方案的求解将上面求出来的各企业到各发放点的单位最少运费ＳＫIＰIF1〈0和最小时间ＳKIPIＦ1<0,还有题目附件1中的已知数据代入模型，编写Lｉngｏ程序,利用Lingo求解（源程序和运行结果见附录２），得到最优值为元；最优解为：SKIＰIF1〈0；SKIPＩF1＜0；SKIPIＦ1<0;ＳKIPＩF1〈０SKIＰIF１<0；SKIPIＦ１＜0；SＫＩPＩF1〈0ＳKIPIF1<０；SKIＰＩF1<0；SＫIPIF1〈0；SKIＰIF１<０运输方案如下：第一问运量表（单位：百件）发放1发放２发放3发放４发放5发放６发放７发放8企业11４0３00企业2300企业3２40储备1４1032０26０储备21602804７0290运输路线如下:企业１ＳＫIPIF1＜0ｅq\ｏ＼ａc（○，26）SＫIPIＦ１〈0eｑ\ｏ\aｃ（○，１９）SKＩＰIF1〈０eq＼o\ac（○,18）SKIPIF１＜0发放点２;企业1SＫIＰIF１〈0eq＼o＼ac（○，20)SKＩPIＦ1<0发放点5；企业２SKIＰIF1<０eｑ\o＼ａc(○，42)SKIＰIF1＜0发放点1；企业2ＳKＩＰＩF1〈０eq\o＼aｃ(○,４２)SKIPIF1<0eｑ＼ｏ\ac（○，28)SKＩPＩF１<0发放点7；企业3SKIＰIF1〈0eq\o＼ac（○，32）SKIＰIF１<０发放3；企业3ＳKIPＩF１〈0eｑ＼o＼ac（○,32）SKIPIＦ1<0发放4;企业3ＳKIＰIＦ1＜0ｅｑ\o\ac（○,1）SKIPIF1＜0eq＼o\ac（○，3３）SKIPIF1＜０发放6;企业3SKIPIF1〈0ｅｑ\o＼ac(○，32)ＳKIPＩF1〈0发放8；储备１ＳＫIPIF1〈0eq\o\ac(○,26）SKIPIＦ1〈0ｅｑ＼o\ac（○,19）SKＩPIＦ1〈0eq\ｏ\ac(○,１8）SKＩPIF1＜0发放2;储备１ＳKIＰIF1<0eq＼o\ａc（○，9)ＳKIPＩF１〈0发放4;储备1ＳKIPIF1<０eq\o＼ac(○,26)SKＩＰIF1〈0eｑ＼o\ac（○，１９）ＳKIPＩF１＜0发放5;储备１ＳKIＰIF1〈0eq＼ｏ＼aｃ（○,９)SKＩPIF1＜0ｅq\o\aｃ(○,２）SKＩPIF1〈0eq\o＼ac（○，3)ＳKIPＩＦ1〈０发放6；储备2SKIPＩF1〈０eq\ｏ\ac(○，2９)ＳKＩPIF1<0发放1;储备2SKIＰIF1＜０eq\o\ac(○，39)SＫＩPIＦ1〈０eｑ\o\ａc（○,32）SKＩＰIＦ1<0发放点3;储备2ＳKIPＩF1＜０发放点7；eq\o\ac(○，１）储备２SKIPIＦ1<０ｅｑ\o＼ａｃ(○，３9）ＳKIPIF１〈0eq＼o\ac（○,３２)SKIPＩＦ1〈０发放点８５．３。2第二问此问中t=20,由第一问可看出生产８天就可以满足各发放点的最低需求，现在生产20天,肯定能满足各发放点的最低需求，如果还采用上题的模型，目标是运费最少,货物越少运费就越少，那在上题的约束条件下求出来的解肯定是满足最低需求的最少运量，这让各发放点仅仅达到最低需求，而各企业还有库存不向发放点调配，这不符合实际。为了克服这个问题,让各企业在发放点没有达到实际需求时有库存就都要往发放点调运。根据这个原则,修改约束条件(1),将小于或等于改成等于，即SKIPIF１〈０；SKIPＩF1<０=1，2，3，4,５;同时修改Lｉngo程序，利用Lingo10．0重新求解（源程序和运行结果见附录3)，得到最优值为元；最优解为：SKIPIF１<0；ＳKIPIF1＜0;ＳKIＰIF１＜0；SKIＰIF1＜０;SＫIPIF1＜0SＫIＰIF1<0;SKIPＩF1〈０；SKＩＰIＦ1＜0SKIPIＦ1＜0;SKIPIＦ1<０；ＳKIＰIF１<0最优调运方案如下：第二问运量表（单位：百件)发放１发放2发放3发放4发放5发放６发放7发放8企业1480４40企业266０企业328０２00储备137037026０储备21005７0530运输路线：企业1SＫIPIF1〈０eq\o＼ac（○,26)SKIＰIF1＜０eq＼ｏ\aｃ(○，19）SＫIＰIＦ1〈０eq\ｏ\ａｃ（○,18)SKIPＩＦ1<0发放点2;企业1SKIＰIＦ１<0eq＼o\ac(○,20）SＫIPIＦ１<0发放点5；企业2SKIＰＩF1＜0eq＼o\ac(○,42）SＫIPIＦ1〈0发放点1；企业3SKＩPIF1<0eｑ\ｏ\ac(○,3２)SKIPIF1〈０发放3；企业3SKIＰIF1＜0eｑ\o＼ac(○,32)SKIPIF1〈０发放８；储备1ＳＫＩPＩF1〈0eq＼ｏ\ac(○，26)SKIPIＦ1<0eq\o\ａc(○，19)SKIPＩF1<0ｅｑ＼ｏ\ac（○,１8）ＳKIPIF1<0发放2；储备1SKＩＰIＦ1〈0ｅq\o\ａc(○,9）SＫＩＰＩF1＜0发放4;储备1SＫIPIF1<0eｑ＼o\ａｃ（○，9）SKＩPIF1〈0eｑ＼o＼ａc(○,２）SＫIPIF1〈0eq＼o\ａｃ（○,３）SKIＰIF１〈0发放6；储备2SＫIＰIＦ１〈0eq＼o＼aｃ（○，29）SＫIPIF1〈0发放1;储备2SKIPIF１〈０发放点7；eq\o\ac(○，1）储备２SKIPIF1＜0eq\o\ac(○，39）SＫＩＰＩF1<0eｑ\ｏ\aｃ(○,32）SＫIＰIF1＜０发放点85.3．3第三问问题三研究的是能否在２5天内满足各发放点的实际需求，通过计算，25天各企业生产总量＝９0*２5=２250各发放点总的实际需求=８００+900+６0０＋40０+1００0＋5０0+60０+80０=5６００总储备量=284０总产量+总储备量＝2250+2840=5０90<5６00故２５天之内是满足不了各发放点的实际需求的。解决的办法可以让企业增产。设增产后企业1、２、3的产量分别为ｘ、ｙ、z，增加约束条件SKIPＩF1<0；SKIＰIF１〈0；SKIPIF1〈0；将约束条件(2）改成SＫIＰIF1<０，SKIPIＦ1＜0＝1，２，３，4,5,6，,7,8；重新编写Lｉｎgo程序，利用Lingo求解（源程序和运行结果见附录4）,得到解决方案为让企业３增产，日产量由原来的２0百件增加到4０.4百件，得到最优值为元;最优解为：x＝4０;y=30；z=40。4；SKＩPIF１<0;SKIＰＩF1〈0；ＳKＩPIF１〈0；ＳKＩPIF1〈0；SKＩPＩF1<0；ＳKＩPIF1<0；SKＩPIF1〈０ＳＫIPIF1<0;SＫIPＩF1＜0;SKIＰIＦ1<0SKIＰIF1<０；SKIPＩF１<0；最优运输方案为：第三问运量表(单位:百件）发放1发放2发放３发放4发放5发放6发放7发放８企业18００32０企业2７6050企业3580410１00储备1３7058050储备257０6３0运输路线：企业１SＫIPＩＦ1〈0eq\o＼aｃ（○,２6)SKIPＩF１<０eq\o\ａc（○，1９)ＳKIPＩF1<０eq\ｏ\ac(○，１８）SＫＩＰＩF1<0发放点2;企业1SＫIＰIＦ1＜0eｑ\o\aｃ（○,20）ＳＫIPIF１＜0发放点5；企业2SＫＩPIF１〈0eｑ\o\aｃ（○,42)SKＩPIF1〈０发放点1；企业2SKIPIF1＜0eq\o＼ａc（○,4２)SKＩPIＦ1〈0eq\o\ac（○，15）SＫＩＰＩF1〈0ｅq＼ｏ＼ac（○,18）ＳKIPIF１〈0发放点２;企业3SKIPIF１<0eq＼o\ａc(○，３2)SKIPＩF1<0发放3；企业3SＫIPＩF1〈0eｑ\o＼ac(○，1）SＫＩPIF1＜0eq\ｏ\ａｃ（○,３3）SKＩPIF1<0发放6；企业3SKＩPIF1<0eq＼ｏ\ac(○,32)ＳKIPIF1<０发放8；储备1SKIPIＦ1〈0eq\ｏ\ac（○,9)ＳKIPＩＦ1〈０发放4;储备１SKIＰIF1＜0eｑ\o\ａc(○，2６）SKIPIF1<0eｑ\o\ac（○,１９）SKＩＰＩF1＜0发放５；储备１SKIPIF１<0ｅｑ\o＼aｃ(○，９)ＳＫIPＩＦ1＜0eq＼o\ａc(○,2）SKＩPIF1<0eq\ｏ\ａc(○,3)ＳＫIPIF１＜0发放６;储备2SKＩPIF1〈0发放点7；eｑ＼ｏ\aｃ（○,1)储备2SKＩPＩＦ1<0eq＼o＼ac（○，39）SＫIPIF1<0eq\ｏ\ａc（○，32)SＫIPＩF１〈０发放点85。3。4第四问31，927，2623，25，11--14--第四问考虑的是灾害发生时可能造成交通中断,以下四段路段交通中断:31，927，2623，25，11--14--前三问中只涉及到了eq\o\aｃ(○，26）到eq\o＼ac（○,2７）、eq\o\ac(○，９）到eq\o＼ａc(○,３１）这两段路中断,其余的路都没有中断，而其余两条中断的路前面的方案中也不经过。考虑中断的两条运输路线:储备１SＫＩPIＦ1＜0eq\o\ac(○,２6）SＫＩPIF１＜0eｑ＼o\ac(○,19)SＫIPIF１〈0发放5;储备1SＫＩPIF１<０eq＼o\ａc(○,9）SKIPIF1〈0发放4；找储备１到发放5,储备1到发放4的次最短路,发现和原来相差很大,即找的新路线运费和原来相差很大，这可能会引起运输方案的改变，如果继续用原方案计算的话,误差将会很大,所以考虑修改权数矩阵，重新计算前三问。重新修改Lingo程序，利用Lｉｎgo求解，第一问的源程序和运行结果见附录5，第二问的源程序和运行结果附录6,第三问的源程序和运行结果附录7，得到如下运输方案.第一问答案：最少运费：元运量表(单位：百件）发放１发放2发放３发放４发放5发放6发放７发放８企业1440企业2３00企业3２4０储备1160１1０3002６0160储备228080310５30运输路线：企业1SKＩＰＩF1〈0eｑ＼ｏ\ａc(○，２6)ＳKIPIF1〈0ｅq＼o\ａｃ（○，19）ＳKＩPIF1＜0eq\ｏ\aｃ(○，１８）SKIＰIＦ１<0发放点2；企业2ＳKIPIF1<0eｑ\o\aｃ（○，4２)ＳKＩＰＩF1＜0发放点1；企业2SKIPIＦ１〈0eq\o\ac（○，42)ＳKIPIF１<0eｑ＼o\aｃ（○，28)ＳKIPIF１〈0发放点7;企业３SＫIPIF1＜0eq\o\ac(○，32)SKIPIF1〈0发放4;企业3ＳKIPIＦ1〈0eｑ＼ｏ\ac(○,1)SKIPIＦ1＜０eq\ｏ\ac(○，３3）ＳKIＰＩF1＜0发放点6；企业３SＫIPIF1<０eq＼o\ac(○,３2）SKIＰIF1<０发放点8;储备1SＫIPIＦ１＜0eq＼o＼ａc（○,40）SＫIPIF1＜0eq\ｏ＼ac(○，６）ＳKＩＰIF1＜0eq\o\ａc(○,41）ＳKIPIＦ１〈0eq＼o\ac（○,４2)ＳKIPIＦ1<0发放点１；储备1ＳKIPＩＦ1〈0eq＼o\ac(○,２6)SKＩPＩＦ1＜0eq\o\ａc（○，１9）SKIPIF1〈0eq＼o\ac（○,18）SKIＰＩF１〈0发放点2；储备１SKＩＰIＦ1<0eq\o\aｃ（○，26)SKIPIF1〈0eq\ｏ＼aｃ（○，19）SKIPIF１〈0发放点5；储备1ＳKIPIF1〈０eｑ＼o\ac(○，9)SKＩＰＩF1〈0ｅq\o\aｃ（○，2）SKＩＰIF1<０eｑ\o＼ac（○，３)SＫIPIF１＜0发放点6;储备1ＳKＩPＩF１<0ｅq\ｏ\ａc(○，４0)SKＩPIF1＜0eｑ\o\ａc(○,6)SＫＩＰIF1＜0eq＼o\ac（○,4)SKIＰIＦ1<0发放点７;储备2SKIPIF1＜0eq\o＼aｃ(○,3９）SKIＰIF1＜0eq\o\ac(○，32)SKＩPIF1<0发放点3；储备2SKIＰＩＦ1<0ｅq\ｏ\ac(○,3９)SKIPIF1＜0eq＼o\aｃ(○,３2)ＳＫＩPIF１〈0发放点４；储备2SＫIPＩF１＜０发放点７;eq\o＼ａc(○，1）储备2SKIPＩＦ１〈0eｑ\o\ac(○,39）ＳKIPＩF1＜０eq＼o\ac(○，3２)SKＩＰＩF1<０发放点8第二问答案：最少运费：元运量表（单位：百件)发放１发放2发放3发放4发放5发放6发放7发放8企业1８50７0企业2660企业３16０３２0储备1100４2046020储备２120５5０5３0运输路线：企业1SKIPIＦ1＜０ｅq\o\ac（○，２6)ＳＫＩＰＩF1＜0eq＼ｏ\ac(○，19）ＳKIPIF1〈０eq\o\ac（○,１8)ＳKIPＩF1〈0发放点2；企业１ＳKＩPIF1〈0eq\ｏ＼ac（○，20）SＫIPＩF1＜0发放点５;企业2ＳＫＩＰＩF1<0eq\o＼ac(○,4２)SKＩPIF1〈0发放点１；企业3SKIＰIF1＜0ｅｑ\o\ac（○，32)SＫIＰIF1〈０发放点3；企业3SＫIＰＩF1＜0eq＼o＼ａc（○,32)SKＩＰIF1<0发放点４；储备1ＳＫIPIF1〈0eq＼o\ａｃ（○，4０)SKIPＩＦ1<0eｑ\o\ａc（○,6）ＳKIPＩF1〈0eq\o\ａc(○，４1）ＳＫIPＩF1＜0eq＼o\ac(○，42）ＳKIＰIＦ1<0发放点1；储备１ＳＫIPIF1＜０ｅｑ＼o\aｃ(○，26)SＫＩＰIF1<0eq\o\ａc（○，1９)SKIＰIF1＜0发放点5；储备1ＳKIPＩＦ１<０ｅｑ\o\ac（○,9）ＳKIＰIF1<0ｅq\ｏ\aｃ(○,2）SKIPIF1〈０eq\o\aｃ(○，３）SKIＰIＦ1<0发放点6;储备1SKＩPＩF1〈０eｑ＼ｏ\aｃ（○，40）ＳKＩＰIF１<0eｑ\o\aｃ(○，6)ＳKIＰＩF1〈0eq\ｏ\ac（○，4)SKＩＰIF1〈0发放点7；储备２ＳKIPIF1<０eｑ\o\ａc（○,39）ＳＫIＰＩＦ1<0eq\o\ac（○,32）ＳKIPIF１＜0发放点3；储备２SKＩPIF1〈0发放点7；eq\o\ａc（○，１）储备2ＳKＩPIＦ1〈0ｅq\o\ａc（○,39）SＫIＰＩF1<０eｑ\o\ac（○，32）SＫＩPIF1＜0发放点8第三问答案:最少运费：元运量表（单位：百件）发放1发放2发放3发放4发放５发放６发放7发放８企业1800360企业2760５０企业337０68０储备１540460储备２5805705０运输路线：企业1ＳKIPＩF１<0ｅｑ\o＼ac(○，26）SＫＩPＩF1〈0eq\o\ac（○，19）ＳKIＰIF1<0eq\o\ac（○，１8）SKＩPＩF1<0发放点２;企业１SＫIPＩF1<０eq\ｏ\aｃ(○,２0）SKIPIF1〈0发放点5;企业2SKIPIＦ１＜0eq＼o＼ac(○,４２）SKIＰIF1〈0发放点1;企业２ＳKIＰIF１＜0ｅq\o\ac(○,42)SKIPIF1＜0ｅq\o\ac（○，１５)ＳＫIＰIF1〈0eq＼ｏ＼ac（○，１８)SKIPＩF１〈0发放点２企业3SKＩPIF1<0eq＼ｏ\ac（○，３2）SKIＰＩＦ１<０发放点4;企业3SＫＩPIF1＜0eq\o\ac（○，３２)ＳKＩＰIF1<0发放点８；储备1ＳＫIPIF1<０eq\o\ac(○，26）SKIPIＦ１〈０eq\o\ac（○,１9）SＫＩPIF1<0发放点5;储备1SKIPIF1＜０eq\o＼ac（○,9)SKＩＰIF1＜０eq\o\aｃ（○,2）SＫIPIF1〈０ｅq\o＼ac(○,3)ＳKＩPIＦ1＜0发放点6;储备２ＳKIPIＦ１<０ｅq\ｏ\ac（○，３9)SKＩPIF１〈0ｅq＼ｏ＼ac(○，32)ＳKIPIＦ1<0发放点3；储备2SKIPIF１＜0发放点7；eq＼ｏ\aｃ（○，1）储备2SKIＰIF1〈0ｅq＼ｏ\ac（○，３9）SKIPＩＦ１<0eq＼o\ac（○，3２)SKIPIF1〈0发放点８六、模型改进与分析6.1模型的改进观察生产企业，发放地点及储备库分布图,可看出有些企业与发放点之间的距离很远运费也很贵，在实际情况中要求尽快和尽量少的运费，也不会从这些企业调运货物到离它很远的发放点。所以我们考虑根据就近原则,对各发放点和企业区域划分。分区原则：按照权数图中各发放点到各企业的最少运费相比较,离哪个企业的运费最少就把该发放点归到那个企业所在区,这样可以按企业所在地将发放点分成三个区；同理，可以按储备库将发放点分成两个区。分区结果:企业1企业1发放点2、5企业2企业3储备库4储备库5发放点1、7发放点3、4、6、8发放点2、4、5、6发放点1、3、7、8分完区以后,就认为每个发放点的物资只从同一区的企业或储备库调运,每个企业或储备库之调运货物到同一个区的发放点,即物资调运只发生在同一个区的企业或储备库到发放点之间。这样就可以减少所设的变量，减少运算量,从而达到简化模型的目的。仅设SKＩＰＩF１〈0,SKIPIF１＜０,SＫＩPＩF1〈0，ＳKＩPＩF1<0等１6个变量,比原来的４0个变量减少了一半以上,根据所设变量,以第一问为例,编写Lingo程序(第一问的源程序和运行结果见附录8）,利用Liｎｇo求解，结果与第一问相同，区域划分效果很好。6．２模型的分析利用图论有关知识把复杂的交通路线图简化为带权图，再根据权的大小及Dijkstra算法求得两点的最短路径,即为调运路线，既有理论依据，又符合实际要求.假设企业与储备库之间没有调运，可能忽略了其它的调运路线,使得调运方案具有局限性，从而使总路费存在误差。考虑在调运过程中与时间无关的情况，但是在实际情况中，如果遇到紧急情况时，可能使得救灾物资短缺或者路段损毁,从而被迫改变调运路线,导致运费改变。七、意见和建议在对救灾物资的调运方案的优化问题的研究过程中，我们发现了应对灾害的紧急调运物资的一些可行的措施，故在此给出建议。增加物资的战略储备。灾害的发生属于突发事件,准确预测灾害的发生比较困难,所以增加战略储备，有助于政府能够及时应对灾害的发生。合理布局储备库的分布。合理的储备库分布可以减少物资的运输时间,提高其运输效率.提倡直线运输。按照实际情况选择最短的运输路线，避免物资的迂回倒流等不合理现象，减少运输的中间环节。开辟绿色通道保证物资运输的畅通.参考文献：[1]邓成梁《运筹学的原理和方法》华中科技大学出版社2001年版[２］朱道元《数学建模案例精选》科学出版社2００3年版［3］湖北大学生建模竞赛专家组《数学建模》华中科技大学出版社２006年版［4］王国丰《粮食应急运输调度问题研究》河南工业大学学报2008年３月版[5]袁新生《linｇｏ和eｘcｅｌ在数学建模中的应用》科学出版社2007年版附录：附录1:Dijｋstra算法求最短路源程序W=［……]%Ｗ为的权数矩阵n=ｓｉｚe（W,1)；ｆoｒ（i=1:n)ｌ(ｉ)=W（1,i）；z（i)=１;enｄfor（i=１:n）for（ｊ=1：n)if（l(i)〉l(j）＋W（j,ｉ))l（i）=l(j)+W(ｊ,i）；z（ｉ)＝ｊ;eｎｄ；end；eｎdlz附录2：第一问Ｌinｇo程序方法1:mｏｄeｌ:！5发点８收点运输问题;sets:warehoｕｓes/wh1。。wh５/：ｃapaｃity；ｖｅndors/v１。．v8/：demanｄ；linkｓ（warehouses,ｖenｄorｓ）：ｃｏｓt,voｌｕme；eｎdｓeｔs！目标函数;min=@ｓum(links：cost*voluｍe)；！需求约束;@for（vｅnｄors（J):＠suｍ(warehouｓes（Ｉ）：voｌumｅ（I,J））＞=ｄｅmaｎd（J）)；！产量约束；＠ｆor（waｒｅhouseｓ(I）：@sum（vｅｎdors(J）：ｖｏlｕme（Ｉ，J））〈=capacity（I））;!这里是数据；dａｔa:capacｉty＝4403０02４0100０120０；ｄemａnd=４605502８032030０２６0470530；cost=1８４815０040８０2３０４１560344４2５683７2０696188４36７21８96２4７2３０3６14１63312268８３984１４７6900４04４1７4０１96811１622７2198028801104２０402２４4２1602５2０146434202１00１５２44０0826767441７４0;enddaｔaend方法2：min=1848*x１１+１５00＊x12+４080*x13+２３０4*x１4＋1560*ｘ１5+３44４*x16+2568＊x１7+３7２０＊x18+６９６＊x2１＋１884*x22+３6７2＊x２3＋1８96*x24＋247２*x２5＋30３6＊x2６+1416＊x2７+3３12＊ｘ２８＋2６8８*x３1+39８4＊x３2+1４76＊x33+9０0*ｘ34＋40４4*x35+１７4０*x36+1968＊x37+1116*x38+2272*x41+1９8０*x42+2880*x４3＋１１０4＊x４4+2０４０*ｘ45＋22４4＊x4６+2１60＊x47+25２0＊ｘ48+１46４*x51＋3420＊x５2+２100*x53+1５24＊x５4+4０08＊x５5＋２964＊x５６+74４＊x５７+１740*x5８；t＝8；x11+ｘ12+x１3+x14+x１5+x16+x１7+x18<=12０+40＊t；x2１+x２2+x23＋x24＋ｘ2５+x２6+x27＋x２8〈=60+３0*t；ｘ31＋x3２+ｘ3３+ｘ３4+ｘ3５+x36＋x３7+ｘ３8〈=80+２０＊t；x４1+x42+x４3+ｘ4４+x45+x４6+x４7+x48〈=1000;x５1+x５2+ｘ５3+x54+x55+x5６+ｘ5７+x58<=12００；x１1＋x2１+x31＋x4１+ｘ51〉＝5０0-40；x１2+x22+x3２+x42+x52>＝600-50;ｘ13＋ｘ2３+x33+ｘ4３＋x5３＞=300-20;x1４+ｘ24＋ｘ34+ｘ44+ｘ54>=3５0—30；x１5＋x25+x３５+x4５+ｘ55〉=400-10０;ｘ１6+ｘ26+ｘ36+x４6+x5６＞=3０0-40；x17+x27＋x3７+ｘ47+x57〉＝５０0-30；ｘ18+x28+x38＋x48+ｘ58〉=６00－70;ｘ1１+x２1＋x31＋x4１+x51<=８00-40；x１2+x２2＋x32+x42+x52＜＝９00-50;x１３+x23+x3３＋x43+x53〈＝600－2０；x14+x24+ｘ34＋x４4+x54〈＝400—３0；x１5+x25+x３5+x45+ｘ５５<＝１0０0—１00;x16＋x２6+x３6＋x４６+x56<=50０-40;x１7+ｘ2７+x37+x47+x57<＝600—30；x１8+x28+x38+x４8+x58<=8００-70;运行结果：附录3：第二问Ｌｉngo程序ｍｉn＝1848＊x１1＋1500*x12+4０80＊x13+２30４＊x14＋1５6０＊x15+3444*ｘ１6+2５68＊x17+３720＊x1８+６９6*x21+１884＊ｘ22+3６72*x2３＋１８96＊ｘ2４＋2472＊ｘ25+3０3６*x２6+１416＊ｘ２7＋３312＊x28+２6８8＊x３1+３9８4＊ｘ3２+1４76*x33＋900＊ｘ34+4044*ｘ35+1740＊x3６＋１968＊ｘ37+１1１6＊ｘ38+２27２*x41+1９８0*x４2+２８80*x４3+1104＊x44+204０*ｘ45+2２44*x46+2１６0*x47+252０＊ｘ4８＋１46４＊x5１＋３4２0*x５2+2１0０*ｘ53＋1524*x54+400８＊x55+296４*ｘ56+744＊x57+1740＊ｘ58；ｔ=20；x11+x1２+x13+x14+x15＋ｘ16+x1７+x18＝120+4０*t；x21+x22＋x23+x24＋x25+x26＋x27+x2８=60+3０＊t；x31+ｘ３2+x33+ｘ3４+x35+ｘ36+x3７+ｘ3８=80+20＊t；x41+ｘ42+ｘ43＋ｘ4４＋ｘ45+ｘ46+x47＋x48=1000；x51+x52+x53+x54＋x55+x５6+x57+x58=１２0０;ｘ１1+x２1+x31+x41+x51〉=500-40;x１2＋x22+x32＋x42＋x5２>=６00-5０;ｘ１3+ｘ23+x３3＋ｘ43＋x53＞=300－20;x１４+x24+x34+x44+ｘ54〉=350-３0;x1５+x2５+x35+x4５+x55〉=4０0-100；x16＋x26+ｘ36＋x46+x56＞=300—40；x17+x27＋x37＋x47+x５7〉＝500—3０；x１8+ｘ2８+x38+ｘ４8+x５８＞=６00-70;x11+ｘ21+ｘ3１+x４1＋x５1<=80０-4０;x12+ｘ22+x32+ｘ４2+ｘ５2<＝900-５０；x13+ｘ２3+x33＋x43＋x53〈=6００-20；x1４+ｘ２4＋x34+x４４＋ｘ５4<=400-30;ｘ15＋ｘ25＋ｘ35＋x４5+ｘ55〈=10０0—１０0；ｘ１６+ｘ2６+x36＋x46+x5６<=500-40；ｘ17＋ｘ2７＋ｘ37+x４7＋x5７<=60０—３0；x1８+ｘ28＋x38+x４８+x５8<=800-70;运行结果：Ｇｌｏｂaloptimａlｓｏlｕtioｎfound。Ｏｂjｅctiｖevalue:5719440。Totaｌｓolveｒitｅrａtions:17VariableVaｌueＲeduｃedＣｏｓtX11０．000０00564。0000X12480．000０0。00０00０X１３0．0000002１６0。００0X1４0．０00000１68０.０00X15440.0０00０。000000X160。00０0０01680。０0０X１７０．0０0000２004。0０0X１80。０000002160．000X21660．00000.0000０0X220．000000972。0000Ｘ230.0００0002３4０．0０0Ｘ240.0０00０01860。０００X2５０．0000001５00。０0０X2６0.00０000１860.０００X270。0００0０0144０。０00X2８0.0０0０00２340。０00Ｘ３10.０0００0０18４８．0０0Ｘ3２０.00000０2９2８．０00X33２80。00000。０0０000X34０.０000００72０。0000Ｘ350.00０0０0２9２8。００0X360．000000４20。0０00Ｘ370.000000184８.0００X３8200．0００0０。000０００X4１０。00０000５０8.00０0X423７0。０0０00.００0000X4３0。0０00０04８0．０00０X44３７０．0０00０。０00000X4５0．０00０000。0００000X46260.00０0０.00000０Ｘ470．000000１116．0０0X480。00０000４80.00０0Ｘ51100.０0000.0０0000Ｘ５２0.000０00174０.000X5３０.0０００００0.000０0０X５40．０000０07２０．０000X550.０00０002268.00０X5６0．０0０000１０20．０00Ｘ57５70.0００00。00０000Ｘ58530。00000.０000０0Ｔ20。000００0。0０0０00附录４：第三问Liｎgo程序ｍｉn=１848*x１1+1５００＊x12+4080＊x１3＋2304*x14＋1560＊x1５＋344４*x16＋２568＊x１7+３72０＊x１8+69６＊x２1+１8８4＊x22+367２＊x２3+1８９6*x２４+24７２＊x2５+30３6*ｘ26＋14１６＊x2７＋331２＊ｘ28+2688＊ｘ31+３9８4*ｘ32＋14７6*x３３＋9０0＊x3４+40４4＊x３5+1740＊x36+1968＊x37+１116*ｘ３8+2272＊x４1+1980＊x4２＋28８0*ｘ43＋１104＊ｘ44＋２040＊ｘ45+２244＊x46＋21６０＊x４7＋2５2０*x48+14６4＊x5１+３420＊x５2+2100*x5３+１５24*ｘ54＋4008*x５5+２９64＊x56+7４4＊ｘ5７＋1740*x5８;t=2５;x>＝４0；y>=30;z〉=2０;x１1＋x12+x13+x１4+x15+x16＋x17+x1８=１２0+ｘ*t；x21+x22+x23＋x24＋x25+x2６+x27+x2８=60+y＊t；x31+x32+ｘ33+x34+ｘ35+x36＋x3７+ｘ38=８０+z＊t;ｘ41+ｘ4２+x４3+x44+x４５＋x4６+x47+ｘ４8＝1000；x51＋ｘ52+x53+ｘ54＋x55＋ｘ56+x５7+ｘ58＝120０;x1１＋x2１+x31+ｘ4１＋ｘ51=8０0—4０；x１２＋ｘ22＋ｘ３2+x4２+x５2=9０0-50；x1３＋x23+x33+x43+x５3=60０-2０；x１4+x24+ｘ34+x44+ｘ５４=4０0-３0;x15+ｘ25+x35+x45+x５５=1000－1０0;x1６＋ｘ26+x36＋x46+x5６＝５00－4０；ｘ17+ｘ２7+x37+x4７+x57=６00—30;x１８＋ｘ28+x３8+ｘ48+x58=8０0－7０;运行结果:Ｇlｏbalopｔimalsolutionfoｕnd。Oｂｊeｃtiveｖaｌｕｅ：7227600。Totalｓoｌveriteratioｎs：１5ＶaｒｉablｅValueＲedｕceｄCoｓtX１10。00０0001536。000X12８00.０0000.0０００00X１3０.0０000０2580。000X140。000000１6８０．000X１5320。００00０．0０0000X160。０000001680。000X1７0．０000002424．0００X1８0.000０00２580．０00X21760.00０00。000000X2250.000000。000000X２30.00000017８8。000X2４0。００00008８8。0000X２50.０0０00０528.００00X２60。000000８88.0000X２70.０0０0００８８8。０0０0X２80。00000０１788.00０Ｘ31０。００0000２400.０0０X３20．00０0002５０8。000Ｘ３3580.00000．０000０0X3４０．0００000300．０00０X3５0。000００02508.000X36410.00000。000００0X3７０.0０00001８48。000X３８1０0.000０0．00０0０0X410.0000001480.0００X4２0．0０00000.０00000Ｘ430.0０0000９00.0０00X44370。0000０。000000X4558０。000００.00００0０X４6５0.000000.0０0000Ｘ470．０00０00１536．000X48０。0０000090０。00０0X510.000０００552。０000X５20。00０00０1３2０.000X５３0.00０00００．０0000０X５40.0000０0３00。０000Ｘ5５0。00０000１848．０００X560.000000600.０000X5７57０。０0０0０.000０00X５8630．00000。０00000T２5.０0００00．0000００Ｘ40.0000０0。００000０Y３０。000000．00０000Z40。40000０．000００0附录5:第四问中8天的程序min=1８4８＊x1１+150０＊x12+5412＊x1３＋4836＊x1４+１５60＊x１5+4１04*x16+2568＊ｘ1７＋505２*x１８＋６９6＊ｘ21+１884＊x22+38７6＊x23+３300＊x24+2472*x2５＋303６＊x２6+1416＊ｘ２7＋35１6＊x2８+２688＊ｘ31+４64４*x３2+1476*ｘ3３+９00*x34+50２０*x35＋１74０＊x3６+19６８*x37＋111６*x3８＋2272＊x41＋３３１６＊x4２+37２0＊x43+314４＊x44＋27７6＊ｘ45+2２44*x４6+21６0＊x4７+3300*ｘ48+１4６4*x51＋3４20＊ｘ５２+2１00＊ｘ５3+１52４*x54+4008＊x5５+２964*x56＋７44*x5７+1740＊x５８;t=８；x１1+x1２+ｘ13+x1４+x15＋x1６＋x1７＋x1８<=1２0+４0＊t；ｘ21+ｘ22+x２3+ｘ２4+x25＋x２6+ｘ２7+x28〈=60＋３０＊t；x３1+x３2+x3３+x34＋x35+x36＋x３７+x３8<=80+20*t；x41+ｘ4２+ｘ43+x44+x４5＋x46＋x４7+x48<=1０00;x5１＋x52+x53+ｘ5４+x５５+x5６＋x57＋x58〈=１20０；ｘ11+x21＋ｘ31+ｘ41+ｘ5１〉=5００－40;ｘ1２+x22+x32+ｘ4２＋x５２>＝６00—50；x13+x23+x33+x43＋x5３〉=３00—20；x1４+x2４+x34+x44+x54〉=350-３０；x１５＋x25+x３5+ｘ45+x55〉=400-１00；ｘ16+ｘ２６+x３6+x４6+x5６>=３00-4０;x１7+ｘ2７+ｘ37+ｘ47+x５７＞=500-30；x18+x28+x３8+x48+x５8〉=600－70；ｘ１１＋x２1+ｘ31+ｘ41+x51〈=800—40；x１2+x22+x３2+x42+x５2＜＝９00-５0;x１3＋x23+x3３+x43+x５3