线性规划.doc

什么是线性规划作者：佚名 来源：网络 点击数:6080 日期：2007-10-18什么是线性规划？线性规划是什么意思？线性规划是合理利用、调配资源的一种应用数学方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务完成的最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值(极小值和极大值)问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此，线性规划是辅助企业“转轨”、“变型”的十分有利的工具，它在辅助企业经营决策、计划优化等方面具有重要的作用。线性规划是运筹学规划论的一个分支。它发展较早，理论上比较成熟，应用较广。20世纪30年代，线性规划从运输问题的研究开始，在二次大战中得到发展。现在已广泛地应用于国民经济的综合平衡、生产力的合理布局、最优计划与合理调度等问题，并取得了比较显著的经济效益。线性规划的广泛应用，除了它本身具有实用的特点之外，还由于线性规划模型的结构简单，比较容易被一般未具备高深数学基础，但熟悉业务的经营管理人员所掌握。它的解题方法，简单的可用手算，复杂的可借助于电子计算机的专用软件包，输入数据就能算出结果。线性规划的研究与应用工作，我国开始于20世纪50年代初期，中国科学院数学所筹建了运筹室，最早应用在物资调运筹方面，在实践中取得了成果，在理论上提出了论证。目前，国内高等学校已将其列为运筹学中必选的课程内容之一，在实际应用方面也已列入重点企业试点和研究项目之一。线性规划模型的结构企业是一个复杂的系统，要研究它必须将其抽象出来形成模型。如果将系统内部因素的相互关系和它们活动的规律用数学的形式描述出来，就称之为数学模型。线性规划的模型决定于它的定义，线性规划的定义是：求一组变量的值，在满足一组约束条件下，求得目标函数的最优解。根据这个定义，就可以确定线性规划模型的基本结构。（1）变量 变量又叫未知数，它是实际系统的未知因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如xl，x2，x3，xmn等。（2）目标函数 将实际系统的目标，用数学形式表现出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。（3）约束条件 约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面，如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件。约束条件的数学表示形式为三种，即、。线性规划的变量应为正值，因为变量在实际问题中所代表的均为实物，所以不能为负。在经济管理中，线性规划使用较多的是下述几个方面的问题：(1) 投资问题确定有限投资额的最优分配，使得收益最大或者见效快。(2) 计划安排问题确定生产的品种和数量，使得产值或利润最大，如资源配制问题。(3) 任务分配问题分配不同的工作给各个对象(劳动力或机床)，使产量最多、效率最高，如生产安排问题。(4) 下料问题如何下料，使得边角料损失最小。(5) 运输问题在物资调运过程中，确定最经济的调运方案。(6) 库存问题如何确定最佳库存量，做到即保证生产又节约资金等等。应用线性规划建立数学模型的三步骤：(1) 明确问题，确定问题，列出约束条件。(2) 收集资料，建立模型。(3) 模型求解(最优解)，进行优化后分析。其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。线性规划的应用实例例1 某工厂甲、乙两种产品，每件甲产品要耗钢材2kg、煤2kg、产值为120元；每件乙产品要耗钢材3kg，煤1kg，产值为100元。现钢厂有钢材600kg，煤400kg，试确定甲、乙两种产品各生产多少件，才能使该厂的总产值最大？解 设甲、乙两种产品的产量分别为x1、x2，则总产值是x1 、x2的函数f(x1，x2)120x1100x2资源的多少是约束条件：由于钢的限制，应满足2x13x2600；由于煤的限制，应满足2x1x2400。综合上述表达式，得数学模型为求最大值（目标函数）：f(x1，x2)120x1100x22x13x26002x1x2400x10，x20xl，x2为决策变量，解得xl150件，x2100件fmax(120 150100100)元28000元故当甲产品生产150件、乙产品生产100件时，产值最大，为28000元。 表1-1 加工台时数例2 某工厂在计划期内要安排甲、乙两种产品。这些产品分别需要在a、b、c、d四种不同设备上加工。按工艺规定，产品甲和乙在各设备上所需加工台数列表于表1-1中。已知设备在计划期内的有效台时数分别是12、8、16和12(一台设备工作lh称为一台时)，该工厂每生产一件甲产品可得利润20元，每生产一件乙产品可得利润30元。问应如何安排生产计划，才能得到最多利润？解 l) 建立数学模型设 x1 、x2分别表示甲、乙产品的产量，则利润是f（x1，x2）=20 x130 x2，求最大值。设备的有效利用台时为约束条件：a：2 x12 x212b：x12 x28c：4 x116d：4 x212x10，x202）求解未知数x14、x23，但由式（l）、式（2）得x14、x22，所以取x14、x22 故fmax(204302)元140元3）结论：在计划期内，安排生产甲产品4件、乙产品2件，可得到最多的利润(140元)。例3 某工厂为维修全厂某类设备制造备件，需由一批5.5m长的相同直径的圆钢截取3.1m、2.1m、1.2m的胚料。每台设备所需的件数如表1-2所示。用5.5m长的圆钢截取上述三种规格的零件时，有下列五种截取方法可供选择，如表12所示。问当设备总数为100台时，采取何种方案可使5.5m的圆钢用料最省？ 表1-2 每台设备所需的件数表1-3 五种截取方法假设：按第一方案截取的5.5m长的圆钢数为x1按第二方案截取的5.5m长的圆钢数为x2按第三方案截取的5.5m长的圆钢数为x3按第四方案截取的5.5m长的圆钢数为x4按第五方案截取的5.5m长的圆钢数为x5据此表1-4：表 1-4因为设备总台数为100台,所以按各方案截取的零件数必须满足下列约束条件:x1+ x2=100x2+2 x3+ x4=2002 x2+ x3+2 x4+4 x5=400x1 ,x2 ,x3, x4, x50目标函数为 fminx1x2x3x4x5通过计算机运算得最优解为 x1=0、 x2=100、x3=100、x40、x5=25，故最优值 (最省方案)为fmin= 225根什么是线性规划方法线性规划方法是在第二次世界大战中发展起来的一种重要的数量方法，线性规划方法是企业进行总产量计划时常用的一种定量方法。线性规划是运筹学的一个最重要的分支，理论上最完善，实际应用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多品种问题。 线性规划方法的数学模型目标函数： 式中， xi-i产品的计划产量；aik-每生产一个i产品所需k种资源的数量；bk-第k种资源的拥有量；ui-i产品的最高需求量；li-i产品的最低需求量； pi-i产品的单价； ci-i产品的单位成本。 实际运用线性规划模型进行总生产计划时需要注意的一些问题1、线性规划模型考虑的因素可能不全面，实际中有些情况没有被考虑到，这就使得线性规划模型过于理想化； 2、实际运用线性规划模型时，虽然一些因素或约束条件被考虑到了，但是由于这些因素或约束条件不易量化或求得（如进行总生产计划常需考虑到的能源单耗就不易求得）时，线性规划模型的运用和有效性因而受到了一定的限制； 3、对一些基础管理不善的企业而言，模型中的单位产品资源消耗系数a很难得到； 4、目标函数中的产为成本系数c实际上是个变量，他随计划的数量结构和品种结构而变。这些问题给机械行业应用线性规划模型带来许多困难，如