运筹学1310515007刘权

1运筹学课程论文线性规划理论在实际问题中的应用二级学院理学院专业数学与应用数学年级三年级学号1310515007学生姓名刘权指导教师陶胜达职称讲师完成时间2015年12月30日2【摘要】线性规划在现代管理中扮演着很重要的角色，其广泛应用于经济领域，如运输最优化，生产计划、投资决策、资本预算、人事安排、产品配比问题等，线性规划是进行管理决策的最有效的方法之一。线性规划分析了在资源一定的条件下，如何合理的分配利用，最终使企业利润最大，说明了线性规划在现代管理中的应用，而且对线性规划问题模型的建立，模型的解进行了分析。线性规划的研究对象是计划管理工作中有关安排和估值的问题,解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案.关键词线性规划;最优解;资源配置；建模；运输问题；数学模型；线性代数一、线性规划的理论线性规划方法是在第二次世界大战中发展起来的一种重要的数量方法,线性规划方法是企业进行总产量计划时常用的一种定量方法.线性规划是运筹学的一个最重要的分支,理论上最完善,实际应用得最广泛.主要用于研究有限资源的最佳分配问题,即如何对有限的资源作出最佳方式地调配和最有利地使用,以便最充分地发挥资源的效能去获取最佳的经济效益.由于有成熟的计算机应用软件的支持,采用线性规划模型安排生产计划,并不是一件困难的事情.在总体计划中,用线性规划模型解决问题的思路是,在有限的生产资源和市场需求条件约束下,求利润最大的总产量计划.该方法的最大优点是可以处理多品种问题.线性规划（Linearprogramming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。1、规划问题的数学模型由三个要素组成：（1）变量来源于数学，是计算机语言中能储存计算结果或能表示值抽象概念。变量可以通过变量名访问。在指令式语言中，变量通常是可变的；但在纯函数式语言（如Haskell）中，变量可能是不可变（immutable）的。在一些语言中，变量可能被明确为是能表示可变状态、具有存储空间的抽象（如在Java和VisualBasic中）；但另外一些语言可能使用其它概念（如C的对象）来指称这种抽象，而不严格地定义“变量”的准确外延（2）目标函数(objectivefunction)是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。简单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。（3）运用单纯形法解某些线性规划问题时，该问题已知的并须遵守的前提条件称为约束条件。2、线性规划的模型结构实际问题中线性的含义：一是严格的比例性，生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润是各项产品的利润之和，对某项资源的消耗量应等于各产品对该项资源的消耗量的和。在实际处理不符合条件的问题时，为方便可将其看作近似满足线性条件。33、线性规划的数学模型的一般形式为：目标函数：max(min)z=c1x1+c2x2+…+cnxn满足约束条件：a11x1+a12x2+…+a1nxn≤(＝,≥)b1a21x1+a22x2+…+a2nxn≤(＝,≥)b2………….……………………….am1x1+am2x2+…+amnxn≤(＝,≥)bmx1,x2,…,xn≥04.运输问题实例A公司是一个拥有3个木材区和5个需要供应的市场的木材集团。木材区1、2、3年产木材量分别为1500万、2000万和1500万米。每年市场1、2、3、4、5能够销售的木材量分别为800万、900万、1000万、1100万和1200万米。过去，运输通过火车来运输木材。然而，但是使用火车的运输成本逐步上升，最近，该城市建立了一个新的港口，故考虑水运的方式来运输其中的一部分木材。但却需要公司要在水运方面进行投资。除了这些投资成本之外，使用火车运输木材的成本（单位：万元每米），沿着每一条路线使用轮船来运输木材（如果这个方式可行的话）的成本如下1表所示：表1使用火车运输的单位成本（单位：万元）单位成本12345166455561722566049697834763615966表2使用轮船运输的单位成本（单位：万元）单位成本1234513524-3138231282436433263632-33沿着每一条路线用轮船每年运输每100万米，如下表3所示：表3向市场运输木材的轮船的单位资金投入（单位：万元）单位资金投入123451285238-2753032265270250233183240275268-283考虑到轮船的预计使用期限和货币的时间价值，年成本大约就是表中所列数值的1/10。公司的目标是要制定出一个全面运输计划，使年总成本最小（包括运输成本）。现在，公司管理科学小组的负责人分别制定出了三个能够使年成本最小的运输计划。方案1：使用火车运输木材，并仅使用此方式。方案2：仅使用轮船运输木材（只能使用火车的地方除外）。方案3：根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材。求出能使运输成本最低的从各木材资源区到各个市场的运输数量及最低的运4输成本。这是一个典型的运输问题，分别就三个不同的方案进行估计，看哪个方案的总运输成本最低，并且用excel可以很快得到一个最优解决方案。首先，运用线性规划用代数的形式来建立它的数学模型。假设ijx（i=1,2,3；j=1,2,3,4,5）为从每个木材资源区到每个市场的运输数量，目标是为了找出能使总运输成本最低的从每个木材资源区到每个市场的运输数量。运用excel进行线性规划求解可以很快得出使用火车到达各市场的木材公司最低的运输单位成本的最优值，如下表4所示：表4火车运输的最低运输单位成本最优值运输量12345总产量1090006000150028000100020092000300030012001500总需求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向市场轮船运输木材的单位总成本（万元）5运用excel进行线性规划求解可以很快得出使用轮船到达各市场的木材公司最低的运输单位成本的最优值，如下表7：表7使用轮船运输最低的运输单位成本的最优值运输量12345总产量1090006000150025000100050002000330000012001500总需求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重新所选择的单位成本单位成本12345163.5455558.568.3256554965.374.83476358.85961.3目标函数:6运用excel进行线性规划求解可以很快得出使用方案3最低的运输单位成本的最优值，如表9：表9方案3最低的运输单位成本的最优值运输量12345总产量1090006000150025000100050002000330000012001500总需求800900100011001200由此可知，通过不叫不同路径方式的运输对陆运和水运进行比较，最低的运输成本为27291万元。区1到市场2的运输量为900万米，区1到市场4的运输量为600万米，区2到市场1的运输量为500万米，区2到市场3的运输量为1000万米，区2到市场4的运输量为500万米，区3到市场1的运输量为300万米，区3到市场5的运输量为1200万米。综上所述，方案1的继续使用火车来运输木材，最低的运输成本为28160万元。方案2的仅使用轮船来运输木材（只能使用火车的地方除外），最低的运输成本为27708万元。方案3的根据在每一条特定地路线上哪种方式的运输成本比较低来选择使用火车还是轮船运输木材，最低的运输成本为27291万元。因此，该公司的最优调运方案为方案3，即同样的运输量，总运输成本最低。众所周知,在生产生活中人们经常遇到一些要求对现有资源、设备进行统一分配,全面安排,合理调度或最优设计等问题.从而提高经济效益,创造更多的价值.而提高经济效益的途径,一方面是靠技术的改革,另一方面要改进生产组织和计划,也就是作到合理安排人力、物力资源,合理组织生产过程,在条件不变的情况下统筹安排.在众多可能的方案中,选取出最经济、最合理的一个可行方案,从而进行最优决策.3简单线性规划问题的解法生活中许多问题，通过线性规划建立模型把抽象的概念具体化，从而解决问题，我们为止作出以下的讨论。3.1最大利润问题某工厂在计划期内要安排生产A、B两种产品,已知生产单位产品所需的设备台时及a、b两种原材料的消耗.如表1所示:表1AB7设备128台时原材料a4016㎏原材料b0412㎏该厂生产一件产品A便可以获利2元,每生产一件产品B便可以获利3元.问应如何安排计划,使该工厂在限定条件下获利最多?当然,我们通过建立数学模型分析讨论的话：设21,xx分别表示在计划期内产品A、B的产量.因为设备的有效台时是8,这是一个限制产量的条件,所以确定产品A、B的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为:8221xx.同理,因原材料的限量,可以得到两个不等式:1641x,1242x.该厂的目标是在不超过所有资源限量的条件下,如何确定产量21,xx以得到最大的利润.用z表示利润,这时2132xxz.综合上述,此计划问题可用数学模型表示为:目标函数:1223zxx约束条件:0,12416482212121xxxxxx3.2两个变量的线性规划问题的图解法现在我们用图解法来解上述的例1:在以21,xx为坐标轴的直角坐标系中,非负条件0,021xx是指第一象限.每一个约束条件都代表一个半平面,如约束条件8221xx是代表以直线8221xx为边界的左下方的半平面.若同时满足:0,021xx,8221xx,1641x和1242x的约束条件的点,必然落在21,xx坐标轴和由这三个半平面交成的区域内(如右图).8阴影区域中的每一个点(包括边界)都是这个线性规划问题的解,因而此区域是此线性规划问题的解集合,称它为可行域.再来分析目标函数2132xxz.在这个坐标平面上,它可表示以z为参数,以32为斜率的一族平行线:3)32(12zxx.位于同一直线上的点,具有相同的目标函数值,因而称它为“等值线”.当z值由小变大时,直线3)32(12zxx沿其法线方向向右上方移动．当移动到2Q点时，使z值在可行域边界上实现