线性规划法在救援物资调运问题中的应用1

《运筹学教程》综合设计项目名称：线性规划法在救援物资调运问题中的应用2011年122011年12月19日组长：学号：——姓名：—成员：学号：—姓名：_学号：姓名：学号：姓名：开课学期：2011至2012学年第一学期指导教师：完成时间:成线性规划法在救援物资调运问题中的应用【摘要】最近几年，我国物流产业快速发展，形成了物流热，在物流作业管理中，有着大量的规划问题，物资的合理调运就是其中一个比较重要的问题。本文通过建立线性规划模型，利用线性规划法，用Excel求出了物资调运问题的最优解，得到了一个最佳的物资调运方案。分析的过程中，我们要确定出合适调运方案，使运输总费用最小，即将“费用最小化”作为调运最终目标。在具体的求解过程中，借助运筹学相关知识将此问题转化为线性规划模型的最优解求解问题，并建立线性规划模型、运用Excel软件得出最优化解。【关键词】：线性规划法；Excel；调运，运输总费用，最优解一、问题提出由于近几年来地壳运动剧烈，各种自然灾害频频发生，其中各地的地震灾害尤其严重。汶川地震发生后，为了尽可能的减小国家和人民的损失，各级政府对灾区进行物资救助。为了解决大规模物资调运的实际问题（通常要处理的实际问题都是大规模的物资调运问题）以及物流管理中的类似问题，我们必须先建立这类问题的数学模型，而后选择合适的计算方法并利用计算机工具求解。这种数学模型称为规划问题，规划问题中涉及的线性函数关系，我们就称为线性规划问题。本文将在物资调运中的实际问题建立数学模型，用Excel求出物资调用的最优方案。我们首先应确立线性规划的模型和其应用以及Excel的作用。一、线性规划问题及其数学模型线性规划的模型决定于它的定义，线性规划的定义是：求一组变量的值，在满足一组约束条件下，求得目标函数的最优解。根据这个定义，就可以确定线性规划模型的基本结构。（1）变量又叫未知数，它是实际系统的未知因素，也是决策系统中的可控因素，一般称为决策变量。（2）目标函数将实际系统的目标，用数学形式表现出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。（3）约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面，如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件。约束条件的数学表示形式为三种，艮吃、=、〔线性规划的变量应为正值，因为变量在实际问题中所代表的均为实物，所以不能为负。在经济管理中，线性规划使用较多的是下述几个方面的问题：（1）投资问题一确定有限投资额的最优分配，使得收益最大或者见效快。（2）计划安排问题一确定生产的品种和数量，使得产值或利润最大，如资源配制问题。任务分配问题一分配不同的工作给各个对象(劳动力或机床)，使产量最多、效率最高，如生产安排问题。下料问题一如何下料，使得边角料损失最小。运输问题一在物资调运过程中，确定最经济的调运方案。库存问题一如何确定最佳库存量，做到即保证生产又节约资金等等。应用线性规划建立数学模型的三步骤：明确问题，确定问题，列出约束条件。收集资料，建立模型。模型求解(最优解)，进行优化后分析。其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。本题我们选取了运输问题来建立模型。二、Excel的简介：Excel是分析和求解线性规划问题的良好工具，它不仅可以很方便地将线性规划模型所有参数录入电子表格，而且可以利用规划求解工具迅速找到模型的最优解。更重要的是，在利用Excel电子表格求解模型时，改变任何参数都能立刻反映到模型的解，不需要重新应用求解工具和重新录入数据，即使重新求解也只需按回车键即可完成。当然，Excel不但可以处理线性规划问题，还可以处理整数规划和运输问题等经典的线性规划问题，极大满足了人们学习运筹学和在实践中解决线性规划问题的需要。二、物资调运问题针对物资调运，我们想到了关于在自然灾害发生时，我们向受灾点调运受灾物资的情形。但运输物资，需保证物资的完备性，必须满足受灾点的需要。并且更主要的也要考虑运输的总费用最低，从而节约成本。针对这些现象，我们找了一个案例用来分析物资调运问题。以下就是我们所收集的资料和数据：现有三家企业捐献物资调运到四个受灾点。企业A，B，C捐赠物资量分别为110吨、70吨、100吨；四个受灾点I，Il，III，W，需求量分别为60吨、70吨、50吨、70吨。企业A往受灾点I，II，III，W每吨的运价分别为l0元、15元、20元、25元；企业B到受灾点I，II，III，W每吨的运价分别为2O元、10元、l5元、15元：企业C到受灾点I，II，III，W每吨的运价分别为25元、30元、20元、25元。如何确定调运方案，才能使运输总费用最小。在这个题目中我们所了解的约束条件主要有三个：一是企业捐赠物资量的限制，总数是280吨，而其中A企业捐赠110吨，B企业捐赠70吨，C企业捐赠100吨，我们在计算各受灾点需求量的时候绝对不能超过这个量；二是各受灾点需求量的限制，受灾点收到的物资不得小于它们的需求量，也就是说各受灾点需求量是下限；三是调运物资的数量的限制，企业运输到受灾点的物资数量必须大于等于零。在这些约束条件的限制下，我们经过计算，得出运输总费用为3800元，并且各受灾点所需的物资量达到满足。下面我们就把该问题规范为一个线性规划问题，用相关Excel求解。首先我们需要的是目标函数，毫无疑问，这里肯定是以运输费用最小化作为目标。费用是用各点的运价乘以它们的需求量，再汇总求和，计算出最小值。其主要的项目和数据如下表：运输费用数据表\受灾点企业'IIIIIIW供应量A10152025110B2010151570C25302025100需求量60705070首先，设运输总费用为W，我们要求运输总费用最小，现在我们可以得到目标函数了，即目标函数为：MinW=10x+15x+20x+25x+20x+10x+15x+15x+25x+30x+20x+25x111213142122232431323334得到目标函数之后我们需要把约束条件列出才能求解，那现在我们依据前文的描述可以知道，约束条件共有三各方面，分别是企业捐赠物资量的限制，各受灾点需求量的限制，调运物资的数量的限制。其中孔表示从企业i调运到受灾点j物资的数量，minW表示运输费用最少。考虑约束条件如上表所述的供应量和销地的需求量要满足运输平衡条件，以及各变量取非负数，就是限制条件。首先是供应量方面，即四个受灾点的物资需求量不能超过三个企业的供应量。所以有x+x+xx<=110，x+x+xx<=70，x+x+xx<=100；111213+14212223+24313233+34然后是需求量方面，三企业分别运输到四个受灾点的物资的总和不能少于受灾点的需求量，否则就不能得到满足。所以有x+x+x>=60，x+x+x>=70，x+x+x>=50，112131122232132333x+x+x>=70；最后是调运物资的数量方面，即分别运输到各受灾点的物资要大于等于142434零。所以有Xij^0(i=1,2,3;j=1,2,3,4)经过上面的描述，我们经过整理之后可得如下约束条件：rx+x+xx<=110111213+14x+x+xx<=70212223+24x+x+xx<=100313233+34x+x+x>=60112131xi2+x22+x32>=70x+x+x>=50x+x+x>=70142434孔日0(1=1,2,3门二1,2,3,4)最后，我们将目标函数和约束条件写在一起，就得到了物资调运问题的数学模型，即线性规划问题：MinW=10x+15x+20x+25x+20x+10x+15x+15x+25x+30x+20x+25xTOC\o"1-5"\h\z111213142122232431323334rx+x+x<=110111213x21+x22+x23<=70x31+x32+x33<=100x+x+x>=60112131x12+x22+x32>=70x+x+x>=50x+x+x>=70142434IXjjN0(i=1,2,3;j=1,2,3,4)三、用Excel实现结果卜面我们根据建立出来的数据模型用Excel来计算出结果。具体过程如下：(1)根据题目把表中的数据以及所有约束条件及数据输入Excel中，如图所示:对每一步进行求解，求解过程如下：11|A]二11)|12|B=suid(B12:E12)CB_=suid(B11:B13)C||=SUIo(Cll:C13)|=suid(E11:E13)(2)分别建立单位运价表和调运量表:从调运量表工厂IIIIIIIV605000B020050I-100502060705070(3)通过规划求解参数来求出问题最优解:j=S1-UTl(B13:E13)|=BH=suid(D11^D13)决策变量运输问题规划求解参数设置:由上述计算结果可知，、二60,X12=50,X13=0X2「0,X/20,X23=0,X=0,X=0,X=50,313233该线性规划的最优解为:X14=0X24=50X34=20由此求出最优值为：minW=3800。即运输总费用的最小值为3800元。并且每个受灾点都达到了它们的需求量。四、总结以上是一个供大于求的运输问题的示例，运用以上示例即可求得一个最佳的物资调运方案。对于平衡问题，只需在填写规划求解参数中添加约束条件时稍做改动即可求解，或者将其转化为平衡问题后建立相应的线性规划模型，再用以上方法求解亦可。通过这个物资运输问题的求解，我们学到了如何去灵活运用线性规划方法来求得运输问题的最优解，知道怎么根据问题来分步建立数学模型，同时也掌握了用Excel求解的方法，使我们更深的认识了运筹学的魅力，也明白了线性规划问题在实际生活应用中求最优化问题时起到了很大的作用。这次的运筹学大作业，我们小组合力完成，分工协作，相互讨论，分工寻找案例，分析数据，绘制表格，列出数据模型，并运用Excel求解，这让我们明白小组合作的重要性，每个成员都尽心尽力，做好自己应该做的工作，但同时我们也意识到这次我们寻找的案例