救灾物资分配问题_刘艳.pdf

《救灾物资分配问题_刘艳.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、科技信息○高校讲坛○SCIENCE&TECHNOLOGYINFORMATION2009年第15期救灾物资分配问题刘艳(营口职业技术学院辽宁营口115000)【摘要】救灾物资的优化分配属于动态规划法的资源分配问题，即把救灾物资合理地分配给受灾群众，使受灾群众需求的满足程度最大，即分配效益最大。本文针对救灾物资分配的优化设计，介绍了动态规划法在以经济效益为目标建立非线性规划的数学模型，探讨用Matlab语言实现该模型，通过遗传算法工具箱(GAOT)的程序求解。通过编程，对实例的优化过程表明，在动态规化法思想的基础上，利用Ma

2、tlab遗传算法工具箱辅助计算和设计，可使得救灾物资分配的优化设计简捷方便，具有工程实用价值。在实际问题中，综合考虑各种因素后，就要对效益函数的具体确定做出讨论，解决方法也相对复杂。【关键词】动态规划法；优化设计；遗传算法；救灾物资1.模型建立max［gi1(xi1)+gi2(xi2)+…+giN(xiN)］(i=1，2，…，M)1.1引言xi1+xi2+…+xiN=ci(i=1，2，…，M)≥（1）本世纪以来，洪水、地震、SARS、禽流感等自然灾害仍然十分严xij≥aij(i=1，2，…，M；j=1，2，…，N)重，这

3、些灾害不仅造成了重大的人员伤亡和经济损失，而且使城市生式中aij是对xij的约束量，即所限定的最低物资价值。命线系统也遭受严重破坏或对一个国家的发展速度造成不可忽视的若gij(xij)(i=1，2，…，M；j=1，2，…，N)均为线性函数，是线性规划问阻碍，在很大程度上降低、甚至丧失了城市居民的基本生活条件和城题；而若gij(xij)不全是线性函数，一般是非线性规划问题，且当N很大市社会经济运营的基本能力。严重的自然灾害发生后必须有效地将城时，具体求解比较繁琐。但可以将此问题看作是一个多阶段决策问题，市生命线以及人们生活

4、水平基本恢复到灾前水平，并结合灾后新城市给出其动态规划方程式后求解。的崛起不断完善、发展，以适应现代化建设发展的需要。其中，救灾物采用动态规划化法划分阶段，即将物资ci1分配给N个人中的第资的优化分配是灾后恢复必须充分考虑的重要问题之一。救灾物资的一个人为第一阶段；剩余资金分配给剩下的人（第2项直至第N项）中优化分配属于动态规划法的资源分配问题，即把救灾物资合理地分配的第二个人为第二阶段，以此类推，直至最后一个人，即第j阶段。而给受灾群众，使受灾群众需求的满足程度最大，即分配效益最大。一般在第j(j=1…N)阶段上的决策

5、就是对此阶段的剩余资金做出决定，确情况下，最优化效益函数不全是线性函数，而是一个非线性规划问题。定分配给剩下人(第j个人直到第N个人)中第j个人的资金数量应为如果需要受灾群众较多时，则问题求解变得比较困难。因此，应用动态多少。可得动态规划递推方程，即规划法和遗传算法等算法来建立数学模型，将救灾物资的优化设计方fij(cij)=max［gij(xij)+fi(j-1)(cij-xij)］(2)a≤x≤cijiji法中大量的运算交给计算机来完成，成为我们对救灾物资分配优化的式(2)可以从最后一项活动开始进行逆序推算或从第一项

6、活动开探讨方向。始进行顺序推算。关于资源的优化分配问题目前有采用程序估计法研究中低压煤1.2.2动态规划的效率问题气管网震后恢复资源分配优化的报道和建立一个动态优化模型来合动态规划思想设计的算法从整体上来看基本都是按照得出的递理、有效地分配救灾物资的方法，但研究成果极少，研究范围极窄，实推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率用性不强，本文应用遗传算法来处理救灾物资分配问题，思路简明，执往往是比较高的，这样在时间上溢出的可能性不大，而相反，动态规划行简便。需要很大的空间以存储中间产生的结果，这样可以

7、使包含同一个子问1.2动态规划法思想题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这1.2.1动态规划的主要思想以及相关问题描述是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩动态规划法解决多阶段决策过程最优化问题的一种数学方法。这存储，因而空间矛盾是比较突出的。另一方面，动态规划的高时效性往种方法把解决的问题(或任务)划分为若干个阶段(或步骤)，并依序在往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规每个阶段上实施决策，解决各个阶段的问题或完成各个阶段的任务。模的问题如何在基本不影

8、响运行速度的条件下，解决空间溢出的问各个阶段的决策组合起来构成整个过程的一种完成方案。动态规划法题，是动态规划解决问题时一个普遍会遇到的问题。我们希望得到应是在完成整个过程的各方案中确定一种能够使预定目标是最优化方用一种计算精度高、设计效率快的思想及其算法来代替繁冗的处理过案的方法。在救灾物资分配问题中，每个人可看作