简单的线性规划问题绵竹中学2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,简单的线性规划,(1),x,y,o,2,、,确定步骤,：,回顾,:,直线定界（注意虚、实线），,特殊点定域,1,、,重要 结论,：,直线,Ax+By+C=0,同侧的所有点的坐标（,x,y,）代入,Ax+By+C,，所得实数的符号相同。,二元一次不等式,Ax+By+C0,表示直线,Ax+By+C=0,的某一侧所有点组成的平面区域，此区域不包括边界，把边界画成,虚线,；,不等式,Ax+By+C0,表示平面区域时，此区域包括边界，把边界画成,实线,。,3,、,思想方法,：特殊到一般、数形结合、函数思想,例,3,：满足线性约束条件 的可行域中共有,多少个整数解。,x+4y,11,3x,+,y10,x,0,y,0,1,2,2,3,3,1,4,4,5,5,x,y,0,3x+,y=10,x+,4,y=11,解：,由题意得可行域如图,:,由图知满足约束条件的,可行域中的整点为,(1,1),、,(1,2),、,(2,1),、,(2,2),故有四个整点可行解,.,不等式组 表示的平面区域内的,整数点,共有（）个,巩固练习,1:,1 2 3 4 x,y,4,3,2,1,0,4x+3y=12,例题分析,例,2,要将两种大小不同规格的钢板截成,A,、,B,、,C,三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：,规格类型,钢板类型,第一种钢板,第二种钢板,A,规格,B,规格,C,规格,2,1,2,1,3,1,今需要,A,B,C,三种规格的成品分别为,15,，,18,，,27,块，用数学关系式和图形表示上述要求。,X,张,y,张,例,3:,一个化肥厂生产甲、乙两种混合肥料，生产,1,车皮,甲,种肥料需要的主要原料是磷酸盐,4t,、硝酸盐,18t,；,生产,1,车皮,乙,种肥料需要的主要原料是磷酸盐,1t,、硝酸盐,15t,。现库存磷酸盐,10t,、硝酸盐,66t,，在此基础上生产这两种混合肥料。列出满足生产条件的数学关系式，并画出相应的平面区域。,例题分析,在生产与营销活动中，我们常常需要考虑：怎样利用现有的资源（人力、物力、资金,），取得,最大的收益,。或者，怎样以,最少的资源,投入去完成一项给定的任务。我们把这一类问题称为,“最优化”问题。,不等式的知识是解决“,最优化,”问题的得力工具。,我们将借助,二元一次不等式,（组）的几何表示，学习,“最优化”问题,中的简单,“线性规划”问题,。,画出不等式组 表示的平面区域。,3x+5y 25,x,-,4y,-,3,x1,3x+5y25,x,-,4y,-,3,x1,在该平面区域上,问题,1,：,有无最大,(,小,),值？,问题,：,有无最大,(,小,),值？,x,y,o,x-4y=-3,3x+5y=25,x=1,问题,：,2,+,有无最大,(,小,),值？,C,A,B,x,y,o,x=1,C,B,设,z,2,+,式中变量,、,满足下列条件,，,求,的最大值和最小值。,3x,+,5y,25,x,-,4y,-,3,x1,x-4y=-3,3x+5y=25,x,y,o,x-4y=-3,x=1,C,设,z,2,+,式中变量,、,满足下列条件,，,求的最大值和最小值。,3x+5y25,x-4y-3,x1,B,3x+5y=25,问题,1:,将,z,2,+,变形,?,问题,2:,z,几何意义是,_,。,斜率为,-2,的直线在,y,轴上的截距为,Z,则直线,l,：,2,+,=z,是一簇,与,l,0,平行的直线,故,直线,l,可通过平移直线,l,0,而得,，当直,线往右上方平移时,z,逐渐增大：,当,l,过点,B(1,1),时,z,最小,即,z,min=,3,当,l,过点,A(5,2),时，最大,即,z,max,25+2,12,。,析,:,作直线,l,0,：,2,+,=0,-2,+z,在上述问题中，我们把要求最大值或最小值的,函数,f,2,+,叫做,目标函数,，,目标函数中的变量所要满足的,不等式组,称为,约束条件,。,如果,目标函数,是关于变量的,一次函数,，则称为,线性目标函数,，如果,约束条件,是关于变量的,一次不等式,（或等式），则称为,线性约束条件,。,在线性约束条件下求线性目标函数的最大值或最小值问题，称为,线性规划问题,。使目标函数达到最大值或最小值的,点的坐标,，称为问题的,最优解,。,一般地，满足线性约束条件的,解,(,x,，,y,),叫做,可行解,，由所有可行解组成的,集合,叫做,可行域,。,最优解,：,使,目标函数达到,最大值或 最小值 的可 行 解。,线性约束条件：,约束条件中均为关于,x,、,y,的,一次,不等式或方程。,有关概念,约束条件,：,由、的不等式（方程）构成的不等式组。,目标函数：,欲求最值的关于,x,、,y,的解析式,。,线性目标函数：,欲求最值的解析式是关于,x,、,y,的,一次,解析式。,线性规划：,求线性目标函数在线性约束条件下的最大值或最小值,。,可行解：,满足线性约束条件的解（,x,，,y,）。,可行域：,所有可行解组成的集合。,x,y,o,x-4y=-3,x=1,C,B,3x+5y=25,设,Z,2,+,式中变量、,满足下列条件，,求的最大值和最小值。,3x+5y25,x-4y-3,x1,使,z=2x+y,取得,最大值,的可行解为,，,且最大值为,；,1.,已知二元一次不等式组,x-y0,x+y-10,y-1,（,1,）画出不等式组所表示的平面区域；,满足,的,解,(x,y),都叫做可行解；,z=2x+y,叫做,；,（,2,）设,z=2x+y,，则式中变量,x,y,满足的二元一次不等式组叫做,x,y,的,；,y=-1,x-y=0,x+y=1,2x+y=0,返回,(-1,-1),(2,-1),使,z=2x+y,取得,最小值,的可行解,，,且最小值为,；,这两个,可行解,都叫做问题的,。,线性,约束条件,线性,目标函数,线性约束条件,(2,-1),(-1,-1),3,-3,最优解,x,y,0,1,1,结论,:,1,、线性目标函数的最大值、最小值一般在可行域的顶点处取得,所以，通常通过解方程组，求出要用的顶点坐标。,2,、线性目标函数的最大值、最小值也可能在可行域的边界上取得，即满足条件的最优解有无个。,3,、求线性目标函数的最优解，要注意分析线性,目标函数所表示的,几何意义,-,与,y,轴上的截,距相关的数。,B,C,x,y,o,x,4y=,3,3x+5y=25,x=1,例,1,：设,z,2x,y,式中变量,x,、,y,满足下列条件,求的最大值和最小值。,3x+5y,25,x,4y,3,x1,解：作出可行域如图,：,当,0,时，设直线,l,0,：,2x,y,0,当,l,0,经过可行域上点,A,时，,z,最小，即,最大。,当,l,0,经过可行域上点,C,时，,最大，即,最小。,由 得,A,点坐标,_,；,x,4y,3,3x,5y,25,由 得,C,点坐标,_,；,x,=,1,3x,5y,25,z,max,25,2,8 z,min,21,4,.,4,2,.,4,(5,2),(5,2),(1,4.4),(1,4.4),平移,l,0,，,平移,l,0,，,(5,2),2x,y,0,(1,4.4),(5,2),(1,4.4),解线性规划问题的步骤：,2,、在线性目标函数所表示的一组平行线,中，用平移的方法找出与可行域有公,共点且纵截距最大或最小的直线；,3,、通过解方程组求出最优解；,4,、作出答案。,1,、画出线性约束条件所表示的可行域；,画,移,求,答,3x+5y=25,例,2,：已知,x,、,y,满足 ，设,z,ax,y(a0),，若,取得最大值时，对应点有无数个，求,a,的值。,3x+5y,25,x,4y,3,x1,x,y,o,x-4y=-3,x=1,C,B,解：,当直线,l,：,y,ax,z,与,AC,直线重合时，有无数个点，使函数值取得最大值，此时有：,k,l,k,AC,k,AC,k,l,=,-a,-a,=,a,=,练习：,设,Z,+3,式中变量,、,满足下列条件,，,求,的最大值和最小值。,x,-y,7,2x+3y24,x0,y,6,y,0,例题分析,例,1:,某工厂生产甲、乙两种产品,.,已知生产,甲,种产品,1t,需消耗,A,种矿石,10t,、,B,种矿石,5t,、煤,4t,；生产,乙,种产品,1,吨需消耗,A,种矿石,4t,、,B,种矿石,4t,、煤,9t.,每,1t,甲种产品的利润是,600,元,每,1t,乙种产品的利润是,1000,元,.,工厂在生产这两种产品的计划中要求消耗,A,种矿石不超过,300t,、消耗,B,种矿石不超过,200t,、消耗煤不超过,360t.,甲、乙两种产品应各生产多少,(,精确到,0.1t),能使利润总额达到最大,?,返回,甲产品,（,1t,）,乙产品,（,1t,）,资源限额,（,t,）,A,种矿石（,t,）,B,种矿石（,t,）,煤（,t,）,利润（元）,产品,消耗量,资源,列表,：,5,10,4,600,4,4,9,1000,300,200,360,设生产甲、乙两种产品,.,分别为,x t,、,yt,利润总额为,z,元,例题分析,返回,甲产品,（,1t,）,乙产品,（,1t,）,资源限额,（,t,）,A,种矿石（,t,）,B,种矿石（,t,）,煤（,t,）,利润（元）,产品,消耗量,资源,列表,：,5,10,4,600,4,4,9,1000,300,200,360,把题中限制条件进行,转化：,约束条件,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,目标函数：,设生产甲、乙两种产品,.,分别为,x t,、,yt,利润总额为,z,元,xt,yt,例题分析,解,:,设生产甲、乙两种产品,.,分别为,x t,、,yt,利润总额为,z,元,那么,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,作出以上不等式组所表示的可行域,作出一组平行直线,600 x+1000y=t,，,解得交点,M,的坐标为,(12.4,34.4),5x+4y=200,4x+9y=360,由,10 x+4y=300,5x+4y=200,4x+9y=360,600 x+1000y=0,M,答,:,应生产甲产品约,12.4,吨，乙产品,34.4,吨，能使利润总额达到最大。,(12.4,34.4),返回,经过可行域上的点,M,时,目标函数在,y,轴上截距最大,.,90,30,0,x,y,10,20,10,75,40,50,40,此时,z=600 x+1000y,取得最大值,.,例题分析,例,2,要将两种大小不同规格的钢板截成,A,、,B,、,C,三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示,：,解：,设需截第一种钢板,x,张，第一种钢板,y,张，则,规格类型,钢板类型,第一种钢板,第二种钢板,A,规格,B,规格,C,规格,2,1,2,1,3,1,2x+y15,x+2y18,x+3y27,x0,y0,作出可行域（如图）,目标函数为,z=x+y,今需要,A,B,C,三种规格的成品分别为,15,，,18,，,27,块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。,返回,X,张,y,张,例题分析,x,0,y,2x+y=15,x+3y=27,x+2y=18,x+y=0,2x+y15,x+2y18,x+3y27,x0,xN,*,y0 yN,*,直线,x+y=12,经过的,整点是,B(3,9),和,C(4,8),，它们是最优解,.,作出一组平行直线,z=x+y,，,目标函数,z=,x+y,返回,B(3,9),C(4,8),A(18/5,39/5),当直线经过点,A,时,z=x+y=11.4,x+y=12,解得交点,B,C,的坐标,B(3,9,),和,C(4,8),调整优值法,2,4,6,18,12,8,27,2,4,6,8,10,1