《防洪物资调运问题模型的建立及求解》由会员分享，可在线阅读，更多相关《防洪物资调运问题模型的建立及求解（17页珍藏版）》请在金锄头文库上搜索。
1、防洪物资调运问题模型的建立及求解摘 要本文将题目所给出的防洪物资调运问题转化为图论中的最短路问题求解及一个多目标规划问题求解。关于问题一，本文建立了关于交通网络的最短路问题，并分别采取了dijkstra算法和floyd算法对其进行了求解。求解得出了任意一对起点和终点之间运输费用最小的路线，建立了该地区的交通网络数学模型。对于问题二，根据客观需要，建立各仓库及储备库最终库存的合理度函数，并结合目标建立多目标规划模型，通过求解模型，得到具体的调运方案。我们将问题三调运过程看成是一个多阶段性的静态过程。讨论运输周期的长短（即阶段的数量）对整个模型的影响，最终得出最合适的方案。问题四仍旧通过问题一和问
2、题二的模型建立过程，根据新情况重新建立该地区的交通网络数学模型，并利用新模型解决新问题。最后我们分析了最终解的稳定性，可延拓性等，提出了该模型所具有的优缺点。本文的最终模型稳定，可扩展性好，算法简单，复杂度低，有效的解决了本文所提出的所有问题。一问题的重述（略）二模型的假设1一定要满足各个仓库的最低库存量，否则整个问题系统就是一个极不稳定合理的系统。2运输使用的运输工具足够多，可以一次性满足运输的需求。3运输费用没有规模成本，小规模运输和大规模运输中单位数量的物资运输成本相等。4每条公路都没有承载上限，既在不中断情况下不会出现因为堵车原因不能同多的情况。5运输的速度足够快，任何一次运输调度都可
3、以在一天内完成。6运输的最小单位为百件。7工厂的物资的生产以一天为最小周期，即每天统一将生产出来的物资入库。8本题只考虑运输费用，不考虑货物装卸、储存等其他费用。三符号系统inf:表示正无穷(i=18)表示仓库18的库存，(i=9,10)表示储备库1，2的库存，(i=1,2,3)表示企业 1，2，3的库存，mi（i=18）表示仓库18的最小库存mi（i=9，10）表示储备库1，2的最小库存(i=18)表示仓库18的预测库存，(i=9，10)表示储备库1，2的预测库存，(i=18)表示仓库18的最大库存，(i=9,10)表示储备库1,2的最大库存(i=18)为仓库18的合理度函数(i=9,10)
4、为储备库的合理度函数四问题的分析1将该地区的公路交通网转换为求解无向图中个节点间最短路问题。首先将该地区的交通地图，转换为一个边是带权的无向图： 图-1图中，细黑线表示普通公路，粗黑线表示高等级公路。 圈中数字表示公路各个交汇点；线上数字表示公路区间距离，单位：公里 根据题目中：物资的运输成本为高等级公路2元/公里百件，普通公路1.2元/公里百件。对此图进行修改，将公里数改为运费： 图-2所以对于问题一的求解就是，求解各个节点间的最短路问题（即得到任意两点之间运费最小的运输路线）。2物资调运方案的合理度分析本文最后要解决的就是如何调运物资才是最合理的。要考虑两个因素：（1）每个国家级储存库和仓
5、库的最终库存和预期库存及其最大库存之间的关系，优先考虑国家级储存库。 （2）运费越低越好两个因素的优先级和各因素之中的个别约束权重一般都不相等，要结合实际情况进行假设。并利用多目标规划的模型对其进行建模求解。五模型的建立与求解问题一：结合图-2，将各节点之间的运费表示成一张表（直接相连两点运费即为两点之间连线的权重，不直接相连两点则为inf）具体表格见附录1.1将表格转化为一个矩阵，分别用floyd算法和dijkstra算法对其进行求解。floyd算法1：求任意两点间的最短路D(i,j):i到j的距离R(I,j):i到j之间的插入点输入带权邻接矩阵W,(1) 赋初值：对所有i,j,d(i,j)
6、w(i,j),r(i,j)j,k1(2) 更新d(i,j),r(i,j):对所有i,j，若d(i,k)+d(i,k)d(i,j),则 d(i,j)d(i,k)+d(k,i),r(i,j)k(3) 若k=v，停止；否则kk+1,转(2)在此我们只求并输出代表着企业、仓库、储备库的节点之间任意两点的最小运输费用。Matlab程序见附录1.2计算结果如下：(本表格只列出了任意两企业，仓库或储备库之间的最低运费) 单位：元/百件企业一企业二企业三仓库一仓库二仓库三仓库四企业一0177.6000320.4000184.8000150.0000408.0000230.4000企业二177.60000279
7、.600069.6000188.4000367.2000189.6000企业三320.4000279.60000268.8000398.4000147.600090.0000仓库一184.800069.6000268.80000195.6000356.4000259.2000仓库二150.0000188.4000398.4000195.60000486.0000308.4000仓库三408.0000367.2000147.6000356.4000486.00000177.6000仓库四230.4000189.600090.0000259.2000308.4000177.60000仓库五156.
8、0000247.2000404.4000254.4000166.8000492.0000314.4000仓库六344.4000303.6000174.0000373.2000422.4000321.6000238.8000仓库七256.8000141.6000196.800072.0000267.6000284.4000226.8000仓库八372.0000331.2000111.6000320.4000450.0000199.2000141.6000储备库一120.0000157.6000200.4000227.2000198.0000288.0000110.4000储备库二321.6000
9、177.6000122.4000146.4000342.0000210.0000152.4000仓库五仓库六仓库七仓库八储备库一储备库二企业一156.0000344.4000256.8000372.0000120.0000321.6000企业二247.2000303.6000141.6000331.2000157.6000177.6000企业三404.4000174.0000196.8000111.6000200.4000122.4000仓库一254.4000373.200072.0000320.4000227.2000146.4000仓库二166.8000422.4000267.600045
10、0.0000198.0000342.0000仓库三492.0000321.6000284.4000199.2000288.0000210.0000仓库四314.4000238.8000226.8000141.6000110.4000152.4000仓库五0428.4000326.4000456.0000204.0000400.8000仓库六428.40000362.0000135.6000224.4000296.4000仓库七326.4000362.00000248.4000216.000074.4000仓库八456.0000135.6000248.40000252.0000174.0000储
11、备库一204.0000224.4000216.0000252.00000220.0000储备库二400.8000296.400074.4000174.0000220.00000本表格只列出了任意两企业，仓库或储备库之间的最低运费，每一个最低运费都对应着一条具体的通过几个节点的路径。这样的路径一共有156条。具体的路径请参见附录1.2 matlab程序中的矩阵rfloyd算法是一个可以算出任意两个节点之间最短距离及路径的简单且容易理解的算法，在本题中，可以很好的解决问题。可是起计算复杂度为O(n3)。不适合处理大规模运算。：为了简化复杂的floyd，我们现在讨论用dijkstra算法解决该问题。
12、dijkstra算法2：设G为一赋权有向图或无向图，G边上的权均非负。求G中从顶点u0到其余顶点的最短路S：具有永久标号的顶点集。对每个顶点，定义两个标记(l(v),z(v)，其中：l(v)：表示从顶点u0到v的一条路的权z(v)：v的父亲点，用以确定最短路的路线。算法的过程就是在每一步改进这两个标记，使最终l(v)为从顶点u0到v得最短路的权。输入为带权邻接矩阵W（1）赋初值：令.（2） （3）（4）用上述算法求出的l(v)就是u0到v的最短路的权，从v的父亲标记z(v)追溯到u0，就可以得到u0到v得最短路的路线。该算法一个点的计算复杂度为O(n2),通过循环和矩阵变换我们可以分别求出各个
13、企业、仓库和储备库到各个节点的最小运输费用。由于表示企业、仓库和储备库的节点要远少于总节点数，所以相比于floyd算法，计算过程将被大大简化。dijkstra算法的Matlab程序见附录1.3结果与floyd算法所得一样，再次不再赘述。至此我们就得到了一个关于该地区公路交通网的数学模型。问题2：让我们先不考虑生产的问题，先对初始的物资进行分配。首先只考虑运费最小的问题。现在要使各仓库及储备库的库存最大限度的达到预测值。企业1、企业2、企业3为供应地，它们的现有量全部作为供应量，而且仓库3现有量、仓库5的现有量都超过了预测值，那么可以用现有量与预测值之差作为供应量；仓库1、2、4、6、7、8和储备库1、2，由于它们的现有量都低于预测值，所以将它们看作需求地，且预测值减去现有量作为需求量。先不考虑各种约束条件，按运输问题的产销不平衡问题来解。因为供应量即可看作产量少于需求即可看作的销量，则需要假想一个产量节点，这个假想的地点的产量为 由本题初始条件，有：=600，=360，=500，=150，=400，=670=300，=330，=120，=20，=110，=100，=1000，=700结合问题一中得出的运费表，我们用lingo软件对其进行求解。
