运筹学大作业(线性规划问题).doc

线性规划法在救援物资调运问题中的应用 【摘 要】线性规划法是物资调运问题中最常用的一种方法，本文通过建立线性规划模型，用LINGO数学软件求出了最优解，得到了一个最佳的物资调运方案。 【关键词】:线性规划法；LINGO；调运一、引言 由于近几年来地壳运动剧烈，各种自然灾害频频发生，其中各地的地震灾害尤其严重。汶川地震发生后，为了尽可能的减小国家和人民的损失，各级政府对灾区进行物资救助。为了解决大规模物资调运的实际问题(通常要处理的实际问题都是大规模的物资调运问题)以及物流管理中的类似问题，我们必须先建立这类问题的数学模型，而后选择合适的计算方法并利用计算机工具求解。这种数学模型称为规划问题，规划问题中涉及的线性函数关系，我们就称为线性规划问题。本文将在物资调运中的实际问题建立数学模型，用LINGO数学软件求出物资调用的最优方案。一下是LINGO软件的简介。 LINGO是LINGO是Linear Interactive and General Optimizer的缩写，即“交互式的线性和通用优化求解器”，由美国LINDO系统公司（Lindo System Inc.）推出的，可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解优化模型的最佳选择。其特色在于内置建模语言几个内部函数，可以允许决策变量是整数(即整数规划，包括 0-1 整数规划)，方便灵活，而且执行速度非常快。能方便与EXCEL，数据库等其他软件交换数据。二、一个物资调运问题 现有三家企业捐献物资调运到四个受灾点。企业A，B，C捐赠物资量分别为100吨、60吨、90吨 四个受灾点I， Il，III， 需求量分别为60吨、70吨、50吨、70吨。企业A往受灾点I，II，III，每吨的运价分别为l0元、15元、20元、25元；企业 B到受灾点I，II，III，每吨的运价分别为2O元、10元、l5元、15元：企业 C 到受灾点I，II，III， 每吨的运价分别为25元、30元、20元、25元。运输费用数据表 受灾点 企业IIIIII供应量A10152025110B2010151570C25302025100如何确定调运方案，才能使运输总费用最小。首先，设运输总费用为，我们要求运输总费用最小，故目标函数为：Minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+30x32+20x33+25x34其中Xij表示从企业i调运到受灾点j物资的数量，minf表示运输费用最少。考虑约束条件如上表所述的量和销地的需求量要满足运输平衡条件，以及各变量取非负数，就是限制条件。于是可得如下约束条件：x11+x12+x13=110x21+x22+x23=70x31+x32+x33=60x12+x22+x32=70x13+x23+x33=50x14+x24+x34=70Xij0(i=1,2,3;j=1,2,3,4)最后， 我们将目标函数和约束条件写在一起，就得到了物资调运问题的数学模型，即线性规划问题：Minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+30x32+20x33+25x34x11+x12+x13=110x21+x22+x23=70x31+x32+x33=60x12+x22+x32=70x13+x23+x33=50x14+x24+x34=70Xij0(i=1,2,3;j=1,2,3,4)三、用lingo软件实现结果 (1)由上述线性规划模型可得：Global optimal solution found. Objective value: 3350.000 Total solver iterations: 11 Variable Value Reduced Cost X11 60.00000 0.000000 X12 0.000000 0.000000 X13 50.00000 0.000000 X14 0.000000 10.00000 X21 0.000000 15.00000 X22 70.00000 0.000000 X23 0.000000 0.000000 X24 70.00000 0.000000 X31 0.000000 15.00000 X32 0.000000 15.00000 X33 0.000000 0.000000 X34 0.000000 10.00000 Row Slack or Surplus Dual Price 1 3350.000 -1.000000 2 0.000000 0.000000 3 0.000000 5.000000 4 100.0000 0.000000 5 0.000000 -10.00000 6 0.000000 -15.00000 7 0.000000 -20.00000 8 0.000000 -15.00000在lingo软件的lingo model窗口中输入表达式model:min=10*x11+15*x12+20*x13+25*x14+20*x21+10*x22+15*x23+15*x24+25*x31+30*x32+20*x33+25*x34;x11+x12+x13=110;x21+x22+x23=70;x31+x32+x33=60;x12+x22+x32=70;x13+x23+x33=50;x14+x24+x34=70;end (3)由上述计算结果可知，该线性规划的最优解为：X11=60.00000, X12=0.000000,X13=50.00000,X14=0.000000X21=0.000000, X22=70.00000,X23=0.000000,X24=70.00000 X31=0.000000, X32=0.000000,X33=0.000000,X34=0.000000 最优值为：min发=3350.00。即运输总费用的最小值为3350元。四、总结 以上是一个供大于求的运输问题的示例，运用以上示例即可求得一个最佳的物资调运方案。对于平衡问题，只需在填写规划求解参数中添加约束条件时稍做改动即可求解，或者将其转化为平衡问题后建立相应的线性规划模型，再用以上方法求解亦可，