前言:中文期刊网精心挑选了线性规划范文供你参考和学习,希望我们的参考范文能激发你的文章创作灵感,欢迎阅读。
线性规划范文1
一、向量中的线性规划
例1(南京市2012届高三第一次调研测试)如图1,在正方形ABCD中,已知AB=2,M为BC中点若N为正方形内(含边界)任意一点,求AM·AN的最大值
解:以A为坐标原点、AB所在直线为x轴建立如图2所示的
平面直角坐标系,则M点的坐标为(2,1)设N(x,y),则
N点所在区域由不等式组
确定,将x=2,y=2代入2x+y求得
最大值等于6
二、数列中的线性规划
例2 (苏州、无锡、常州、镇江2012届高三一模试题)等差数列
解:设此等差数列的首项为a,公差为d,
则
目标函数的范围如图3所示,可行域中两直线的交点坐标是(29,-2),
代入得a12=a+11d
的最大值是7故
三、导数中的线性规划
例3已知函数
[-1,3]上是减函数,求a+b的最小值
解:因为f(x)在区间[-1,3]上是减函数,所以f ′(x) 在区间
作出可行域(图4),求得a+b的最小值为2
四、函数单调性中的线性规划
例4定义在R上的函数y=f(x)是增函数,且为奇函数,若实数s,t满足不等式f(s2-2s)≥f(2t-t2)
,则当1≤s≤4时,求
3t+s的取值范围
解:因为f(x)是奇函数,
所以-f(2t-t2)=f(t2-2t)又y=f(x)是增函数,且
所表示的可行域(图5)将边界点A、B、C的坐标分别代入求得
3t+4的值
,比较得最大值和最小值分别为16、-2所以-2≤3t+s≤16
五、方程根的分布中的线性规划
例5已知
方程
x2-mx+n=0两根为
α,β,且
1≤α≤2≤β,求m2+n2的取值范围
解:设
f(x)=x2-mx+n,由已知得方程
x2-mx+n=0的一根在区间[1,2)内,另一根在区间
[2,+∞)内,因此
作出其可行域(图6)图中阴影部分的点到原点O的距离的最小值为
13,故
m2+n2的取值范围是
[13,+∞)
六、复数中的线性规划
例6(2012届高三同心圆梦模拟一)
复数
可行域如图7所示,将mn看成可行域内的点与原点O连线的斜率,求得
七、三角形三边关系中的线性规划
例7(苏州市2011届高三第一学期期末调研试题)已知ABC的三边长为a,b,c且满足
b+2c≤3a,c+2a≤3b,
求ba的取值范围
解:因为a,b,c是三角形的三边,
所以a+b>c,
|a-b|
可行域如图8所示
将ba看成可行域内的点(a,b)与原点连线的斜率,
b-0a-0
的最大值为
八、直角三角形中的线性规划
例8直角三角形的三边长分别是7,24,25,P是其形内(包括边界)的一点,求P点到三边距离之和的最大值与最小值
解:不妨设三角形三边为AC=7,BC=24,AB=25,以直角顶点为坐标原点,建立如图9所示的平面直角坐标系,则AB的方程为
即7x+24y-168=0设ABC形内(包括边界)
一点为P(x,y),它到三边的距离之和为
所确定的可行域组成将A(0,7)、B(24,0)、C(0,0)代入d中,当x=24,y=0时求得d的最大值等于24;当x=0,y=0时求得d的最小值等于
所以P点到三边距离之和的最大值等于24,最小值等于
九、不等式中的线性规划
例9已知实数a,b满足
a≥10,
a2b的最大值为n,最小值是m,求
nm的值
解:由题得a>0,b>0,将条件取常用对数,得
在此条件下求z =2x+y的最大值与最小值
可行域如图10所示,求得
线性规划范文2
1、线性规划(Linear programming,简称LP),是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。
2、线性规划是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。
(来源:文章屋网 )
线性规划范文3
例1已知实数x,y满足y≤2x,y≥-2x,x≤3,则目标函数z=x-2y的最小值是.
错解:题中的可行域如图1的阴影部分所示,其中O为坐标原点,A(3,6),B(3,-6).
先作出动直线l:z=x-2y过原点时的情形,如图中的虚线l0所示. 由图1可知,当l过点B时,z取到最小值zmin=3-2×(-6)=15.
【剖析与纠正】 动直线l的方程为:y=-,该直线的截距为-,故当动直线截距取到最大值时,对应目标函数z才取到最小值. 显然,当l过点A时,其截距最大, zmin=3-2×6=-9.
点评: 理所当然地把目标函数“z”跟“截距”画上等号是大错特错的. 一般地,若目标函数为z=ax+by (b≠0),则动直线l的方程为:y=-+,才是动直线在y轴上的截距. 由此可见,当b>0时,目标函数z取到最大(最小)值等同于截距取到最大(最小)值;当b
这一错解告诉我们,先将目标函数改写为动直线的斜截式方程,再从中确定目标函数值与动直线截距间的对应关系,是准确求解线性规划问题的第一步.
二、无视动直线与可行域边界直线间的相对倾斜程度
例2若实数x,y满足x+y≥2,2x-y≤4,x-y≥0,则2x+3y的最小值是.
错解: 可行域如图2阴影部分所示,其中A(2,0),B(1,1),C(4,4).设z=2x+3y,则动直线l:y=-x+过原点时的位置为l0,平移l,由图2可知,当l过点B时有zmin=2+3=5.
【剖析与纠正】 错解无视动直线l与可行域边界直线AB间的相对倾斜程度,草率作出了l0的图象,从而导致了错解. kl=->kAB=
-1,由斜率的几何意义可知,l的“陡峭”程度要小于AB,故l过原点时的位置应如图中的l1所示. 由此可知,当l过A点时z取到最小值,zmin=2×2+0=4.
点评: 当线性约束条件表示的可行域为一多边形时,明确动直线与可行域边界直线的相对倾斜情况,是正确求解线性规划问题的第二步.
一般地,可先观察直线斜率的正负,然后再根据斜率绝对值的大小来确定动直线与边界直线的相对倾斜情况.
三、忽视变量实际意义,“想当然”推断最优解
例3要将两种形状不规则的钢板截成A,B,C三种规格的小钢板,每张钢板可截得的各种小钢板的块数如表1所示.
表1
已知第一种钢板的面积为1m2,第二种钢板的面积为2m2. 今分别需要A,B,C三种规格的小钢板12,15,27块,则需使用钢板的最小面积为
m2.
错解一: 设需要第一种钢板x张,第二种钢板y张,所用钢板总面积为zm2,则z=x+2y,且x,y满足x+y≥12,2x+y≥15,x+3y≥27,x>0,y>0.易知可行域如图3阴影部分所示,其中L1:x+y=12,L2:2x+y=15,L3:x+3y=27,L1,L3的交点为A,.动直线l:y=-x+过原点的直线为l0,显然当l过点A时,zmin=+15=19.5(m2),即至少需要使用钢板的面积为19.5m2.
错解二: 由于x,y为钢板的张数,故应为正整数,A,不是整数点,所以应选择可行域内离A最近的整数点B(5,8), zmin=5+2×8=21(m2).
【剖析与纠正】错解一忽视了所求变量x,y与目标函数z的实际意义.错解二虽注意到了最优解应为整数解,但选择点B只是想当然的,并没有验证B点是否确为最优解.
设l过点A,时的直线为l1 (此时z=19.5),过点B(5,8)时的直线为l2 (此时z=21). 假设存在其他最优解D(x0,y0),则过点D的直线l必介于l1,l2之间,此时z∈(19.5,21), z∈N*, z=20.
易知l2的方程为x+2y=21,l2与L3的交点为B′(9,6),l2与L2的交点为C(3,9)(也即L1与L2的交点).显然点D必定在如图3所示的AB′C(含边界)内,则有x0+2y0=20,3≤x0≤9,6≤y0≤9,x0,y0∈N*.解得D(8,6)(舍去,不在可行域内),D(6,7)或D(4,8),故z=20可以取到,即需使用钢板的最小面积为20m2.
点评: 求最优整数解是线性规划的难点. 本题的剖析其实给同学们展示了一种求最优整数解的简便方法:第一步,求出不考虑整数条件时的最优解A及此时的目标函数值z(A). 若A恰好为整数解,则问题解决;若A不是整数解,则进入第二步,在该“最优解”附近求得某一整数解B及此时的目标函数值z(B);第三步,推断介于z(A)与z(B)之间的可能的目标函数值,并求出该目标函数值对应的所有整数解;第四步,验证这些整数解是否在可行域内.
四、分析、转化问题不全面
例4已知x,y满足y≤x,x+y≤1,y≥-1,则使2x+y取到最大值的(x,y)为
.
错解: 令z=2x+y,要使2x+y取得最大值,即要使z取得最大值. 题中的可行域如图4阴影部分所示,由图可知,当动直线l:y=-2x+z经过点A(2,-1)时z取到最大值,zmax=2×2-1=3,故使2x+y取到最大值的(x,y)为(2,-1).
【剖析与纠正】错解对“2x+y取得最大值”这一条件进行了不等价转化.2x+y的最大值应为2x+y可取到的最大值与最小值中的绝对值较大者,故解题时还应该考虑z=2x+y取到最小值的情况.
由图4可以看出,当动直线l经过B(-1,-1)时,zmin=2×(-1)-1=-3,故2x+y的最大值确实为3,但其对应的(x,y)却有两组:(-1,-1)或(2,-1).
点评:求解二元一次式的绝对值这个问题似乎并没有直接指向线性规划,但我们通过转化使其具有了线性意义. 设z=2x+y,找出这一目标函数的最值,等于“变相”地去掉了“绝对值”符号. 但如果分析不全面,仍然可能导致错解. 可见,线性转化、全面分析,乃是线性规划应用的原则.
线性规划范文4
关键词:高职院校;线性规划;单纯形法
中图分类号:G642.0 文献标识码:A 文章编号:1002-4107(2015)12-0030-02
运筹学是应用数学的一个分支,是研究如何将生产生活、军事管理等事件中出现的一些问题加以提炼,然后利用数学方法进行解决的学科。主要是利用高等数学、线性代数等数学知识来解决问题,使成本最小化和利润最大化。是高等院校中经济和管理系学生的必修课。线性规划是运筹学的一个重要分支。1947年丹捷格(G.B.Dantzig)提出了解线性规划问题的一种有效方法――单纯形法,线性规划在理论上日益成熟,在实际应用中更加广泛与深入。特别是在计算机能解决成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更加广泛。从解决一些技术问题的最优化设计,到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥重要作用。
线性规划应用日益广泛。高职高专职业院校的许多专业都将这一运筹学基本内容纳入教学计划。可是线性规划是一种数学方法,涉及高维空间。这些专业的本科生、大专生,即便学过线性代数,往往仍比较生疏,不能灵活运用线性代数知识领会线性规划内容。他们觉得线性规划理论抽象难懂。部分学生甚至失去学习信心。另一方面,许多教材把线性规划安排在线性代数后面,有作为线性代数应用举例的用意,若前后教学设计呼应不好,这一安排也将落空。
笔者等应邀为高职高专院校编写线性规划新教材[1],在教材中如何体现从此类学生数学基础的现状出发?如何形象化地讲解线性规划原理?如何与他们学过的线性代数呼应?如何跟着时代步伐,更新教材[2]?――这些问题就提到笔者的面前。
针对高职高专院校学生的情况,笔者提出“夯实理论基础,抓好建模、上机两个实际本领”。在“夯实理论基础”方面,主要是根据经济、管理业务需要,针对学生实际的数学基础,加强与他们学过的线性代数相关知识的联系,在形象化的讲解上下大力气。改变一些概念的提法,使学生感到通俗易懂,在追求概念正确的前提下力求内容讲解形象生动,采用计算机画图并结合动画演示等手段给学生以感性认识。使线性规划的理论部分变得容易接受。在线性规划题目的计算方面,减少笔算,增加机算,降低学生计算的难度,提高计算效率,增强学生学习的自信心。此外,针对线性规划教学和教材中需要注意的一些不确切的表述,笔者提出了一些见解,希望帮助学生对知识的透彻理解,也可与同行交流。在课后习题的设置方面,笔者也作了探讨,请参阅文章《编写线性规划习题的新构思》[3],在教学中为了更好地培养学生的动手能力,笔者写了《线性规划教学中如何培养学生的动手能力》一文,在此均不再赘述[4]。
一、用“自由变量改称非基变量”的提法,破除“基”的神秘感
目前线性规划教材的用语是跟着运筹学的几本大部头著作走的。而权威著作的用语,一方面受早年开创性论文词汇的影响,有些术语今已改译;另一方面权威著作比较深奥,假设读者对于线性代数中的相关基础理论知识均已熟练掌握。但是实际上职业院校的运筹学教材大多只讲到线性方程组的求解,往往未将上述基础理论全部列入大纲,个别概念即便提到,顶多也是草草带过。这就造成在职业院校的运筹学的很多教材中,线性规划的许多术语学生感到生疏、抽象,或与以前学过的线性代数对不上号。
许多线性规划教材一开始就另起炉灶,用学生不熟悉的术语下“基”的定义,举例又很简略。学生用不上刚学的线性代数,以致对“基”的概念懵懂,云遮雾罩,往往全凭死记,也就更谈不上理解“换基”等等内容。
笔者为避免使职业院校的学生感到突兀,从他们熟悉的线性方程组求解知识入手,指出约束方程的增广矩阵化成行最简形矩阵后所得同解方程和相应的通解,实质上就是“用自由变量表达非自由变量”。按线性规划的术语,称作“用非基变量表达基变量”。不过是把“自由变量”改称“非基变量”;把“非自由变量”改称“基变量”罢了。再由“基变量”引入“基”的概念,由此破除“基”的神秘感。再利用他们会的通过“行初等变换”,在增广矩阵系数矩阵中化出单位阵的知识,讲“基”的性质等内容。这样,学生就会很容易理解。
学生容易知道:写线性方程组的通解时,最易手到拈来的是“全部自由变量皆取零值的特解”,这个“特解”在线性规划里叫作“全部非基变量皆取零值”。并指出这个特解在线性规划里更重要,特意命名“基本解”。若“基本解” 还符合非负条件,就成为“基本可行解” (Basic feasible solution),它与图解法中至关重要的可行解域的顶点有对应关系。这样引入新概念,学生感到轻松自然。连差生也能顺畅地由上章知识过渡到本章的新概念。
二、合理运用多种教学手段,增强学生的感性认识
因为线性规划单纯形法比较抽象,许多关键点学生不容易明白,对一些知识的理解比较模糊,为了使学生对解法有清晰感性的理解,笔者想到利用二维图形、对照顶点表及图象和动画演示等手段,达到较好的教学效果。
(一)用二维图形显示“基本可行解”与可行解域顶点的对应关系
因学时限制,职业院校的运筹学教材不作证明,仅介绍“基本可行解”与可行解域顶点的对应关系结论。很多教材一笔带过,学生印象不深。笔者加写一个二维例图让学生验看,增添感性认识。还把该例的对应关系,包括决策变量与张弛变量的值等,详细列出表格,供后面讲“换基”时查验。虽然费些笔墨,因事关单纯形法只到各个顶点搜寻最优解的基本思路,还是值得的。
(二)在二维图上验看可行解域顶点上确实“全部非基变量等于零”
在以往教学中,常有学生对全部非基变量在每个可行解域的顶点都取零值感到疑惑。笔者除了指出代数上的“基本可行解”与几何上的可行解域顶点有对应关系外,还从几何角度在二维图上说明该例中各个非基变量等于零的几何意义:在坐标轴线上的顶点,它的另一个坐标的值为零,其含义为非负条件;在其他边线上的顶点,约束方程的张弛变量为零,表明至此已踩该约束条件的边线。例如二维图解法中,在表示不等式约束x1+x2≤6的边线上,由它标准化所得的等式约束x1+x2+x3=6中的张弛变量x3为零。以此帮助学生接受高维空间也有类似规律的结论。
(三)对照顶点表及图象导出“换基”的感性认识
在从代数学角度讲“换基”的过程中,笔者还让学生观察上述可行解域顶点与“基本可行解”对照表中顶点间各变量值的变化,结合“非基变量必取零值”,自己总结得出“换基”的规律。学生感到生动明白。
(四)用动画概括单纯形法的思路
在讲完单纯形法的思路后,笔者放映一个二变量线性规划题求最优解的动画,以动态形象的动画演示,使学生直观地理解单纯形法的解题思路,以加深学生对此解法的印象,巩固学习成果。
三、裁减笔算法的辅助内容,开展机算
实际工作中遇到的线性规划问题,必然变量很多(往往十个以上)且有效数字长,计算量太大。很多学生面对实际问题,凭笔算解不出来,只能望洋兴叹。身处计算机时代,而因袭几十年前的老教法,只教笔算内容,或虽点到某处刊有源程序,却不上机,这是国内经济管理类专业线性规划教学中相当普遍的现状。为使学生真正具备解决实际问题的能力,笔者痛感必须掌握一种软件。有所失才能有所得,为挤出时间上机,必须割舍一些原有内容。一般教材在讲完单纯形法的表上求解后,还要讲一种求初始基本可行解的方法,一般是“辅助规划法”。笔者考虑这部分与单纯形法主干内容的关系相对而言小些,只好割爱。况且实际工作中,用计算机解题,不需要提供初始可行解。即便偶遇简易笔算场合,由于新讲稿中加强了与上章的联系,真正看懂新教材的学生,从引入基变量概念的例题中,也会悟出对增广矩阵作行初等变换,搜索出一个基本可行解,绘出首张单纯形表,供表上叠代求解用。所以删去这部分内容影响不算太大。这样节约出利用计算机解题的时间,使学生利用上机解题,提高学习效率。
四、注意语言的准确性
线性规划是运筹学中最活跃的分支,经济类、管理类专业学生及从业人士普遍学习。现在市场销售的线性规划书籍很多,但在教学和教材中都有一些需要注意的问题。
讲课中不能因为强调形象有趣而忽视科学性。在职业院校的运筹学课堂上,虽无理工科那么多证明,同样要在关键地方,字斟句酌,锤炼用语。在线性规划的教材中就有若干常见的语病。例如个别书说“基的个数为组合数Cmn”(其中m为标准化后的约束方程数,n为变量数,且R(A)=m )。这句话就漏掉“至多”二字,因为有的m阶方阵的行列式可能为零,因而不能作基。
总之,线性规划单纯形法是一种较为抽象的数学方法,经过改进教学方法,采用上述讲法,学生对该部分的学习普遍接受较好。
参考文献:
[1]阎章杭等.高等数学与经济数学[M].北京:化学工业出
版社,2007:250-262.
[2]阎章杭等.高等数学与经济数学[M].北京:化学工业出
版社,2003:276-281.
[3]阎向曜,张小慧.编写线性规划习题的新构思[J].河南
财政税务高等专科学校学报,2008,(6).
线性规划范文5
一、与概率相联系
例1:设不等式组0?燮x?燮20?燮y?燮2,表示平面区域为D,在区域D内随机取一个点,则此点到坐标原点的距离大于2的概率是
( )。A. , B. , C. , D. 。
解析:题目中0?燮x?燮20?燮y?燮2表示的区域如图1正方形所示,动点D可以存在的位置为正方形面积减去四分之一圆的面积部分,因此P= = ,故选D。
二、与基本不等式相联系
例2:设x,y满足约束条件3x-y-6?燮0x-y+2?叟0x?叟0,y?叟0,若目标函数z=ax+by(a>0,b>0)的最大值为12,则 + 的最小值为( )。
A. , B. , C. , D.4。
解析:不等式表示的平面区域如图2所示阴影部分,当直线ax+by=z(a>0,b>0)过直线x-y+2=0与直线3x-y-6=0的交点(4,6)时,目标函数z=ax+by(a>0,b>0)取得最大12,即4a+6b=12,即2a+3b=6,而 + =( + ) = +( + )?叟 +2= ,故选A。
三、与解析几何相联系
已知线性约束条件,探求线性截距――加减的形式(非线性距离――平方的形式,斜率――商的形式)目标关系的最值问题是本部分的重点。
例3:已知实数x、y满足x+y-1?燮0x-y+1?叟0y?叟-1,则w=x2+y2-4x-4y+8的最值为 。
解析:目标函数w=x2+y2-4x-4y+8=(x-2)2+(y-2)2,其含义是点(2,2)与可行域内的点的距离的平方。由实数x、y所满足的不等式组作可行域如图3所示:
可行域为图中ABC内部(包括边界),易求B(-2,-1),结合图形知,点(2,2)到点B的距离为其到可行域内点的最大值,Wmax=(-2-2)2+(-1-2)2=25;点(2,2)到直线x+y-1=0的距离为其到可行域内点的最小值,Wmax= = 。
四、与函数相联系
例4:设二元一次不等式组x+2y-19?叟0x-y+8?叟02x+y-14?燮0所表示的平面区域为M,使函数y=ax(a>0,a≠1)的图像过区域的取值范围是( )。
A.[1,3], B.2, ], C.[2,9], D.[ ,9]。
解:C,区域M是三条直线相交构成的三角形(如图4), 显然a>1,只需研究过(1,9)、(3,8)两种情形,a1?燮9且a3?叟8即2?燮a?燮9。
五、与向量相联系
例5:已知点P的坐标(x,y)满足:x-4y+3?燮03x+5y?燮25x-1?叟0,及A(2,0),则 的最大值是___。
解析: =| |・cos ∠AOP即为 在 上的投影长,由x-4y+3=03x+5y=25?圯M(5,2),| |・cos ∠AOP的最大值为5。
六、与数列相联系
例6:设不等式组x>0y>0y?燮-nx+3n所表示的平面区域面积为D,记Dn内整点的个数为an(n?缀N?):①求{an}的通项;②记{an}的前项和为Sn,且Tn= ,若对一切n?缀N?,总有Tn?燮m,求m的取值范围。
解:①画可行域知:an=3n。②知Sn= ,故Tn= ,Tn-Tn-1= - = = (n?叟2),当n=2时,Tn-Tn-1>0,即T1
当n=3时,Tn-Tn-1=0,即T2=T3;当n?叟4时,Tn-Tn-1T4>T5…故当n=2或3时,Tn最大,最大值为 ,故m?叟 。
线性规划范文6
[关键词] 线性规划 方法 应用
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法,早在1939年苏联的康托洛维奇(H.B.Kahtopob )和美国的希奇柯克(F.L.Hitchcock)等人就在生产组织管理和制定交通运输方案方面首先研究和应用线性规划方法。1947年旦茨格等人提出了求解线性规划问题的单纯形方法,为线性规划的理论与计算奠定了基础,特别是电子计算机的出现和日益完善,更使规划论得到迅速的发展,可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划(或非线性规划)问题。从应用范围来看,小到一个班组的计划安排,大至整个部门,以至国民经济计划的最优化方案分析,它都有用武之地,从解决技术问题的最优化,到工业、农业、商业、交通运输业以及决策分析部门它都可以发挥作用。线性规划方法具有适应性强,应用面广,计算技术比较简便的特点。其基本思路是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,用最少的资源(人力、物力和财力)去实现这个任务;二是资源的数量已定,如何合理利用、调配,使任务完成的最多。前者是求极小,后者是求极大。线性规划是在满足企业内、外部的条件下,实现管理目标的极值(极小值和极大值)问题,就是要以尽量少的资源输入来实现更多的社会需要的产品的产出。因此,线性规划是辅助企业“转轨”、“变型”的十分有利的工具,它在辅助企业经营决策、计划优化等方面具有十分重要的作用。
一、线性规划模型的结构
企业是一个复杂的系统,要研究它必须将其抽象出来形成模型。如果将系统内部因素的相互关系和它们活动的规律用数学的形式描述出来,就称之为数学模型。线性规划的模型决定于它的定义,线性规划的定义是:求一组变量的值,在满足一组约束条件下,求得目标函数的最优解。
根据这个定义,就可以确定线性规划模型的基本结构。
1.变量:变量又叫未知数,它是实际系统的未知因素,也是决策系统中的可控因素,一般称为决策变量,常引用英文字母加下标来表示,如Xl,X2,X3,Xm等。
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)=120X1+100X2
资源的多少是约束条件:
由于钢的限制,应满足2X1+3X2≤600;由于煤的限制,应满足2X1+X2≤400。
综合上述表达式,得数学模型为
求最大值(目标函数):f(X1,X2)=120X1+100X2
2X1+3X2≤600
2X1+X2≤400
X1≥0,X2≥0
Xl,X2为决策变量,解(略)得:Xl≤150件,X2≤100件
fmax=(120 ×150+100×100)元=28000元
故当甲产品生产150件、乙产品生产100件时,产值最大,为28000元。
例2:已知甲、乙两煤矿每年的产量分别为200万吨和300万吨,需经过东车站和西车站两个车站运往外地。东车站每年最多能运280万吨煤,西车站每年最多能运360万吨煤,甲煤矿运往东车站和西车站的运费价格分别为1元/吨和1.5元/吨,乙煤矿运往东车站和西车站的运费价格分别为0.8元/吨和1.6元/吨。煤矿应怎样编制调运方案,能使总运费最少?
解:设甲煤矿向东车站运x万吨煤,乙煤矿向东车站运y万吨煤,那么总运费
f(X,Y)=x+1.5(200-x)+0.8y+1.6(300-y)(万元)
即f(X,Y)=780-0.5x-0.8y
现要求此目标函数的最小值。
x、y应满足:x≥0 ;y≥0
200-x≥0
300-y≥0
x+y≤280
200-x+(300-y)≤360
解(略)得:X=0 ,Y=280
甲煤矿生产的煤全部运往西车站、乙煤矿向东车站运280万吨向西车站运20万吨时,总运费最少。
上述两例是只有两个变量的线性规划(求目标函数最大,最小)问题,其求解方法为图解法,对于含更多变量的线性规划问题,在解决思路、步骤上基本一致,只是在具体求解方法上要用到所谓的“单纯形”方法,在此不再赘述。
四、结束语
线性规划作为运筹学的重要分支,它在辅助企业经营决策、计划优化,对于企业优化配置资源,降低成本,实现效益最大化等方面都具有重要的作用,因此作为企业的经营决策者有必要学习一点线性规划知识,为科学决策,合理规划做必要的知识准备。
参考文献:
[1]管梅谷郑汉影:线性规划[M].山东科学技术出版社, 1983