运筹学-线性规划模型在实际生活中的应用

1、线性规划模型在实际生活中的应用【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题，其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。【关键词】线性规划、建模、实际生活、图解法、单纯形法前言：线性规划(Linearprogramming,简称LP)是运筹学中研究较早、发展较快、应

2、用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本内容，它在实际生活中有着非常广泛的应用.任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的

3、任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题，贴近生活，很好的吧线性规划应用到生活实践中。1、简单线性问题步骤简单介绍建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际内容，要明确目标函数和约束条

4、件，通过表格的形式把问题中的已知条件和各种数据进行整理分析，从而找出约束条件和目标函数。1.1 从实际问题中建立数学模型一般有以下三个步骤；(1)根据影响所要达到目的的因素找到决策变量；-1-(2)由决策变量和所在达到目的之间的函数关系确定目标函数；(3)由决策变量所受的限制条件确定决策变量所要满足的约束条件线性规划的数学模型的一般形式为：目标函数：max(min)z=c1x1+C2X2+-+Cnxn满足约束条件：a11x1+212x2+a1nxnW(=,)b1a21x1+222x2+a?nxn)b2am1x1+am2x2+amnxn)bmx1,x2,xn01.2 所建立的数学模型具有以下特点

5、：(1)每个模型都有若干个决策变量(x1,x2,x3，xn),其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。(2)目标函数是决策变量的线性函数根据具体问题可以是最大化(max)或最小化(min),二者统称为最优化(opt)。(3)约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。1.3 线性规划模型的基本结构：(1)变量变量又叫未知数，它是实际系统的未知因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如X,X2,X3,Xmn等。(2)目标函数将实际系统的

6、目标，用数学形式表现出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。(3)约束条件约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面，如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件。约束条件的数学表示形式为三种，即、=、0线性规划的变量应为正值，因为变量在实际问题中所代表的均为实物，所以不能为负。把线性规划的知识运用到企业中去，可以使企业适应市场激烈的竞争，及时、准确、科学的制定生产计划、投资计划、对

7、资源进行合理配置。过去企业在制定计划，调整分配方面很困难，既要考虑生产成本，又要考虑获利水平，人工测算需要很长时间，不易做到机动灵活，运用线性规划并配合计算机进行测算非常简便易行，几分钟就可以拿出最优方-2-案，提高了企业决策的科学性和可靠性。其决策理论是建立在严格的理论基础之上，运用大量基础数据，经严格的数学运算得到的，从而在使企业能够在生产的各个环节中优化配置，提高了企业的效率，对企业是大有益处的。2、线性规划问题的标准形式：由于目标函数和约束条件内容和形式上的差别，线性规划可以有多种表达式。为方便和制定统一算法，规定线性规划问题的标准形式如下：nmaxzCjXjjinaijXjbi(i1

8、,K,m)stjixj0(i1,K,m)标准形式的线性规划模型中，目标函数为极大值(有些书上规定是级小值)，约束条件全为等式，约束条件右端为常数项b全为非负数，变量x的取值全为非负值。符合标准形式的线性规划问题，课通过下列方法化为标准式。(1)目标函数为极小值，即为：nminzCjXjj1因为求minz等价于求max(-z),令z-z,即化为：nmaxzcjxjj1(2)约束条件右端b0.当约束条件为f时，如有10次+12发18,可令X4=10X1+12x2-18,得10x1+12x2-x4=18,x40.x3,x4是新加上去的变量，取值均为非负值，加到原约束条件中去的变量，其目的是使不等式转

9、化为等式，其中X3为松弛变量，X4一般称为一般变量，等也称松弛变量。松弛变量或剩余变量在实际问题中分别表示为未被允分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后他们在目标函数中的系数为零。(4)取值无约束的变量。如果变量x代表某产品当年计划与上一年计划数之差，显然x的取值可能是正的也可能是负的，这时令x=x-X,将其代入线性规划模型。(5)对x00的情况，令x=-x,显然x3、简单线性规划问题的解法线性规划作为数学规划中最简单的一种问题.它的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足

10、约束条件下的极大或极小值问题.如果约束条件和目标函数都是呈线性关系的就叫线性规划.要解决线性规划问题，从理论上讲都要解线性方程组，而解线性方程组的常见方法是图象法和单纯元法。将实际生活中的线性规划问题，抽象为数学形式，目的在于找到解决问题的方法.为此,我们作以下一些讨论.3.1 最大利润问题例1某工厂在计划期内要安排生产I、R两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗.如表1所示：表aIR设备128台时原材料A4016kg原材料B0412kg该厂每生产一件产品I可获利2元，每生产一件产品II可获利3元.问应如何安排计划使该工厂在限定条件下获利最多？显见，这个问题可以用以下

11、的数学模型来描述设xi,x2分别表示在计划期内产品I、R的产量.因为设备的有效台时是8,这是一个限制产量的条件，所以确定产品I、n的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：X2x28.同理，因原材料的限量，可以得到两个不等式：4xi16,4x212.该厂的目标是在不超过所有资源限量的条件下，如何确定产量xx2以得到最大的利润用z表示利润，这时z2x13x2.综合上述，此计划问题可用数学模型表示为目标函数：z2x13x2x12x28约束条件:4xi164x212Xi,X203.2 两个变量的线性规划问题的图解法现在我们用图解法来解上述的例1：在以xi,x2为坐标轴的直角坐标系中

12、，非负条件xi0,x20是指第一象限.每一个约束条件都代表一个半平面，如约束条件xi2x28是代表以直线xi2x28为边界的左下方的平平面.若同时满足：xi0,x20,xi2x28,4xii6和4x2i2的约束条件的点，必然落在xx2坐标轴和由这三个半平面交成的区域内（如下图）.阴影区域中的每一个点（包括边界）都是这个线性规划问题的解，因而此区域是此线性规划问题的解集合，称它为可行域.再来分析目标函数z2%3x2.在这个坐标平面上，它可表示以z为参数，以2,2z、2为斜率的一族平行线：x2（2）xi：.位于同一直线上的点，具有相同的目标函数值,因而称它为“等值线”.当z值由小变大时，直线x2（

13、-）xi-沿其法线方向33向右上方移动.当移动到Q2点时，使z值在可行域边界上实现最大化（如下图）：这就得到了例1的最优解对应的点Q2,Q2点的坐标为(4,2).于是可计算出满足所有约束条件的最大值z14.这说明该厂的最优生产计划方案是：生产4件产品I,生产2件产品可得最大利润为14元.【拓展延伸探究】例2预算有2000元购买单价为50元的桌子和20元的椅子，希望使桌椅的总数量尽可能的多，但椅子数不少于桌子数，且不多于桌子数的1.5倍，问桌子和椅子各购买多少？分析这是生活实际中的一个物资采购问题，可归结为线性规划问题，利用图解法进行求解。解设桌子和椅子各购买x、y张，则x、y必须满足线性约束条

14、件50x20y2000xyx,y0其目标函数z=x+y。xxy,由50x20y2000,解得yx,yN20,7200200200、.,r（二，）7故图14中点A的坐标为77y1.5x由50x20y2000x257575./口y(25,)解得2故图中点B的坐标为2满足以上条件的可行域为如图所示的阴影部分(包括边界和内部)，以A、BO为顶点三角形区域。动直线z=x+y表示斜率为1,在y轴上的截距为z的直线，如图所示的虚75一一.yt线，当动直线运动到如图所小的B点时，z的取值最大，止匕时x=25,20但由于x、y的取值均为整数，故y应取37,即购买25张桌子、椅子37张,是最优选择。（25,）点悟

15、：由于本题是一个实际问题，当求得最优解2后，显然它不满足题意，故应取最优解的近似值，这便是实际问题与一般的非应用问题的最大区别。在实际问题中椅子必须是整数，所以x=25,y=37。3.3用单纯元法解两个变量的线性规划问题例3:某车间生产甲、乙两种产品，已知制造一件甲产品需要A种元件5个，B种元件3个；制造一件乙产品需要A种元件2个，B种元件3个.现因某种条件限制，只有A种元件180,B种元件135个；每件甲种产品可获利20元，每件乙种产品可获利15元.试问在这种条件下，应该生产甲、乙两种产品各多少件才能得到最大利润?解：设应该生产甲产品%件，乙产品X2件，才能得到最大利润S元.根据题意,此问题

16、可用数学模型表示为：目标函数S20为15x2满足约束条件5x13x12x23x2180135x1,x20S20x115x20x30x4将上述问题化成标准形式:5x12x2x3180343x2x4135x1,x2，x3，x4添加的松弛变量x3和x4在约束方程组中其系数列正好构成一个2阶单位阵,它们可以作为初始基变量，初始基可行解为X=（0,0,180,135）表1Cj一201500Cb基bXixx2x3x40%18052100X41353301Cj-Zj02015-00由于只有（720,说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对

17、应的基变量作为换出的基变量。min(180135)5,3)36因此确定5为主元素(表1中以防括号口括起)，意味着将以非基变量X2去置换基变量X6,采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将Xi的系数列(20,15)T变换成X3的系数列(0,1):变换之后重新计算检验数。变换结果见表2表2Cj一201500Cb基bX1XX2X3X403612/51/500X42709/5-3/51Cj-Zj-72007-40再按上述方法可得表3表3Cj一201500Cb基bX1lX2X3X40K30103/5-2/90X41501-1/55/9Cj-Zj-88900-1/5-7此时，2个非基变量的检验数都小于0,(T3=-1/5,(74=-7,表明已求得最T优解：X(30,15,0,0)To去除添加的松弛变量，原问题的最优解为：*TX(30,15)，最打值为20*30+15*15=825。若企业在生产、运输、市场营销等方面，没有很好地利用线性规划进行合理的配置，往往会导致增加了企业的生产，使企业的利润不能达到最大化，使