东三省建模联赛论文c题.doc

- 1 - -物资分配问题物资分配问题摘要摘要在各种各样的抢险救灾行动中，应急物资的合理分配在降低灾害的影响方面体现 出重要作用我们通过对问题的深入理解和分析，将问题归结为非线性规划问题 我们首先确立了通过合理优化救灾物资的分配使其能最大限度降低灾害的影响为 根本分配原则接着我们根据不同物资在维持灾民正常生活中所起到的作用大小不同划定了各物 资的优先级，给定了适当的权重；接着综合考虑各个灾民所缺物资的数量、种类、供 给量及物资的权重，确定了不同灾民受灾程度的判定标准；随后对受灾情况和物质分 配情况进行了矩阵描述 在此基础上我们用救灾效果表示整个救灾过程使灾情降低的程度，并假设每分配 出一个最小单位的救灾物资就相应产生一定量的救灾效果，最终整体救灾效果为它们 之和我们又进一步假设每个最小单位救灾物资产生的救灾效果与分配物资的权重、 分配给的灾民受灾程度正相关，得到了基本的数学模型：单位物资救灾效果 = 该物资权重 × 分配给灾民的受灾程度 最终救灾效果 = 单位物资救灾效果求和模型的约束条件由各种物资的数量有限得到我们以最大限度减小灾害影响为分 配原则，即最大限度增强最终救灾效果，在此抽象为求解最终救灾效果在约束条件下 的最大值。

其对应的最优解即为最佳分配方案在模型求解中，我们本着最大程度地发挥各种物资效用的原则，按照物资的优先 级从高到低逐一对物资进行了分配在具体分配某一物资时，首先求得分配结果与产 生的救灾效果的函数，继而简化为有约束的多元函数最值问题，并分别采用了 MATLAB 程序解法和拉格朗日乘数法紧接着我们给出了一个具体灾情，并用量化后的模型求出最优解，通过对结果的 分析研究讨论了模型的合理性最后，我们对模型的优缺点进行了讨论，并提出了模型的改进方案，并且对模型 的实际应用做了推广关键词关键词救灾效果 物资权重 受灾程度 单位物资- - 2 - -一、问题重述一、问题重述某一灾区有 N 名受灾群众，现有一批救灾物资要发放给这些受灾者物资共有 M 种，每种物质的数量有限；各受灾者的灾情不同，对每种物资的急需程度和需求量不 同 （1） 你作为一名分配者，请制定分配原则并给出合理的分配方法 （2） 试给出一个符合题意的数值算例二、符号说明与基本假设二、符号说明与基本假设2.1 符号说明符号说明2.2基本假设基本假设 1.所有物资对降低灾害的贡献取决于每单位物资贡献之和 2.每单位物资对降低灾害的贡献与该物资的作用大小正相关 3.每单位物资对降低灾害的贡献与得到该物资灾民的灾情大小正相关 4.每种物资的供给均小于需求三、问题分析与基本思路三、问题分析与基本思路为减轻自然灾害的影响，对应急物资分配策略的研究就有了十分重要的意义。

通 过对问题的分析与理解并结合实际情况，我们给出了抗险救灾中物资分配的基本原则： 在应急物资有限的情况下，对救灾物资进行最优分配，使得分配结果能最大限度地降 低灾害我们用最终救灾效果表示物资分配降低灾害的程度，那么分配原则就等价于 使最终救灾效果最大而最终救灾效果又与每单位物资产生的救灾效果有关通过给 出物资权重和受灾程度的概念我们对每单位物资产生的救灾效果进行了数学表示，从符号含义iP第 i 位灾民jM第 j 种物资iS第 j 种物资总量ijt第 i 位灾民短缺第 j 种物资的数量ijx第 i 位灾民分配到的第 j 种物资的数量 j第 j 种物资的权重ip第 i 位灾民的受灾程度 - - 3 - -而通过求和，最终确定了主函数——最终救灾效果 在求解模型时，由于非线性离散优化问题的求解十分困难，我们进行了适当的简 化，转化为非线性连续优化问题，继而通过 MATLAB 优化工具箱和拉格朗日乘数法求 解了模型在此我们给出整体研究思路：M××N 矩阵对矩阵对物资需求的描述物资需求的描述 目标函数规划目标函数规划受灾程度的受灾程度的 分析判定分析判定物资权重物资权重 的说明与优的说明与优 先级划分先级划分Matlab 优化优化 工具箱工具箱拉格朗日极值拉格朗日极值M××N 型矩阵描述型矩阵描述物资分配的方案物资分配的方案具体算例比较具体算例比较 模型改进与推广模型改进与推广 优缺点评价优缺点评价- - 4 - -四、模型的准备四、模型的准备4.14.1 物资需求状况的描述物资需求状况的描述 某地区遭受灾害的一种表现形式为该地区灾民的各种生活物资出现了不同程度的 短缺。

为了描述灾情即各个灾民缺少各种物资的量，我们建立了 N×M 型矩阵 A：11121211MNNMttt tAtt   … ……… ………… ……其中表示灾民缺少物资的量ijtipjMA 中数据由物资分配者通过对灾情的调查得到，均为非负常数其中 A 的行向量表示灾民对不同物资的需求量A 的列向量表示整个灾区对物资的需求量iau ripjbu u rjM情况 4.2物资权重的说明物资权重的说明 由于不同物资在维持灾民正常生活中的作用不同，相同量的不同物资在减轻灾害 的效用上不同为表征物资的这一特性，我们首先将物资化分为四大类，并为其评定 了优先级优先级物资大类举例 最高优先级关键物资应急食品：方便面、矿泉水等 较高优先级基础物资衣被、棉被等 中等优先级重要物资大米、面粉、豆油等 较低优先级可替代物资其他生活物资：帐蓬等根据物资所属大类及其优先级，按优先级与权重正相关的原则，给于物资jM合理的权重，规定1>>0jMjj4.3受灾程度的评定受灾程度的评定为表征不同灾民受灾严重程度的大小不同，引入函数表示灾民的受灾程度iJip受灾程度取决于短缺物资的种类和数量，同时受灾程度也与供给物资总量有关，当物 资充足，受灾程度就相应较小。

假设某一时刻灾民已分到各物资的量为，ip12iiimxxx、… …我们定义这一时刻为：iJ- - 5 - -， 1()Mijijij jJtx(/)jjjS4.4分配方案的描述分配方案的描述 为了说明某一时刻分配出去物资的情况，我们建立了 N×M 型矩阵 B：11121211MijNNMxxxxBxxx   ………………………这里表示该时刻已分配给灾民物资的数量ijxipjM其中 B 的行向量表示该时刻灾民已分配到各种物资的数量，B 的列向量icu rip表示该时刻已分配出物资的情况jduu rjM五、模型的建立五、模型的建立5.1 目标函数说明目标函数说明设函数 y 表示最终救灾效果，则目标函数为 ，max y（1）设物资的第k个单位量分配给灾民之后产生的救灾效果为jMip, ,i j ky则由假设 2 和 3 可得, ,11i j kjiyJk （2）当物资分配该灾民的数量为时，物资在灾民上产生的救灾效jMipijx jMip果之和为 ,, , 1ijxi ji j k kyy（3）物资全部分完后在所有灾民中产生的救灾效果之和为jM ,, , 111111ijijxxNNNji ji j kji iikikyyyJk- - 6 - -（4）所有种物资分配完后，得到最终救灾效果为：1Mj jyy从而 11111ijxMNjI jikyJk目标函数进一步表示为： 111max11ijxMNjI jikJk5.2 约束条件约束条件本题约束条件为：各种物资的数量有限，即物资的分配总量不大于其给供给jM总量，iS通过 4.4 中矩阵 B 的列向量，可将约束条件表述为:jduu r1Nijj ixS同时附加一约束条件：灾民得到物资的量不大于其需求总量，即：ipjMijt。

ijxijt六、模型求解六、模型求解6.1 分配次序的确立分配次序的确立根据不同物资的优先级，对物资进行排序考虑到实际救灾中必须优先对关键性 物资进行分配，我们按物资的优先级从大到小进行排序，之后再逐一对每种物资进行 分配不妨设排序后物资先后顺序为12MMMM、… …6.2 物资的分配方法物资的分配方法按排序后的物资的顺序逐种进行分配，假设已分配了12MMMM、… …种，现给出第种j物资的分配方法：1j - - 7 - -（（1））设前种物资分配情况为矩阵 B’：1j 111,1212,11,1''00''0'''00jjNN jxxxxBxx       ……………………0 ……………0 ……………0 …………用 A’表示此时各种灾民物资短缺情况则有111112211,11,11,1,121212,12,12,2,1''''' ''jjjjjjjjtxtxtxtttxtxtt AAB     ……………………………………………………………………（（2））设对的分配方案为，即灾民分到物资的数jM12TjjjNjdxxxuu r…ipjM量为。

ijx未分时，灾民的受灾程度为：jMip   111222,1,11,,11,1,,,, 11,1,,, 110'''iiiiii ji jji jji jji MMjMi ki kki kki jj kkji jjjMi ki kki kk kkjJtxtxtxttttxttatatxt   … …… …当灾民得到 1 个单位物资时，产生救灾效果为：ipjM2 , ,11(0)()i jijjijjjjijyJatat - - 8 - -此时，由于得到一个单位，发生变化；当再得到一个单位时，ipjMiJipjM产生救灾效果为：2 , ,21(1)[(1)](1)i jijjijjjjijyJatat 以此类推，当得到第个单位时，产生救灾效果为：ijx jM2 , ,,,(1) iji j xjji ji jyatx综上，当分到的数量为时，产生的救灾效果之和为：ipjMijx2 , ,, , 11[(1)]ijijxxi ji j kjjij kkyyatk 222()(1)/2ijjj ijjjijijx atxx所以最终 。

, 1Nji j iyy即当只针对进行分配时目标函数为：jM1maxmaxNjij iyy约束条件为：1Nijj ixS（（3））MATLAB 程序直接求解在分物资时，目标函数为关于的 N 元二次函数，约束jM1,2,1,,,......jjiji jxxxx条件为此时可直接利用 MATLAB 程序求出最优解 1Nijj ixS（（4））利用拉个朗日乘数法继续化简引入变量，对方程22211()(1)/2()0NNijjj ijjjijijijj iixatxxxS- - 9 - -两边分别对求导，得到由 i+1 个一次方程组成的方程组1,2,1,,,......,jjiji jxxxx求解该方程组得到可疑点将可疑点回带到目标函数，取其中使函数值最大的一组解 即为最优解 （（5））结果的处理因为非离散的最优解问题处理起来过于困难，我们在此将其近似为连续的最优解 问题，但这使求解出的结果可能不为整数我们对求解出的结果按实际情况进行了合 理调整之后得到了最终分配方案七、数值算例七、数值算例为了对问题进行进一步说明，并讨论和证明该模型的合理性，我们假设了一个具 体情景，给出了具体的数据对模型进行了量化。

在此基础上我们使用 MATLAB 程序求 解了最优解并对其进行了分析 7.17.1 问题背景问题背景 2008 年春节期间，南方发生了几十。