关于防洪物资调运的优化模型.doc

《关于防洪物资调运的优化模型.doc》由会员分享，可在线阅读，更多相关《关于防洪物资调运的优化模型.doc（13页珍藏版）》请在三一办公上搜索。

1、关于防洪物资调运的优化模型摘 要在充分理解题意的基础上，我们将这个运输问题归结为先求最短路再进行线性规划的问题，并给出运输费用等价转换和运输地位等价转换两个转化法则，对模型的统一和简化起了关键作用.在求解最短路时，我们采用了Dijkstra和Floyd两种算法，并利用Matlab软件进行计算.分析我们的线性规划模型，由于变量和约束条件较少，利用Lingo软件可以很容易给出最优方案.对主要问题二，我们向当地有关部门提出的调运方案为16天达到各库预测库存，总运费为335330元.在问题二解决的基础上，又对模型作了推广，即在满足预测库存量后，继续调运。那么20天后各库库存量为库名仓库1仓库2仓库3仓

2、库4仓库5仓库6仓库7仓库8储备库1储备库2库存量50060045035080030050060034802600模型的适应度良好，在遇到如问题四的紧急情况时，模型仍然适用，从而大大拓广了模型的适用范围.在论文中，我们还对所建立的模型的优缺点和需要改进的方向进行了讨论.一、问题重述（略）二、基本符号说明与基本假设2.1 基本符号说明：提供物资的点：需要物资的点：从运往的运量（）：可以提供的物资量：处接收的物资量：单位距离单位百件数的运价：和之间的最短路（）：总运费2.2 基本假设1、 假定天气情况对公路运输的影响不大，可以忽略不计；2、 从分布图上可以看出最远的两个运输点之间的距离也不过是几百

3、公里，按照现在的交通运输水平，我们可以绝对保证物资在一天内运到，这样库存就不再受到最大容量的约束；3、 假定无论运多少物资，我们都有足够的车辆保证运输量；4、 假定提前储备的时间充分，无需在短时间内完成；5、 假设各库达到预测库存后，企业就不再生产.三、问题分析和基本思路3.1 问题分析和建模思路考虑问题的题设和要求，我们要解决的是防洪物资调运优化配置问题.对题目仔细地分析后，我们决定首先建立该地区公路交通网的数学模型.各离散的交汇点之间的关系可以比较容易地用邻接矩阵表示出来，难点是图中有两种不同的公路，它们的单位运输费不同.我们分析了两者之间的联系，根据运输费用等价转换法则，将高等级公路转化

4、为普通公路，这样模型得到了统一.下面的问题便是一个典型的运输问题.我们先求出图中各企业、仓库及储备库之间的最短路，进而利用线性规划模型计算出运输方案.在求解运输方案时，我们根据运输地位等价转化法则，将现有库存量多余的仓库转化为企业，进一步简化了模型.又考虑到要重点保证国家级储备库，我们分别从时间和费用两方面考虑，给出优化方案，并进行了比较. 由于数据量较大，我们借助计算机对模型进行最优求解.3.2 思路流程图下面的思路流程图是我们文章结构的一个缩影，它完整而形象地反映了我们文章的建模思路.图1：建模思路流程图运输费用等价转换法则公路交通网数学模型最短路问题Dijkstra算法Floyd算法线性

5、规划模型最终调运方案Lingo软件运输地位等价转换法则模型优缺点评价四、模型的准备运输费用等价转换法则：对于高等级公路线上的任意两点、之间的长度，根据高等级公路单位运费（2元/公里百件）求得对应的总运费为；设与等费用的普通公路的长度为，又根据普通公路单位运费（1.2元/公里百件），我们得到如下等式： .从而有 .由此，我们把两种公路的交通网化归为普通公路交通网，使模型得到了统一.运输地位等价转换法则：按照我们的调运方案，仓库3和仓库5的地位和企业其实是一样的，我们可以把它们看成是一种特殊的企业（产量为0），分别记为企业4和企业5.因此，我们就把运输问题化为有5个提供物资的点，8个接收物资的点.

6、五、模型的建立与求解5.1 问题一：建立该地区公路交通网的数学模型我们把离散的各交汇点以邻接矩阵的模式在计算机中存储（主程序见附件2），其中0表示两节点无边直接相连，非0表示有边直接相连，且邻接矩阵中的元素以其两节点之间的距离即权重来表示.由于该矩阵太大，且其仅作为解决后续问题的一个铺垫，在此我们不再给出具体的表示，仅将统一后的交通网络图附上（说明见图注）.生产企业、物资仓库及国家级储备库分布图5.2 问题二5.2.1用两种算法求解最短路问题考虑问题的题设和要求，为了给调运方案做个铺垫，我们首先要解决的是最短调运路线问题，即离散型优化问题中的最短路问题.最短路问题是图论应用的基本问题，一般是在

7、赋权图中讨论.由问题一，我们很容易得到一张赋权图，因此，我们可以直接利用以下两种算法求解最短路问题.方法一：Dijkstra算法Dijkstra算法是一种标号法：给赋权图的每一个定点记一个数，称为顶点的标号临时标号（简称T标号）或者固定标号（简称P标号）.T标号表示从始顶点到这个顶点的最短路长的上界，P标号则是从始顶点到这个顶点的最短路长.Dijkstra算法步骤：（1）给顶点标P标号，给顶点标T标号；（2）在所有T标号中取最小值，譬如，则把的T标号改为P标号，并重新计算具有T标号的其它各顶点的T标号：选顶点的T标号与中较小者作为的新的T标号，即设若 ，则改记为顶点的P标号，于是，把中的顶点的

8、T标号修改为，显然，这里只需对与相邻的具有T标号的顶点重新T标号即可.（3）重复上述步骤（2），直到.这时即为从顶点到的最短路长.根据最短路的如下性质：若路径为至的最短路径，则必然就是至得最短路径（即动态规划中的最优性原理），求最短路径可以采用Dijkstra算法直接做出判断如下：表1 生产企业、物资仓库及国家级储备库两两之间的最短距离企1企2企3仓1仓2仓3仓4仓5仓6仓7仓8储1储2企10154125192130100企2058157158118131企301237514593102仓115458060仓2125157.0139165仓31230175仓419215875092127仓51

9、301390170仓61450113仓711860018062仓8931130145储1100131165921701800储2102175127621450注：1）表中数据均已换算成普通公路区间距离，单位：公里；2）对于有的显然不会影响最短路判断的数据，我们就不再赘述了.由表中数据和最短路算法可以粗略得出调运量及调运方案如下：1） 从企业2的库存中运300百件至仓库1，则仓库2达到预测库存；2） 将企业2的剩余库存60百件及生产了5/3天（假设三个企业从同一时刻开始24小时不停生产，即为40小时）后的产量全部运至仓库7，则仓库7达到预测库存；3） 从企业1的库存中运330百件至仓库2，则仓库

10、2达到预测库存；4） 从企业3的库存中运120百件至仓库4，运20百件至仓库6，运100百件至仓库8，则仓库4、仓库6、仓库8都达到预测库存；5） 将仓库3的多余库存150百件、企业3的剩余库存160百件及生产了19.5天后的产量全部运至储备库2，则储备库2达到预测库存；6） 将仓库5的多余库存400百件、企业1的剩余库存270百件及企业1在19.5天内生产的产量中抽1000百件运至储备库1，则储备库1达到预测库存.我们最终得到总运输成本约为：方法二：Floyd算法Floyd 算法的基本思路是：从图的带权邻接矩阵A=nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(

11、1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n).矩阵D(n)的行列元素便是号顶点到号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵来记录两点间的最短路径. 递推公式为： D(0)=A；D(1)=dij(1)nn，其中dij(1)=mindij(0),di1(0)+d1j(0)；D(2)=dij(2) nn，其中dij(2)=mindij(1),di2(1)+d2j(1)；D(n)= dij(n) nn，其中dij(n)=mindij(n-1),di, n-1 (n-1)+d n-1,j(n-1)；采用循环迭代可以简便

12、求出上述矩阵序列，具体算法如下： ：用表示，其含义为到的最短路径存放在数组第个存储单元中.：对应于的路径上的后继点，最终的取值为到的最短路径上的后继点. 输入带权邻接矩阵A=)nn 1）赋初值 对所有；当时，否则；. 2）更新 对所有，若，则转3）；否则，继续执行3）. 3）重复2）直到.根据上述算法，我们的得到了图的距离矩阵D和后继节点矩阵R（见附件5），现在把对我们有用的数据整理如下：表2 生产企业、物资仓库及国家级储备库两两之间的最短距离企1企2企3仓1仓2仓3仓4仓5仓6仓7仓8储1储2企10148267154125340192130287214310100268企2148023358

13、157306158206253118276131148企326723302243321237533714516493167102仓115458224016329721621231160267189122仓21251573321630405257139352223375165285仓33403061232974050148410268237166240175仓419215875216257148026219918911892127仓51302063372121394102620357272380170334仓62872531453113522681993570302113187247仓72141

14、1816460223237189272302020718062仓8310276932673751661183801132070210145储1100131167189165240921701871802100183储2268148102122285175127334247621451830我们通过Dijkstra算法求得的部分最短路数据和计算机用Floyd算法得出的完全吻合，这就基本保证了我们最终调运方案的可靠性和准确性.根据上述表格中数据得出简化的公路交通图如下：5.2.2用线性规划模型解决运输分配问题设有个提供物资的点，可以提供的物资量为，所有物资运送到个接收点，在处接收的物资量为（）.又

15、设表示从运往的运量，表示和之间的最短路，表示单位距离的运价，用表示总运费，则有目标函数： （5-1）下面我们来分析题目中的一些约束条件：首先，各个企业原有库存、新生产的产量和仓库原有的多余预测库存的量应该满足国家级储备库和其它各个仓库的需求，因此，总的供应量总的需求量，即 （5-2）其次，运输量只需让各个仓库都达到预测库存即可，于是得到如下两个约束条件： （5-3） （5-4）综上，可以建立如下的数学模型 （5-5）由于问题可以转化为5个企业向8个仓库运输问题，于是，对于上述线性规划模型来说，由附件1可以很容易得出企业各自的供应量和仓库各自的需求量.设 根据此模型，我们用Lingo语言编写了通

16、用程序（见附件4），便于多次调用.根据题目要求，我们首先考虑国家储备库的物资运输问题.方案一我们发现5个企业的总库存为2010大于储备库的总需求量1700，所以在满足最短时间满足储备库的条件下，可以一天达到.利用Lingo程序，算得总费用为240672元.但考虑到这种方案仅注意到时间，经济效果较差，不予采用，所以也不再给出分配方案.方案二我们发现，储备库和企业1、企业2、企业3之间路程最短，所以我们对方案一进行了修正，以企业1、企业2、企业3在最短时间（3天）内生产出需求量为条件进行分配.此时企业最短距仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）需求量储备库1100131167240

17、1701000储备库2268148102175334700供应量720450560150400用Lingo软件解得企业供应 量仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）储备库1720280000储备库2014056000总费用为223824元.此时企业2有库存30，企业1、企业3为空.方案三在此我们不以最短时间运满储备库为条件，而是先假设企业1、企业2、企业3的产量都可以满足需求，由题目假设与分析知，库容量已不再约束，所以有企业最短距仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）需求量储备库11001311672401701000储备库2268148102175334700

18、供应量170017001700150400用Lingo软件解得企业供应 量仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）储备库110000000储备库20070000总运费为205680元，用时10天.此时，企业1、企业3为空.下面我们解决其它仓库的运输调运问题，此时，我们可以不再受时间约束，仅以运费最小为目标，沿用上面方案三的思想，各仓库的总需求量为980，所以企业最短距仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）需求量仓库115458224297212300仓库2125157332405139330仓库419215875148262120仓库628725314526835

19、720仓库7214118164237272110仓库8100131167240170100供应量980980980980980用Lingo软件解得企业供应 量仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）仓库10300000仓库23300000仓库40012000仓库6002000仓库70110000仓库80010000总费用为111396元.结合上述方案二、三，总时间分别为16天和22天，总运费分别为335220元和317086元.结合时效性和经济效果比较这两个结果，我们选取方案二向当地有关部门提出建议.至此，我们顺利完成了调运防洪抗涝物资的工作.问题三 20天后各库库存量 从问题二

20、的结果可看出，在16天内便达到了各库的预测库存，在此我们继续对上述方案进行扩展。20天后三个企业可提供的货物量分别为350、130、100.考虑到仍然要优先考虑国家储备库，则20天后各库库存量如下表库名仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库2库存量50060045035080030050060034802600问题四 因洪水交通中断后的模型由于洪水冲毁了四条路，即这些交汇点之间断开，所以我们只需对求最短路的Matlab主程序数据稍加修改即可得到下表：表3 修改后的生产企业、物资仓库及国家级储备库两两之间的最短距离企1企2企3仓1仓2仓3仓4仓5仓6仓7仓8储1储2企10

21、148378154125451403130342214421201276企2148025358157333328206253118293131148企337825302243871237541814516493187102仓115458224016329724921231160267189122仓21251573871630460412139410223430276285仓34513331232974600148509268237166310175仓4403328752494121480461220189118262127仓51302064182121395094610372272379231

22、334仓63422531453114102682203720302113187247仓721411816460223237189272302020718062仓8421293932674301661183791132070275145储12011311871892763102622311871802750183储2276148102122285175127334247621451830对其求解方法如问题二，简述如下：仍然先考虑国家储备库企业最短距仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）需求量储备库12011311873102311000储备库2276148102175334700

23、供应量720450560150400用Lingo软件解得企业供应 量仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）储备库1550450000储备库2005601400在考虑其他仓库企业最短距仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）需求量仓库115458224297212300仓库2125157387460139330仓库440332875148461120仓库634225314526837220仓库7214118164237272110仓库842129393166380100供应量980980980980980用Lingo软件解得企业供应 量仓库企业1企业2企业3企业4 （仓3）企业5 （仓5）仓库10300000仓库23300000仓库40012000仓库6002000仓库70110000仓库80010000总运费为421260元，所以问题得到了解决.六、模型优缺点评价巧妙运用了运输费用等价法则和运输地位等价法则这两个模型简化技巧，使得问题简单化；原创性很强，文章中的大部分模型都是自行推导建立的；建立的规划模型能与实际问题的求解紧密联系；模型的计算采用专业的数学软件，可信度较高；模型的适应度良好，从而大大拓广了模型的适用范围. 但是，我们得出的线性规划模型的约束条件有点简单.七、参考文献（略）