《防洪物资调运的优化模型.doc》由会员分享，可在线阅读，更多相关《防洪物资调运的优化模型.doc（21页珍藏版）》请在三一办公上搜索。
1、 防洪物资调运的优化模型摘 要本文首先将题中所给的交通图抽象成一张无向图,以每百件物资在各边上运输所需费用为权值赋给各边.利用弗洛伊德(Floyd)算法求出各点之间的最短路径,滤去无用数据,找出我们需要的两单位之间的最短路径,所得结果即为问题1所要求的最优公路交通网数学模型(见表2和图3).对于问题2,在重点保证国家储备库的前提下,将问题抽象为一个多阶段单目标的规划问题,以总的运输费用最低为目标,采用带模糊条件的物资调运系统(GTSWFC)模型并且引入惩罚函数对物资进行优化调运.其具体调运过程分成四个阶段:第一阶段,只给储备库调运物资,使其达到预测库存量;第二阶段,只给八个仓库调运物资,直到满
2、足其预测库存量;第三阶段,重新考虑储备库,只给它们调运物资,并使其达到最大库存量;第四阶段,只给八个仓库调运物资,直至所有仓库及企业自己的库存都达到最大.对于问题3,运用问题2中带模糊条件的物资调运系统(GTSWFC)模型可以解答出问题3,得到20天后各库的库存量为对于问题4,在汛期来临后,需改进对问题2所建的模型,即在其基础上分三种情况来考虑:情况一,灾情在调运过程的第一阶段发生;情况二,灾情在第二阶段发生;情况三,灾情在调运过程的第三阶段或第四阶段发生.在情况一和情况二中,各个仓库或储备库未达到其预测库存量,此时情况紧急,根据问题1的方法,求出两个单位之间运输所耗时间最少的路径.通过引入“
3、虚拟”运输时间量化“紧急程度越大的单位,就尽量多运输”这一模糊行为,以总的运输所耗时间最少为目的改进带模糊条件的物资调运系统(GTSWFC)模型.在情况三中,由于各个仓库和储备库都已达到预测库存量,此时视为情况不紧急状态,可以以总运输费用最少为目标确定路径.通过所建防洪物资调运的优化模型,在现实生活中,可以根据实际情况,做出合理的决策,使得总的运输费用或所耗时间达到最优,减少损失,为防洪抗洪工作提供可性行方法.1.问题的重述（略）2.模型的假设1.为了简化问题,我们按照题中附件1所示按照各单位的顺序依次标号,如1表示企业1,5表示仓库2,13表示储备库2等;2.取企业1、企业2和企业3的预测库
4、存和最低库存都为0;3.为了做好某种防洪抗涝物资的储备,假设在问题2的解决中没有发生洪灾,并且公路交通不受影响;4.根据实际情况,假设高速公路的平均速度是普通公路的两倍;5.假设有充足的运输车供调运物资;6.由于企业是输出单位,故假设各企业之间是不运输物资的.3.符号说明: 表示在灾情未发生时,第阶段从单位到单位的每天调运量,其中;: 表示灾情发生后, 从单位到单位的每天调运量; : 表示单位的现有库存量,其中; : 表示单位的预测库存量,其中; : 表示单位的最大库存量,其中;: 表示单位的最小库存量,其中;: 表示在灾情未发生时,从单位到单位的每百件物资的最低运费, 可以表示为: 表示在灾
5、情发生后,从单位到单位的每百件物资的最低运费;: 表示在灾情未发生时,第阶段调运方案所需的时间;: 表示在灾情发生后,调运物资所耗费的时间;: 表示在灾情未发生时,从单位到单位调运每百件物资所耗费的时间;: 表示在灾情发生后,从单位到单位调运每百件物资所耗费的时间;：表示在灾情发生后,地的物资相对紧缺程度;: 表示在灾情未发生时,第阶段总的运费;: 表示在灾情发生后,总的运输所耗时量.4.问题的分析及模型的建立与求解4.1 问题1的解答4.1.1 问题1的分析题中指出,现在是提前为防洪抗涝做准备.我们可以认为,在这个过程中,灾情还未发生,时间比较充裕.因此,在决定交通网络的模型时,我们只考虑两
6、个单位之间运输成本最低的路线.很显然,可以把问题抽象成求任意两点间的最小路径问题.4.1.2 问题1模型的建立与求解在题目所给的交通图中,以标有数字的公路交汇点为顶点,交汇点之间的连线为边,将其余无用边和顶点删除,形成一幅无向图.再以每百件物资在各边上运输所需费用为权值赋给各边,有以下两种情况: 图 1 图 2情形1.两公路交汇点之间是普通公路(如图1):在图1中，我们给交汇点20和交汇点22之间的路线重新赋予权值,新的权值两交汇点之间的距离普通公路的单位运输成本,即801.2=96;情形2.两公路交汇点之间是高速公路(如图2):在图2中，我们给交汇点7和交汇点27之间的路线重新赋予权值,新的
7、权值两交汇点之间的距离高速公路的单位运输成本,即702=140.从而,我们得到了任意两交汇点间路线新的权值(见表1):表1路 线权 值路 线权 值路 线权 值路 线权 值1248611641417112252621.61337271096154233.626278413454727140151869.6274064234281576152555.2282972276081472162169.6284238.42974.4828100162378293074.431050.49274816181503039183366094033.6172362.4313260463693162.4181926
8、.43234304520101262.4182354323974.4429801125801825待添加的隐藏文字内容360323881.643084112796192286.43235117.656561115112192633.633364854076121396202296333745.65391701327100202460353920464036132081.621225437384264157.6142360242636414231.2问题转化为求该无向图的任意两点的最小路径.针对该无向图,我们利用弗洛伊德(Floyd)算法4来求出各点之间的最短路径,其基本思想是:假设求从顶点到的
9、最短路径.（，）和（，）分别是从到和从到的中间顶点的序号不大于的最短路径,则将（，）和已经得到的从到且中间顶点序号不大于的最短路径相比较,其长度较短者便是从到的中间顶点的序号不大于的最短路径.这样,在经过次比较后,最后求得的必是从到的最短路径.按此方法,可以同时求得各对顶点间的最短路径.由此可根据该算法,用C+语言编写程序（见附件）求出每对顶点之间的最短路径.在得到的结果中,将无用的结果滤去,筛选出我们需要的各单位之间的最短路径,见表2:表2路 线权值路 线权值企业1仓库1242625154228184.8仓库1储备库128424164027227.2企业1仓库22426191823150仓库
10、1储备库2282930146.4企业1仓库32426279313235408仓库2仓库323181926279313235486企业1仓库4242627931230.4仓库2仓库42318192627931308.4企业1仓库524261922204仓库2仓库523181922166.8企业1仓库624262792336344.4仓库2仓库6231819262792336422.4企业1仓库724262515422829256.8仓库2仓库7231815422829267.6企业1仓库82426279313238372仓库2仓库823181926279313238450企业1储备库124262
11、7120仓库2储备库12318192627198企业1储备库2242625116430321.6仓库2储备库223181542282930342企业2仓库141422869.6仓库3仓库4353231177.6企业2仓库24142151823188.4仓库3仓库5353231927261922492企业2仓库3416409313235367.2仓库3仓库635323413336321.6企业2仓库441640931189.6仓库3仓库73532393029284.4企业2仓库5414215181922247.2仓库3仓库8353238199.2企业2仓库64164092336303.6仓库3储
12、备库1353231927288企业2仓库741422829141.6仓库3储备库235323930210企业2仓库8416409313238331.2仓库4仓库531927261922314.4企业2储备库14164027157.6仓库4仓库63192336238.8企业2储备库2416430177.6仓库4仓库73132393029226.8企业3仓库1343239302928268.8仓库4仓库8313238141.6企业3仓库234323192726191823486仓库4储备库131927110.4企业3仓库3343235147.6仓库4储备库231323930152.4企业3仓库43
13、4323190仓库5仓库62219262792336428.4企业3仓库5343231927261922404.4仓库5仓库722191815422829326.4企业3仓库63413336174仓库5仓库8221926279313238456企业3仓库73432393029196.8仓库5储备库122192627204企业3仓库8343238111.6仓库5储备库22219181542282930400.8企业3储备库1343231927200.4仓库6仓库736329406429362企业3储备库234323930122.4仓库6仓库836333738135.6仓库1仓库228421518
14、23195.6仓库6储备库13632927252仓库1仓库3282930393235356.4仓库6储备库23633134323930296.4仓库1仓库4284241640931259.2仓库7仓库82930393238248.4仓库1仓库5284215181922254.4仓库7储备库129464027216仓库1仓库628424164092336373.2仓库7储备库2293074.4仓库1仓库7282972仓库8储备库1383231927252仓库1仓库8282930393238320.4仓库8储备库238323930174储备库1储备库227406430220表2中,只给出了从单位到
15、单位 ()的最短路径, 单位到单位的最短路径可将从单位到单位的最短路径反序排列便可得到,单位成本相同.下面,再将上面求得的各单位之间最短路径综合起来,算出它们的合集,所得结果即为该地区公路交通网的模型.如图3所示:图34.2 问题2的解答4.2.1 问题2的分析问题2要求我们在重点保证国家级储备库的情况下,给出包括调运量及调运路线的合理的调运方案. 我们可以综合各企业、仓库和储备库的不同情形,考虑灾情未发生时,以总的运输费用最低为目标,将调运过程分成四个阶段:首先,重点考虑储备库,只给储备库调运物资,达到其预测库存量为止.第二个阶段只给八个仓库调运物资,以满足它们的预测库存.第三个阶段,重新重
16、点考虑储备库,只给它们调运物资,直到满足它们的最大库存;第四阶段,将多余的物资调往八个仓库,直至所有仓库及企业自己的库存都到达最大.4.2.2 问题2模型的建立我们规定第阶段从单位到单位的调运量为,每百件最低运输成本为.若满足,则,且.经过计算从单位到单位的运输成本如下:这里我们引入在阶段从单位到单位调运量的惩罚函数6,当时, (惩罚函数为正值,即表示当单位的现有库存量大于其预测库存量,需从单位向单位调运防洪物资);如果,那么(惩罚函数为0,表示无需从单位向单位调运防洪物资).其函数如下:问题2强调在重点保证国家级储备库的情况下,选择合理的调运方案.该方案需要满足以下四个条件:(1).先对国家
17、级储备库进行调运;(2).依次满足各储备库和仓库的预测库存量,并且最终不能超过其最大库存量;(3).总运费最小;(4).日产量多的企业,适当多运输.满足条件(1)(4)的物资调运系统称为带模糊条件的系统5,简记作GTSWFC.系统必须要在优先满足条件(1)的情况下,依次满足各储备库和仓库的预测库存量、最大库存量.因为题中已给出三个企业的日产量,所以要使得系统的总运费最小时,本题中我们认为条件(3)和(4)也应当综合考虑.因为要优先保证国家储备库的库存量,所以我们将调运过程分为四个阶段进行考虑:第一阶段:当国家储备库未达到其预测库存量,此时优先考虑给国家储备库调运物资,即只考虑由可调运出物资的企
18、业或仓库向这两个储备库调运物资,为了满足调运成本最低,可得GTSWFC模型为:第二阶段:当国家储备库已达到其预测库存量时,此时考虑只给仓库1到仓库8中需要调运物资的仓库调运物资,直到它们的库存量达到预测库存量,并且满足调运过程中所花的费用最小;其GTSWFC模型为:第三阶段:完成前两阶段的调运方案后,所有的储备库和仓库都已达到它们的预测量;此时对于多余的物资,仍然按照优先保证国家储备库的原则,在未达到国家储备库的最大库存量的前提下,保证运输费用最低;其GTSWFC模型是:第四阶段:前三阶段完成后,各个仓库都已达到它们的预测库存量,并且两个储备库已达到其最大库存量.此时我们考虑怎样调运物资,使这
19、8个仓库的库存也达到最大库存,而且所花费的运费最小.具体的GTSWFC模型为:用LINGO对这四个阶段的模型进行求解,得出在完成各个阶段的调运方案后,每天的调运量.具体数值如下列表所示:表4(第一阶段每天的调运量)单位储备库1储备库2企业16000企业231050企业30500仓库30150仓库5900完成第一阶段的调运方案,共需费用240796元.表5(第二阶段每天的调运量)单位仓库1仓库2仓库4仓库6仓库7仓库8企业125312000企业215000150企业30043013仓库54200000完成第二阶段的调运方案,共需费用150902.3元.表6(第三阶段每天的调运量)单位储备库1储备
20、库2企业1400企业22010企业3020完成第三阶段的调运方案,共需费用202933.9元.表7(第四阶段每天的调运量)单位仓库12345678企业10130036001企业2130220840企业3001100009完成第四阶段的调运方案,共需费用320643.1元.由前面的模型可以解出经过天,各个储备库和仓库都已经达到它们的最大库存量;若此时3个企业继续生产物资,则不到70天,可使3个企业的仓库也达到它们的最大库存量,本题中因为灾害还未发生,物资没有消耗,所以我们认为这3 个企业暂时停止生产.4.3 问题3的解答根据问题2的调运方案模型模型,我们可以解出执行第一阶段的调运方案的时间为天,
21、前两个阶段的调运方案所需天数为,前三个阶段的调运方案所需天数为,这四个阶段的调运方案都执行所需天数为天后.当调运方案已经执行了20天时,根据前面的调运方案可知,所以我们认为方案已经实施20天后,正在执行第三阶段的调运方案.此时仓库1到仓库8已经达到预测库存量,并且在这个阶段仅给两个储备库,所以由问题2的第三阶段调运方案的GTSWFC模型可以解出第三阶段已向储备库1和储备库2调运的物资量为:从而我们可知20天后各个储备库和仓库的储存量,具体如表8:表8(单位:百件)单位企业1企业2企业3仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库2储存量4.4 问题4的解答4.4.1问题4的分
22、析问题4指出因洪水而使得部分交通中断,此时灾情已经发生,我们所给的模型必须考虑解决紧急调运的问题.而在问题2中,我们假设灾情没有发生,是以运输成本最低为目的,分四个阶段来调运物资的.灾情发生后,由于部分路线中断和情况紧急,所以问题2中的模型不再适用于问题4.为此我们在问题2模型的基础上分三种情况来考虑:情况一、灾情在调运过程的第一阶段发生;情况二、灾情在调运过程的第二阶段发生;情况三、灾情在调运过程的第三阶段或第四阶段发生.4.4.2 问题4模型的建立在情况一和情况二中,由于各个仓库和储备库未达到其预测库存量,这里我们为了在最短时间内将防洪物资运送到各个仓库及储备库,只考虑运输所耗的时间,耗时
23、最短的路线为最优路线.由前面的假设可知,灾情发生后高速公路的速度是普通公路的两倍.以任意两顶点间所需时间为其边的权值,除去洪水冲断的路外,应用弗洛伊德(Floyd)算法1,得出最优路线(见表9):表9路 线时间路 线时间企业1仓库124262515828138仓库1储备库128815112796企业1仓库22426251823108仓库1储备库2282930122企业1仓库324262515116539352455仓库2仓库3231815116539352545企业1仓库42426251511653932313065仓库2仓库423181511653932313155企业1仓库52420221
24、30仓库2仓库523181922139企业1仓库624201327710336294仓库2仓库62318151127710336306企业1仓库7242625151165429177仓库2仓库723171482829183企业1仓库82426251511653932383245仓库2仓库823181511653932383335企业1储备库124201327143仓库2储备库12318151127155企业1储备库224262515116539302095仓库2储备库2231815116539302185企业2仓库141422858仓库3仓库4353231148企业2仓库24142151823
25、157仓库3仓库53539540271320223015企业2仓库3416539351555仓库3仓库635323413336368企业2仓库441653932312165仓库3仓库7353954291185企业2仓库5414215181922206仓库3仓库8353238166企业2仓库64161127710336239仓库3储备库13539540271285企业2仓库7416542987仓库3储备库235393066企业2仓库841653932382345仓库4仓库5313239540271320223625企业2储备库1416112788仓库4仓库631323413336220企业2储备
26、库2416539301195仓库4仓库731323954291795企业3仓库13432395429282145仓库4仓库8313238118企业3仓库234323956111518232905仓库4储备库1313239540271895企业3仓库3343235123仓库4储备库231323930127企业3仓库4343231102仓库5仓库622201327710336324企业3仓库5343239540271320223375仓库5仓库722201327405429233企业3仓库63413336145仓库5仓库8222013274053932383805企业3仓库734323954291
27、545仓库5储备库122201327173企业3仓库834323895仓库5储备库22220132740539302655企业3储备库1343239540271645仓库6仓库736310727405429211企业3储备库234323930102仓库6仓库836333738113仓库1仓库2288141723123仓库6储备库136310727151仓库1仓库328294539351785仓库6储备库23631072740539302435仓库1仓库42829453932312395仓库7仓库829453932381975仓库1仓库528815181922196仓库7储备库129454027
28、60仓库1仓库6288151127710336247仓库7储备库2293062仓库1仓库7282960仓库8储备库1383239540272075仓库1仓库82829453932382575仓库8储备库238323930145储备库1储备库2274053930925下面,再将上面求得的各单位之间最快路径综合起来,算出它们的合集,所得结果即为该地区公路交通网的模型.如图4所示:图4情况一、灾情在调运过程的第一阶段发生:在问题2的第一阶段中,我们优先考虑国家储备库,只给这两个储备库调运物资,这里我们假设在调运之前,灾情已经发生.所以原来问题2中的模型在这里已不再适用.此时我们根据各个储备库和仓库的
29、物资相对紧缺程度进行物资调运.比较各个储备库和仓库的紧缺程度,如果预测库存量小于现有库存量,我们认为其紧缺程度为0;否则,当的值越大,其紧缺程度越大.其中可以表示为:.经计算,可得各个单位的紧缺程度(见表10):表10单位45678910111213即各个储备库和仓库的相对紧缺程度为:仓库2仓库1仓库7仓库8=储备库1仓库4储备库2仓库6.考虑到当某单位的紧缺程度越大,应调运给该单位的物资也就越多.为了量化“紧缺程度越大的单位,就尽量多运输”这一模糊行为.我们作如下处理:对大的单位,调整调运物资到该单位所耗的时间,形成“虚拟”运输时间,其中满足越大,相应的就越小.用代替后进行规划,使得调运方案
30、满足总的运输耗时最少.现选取为:其中是正参数,反映了紧缺程度和总运输所耗时间在决策中的重要程度.由于这里灾情已经发生,我们认为紧缺程度是很重要的,于是这里取值要满足一定的情况,本题的情况可以表示为图4:110图4记,则.对于,函数类似于上的“降半凹(凸)分布”(如图4),下面说明的合理性:(1)显然,满足;(2)时连续递减的,即越大,则相应的越小;(3)参数的选取可使紧缺程度和运输所耗时间的“重要程度”这一模糊概念得到量化;(4)的选取便于计算和控制.于是综合考虑上面的分析,我们得到GTSWFC模型为:情况二、灾情在调运过程的第二阶段发生:第一阶段的调运方案结束后,两个国家储备库已达到其预测库
31、存量,我们认为它们的紧缺程度为0.此时类似情况一的分析,我们只考虑8个仓库的物资相对紧缺程度.可得各单位的相对紧缺程度为(见表11):表11单位4567891011通过“虚拟”运输时间来量化“紧缺程度越大的单位,就尽量多运输”这一模糊行为.在满足调运过程中所消耗的时间最少的前提下,得到其GTSWFC模型为:情况三、灾情在调运过程的第三阶段或第四阶段发生:无论是第三阶段还是第四阶段,各个储备库和仓库都已达到了预测库存量,这里我们认为预测库存量即发生灾情下,物资充足够用的量.此时,按照问题一中的讨论,以总运输费用最低为目标,进行物资调运的分配.此时,除去洪水冲断的路外,利用弗洛伊德(Floyd)算
32、法可得新的路线为(见表11):表11路 线成本路 线成本企业1仓库1242625154228184.8仓库1储备库128424164027227.2企业1仓库22426191823150仓库1储备库2282930146.4企业1仓库32426251542282930393235541.2仓库2仓库323181542282930393235552企业1仓库42426251542282930393231483.6仓库2仓库423181542282930393231494.4企业1仓库5242022156仓库2仓库523181922166.8企业1仓库62420131210336410.6仓库2仓库
33、6231815424164092336492企业1仓库724262515422829256.8仓库2仓库7231815422829267.6企业1仓库82426251542282930393238505.2仓库2仓库823181542282930393238516企业1储备库124201327241.6仓库2储备库12318151127331.6企业1储备库22426251542282930331.2仓库2储备库223181542282930342企业2仓库141422869.6仓库3仓库4353231177.6企业2仓库24142151823188.4仓库3仓库535323930292842
34、15181922610.8企业2仓库3416430393235387.6仓库3仓库635323413336321.6企业2仓库4416430393231330仓库3仓库73532393029284.4企业2仓库5414215181922247.2仓库3仓库8353238199.2企业2仓库64164092336303.6仓库3储备库135323412927372企业2仓库741422829141.6仓库3储备库235323930210企业2仓库8416430393238351.6仓库4仓库53132393029284215181922553.2企业2储备库14164027157.6仓库4仓库6
35、31323413336264企业2储备库2416430177.6仓库4仓库73132393029226.8企业3仓库1343239302928268.8仓库4仓库8313238141.6企业3仓库234323930292842151823464.4仓库4储备库131323412927314.4企业3仓库3343235147.6仓库4储备库231323930152.4企业3仓库434323190仓库5仓库62220131210336446.4企业3仓库53412927132022502仓库5仓库722191815422829326.4企业3仓库63413336174仓库5仓库8221918154
36、2282930393238574.8企业3仓库73432393029196.8仓库5储备库122201327277.6企业3仓库8343238111.6仓库5储备库22219181542282930400.8企业3储备库13412927224.4仓库6仓库736329406429362企业3储备库234323930122.4仓库6仓库836333738135.6仓库1仓库22842151823195.6仓库6储备库136329272244仓库1仓库3282930393235356.4仓库6储备库23633134323930296.4仓库1仓库4282930393231298.8仓库7仓库82930393238248.4仓库1仓库5284215181922254.4仓库7储备库129464027216仓库1仓库628424164
