《东三省建模联赛论文C题》由会员分享，可在线阅读，更多相关《东三省建模联赛论文C题（15页珍藏版）》请在金锄头文库上搜索。
1、物资分配问题摘要在各种各样的抢险救灾行动中，应急物资的合理分配在降低灾害的影响方面体现出重要作用。我们通过对问题的深入理解和分析，将问题归结为非线性规划问题。我们首先确立了通过合理优化救灾物资的分配使其能最大限度降低灾害的影响为根本分配原则。 接着我们根据不同物资在维持灾民正常生活中所起到的作用大小不同划定了各物资的优先级，给定了适当的权重；接着综合考虑各个灾民所缺物资的数量、种类、供给量及物资的权重，确定了不同灾民受灾程度的判定标准；随后对受灾情况和物质分配情况进行了矩阵描述。在此基础上我们用救灾效果表示整个救灾过程使灾情降低的程度，并假设每分配出一个最小单位的救灾物资就相应产生一定量的救灾
2、效果，最终整体救灾效果为它们之和。我们又进一步假设每个最小单位救灾物资产生的救灾效果与分配物资的权重、分配给的灾民受灾程度正相关，得到了基本的数学模型：单位物资救灾效果 = 该物资权重 分配给灾民的受灾程度最终救灾效果 = 单位物资救灾效果求和模型的约束条件由各种物资的数量有限得到。我们以最大限度减小灾害影响为分配原则，即最大限度增强最终救灾效果，在此抽象为求解最终救灾效果在约束条件下的最大值。其对应的最优解即为最佳分配方案。 在模型求解中，我们本着最大程度地发挥各种物资效用的原则，按照物资的优先级从高到低逐一对物资进行了分配。在具体分配某一物资时，首先求得分配结果与产生的救灾效果的函数，继而
3、简化为有约束的多元函数最值问题，并分别采用了MATLAB程序解法和拉格朗日乘数法。 紧接着我们给出了一个具体灾情，并用量化后的模型求出最优解，通过对结果的分析研究讨论了模型的合理性。 最后，我们对模型的优缺点进行了讨论，并提出了模型的改进方案，并且对模型的实际应用做了推广。关键词 救灾效果 物资权重 受灾程度 单位物资一、问题重述某一灾区有N名受灾群众，现有一批救灾物资要发放给这些受灾者。物资共有M种，每种物质的数量有限；各受灾者的灾情不同，对每种物资的急需程度和需求量不同。（1） 你作为一名分配者，请制定分配原则并给出合理的分配方法。（2） 试给出一个符合题意的数值算例。二、符号说明与基本假
4、设2.1 符号说明符号含义第i位灾民第j种物资第j种物资总量第i位灾民短缺第j种物资的数量第i位灾民分配到的第j种物资的数量 第j种物资的权重第i位灾民的受灾程度 2.2 基本假设1. 所有物资对降低灾害的贡献取决于每单位物资贡献之和2. 每单位物资对降低灾害的贡献与该物资的作用大小正相关3. 每单位物资对降低灾害的贡献与得到该物资灾民的灾情大小正相关4. 每种物资的供给均小于需求三、问题分析与基本思路为减轻自然灾害的影响，对应急物资分配策略的研究就有了十分重要的意义。通过对问题的分析与理解并结合实际情况，我们给出了抗险救灾中物资分配的基本原则：在应急物资有限的情况下，对救灾物资进行最优分配，
5、使得分配结果能最大限度地降低灾害。我们用最终救灾效果表示物资分配降低灾害的程度，那么分配原则就等价于使最终救灾效果最大。而最终救灾效果又与每单位物资产生的救灾效果有关。通过给出物资权重和受灾程度的概念我们对每单位物资产生的救灾效果进行了数学表示，从而通过求和，最终确定了主函数最终救灾效果。在求解模型时，由于非线性离散优化问题的求解十分困难，我们进行了适当的简化，转化为非线性连续优化问题，继而通过MATLAB优化工具箱和拉格朗日乘数法求解了模型。 在此我们给出整体研究思路： MN矩阵对物资需求的描述目标函数规划受灾程度的 分析判定物资权重的说明与优先级划分Matlab优化工具箱拉格朗日极值MN型
6、矩阵描述物资分配的方案具体算例比较模型改进与推广优缺点评价 四、模型的准备4.1 物资需求状况的描述某地区遭受灾害的一种表现形式为该地区灾民的各种生活物资出现了不同程度的短缺。为了描述灾情即各个灾民缺少各种物资的量，我们建立了NM型矩阵A： 其中表示灾民缺少物资的量。 A中数据由物资分配者通过对灾情的调查得到，均为非负常数。其中A的行向量表示灾民对不同物资的需求量。A的列向量表示整个灾区对物资的需求量情况。4.2 物资权重的说明由于不同物资在维持灾民正常生活中的作用不同，相同量的不同物资在减轻灾害的效用上不同。为表征物资的这一特性，我们首先将物资化分为四大类，并为其评定了优先级。优先级物资大类
7、举例最高优先级关键物资应急食品：方便面、矿泉水等较高优先级基础物资衣被、棉被等中等优先级重要物资大米、面粉、豆油等较低优先级可替代物资其他生活物资：帐蓬等根据物资所属大类及其优先级，按优先级与权重正相关的原则，给于物资合理的权重，规定10。4.3 受灾程度的评定为表征不同灾民受灾严重程度的大小不同，引入函数表示灾民的受灾程度。受灾程度取决于短缺物资的种类和数量，同时受灾程度也与供给物资总量有关，当物资充足，受灾程度就相应较小。假设某一时刻灾民已分到各物资的量为，我们定义这一时刻为： ， 4.4 分配方案的描述为了说明某一时刻分配出去物资的情况，我们建立了NM型矩阵B： 这里表示该时刻已分配给灾
8、民物资的数量。其中B的行向量表示该时刻灾民已分配到各种物资的数量，B的列向量表示该时刻已分配出物资的情况。五、模型的建立5.1 目标函数说明 设函数y表示最终救灾效果，则目标函数为 ，（1）设物资的第k个单位量分配给灾民之后产生的救灾效果为。则由假设2和3可得。（2）当物资分配该灾民的数量为时，物资在灾民上产生的救灾效果之和为。（3）物资全部分完后在所有灾民中产生的救灾效果之和为（4）所有种物资分配完后，得到最终救灾效果为：从而 目标函数进一步表示为： 5.2 约束条件本题约束条件为：各种物资的数量有限，即物资的分配总量不大于其给供给总量，通过4.4中矩阵B的列向量，可将约束条件表述为:同时附
9、加一约束条件：灾民得到物资的量不大于其需求总量，即：。六、模型求解6.1 分配次序的确立 根据不同物资的优先级，对物资进行排序。考虑到实际救灾中必须优先对关键性物资进行分配，我们按物资的优先级从大到小进行排序，之后再逐一对每种物资进行分配。 不妨设排序后物资先后顺序为。6.2 物资的分配方法按排序后的物资的顺序逐种进行分配，假设已分配了种，现给出第种j物资的分配方法：（1）设前种物资分配情况为矩阵B：用A表示此时各种灾民物资短缺情况则有 （2）设对的分配方案为，即灾民分到物资的数量为。未分时，灾民的受灾程度为： 当灾民得到1个单位物资时，产生救灾效果为： 此时，由于得到一个单位，发生变化；当再
10、得到一个单位时，产生救灾效果为： 以此类推，当得到第个单位时，产生救灾效果为：综上，当分到的数量为时，产生的救灾效果之和为： 所以最终 。 即当只针对进行分配时目标函数为：约束条件为：（3）MATLAB程序直接求解在分物资时，目标函数为关于的N元二次函数，约束条件为。此时可直接利用MATLAB程序求出最优解。（4）利用拉个朗日乘数法继续化简 引入变量，对方程两边分别对求导，得到由i+1个一次方程组成的方程组。求解该方程组得到可疑点。将可疑点回带到目标函数，取其中使函数值最大的一组解即为最优解。（5）结果的处理 因为非离散的最优解问题处理起来过于困难，我们在此将其近似为连续的最优解问题，但这使求
11、解出的结果可能不为整数。我们对求解出的结果按实际情况进行了合理调整之后得到了最终分配方案。七、数值算例为了对问题进行进一步说明，并讨论和证明该模型的合理性，我们假设了一个具体情景，给出了具体的数据对模型进行了量化。在此基础上我们使用MATLAB程序求解了最优解并对其进行了分析。7.1 问题背景2008年春节期间，南方发生了几十年不遇的特大雪灾。假设某山区十几位居民遭雪灾围困，与外界失去短暂联系，灾民的各种生活物资出现程度不同的短缺。现已将紧急抽调的一批救灾物资运送到该灾区，但由于时间仓促运抵的物资不能完全满足需求。我们利用模型求解最佳分配方案。7.2 数值算例（1）不妨设灾民的物资短缺情况（受
12、灾情况）经调查如下表所示：灾民需求表物资 灾民123456789方便面 （袋）1011789101289羽绒服 （件）111011001大米 （斤）202518262020162922帐篷 （件）100110111101112131415161718方便面 （袋）121412918810158羽绒服 （件）011101100大米 （斤）183016222518241625帐篷 （件）011000110由该表我们就得到了模型所需矩阵A。对应于我们研究的物资分配问题，其中M=4，N=18。（2）对四种物资方便面，羽绒服，大米，帐篷，考虑到方便面能立即解决暂时的吃饭问题，羽绒服对于抗寒作用重大，而大
13、米发挥作用较慢但是基础物资，帐篷作用最小。据此我们规定方便面优先级最高，其次分别为羽绒服，大米，帐篷。用分别表示方便面，羽绒服，大米，帐篷的权重。不妨设我们假设方便面，羽绒服，大米，帐篷的供应量分别为160，8，320，6。则各物资需求总量，供应总量和权重如下表所示： 方便面（袋）羽绒服（件）大米（斤）帐篷（件）总量16083206需求2001139010物资权重0.90.70.50.3（3）我们利用所建立的模型首先对方便面进行了分配，得到一组结果，在此基础上，我们根据每人所得物资不超过其需求的原则对数据进行了化整和进一步优化得到了最终分配方案。再将得到的最终结果回带到方程中继续求解下一种物资的分配方案并作同样的优化处理。以此类推求出所有分配结果。在对目标函数的求解过程中，我们对其作了微小的改动，将其整体乘以（-1），转化为求函数的最小值，于是在应用MATLAB优化工具箱时，我们便于应用fmincon函数来进行求解。求解过程中，我们对目标函数的变化趋势作了进一步的图形分析，得出以下四组目标函数变化曲线：从四组曲线的变化趋势中，我们可以看到，目标函数值收敛，趋于最小值，这也证明了我们建立的数学模型的合理性。对四种物资分配的最初计算结果与最终优化结果如下表所示：
