《防洪物资调运问题模型的建立及求解.doc》由会员分享，可在线阅读，更多相关《防洪物资调运问题模型的建立及求解.doc（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.0000.204.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和
14、储备库1、2，由于它们的现有量都低于预测值，所以将它们看作需求地，且预测值减去现有量作为需求量。先不考虑各种约束条件，按运输问题的产销不平衡问题来解。因为供应量即可看作产量少于需求即可看作的销量，则需要假想一个产量节点，这个假想的地点的产量为 由本题初始条件，有：=600，=360，=500，=150，=400，=670=300，=330，=120，=20，=110，=100，=1000，=700结合问题一中得出的运费表，我们用lingo软件对其进行求解。lingo程序3见附录2.1程序解得：各节点之间的运输情况企业一企业二企业三仓库三仓库五虚拟产地仓库一03000000仓库二00003300
15、仓库四00120000仓库六0000020仓库七06000050仓库八00010000储备库一60000070330储备库二00380500270解得最小运费为258432.0在实际情况中，优先考虑运费显然是不合理的，因为我们首先必须应该保证防洪抗涝工作顺利进行，即首先应先尽量使运输完毕后个仓库库存的合理度最高。现在考虑每个仓库的实际库存与它的预测库存及最大库存的内在关系。即每个仓库的最终库存的合理度问题。而为了能够用数学语言来清楚地描述这种关系，我们需要引入每个仓库的储存合理度函数hi(xi),i=110,分别对应八个普通仓库，两个储备库。(i=18)为仓库18的合理度函数(i=9,10)为
16、储备库1，2的合理度函数由于十个仓库各自的预测库存、最小库存、最大库存之间并没有固定的比例系数，不同仓库在同一类要求库存中，要求数额也相差很大，因此这十个仓库的合理度函数在具体系数上并不相同。但是，结合实际，我们可以抽出一个共性的函数模式。而这个模式函数hi应能够体现所有仓库的实际库存与三个要求库存之间的关系。这个模式函数应满足以下实际约束条件： 对于每个i而言，hi应是一个以xi为单一自变量的递增函数。正如前面假设中所写，我们认为xi的取值只能介于最小库存mi和最大库存Mi之间，否则系统崩溃。 为了统一模式，合理度函数应是一个值域为0，1的函数。因此我们可以让xi等于最小库存mi时hi取0（
17、注意，这里的0只是一个相对的0，并不是说起完全不合理），而xi等于最大库存Mi时hi取1。 又在实际问题中，预测库存gi是衡量一个仓库储存合理度的极其重要的标准，因为实际库存是否达到预测库存直接关系着防洪抗洪任务能否确实完成，所以在合理度函数hi中，我们应该凸显出预测库存gi对合理度曲线的关键影响。为了统一标准，取xi等于gi时，hi等于Q0，Q0是标识gi关键性的一个因素。Q0的取值应在0.51.0之间。 在的基础之上，hi函数应该在xi介于migi之间时，随xi增长而增长的速率较快，而当xi超过gi 向Mi趋近时，随xi增长而增长的速率较慢。用数学的语言就是:ximi,gi时，hi的导数较
18、大；xigi,Mi时，hi的导数较小。这样综合以上的条件限制，我们认为，取hi采取分段线性函数最能在满足大模式限制的前提下，凸现出预测库存的重要性。这个分段函数的表达式如下：函数的图形如下图所示：各仓库、储备库具体函数见附录22下面我们就可以将其转换为一个多目标规划问题：本题应该有五个优先级由高到低的目标分别为：Goal1：尽量使国家级储备库库存量达到预期库存Goal2：尽量使每个仓库库存量达到预期库存Goal3：尽量使国家级储备库库存量达到最大库存Goal4：尽量使每个仓库库存量达到最大库存Goal5：尽量使运费最低我们先抛开运费的问题，建立关于库存的多目标规划模型：在同一优先级中，由于各储
19、备库、仓库之间的差异，我们通过每一个储备库、仓库的合理度函数hi的斜率对其进行赋权。模型如下使用winqsb软件对其进行求解。结果如下：我们取Q0=0.9，分别计算出了每个仓库和储备库的库存合理度。最优分配完后的结果： 普通仓库12345678总计分配货量1003303003504003005006002880合理度00.29250.90.90.90.90.90.956925 储备库12总计分配货量300025005500合理度0.90918此时总的合理度为：国家级储备库为 1.8普通仓库为 5.69我们考虑在此条件下的运输问题：企业1、企业2、企业3为供应地，它们的现有量全部作为供应量，而且
20、仓库1，仓库3仓库5的现有量都超过了最终值，那么可以用现有量与最终值之差作为供应量；仓库2、4、6、7、8和储备库1、2，由于它们的现有量都低于最终值，所以将它们看作需求地，且最终值减去现有量作为需求量。这是一个产销平衡问题。模型如下：表示第个产地的产量，表示第个销地的销量，指的是企业1，2，3；，指仓库1，3，5；指仓库2，4，6，7，8； 指储备库1，2。 。这是一个产销平衡问题。 由本题初始条件，有：=600，=360，=500，=100，=150，=400=60，=120，=20，=110，=100，=1000，=700，结合问题一中得出的运费表，我们用lingo软件对其进行求解。li
21、ngo程序见附录23求解得：（其中企业一、二、三，仓库一、三、五向外运输） 仓库二、四、六、七、八，储备库一、二接受物资， 表中数字表示从一外运地到一接受地的物资量） 各节点之间的运输情况 单位：百件企业一企业二企业三仓库一仓库三仓库五仓库二0000060仓库四00700500仓库六0020000仓库七010010000仓库八00001000储备库一60060000340储备库二0290410000最小运费为309708元问题三：根据假设7我们将生产过程看成是一个阶段性的静态过程。我们把问题简化一下：在最开始，我们首先已经按照问题2的模型进行了一次调运。所以各企业、仓库和储备库的初始库存都有了
22、变化。（这样企业的最大库存量我们可以暂不考虑。）各企业、仓库和储备库的初始库存情况 企业123总计存货量0000普通仓库12345678总计存货量1003303003504003005006002880 储备库12总计存货量300025005500先让我们考虑以二十天为一个运输周期：二十天时各企业、仓库和储备库的初始库存情况 企业123总计存货量8006004001800普通仓库12345678总计存货量1003303003504003005006002880 储备库12总计存货量300025005500按照问题二的模型对其进行求解：得到结果如下：最优分配完后的结果： 普通仓库12345678
23、总计分配货量5006003003504003005006003550合理度0.90.90.90.90.90.90.90.97.2 储备库12总计分配货量363030006630合理度0.96311.963此时总的合理度为：国家级储备库为 1.963普通仓库为 7.2最小运费为214420元总运费为524128元同样让我们来考虑一下以十天为一个运输周期的分配方案：第十天时各企业、仓库和储备库的初始库存情况 企业123总计存货量400300200900普通仓库12345678总计存货量1003303003504003005006002880 储备库12总计存货量300025005500第十天进行过
24、运输后，各仓库和储备库的储备量及合理度普通仓库12345678总计分配货量5006003003504003005006003550合理度0.90.90.90.90.90.90.90.97.2 储备库12总计分配货量300027306630合理度0.90.9461.846运费为：113124元二十天时各企业、仓库和储备库的初始库存情况 企业123总计存货量400300200900普通仓库12345678总计存货量5006003003504003005006002880 储备库12总计存货量300027306630二十天进行过运输后各仓库和储备库的储备量最优分配完后的结果：普通仓库12345678
25、总计分配货量5006003003504003005006003550合理度0.90.90.90.90.90.90.90.97.2 储备库12总计分配货量363030006630合理度0.96311.963运费为：121160元此时总的合理度为：国家级储备库为 1.963普通仓库为 7.2该方案最小运费为543992元由于最终物资总量是一样的，所以按照模型，最终的分配结果和合理度都是一样的。由此我们可以看出进行生产后的统一调配，运费要比一阶段一阶段的运输便宜一些。但是进行多阶段的运输可以有效的降低风险，和不确定性（比如在问题中，因汛期带来的交通中断。）所以选取方案时，要结合系统性思考和降低风险性
26、两点出发全面考虑。若回到简化之前的问题，则我们可以看出：使用任意一种运输周期，按照模型，各仓库、储备库最终的库存和合理度都是一样的。在运输时，各企业的仓库装得越满越好。在此我们就选用以二十天为运输周期的方案。给出结果，其余的就暂不考虑了。二十天后各仓库和储备库的储备量的分配结果及合理度： 普通仓库12345678总计分配货量5006003003504003005006003550合理度0.90.90.90.90.90.90.90.97.2 储备库12总计分配货量363030006630合理度0.96311.963此时总的合理度为：国家级储备库为 1.963普通仓库为 7.2最小运费为52412
27、8元问题四：由于汛期导致有些路段因洪水交通中断，整个交通网络图将有所变化。 图-三本图仍旧是一个连通的，边上有权的无向图。重复问题一重新建立该地区交通网络图模型。在此我们只用dijkstra法对其进行求解Matlab程序见附录31最终得到结果如下：(本表格仍旧列出了任意两企业，仓库或储备库之间的最低运费) 单位：元/百件企业一企业二企业三仓库一仓库二仓库三仓库四企业一0177.6000453.6000184.8000150.0000541.2000483.6000企业二177.60000300.000069.6000188.4000387.6000330.0000企业三453.6000300.
28、00000268.8000464.4000147.600090.0000仓库一184.800069.6000268.80000195.6000356.4000298.8000仓库二150.0000188.4000464.4000195.60000552.0000494.4000仓库三541.2000387.6000147.6000356.4000552.00000177.6000仓库四483.6000330.000090.0000298.8000494.4000177.60000仓库五156.0000247.2000502.0000254.4000166.8000610.8000553.200
29、0仓库六410.4000303.6000174.0000373.2000492.0000321.6000264.0000仓库七256.8000141.6000196.800072.0000267.6000284.4000226.8000仓库八505.2000351.6000111.6000320.4000516.0000199.2000141.6000储备库一241.6000157.6000224.4000227.2000331.6000372.0000314.4000储备库二331.2000177.6000122.4000146.4000342.0000210.0000152.4000仓库五
30、仓库六仓库七仓库八储备库一储备库二企业一156.0000410.4000256.8000505.2000241.6000331.2000企业二247.2000303.6000141.6000351.6000157.6000177.6000企业三502.0000174.0000196.8000111.6000224.4000122.4000仓库一254.4000373.200072.0000320.4000227.2000146.4000仓库二166.8000492.0000267.6000516.0000331.6000342.0000仓库三610.8000321.6000284.400019
31、9.2000372.0000210.0000仓库四553.2000264.0000226.8000141.6000314.4000152.4000仓库五0446.4000326.4000574.8000277.6000400.8000仓库六446.40000362.0000135.6000224.4000296.4000仓库七326.4000362.00000248.4000216.000074.4000仓库八574.8000135.6000248.40000330.0000174.0000储备库一277.6000224.4000216.0000330.00000220.0000储备库二400
32、.8000296.400074.4000174.0000220.00000此时问题二的模型依旧适用，用模型求解该问题最优分配完后的库存结果和未停运时相同：普通仓库12345678总计分配货量1003303003504003005006002880合理度00.29250.90.90.90.90.90.956925 储备库12总计分配货量300025005500合理度0.90918此时总的合理度为：国家级储备库为 1.963普通仓库为 7.2结合新得出的运费表，我们用lingo软件对新的运输问题进行求解。lingo程序见附录42求解得：（其中企业一、二、三，仓库一、三、五向外运输） 仓库二、四、六
33、、七、八，储备库一、二接受物资， 表中数字表示从一外运地到一接受地的物资量） 各节点之间的运输情况 单位：百件企业一企业二企业三仓库一仓库三仓库五仓库二0000060仓库四00001200仓库六0020000仓库七010010000仓库八00700300储备库一60060000340储备库二0290410000此时最小运费为407692元二十天后各仓库和储备库的储备量的分配结果及合理度： 普通仓库12345678总计分配货量5006003003504003005006003550合理度0.90.90.90.90.90.90.90.97.2 储备库12总计分配货量363030006630合理度0
34、.96311.963此时总的合理度为：国家级储备库为 1.963普通仓库为 7.2最小运费为278868元总最小运费为686560元六模型的结果分析问题一模型分析： 首先 我们将一个实际地图转化为一个赋权无向图，并依照图作出了一个各节点之间的运费矩阵，分别利用floyd算法和dijkstra算法同样得出了任意两点之间的最小路费矩阵和相应的路径。 综上我们认为，问题一的解决很全面具体，较好的将一个实际地理图转化为一个明了的数学模型。这一模型是指导解决实际问题的基础，而且该模型的建立为解决问题二，三，四提供了一个最基本的平台。问题二模型分析：1 分析合理度函数中Q0的实际意义：取Q0=0.7,0.
35、8,0.9时发现Q0的取值与仓库总体的合理度和储备库总体的合理度成正比关系，容易验证，当Q0在0.5,1)取值时，Q0与仓库和储备库的总体合理度都是成正比关系的。而Q0反映的是预测库存点的合理度，即预测库存点对应的合理度是与整个仓库的合理度成正比。这正与前文中预测库存的关键性相符合。因此，在实际的调用方案中，Q0正反映了相关部门应该对仓库预测库存达到与否的重视程度。所以Q0可以作为相关部门科学决策的一个重要参数。2 分析库存合理度优先级与最小运费优先级之间的关系：之所以将仓库库存的最优化分配作为高于最小运费的优先级，是因为在现实生活中，对待洪水我们总是以防为主，即总是在库存达到抗洪要求的情况下
36、才会考虑运费问题，这正体现了解决实际问题应以人为本，具体问题具体分析的思想。问题三模型分析： 1分析调运周期的选择：在问题三中，我们最终选择的调运方案是以二十天为周期。首先，由于企业1，2，3的最大库存分别是800，600，600，而以20天为调运周期时，从问题二的运输结果开始，20天后企业新生产的货物总量分别为800，600，400。这三个量都没有超过相应的上限，所以此时的调运周期并没有受到企业最大库存的限制。当然，当调运周期小于20天时，更不必考虑企业的最大库存。其次，由于是根据问题二的调运方案来解决问题，所以正如前文所述，20天中采用任一种小于20天为调运周期的调运方案，得到最终各仓的库存结果都是一样的。故调运周期并不影响最终合理度，而是影响运费，那么我们的目标自然是选择运费最小的调运周期所对应的调运方案。由问题三中模型中类比分析即知，调运周期为20天时运费最小，方案最佳。 2分析调运结果：默认Q0为0.9, 则经过调运20天后普通仓库的总合理度为7.2，国家储备库的总合
