地震灾区紧急资源的最优调度问题.docx

A题 资源的最优分配与调度问题摘要 近年来全球的大规模自然灾害频繁发生，海啸、地震、飓风等，特别是2008年发生在我国四川汶川地区的大地震，是我国自建国以来影响非常大的一次灾害，造成了大量的人员与财产损失。因此，在地震发生后，将救援队伍与紧缺物资快速合理地分配调运到指定受灾区域对抗震救灾工作具有重要的意义。本文针对灾区的受灾程度及其地理位置的不同，采用了线性规划的01模型、Floyd最短路径法、匈牙利算法等，研究了在最短时间内实现对人力资源以及物资资源的最优调度与分配方案。我们考虑到受灾地区之多，受灾情况的不同，以及救援队伍和救灾物资的限制，建立了线性规划中的01模型。对于192个特灾区，我们首先分配相应的192支A类救援队伍进行急救，争取在最短时间内分配救援人员和物资到达灾区。对于514个重灾区，我们先分配106支B类队伍去距离较远的106个重灾区施救，接着附近剩余的412个重灾区分别由其他204支C类队伍进行施救，且每支队伍负责救援2个灾区。然后借助于Floyd最短路径算法计算出救援队伍集结点到灾区的最短路径，进一步利用Matlab软件对数据进行计算和筛选，去除异常数据，得到合理有效的方案。由于灾区情况紧急，不能及时调度大量飞机进行救援，所以为了简化问题，我们假设只用陆运去施救，而且陆运救灾队伍和物资都可以到达各个灾区，由此可建立最短路径模型。我们采用了匈牙利算法求得路由矩阵，并利用Lingo软件计算，从而得出快速合理的调度方案。关键词 线性01规划；Floyd最短路径法；匈牙利算法；权值最小1 问题重述灾难无情人有情，一方有难，八方支援,灾难激发了全国同胞众志成城、携手并肩救死扶伤、战胜困难、重建和谐生活、重建美好家园的决心和信心。当地震、瘟疫等灾害事件发生时，如何在最短时间内实现对人力资源以及物资资源的最优调度与分配是十分重要的问题。2008年我国的四川汶川地区发生的大地震是我国自建国以来影响非常大的一次地震，造成了大量的人员与财产损失。因此，我们的救援队伍要以最快速度、最大资源、最大效率进行快速合理的救援。问题分析：（1）参照附录中的表（2）和表（3）所给出的灾区的x和y坐标，由于受灾区的地理位置不同，而且受灾程度也不同，所以为了最大限度进行合理施救，我们要由重到轻、由近及远依次救援，先要解决燃眉之急。即每个特灾区均分配一支救援队伍施救，每两个重灾区至少分配一支救援队伍进行施救，做出最优的救援方案。（2）我们有500支救援队伍，分别分布在30个不同的集结点，根据,队伍的集结点位置和灾区的地理位置，尽可能选择最短路径进行施救。由受灾区域的道路网络示意图（图01/02）可以看出，特灾区相对比较集中，故先调度192支救援队伍抄近路对其施救。然后根据受灾乡镇之间的道路是否通路的情况，再调度剩余的308支队伍分别对各个灾区进行施救，争取在最短时间内，选取最短路径到达受灾区，最快速度抢救被困群众，最大限度降低灾害损失。灾难不等人，我们更不能怠慢，灾难面前，人人有责。 下图是部分特灾区，重灾区和救援队伍的分部示意图：图1：部分特灾区，重灾区和救援队伍的分部2模型假设（1） 将每支A救援队伍看成是一个整体。（2） 将每支B救援队伍看成是一个整体。（3） 将每支C救援队伍看成是一个整体。（4） 192个特灾区所辖的每个乡镇均分配一支A类救援队伍。（5） 408个重灾区所辖的邻近的两个区县都均分配一支B类救援队伍。（6） 106个重灾区所辖的每个乡镇均分配一支C类救援队伍（7） 分配好的救援队伍到达各个乡镇之间的道路无阻塞。（8） 紧急情况之下，没有空救，只有陆运救援队伍。（9） 所有特灾区灾情差不多，所有重灾区灾情差不多。（10） 每支救援队伍到达灾区的速度是一样的。3符号说明m：救援队伍的数量；n：受灾地区的个数；A:救援某一个特灾区的队伍类型；B: 救援某两个重灾区的队伍类型；C: 救援某一个重灾区的队伍类型；(i=1,2,m;j=1,2,n）:决策变量；（i=1,2,m;j=1,2,n）:第i支队伍救援第j个灾区；（i=1,2,m;j=1,2,n）: 第i支队伍救援第j个灾区的最短距离；G（V，E）：灾区网络图，V是灾区点的集合， E是连接每两个灾区的道路边的集合。4 模型建立与求解4.1模型建立根据各个灾区的地理位置，将其简化为图模型，即以各个灾区之间相通的道路建立网络图G（V，E），V是灾区点的集合，共有706个灾区，则就有706个点。E是连接每两个灾区的道路边的集合，共有706条边，每条边赋予一个权值，即就是灾区之间的距离。考虑到受灾地区之多，受灾情况的不同，以及救援队伍和救灾物资的限制，我们依据模型的建立，我们首先分配192支A类救援队伍对192个特灾区进行急救，争取在最短时间内分配救援人员和物资到达灾区。然后我们再分配106支B类队伍去距离较远的106个重灾区施救，接着附近剩余的406个重灾区分别由其他204支C类队伍进行施救，且每支队伍负责救援2个灾区。4.1.1 0-1规划模型：定义决策变量= 特灾区救援：目标函数：min z= s.t. 约束条件：救援特灾区的A类队伍是1192个，即1i192.相应的特灾区也是1192，即1j192.重灾区救援：min z= s.t. 约束条件：救援特灾区的B类队伍是1310个，即1i310.相应的重灾区也是1514，即1j5 匈牙利算法的基本原理：简要地讲，求指派问题的最优解就是要在n 阶系数方阵中找到n个这样的元素：它们分布在方阵的不同行、不同列上，并且这些元素之和为最小。而要使这些元素之和为最小，就要使其中的每一个元素尽可能的小最好这些元素都是其所在行和列的最小元素。而指派问题的最优解又有这样的性质：如果从分配问题效率矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵求得最优解相同。由于新矩阵中每行、每列的最小元素均为“0”，因此，求原指派问题的最优解就转化为在新矩阵中找出n个分布在不同行、不同列上的“0”元素（简称为独立0元素），这些独立0元素就是新矩阵的最优解，找到新矩阵的最优解也就找到原矩阵的最优解了。要在新的矩阵中找到几个分布在不同行，不同列上的“0”元素，前提首先是在新矩阵中确定存在几个这样的“0”元素。那么，如何判断在新矩阵中是否存在n个这样的独立0元素呢？考尼格证明了这样一个定理：“覆盖所有”0“元素的最少直线数等于矩阵中独立元素0的最多个数。利用这一定理，就可以通过寻找“能覆盖所有0元素的最少直线”来确定新的矩阵中独立0元素的具体数量。倘若新矩阵中独立0元素的数量小于矩阵的阶数n,就得继续对新矩阵进行化简，直到有了n个独立的0元素为止，找到这n个独立元素也就找到了救援队伍指派问题的最优解。4.2 模型求解本题是最优分配问题，众所周知，此问题属于NP 完全问题，即求解没有多项式时间算法.( Non-deterministic Polynomial )显然本问题更应属于NP完全问题. 有鉴于此一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解。4.2.1 Matlab软件处理数据将题目所给出的表（1）、（2）、（3）、（4）中的各个数据输入到Matlab软件编辑窗口中，根据表（2）和表（3）给出的每个灾区的地理坐标，计算出图中每条边的权值并按照权值升序的顺序排列，形成能够显示边信息的矩阵K。因为救援队伍分散在不同的集结点，故将每支救援队伍分配到与它距离最近的受灾区域，并假设存在任一条通路，可以使救援队伍到达。4.2.2 Floyd算法计算任意两点之间的距离（1） 按照Floyd最短路径算法（附录一），计算出网络图G中每个顶点到其它顶点的最短路径矩阵d和路由矩阵r，部分如下矩阵d和路由矩阵r如下：（2）表1：最短路径d123456789101110.00E+007.24E+052.66E+05Inf3.52E+054.10E+057.07E+051.17E+06Inf8.49E+059.42E+0527.24E+050.00E+009.90E+05Inf3.72E+051.13E+061.68E+044.80E+05Inf1.59E+052.51E+0532.66E+059.90E+050.00E+00Inf6.18E+051.44E+059.73E+051.44E+06Inf1.11E+061.21E+064InfInfInf0.00E+00InfInfInfInf4.26E+05InfInf53.52E+053.72E+056.18E+05Inf0.00E+007.61E+053.56E+058.19E+05Inf4.97E+055.90E+0564.10E+051.13E+061.44E+05Inf7.61E+050.00E+001.12E+061.58E+06Inf1.26E+061.35E+0677.07E+051.68E+049.73E+05Inf3.56E+051.12E+060.00E+004.63E+05Inf1.42E+052.35E+0581.17E+064.80E+051.44E+06Inf8.19E+051.58E+064.63E+050.00E+00Inf3.21E+052.29E+059InfInfInf4.26E+05InfInfInfInf0.00E+00InfInf108.49E+051.59E+051.11E+06Inf4.97E+051.26E+061.42E+053.21E+05Inf0.00E+009.27E+04119.42E+052.51E+051.21E+06Inf5.90E+051.35E+062.35E+052.29E+05Inf9.27E+040.00E+0012InfInfInf1.43E+05InfInfInfInf2.83E+05InfInf131.29E+071.22E+071.32E+07Inf1.26E+071.33E+071.22E+071.27E+07Inf1.24E+071.25E+0714InfInfInfInfInfInfInfInfInfInfInf15InfInfInfInfInfInfInfInfInfInfInf16InfInfInfInfInfInfInfInfInfInfInf17InfInfInfInfInfInfInfInfInfInfInf18InfInfInfInfInfInfInfInfInfInfInf19InfInfInfInfInfInfInfInfInfInfInf20InfInfInfInfInfInfInfInfInfInfInf21InfInfInfInfInfInfInfInfInfInfInf22InfInfInfInfInfInfInfInfInfInfInf23InfInfInfInfInfInfInfInfInfInfInf表2：路由矩阵r153453559557274777797711341611911123456781210111714517797733343633933525455710910101111114111111891111123125678910117774777119101110101041010108910111234567891011777477779771234567891011123456789101112345678910111234567891011123456789101112345678910111234567891011123456789101112345678910111234567891011（2）在矩阵K中，找到前面距离较短的204条边，因为K中边的长度是按照从小到大的顺序排列的。将这204条边的每条边的两个端点看作一个整体，则相当于B类救援队伍去救由两个端点所组成的一个整体灾区，这就简化成了共有502支队伍救援502个重灾区。再将502支队伍从第一个集结点开始依次编号，此问题就可以看作是匹配问题，使得边权值之和最小，即救援路径最短，利用匈牙利算法便可对此问题进行求解。（3）匈牙利算法是实现二部图的分配问题的方法，因此首先要先建立每个队伍到达各个灾区的最短距离矩阵。本次求解根据假设，可以利用、软件编写程序（附录2），建立救援队伍i（1=i=502）和灾区j(0=j=706)之间的最短距离矩阵si(附录3)。由于匈牙利算法要求所输入的矩阵是方阵，而si矩阵是706*502的行列不等矩阵，则需要删除掉204行，即去除204个顶点，再将502个灾区重新排号。为降低求解的复杂度，删除矩阵K的第一列的前204个顶点所对应的204行，则得到502*502的一个方阵，再将此方阵转置得到矩阵sii,即可方便求解。 程序如下：for i=1:204 si(K(i,1),:)= i=i+1;end（4）匈牙利算法求解步骤（程序见附录4）：设图G=(X, Y，E)是一个二元图,M是任意一个匹配:Step1:令S=kkong,T=yihuo；转Step2；Step2:若M饱和X/S的每个顶点,则M是最大匹配,否则,取M-非饱和点uX/S,令S:=Su；转Step3；Step3:若N(S)=T,转Step6,否则取yN(S)/T。若y是-M饱和点,转Step4,否则转Step5。Step4:存在xX使得(y, x)M,则令：S:=Sx, T:= T y,转Step3。Step5:u-y路是M-增广路,设为P,并令M:=MyihuoP,转Step1；Step6:若X/S=kong，则M是最大匹配,否则转Step2。（5）打开匈牙利算法的程序，在Command Window中输入matching，cost=Hungarian(sii)，调用编写的匈牙利函数，返回的matching矩阵是一个大小与sii完全相同的0，1矩阵，其中0元素表示sii中相同位置的元素未被选中，1表示A中相同位置的元素被选中。由于matching矩阵中0元素较多，为了能够更加清楚显示某个救援队伍营救具体的灾区的情况，编写函数如下：row,col=find(matching=1);final=row,colfinal矩阵中显示的就是某个救援队伍营救某一个灾区的情况。cost是指救援所需要经过的最短距离。经过Matlab软件的计算，可以等到cost=7.7266e+075 模型评价本文主要采用Floyd最短路径算法，匈牙利最优分配分配算法，0-1整数规划模型等对地震灾区紧急资源的最有调度问题进行研究，其中，用Floyd算法并结合就近原则进行研究，同时利用最优分配的匈牙利算法，较好的对救援队和灾区之间进行了分配，并且可以根据路由矩阵，最快的达到灾区，假设合理，结果较好。但是本文也存在着一些不足之处，模型假设中一个救援队伍只能救一个特灾区，一个救援队伍可以救两个重灾区，这一条假设存在着很大的特殊性，若非政策要求，不然这只是可能性的一种，应该在队伍中做一个有效的分配。其次，过程中用到的近似和等价思想可能对结果产生一定的偏差。另外，模型求解中将灾区重新排列后，在最后的方案中没有做进一步的将灾区重新还原成原来的序号。6模型改进本文求解的假设之一是建立在每条道路交通都完好的情况下，也就是每个救援队都能顺利的通过这条道路，达到灾区，但是，地震所造成的危害是巨大的，往往会导致道路发生损害，那么就不能按照原来设定好的路径的方式，那么就需要改变路径，在本次求解中我们已经根据floyd算法得到每两个点之间的最短路径矩阵d和路由矩阵r，当有道路发生损害时，即图中某条边缺少，此时就要重新计算边权的矩阵，用Dijkstra算法计算出这一点道所有点的最短距离矩阵和路由矩阵，再按照前面所讲述的方法得到新的路径。参考文献1姜启源，谢金星，叶俊.数学规模(M)：北京.高等教育出版社，2003.2袁新生.Lingo和Excel在数学建模中的应用M.北京.科学出版社：2007。3王琦.MATLAB基础与应用实例集萃I.北京：人民邮电出版社，2007.4谭用基，蔡志杰.数学规模M.上海.复旦大学出版社.2005.5孙勇.基于网络模型的应急资源优化配置J.计算机工程。1:290-292,20116卓金武.Matlab在数学建模中的应用（M）：北京.北京航空航天出版社，2011.47王海英，黄强，李传涛，褚宝增.图论算法及其Matlab的实现（M）：北京.北京航空航天出版社，8/matlabcentral/fileexchange/11609-hungarian-algorithm附录一 Floyd程序function d,r=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end %r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) P_size; jj = 1; ii = ii+1; end if ii P_size; exit_flag = 0; end end if row = 0 stepnum = 6; zflag = 0; Z_r = 0; Z_c = 0; else M(row,col) = 2; if sum(find(M(row,:)=1) = 0 r_cov(row) = 1; zcol = find(M(row,:)=1); c_cov(zcol) = 0; else stepnum = 5; zflag = 0; Z_r = row; Z_c = col; end endend function M,r_cov,c_cov,stepnum = step5(M,Z_r,Z_c,r_cov,c_cov) zflag = 1; ii = 1; while zflag rindex = find(M(:,Z_c(ii)=1); if r