防洪物资调运问题

、：防洪物资的调运方案直接影响到防洪工作的部署和费用时Dijkstra6.5业、各仓库、各储备库间的最短路径和最低费用，建立了该地区的公路交通、模型和费用最低模型并对两个模型的计算结果进行了分析比（见表3元；当各库都达到最大库存时，方前者比后者提前了30天， 费用增加元。所以，在不考虑紧急调运的情况下，我们选用费用最低模型来117246820（4（54.2的最短时间为8天，但由于部分路段中断，某些必须绕道，所以费用比119539我国地域辽阔，气候多变，各种自然频频发生，特别是每年在长江、淮河嫩江等流域经常爆发不同程度的洪涝给国家和人民财产带来重大损失，防洪抗涝成为各级的一项重要工作。某地区为做好今年的防洪抗涝工作，根1，2。经核算该物资的物资仓库及国家级储备库之间的物资可以通过公路互相调运。1：各库库存及需求情况（单位：百件2：22026269中断路段 91qwr2122物资从企业调运到各仓库、各储备库的时间不计洪涝不在近期发生（22天xij：企业ijxiaxib：企业i12yjayjbj12y3jy5j35j的货物量，单位：百件；cijijd3j、d5j35jej、ea、ebj12fjfafbj12gjgagbj12tw：公路区间调运货物每公里每百件的运费，高等级公路为21.2rDijkstraB.W.DijkstraDijkstra首先求解出各路段的权qwr，其中w设GVE为连通图，图中各边(vi,vj有权lij（lij表示vi，vj边，vs，vt为图中任一两点，求一条道路，使它从vs到vt

lij最小。设TP号，给viP标号时，表示从vs到vtvi给vi点一个T标号时，表示从vs到viP标号的点都有TvtP对于有n个顶点的图，最多经n1步就可以得到从始点到终点的最短路。

给viPvjvi,vj)属于E且vjT标号，对vj的TTvjminTvj,Pvjlij 比较所有具有TP PP否则用vi代替

（21）即可求解出各企业、各仓库与储备库间的最短路径。1：1→262515421→2619181→26279→31321→262791→201→26279→231→26251542281→26279→31321→261→2625116→422→422→4215182→6→4→3039322→6→4→3039322→421518192→6→409→2→32→42282→6→4→3039322→6→409→313212→6→43→323930293→32319→272619183→323→323→32319→27261953→1→333→3239303→323→323193→32392：以下分别考虑以时间最少和费用最低为目标函数建立规划模型[2]2.1时间最少模仓库j预测库存约束：3ejxijy5jy3jfj3

（j

e3xi3y53y3jy3ay3b

e5xi5y35y5jy5ay5b

13eaxiay3ay5afa3

23ebxiby3by5b

又因为企业i向外调运的量不可能超过企业在t天内产量和现有库存之和，8x1jx1ax1b40t

88x2jx2ax2b30t

88x3jx3ax3b20t

最短时间目标函数Tmint 此时的费cij(3 cij(3 y5y5bc5b

x1ax1by52

x21y58y56

时，T取得最小值7.4天，此时 费用z为409810.7元即使得各库达到预测库存的最 时间为7.4天，此时的调运方案企业百件储仓库仓库5百件仓库并且按照此调运方案 费用为409810.7元同理，我们可以利用以上模型求出各库达到最大库存时的最短时间46.9天，费用为823734.7元2.2费用最少模 3ejxijy5jy3jfj3

（j

e3xi3y53y3j

e5xi5y35y5j

13eaxiay3ay5afa

23ebxiby3by5b

此时的最低费用目标函数为cij zmincij 5y5bc5y5bc5ba

x12x36

x21x38

时，此时的费用最低为317076元即使得各库达到预测库存的最 费用时的调运方案为企业件仓库企业2百件仓库企业3件仓库企业3件仓库按照以上方案企业1共需提供物资1330百件而现有库存600百件73018.2521利用以上模型，我们还可以求出各库达到最大库存时的最少费用772.3 方案二 费用最低方案（天（元（天（元14.692734.730.1 ，到预测库存，然后把国家级储备库到最大库存物资剩余，则分配到各，220企业2对仓库1和仓库7的能达到最大值；企业3对仓库4、仓库6、仓8和储备库2的也能达到预测值1251707070部到国家级储备库1；企业2在这20天内能使仓库1和仓库7达到最大库3200803。420（单位：百件）12345678由上表知，以最低费用的方案来进行，20天不能完成使各个仓库和国和国家级储备库进行，所以不考虑企业的最大库存。如果汛期路段14、23、11、25、26、27、9、31因洪水交通中断，222Dijkstra进行适当改进，将中断路段删去，并在程序中进行修改即可。5：（件1→262515421→2619181→2625154228293039321→2625154228293039321→201→2013121031→26251542281→2625154228293039321→30131→26251542282922→422→4215182→6→409→31322→6→4092→421518192→6→409→2→32→42282→6→409→31322→6→409→31322→6→43→323930293→32393029284215183→323→323→1→2→9→27132053→1→333→3239303→323→1→2→93→32392： 低 费 元点38最短的时间内使得企业完成任务因此我们延用问题二中的时间最少模各约束条件与问题二中的时间最少模型的约束方程相同求解出完成各某些是绕道的，所以各库达到预测值时所用费用增大至529349.8元，119539.1元。此时的方案为：x11x1ay51

x36x3ay52

x37x2by34

x38x3by38

仓库1百件

同理，可求出完成最大值的时间为46.9天，同样是由于线路中断，使得各库达到最大值是的费用为993889.3元，比中断前多用了170154.6元。 x12x27x38

x21x33x1a

x22x34x2b

x25x36x3b

百件储备库1⑴DijkstraDijkstra⑵在解决问题2时，分别建立了时间最少模型和 4.2我们需要着重考虑钢铁工厂与钢铁煤炭等原料产地的距离从而利用Dijkstra [M].2003.5[2]夏少刚.运筹学[M].：，2005.9[3]康跃.运筹学OperationalResearch[M].：首都经济贸易大学出[4]，.数学实验[M].：高等教育 谢金星.数学模（第三版 高等教 1：Dijkstra

function[s,d]=minroute(i,m,w,op