运筹学1310515007刘权概要
#运筹学课程论文线性规划理论在实际问题中的应用二级学院专业年级理学院数学与应用数学三年级学号学生姓名指导教师职称完成时间1310515007刘权陶胜达讲师2015年12月30日【摘要】线性规划在现代管理中扮演着很重要的角色，具广泛应用于经济领域， 如运输最优化，生产计划、投资决策、资本预算、人事安排、产品配比问题等， 线性规划是进行管理决策的最有效的方法之一。线性规划分析了在资源一定的条件下，如何合理的分配利用，最终使企业利润最大，说明了线性规划在现代管理 中的应用，而且对线性规划问题模型的建立， 模型的解进行了分析。线性规划的 研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条 件下，按某一衡量指标来寻找安排的最优方案.关键词 线性规划；最优解；资源配置；建模；运输问题；数学模型；线性代数一、线性规划的理论线性规划方法是在第二次世界大战中发展起来的一种重要的数量方法，线性规划方法是企业进行总产量计划时常用的一种定量方法.线性规划是运筹学的一 个最重要的分支，理论上最完善，实际应用得最广泛.主要用于研究有限资源的最 佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益.由于有成熟的计算机应用软件的 支持，采用线性规划模型安排生产计划，并不是一件困难的事情.在总体计划中， 用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下， 求利润最大的总产量计划.该方法的最大优点是可以处理多品种问题.线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、 应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学 方法。研究线性约束条件下线性目标函数的 极值问题的数学理论和方法。英文缩 写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管 I 理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优 决策，提供科学的依据。1、规划问题的数学模型由三个要素组成：（1）变量来源于数学，是计算机语言中能储存计算结果或能表示值抽象概1念。变量可以通过变量名访问。在指令式语言中，变量通常是可变的；但在纯函 数式语言（如Haskell）中，变量可能是不可变（immutable）的。在一些语言 中，变量可能被明确为是能表示可变状态、具有存储空间的抽象（如在 Java和 Visual Basic中）；但另外一些语言可能使用其它概念（如 C的对象）来指称这 种抽象，而不严格地定义“变量”的准确外延 |（2）目标函数（objective function） 是指所关心的目标（某一变量）与相关的 因素（某些变量）的函数关系。简单的说，就是你求解后所得出的那个函数。在求 解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关 系式，即为目标函数。（3）运用单纯形法解某些线性规划问题时，该问题已知的并须遵守的前提 条件称为约束条件。2、线性规划的模型结构实际问题中线性的含义：一是严格的比例性，生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润是各项产品的利润之和， 对某项资源的消耗量应等于各产品对该项资源的消耗量的和。在实际处理不符合条件的问题时，为方便可将其看作近似满足线性条件。3、线性规划的数学模型的一般形式为:目标函数：max（min） z=c1 X1+C2X2+Cn Xn满足约束条件：a11X1+&2X2+anxn& ( =, >)b 1a21X1+&2X2+a2nXn < ( =, >) b 2amlXl + am2X2+amrXn < ( = , >) b mX1, X 2, ,X n >04.运输问题实例 3年产木材量分别为1500万、2000万和 1500万米。每年市场1、2、3、4、A公司是一个拥有3个木材区和5个需要供应的市场的木材集团。木材区1、2、5 能够销售的木材量分别为800万、900万、1000万、1100万和1200万米。过去，运输通过火车来运输木材。然而，但是使用火车的运输成本逐步上升，最 近，该城市建立了一个新的港口，故考虑水运的方式来运输其中的一部分木材。 但却需要公司要在水运方面进行投资。除了这些投资成本之外，使用火车运输木 材的成本（单位：万元每米），沿着每一条路线使用轮船来运输木材（如果这个 方式可行的话）的成本如下1表所示：表1使用火车运输的单位成本（单位：万元）单位成本123451664555区1722566049697834763615966表2使用轮船运输的单位成本（单位：万元）单位成本1234513524-13138231282436433263632-33沿着每一条路线用轮船每年运输每 100万米，如下表3所示： 表3向市场运 输木材的轮船的单位资金投入（单位：万元）单位资金投 入123451285238-27530322652702501233183240275268-283考虑到轮船的预计使用期限和货币的时间价值，年成本大约就是表中所列数值 的 1/10 。公司的目标是要制定出一个全面运输计划，使年总成本最小（包括运输成本）。 现在，公司管理科学小组的负责人分别制定出了三个能够使年成本最小的运输计 划。方案1 :使用火车运输木材，并仅使用此方式。方案2 :仅使用轮船运输木材（只能使用火车的地方除外）。方案3:根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车 还是轮船运输木材。求出能使运输成本最低的从各木材资源区到各个市场的运输数量及最低的运输成本。这是一个典型的运输问题，分别就三个不同的方案进行估计，看哪个方案的总运输成本最低，并且用 excel可以很快得到一个最优解决方案。首先，运用线性规划用代数的形式来建立它的数学模型。假设 ijx （i=1,2,3 ; j=1,2,3,4,5 ）为从每个木材资源区到每个市场的运输数量，目标是为了找出能 使总运输成本最低的从每个木材资源区到每个市场的运输数量。c =版%.45%6kM + 72ir =5依：厂60% -49三-69% -780 -47田产6阳：=6比：_59%一66%663一 45X)2 + §5工骁 + 6lx14 - 72xls £ 150056xy + 60x22 4 4923+ 78x25 < 200047x31 + 63x32 +61x33 + 59工安 +66.y35 <1500x +工h + .% = 800约束条件:Jx：2 + X二 + 如=900茁w + .x23 + x33 = 1000.Y 4 + x24 += 1100x:; +x2i +工安=1200x. >0(j = l;2J;j = 1;2;3;45)运用excel进行线性规划求解可以很快得出使用火车到达各市场的木材公司最低的运输单位成本的最优值，如下表 4所示：表4火车运输的最低运输单位成本最优值运输量12345总产量10900060001500280001000200920003001030012001500总需求800900100011001200由此可知，继续使用火车来运输木材，最低的运输成本为28160万元。区1 到市场2的运输量为900万米，区1到市场4的运输量为600万米，资源区2 到市场1的运输量为800万米，区2到市场3的运输量为1000万米，区2到 市场4的运输量为200万米，区3到市场4的运输量为300万米区3到市场5 的运输量为1200万米。方案2:由于考虑到轮船的预计使用期限和货币的时间价值，年成本大约就是表 4中所列数值的1/10。所以，对于向市场运输木材的轮船的单位资金投入如下表5:表5向市场运输木材的轮船的单位资金投入（单位：万元）单位资金投 入12345128.523.8-27.530.3226.5272529.331.832427.526.8-28.3因此，对于向市场轮船运输木材的单位总成本（万元）如下表6:表6向市场轮船运输木材的单位总成本（万元）单一总成本11345163.547.0555&568.3r57.5554965.374.8三5063.558.85961.3目标函数：c = (BJiljj+47J8X, +55+5B.5i+683jq, +57.513 4s5物 +4% +健% +74% +啊+立.%+SW% +5%-6LU于63.5xr -47.St 2 +55.V , + 58.5. +68.3A- < 150057.5,r2 +55; - 493-65.3x-；4 - 74&3 200050x4-635与：4 58atm3 + 5史 +6L舞非 < 1500豹束条件为:+ 工；1 1+ 心.800Xu -+X-» +*父=9OQ,r13 一 % K瑟=1000-% + 5 +0 =11。力打斗二万+4炉=l - OO% i0<J = L2Jl； = l,2J:4:5运用excel进行线性规划求解可以很快得出使用轮船到达各市场的木材公司最低的运输单位成本的最优值，如下表 7：表7使用轮船运输最低的运输单位成本的最优值运输量12345总产量10900060001500250001000500020003300010012001500总需求800900100011001200由此可知，仅使用轮船来运输木材（只能使用火车的地方除外），最低的运输成本为27708万元。区1到市场2的运输量为900万米区1到市场4的运输量 为600万米，区2到市场1的运输量为500万米，区2到市场3的运输量为1000 万米区2到市场4的运输量为500万米，区3到市场1的运输量为300万米，区 3到市场5的运输量为1200万米。方案3:因为要根据运输成本最低来确定使用火车或轮船，所以重新所选择的单位成本如表8:表8重新所选择的单位成本单位成本1231 45163.54555阿568.3256554965.374.83476358.85961.3目标函数:+ 555 一5金痂 +68%+5 叫：+5&0 +4%+65%-74月4 一工 -6取：-5&&%一59%-61,罚$fi3,5r,-45x.; +550 + 5&5工皿.<1500
