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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,x,y,o,简单的线性规划（3）,线性规划的简单应用,复习回顾,新课讲授,课堂练习,小结,课后作业,不等式,2,x,+,y,-60,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,、在线性目标函数所表示的一组平行线,中，用平移的方法找出与可行域有公,共点且纵截距最大或最小的直线；,3,、通过解方程组求出最优解；,4,、作出答案。,1,、画出线性约束条件所表示的可行域；,画,移,求,答,二,:,给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源最小。,一,:,给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，收到的效益最大。,线性规划研究的两类重要实际问题：,【,引例,】,某工厂用,A,、,B,两种配件生产甲、乙两种产品,每生产一件,甲产品,使用,4,个,A,配件,并耗时,1h,每生产一件,乙产品,使用,4,个,B,配件,并耗时,2h,该厂每天最多可从配件厂获得,16,个,A,配件和,12,个,B,配件,按每天工作,8h,计算,该厂所有可能的日生产安排是什么,?,若生产一件甲产品获利,2,万元,生产一件乙产品获利,3,万元,采用哪种生产安排获得的利润最大,?,二,.,新课讲授,解：设甲、乙两种产品的日生产分别为,x,y,件时,工厂获得的利润为,z,万元,则,x,y,满足约束条件为,作出约束条件所表示的可行域，,如右图所示,目标函数为,z=2x+3y,可变形为,如图,作直线,当直线,平移经过可行域时,在点,M,处达到,y,轴上截距,的最大值,即此时,z,有最大值,.,解方程组,(1),得点,M(4,2),当每天安排生产,4,件甲产品,2,件乙产品时,工厂获利最大为,14,万元,.,不等式组,(1),是一组对变量,x,、,y,的约束条件，这组约束条件都是关于,x,、,y,的一次不等式，所以又称为,线性约束条件,z=2x+3y,是欲达到最大值或最小值所涉及的变量,x,、,y,的解析式，叫做,目标函数,由于,z=2x+3y,又是,x,、,y,的一次解析式，所以又叫做,线性目标函数,求线性目标函数在线性约束条件下的,最大值或最小值的问题，统称为,线性规划问题,在上述问题中，可行域就是阴影部分表示的,三角行区域其中可行解,M(4,2),使目标函数取得,最大值和最小值，它们都叫做这个问题的,最优解,满足线性约束条件的解,(,x,y,),叫做可行解，,由所有可行解组成的集合叫做,可行域,【,例,5】,营养学家指出,成人良好的日常饮 食应该至少提供,0.075kg,的碳水化合,0.06kg,的蛋白质,0.06kg,的脂肪,.,1kg,食物,A,含有,0.105kg,碳水化合物,0.07kg,蛋白质,0.14kg,脂肪,花费,28,元,;,而,1kg,食物,B,含有,0.105kg,碳水化合物,0.14kg,蛋白质,0.07kg,脂肪,花费,21,元,.,为了满足营养专家指出的日常饮食要求,同时使花费最低,需要同时食用食物,A,和食物,B,多少,kg,？,三,.,课堂练习,解：设每天食用,xkg,食物,A,ykg,食物,B,总花费为,z,元,则目标函数为,z=28x+21y,且,x,、,y,满足约束条件,整理为,作出约束条件所表示的可行域，,如右图所示,目标函数可变形为,如图，作直线,当直线,平移经过可行域时，在,点,M,处达到,轴上截距,的最小值，即此时,有最小值,.,解方程组,，,得点,M,的坐标为,，,每天需要同时食用食物,A,约,0.143 kg,，,食物,B,约,0.571 kg,，能够满足日常饮食要求，,且花费最低,16,元,.,例题分析,例,6,要将两种大小不同规格的钢板截成,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,15,但它不是最优整数解,.,作直线,x+y=12,答（略）,例题分析,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,*,经过可行域内的整点,B(3,9),和,C(4,8),且和原点距离最近的直线是,x+y=12,，,它们是最优解,.,答:(略),作出一组平行直线,t,=,x+y,，,目标函数,t,=,x+y,返回,B(3,9),C(4,8),A(18/5,39/5),打网格线法,在可行域内打出网格线，,当直线经过点,A,时,t=x+y=11.4,但它不是最优整数解，,将直线,x+y=11.4,继续向上平移，,1,2,1,2,18,27,15,9,7,8,在可行域内找出最优解、线性规划整数解问题的一般方法是：,1.,若区域“顶点”处恰好为整点，那么它就是最优解；（在包括边界的情况下）,2.,若区域“顶点”不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值,Z,，,然后在可行域内适当放缩目标函数值，使它为整数，且与,Z,最,接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。,3.,在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解,解线性规划应用问题的一般步骤,：,2,）设好变元并列出不等式组和目标函数,3,）,由二元一次不等式表示的平面区域做出可行域；,4,）,在可行域内求目标函数的最优解,1,）理清题意，列出表格：,5),还原成实际问题,(,准确作图，准确计算,),二,:,给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源最小。,一,:,给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，收到的效益最大。,线性规划研究的两类重要实际问题：,二元一次不等式表示平面区域,直线定界，特殊点定域,简单的线性规划,约束条件,目标函数,可行解,可行域,最优解,应用,求解方法：画、移、求、答,0,（图,1,）,【,练习,2】,如图,1,所示，已知,ABC,中的三顶点,A(2,4),B(-1,2),C(1,0),点,P(x,y,),在,ABC,内部及边界运动，,请你探究并讨论以下问题：,在,_,处有最大值,_,，在,_,处有最小值,_,；,你能否设计一个目标函数，使得其取最优解的,情况有无穷多个？,请你分别设计目标函数，使得最值点分别,在,A,处、,B,处、,C,处取得？,(,课后思考题）,若目标函数是,你知道其几何意义吗？,？如果是,或,在,_,处有最大值,_,，在,_,处有最小值,_,；,呢,？,你能否借助其几何意义求得,z=,x+y,z=,x-y,z=,x,2,+y,2,，,z,min,和,z,max,A(2,4),C(0,1),B(-1,2),小结：,解线性规划应用问题的一般步骤：,1,）理清题意，列出表格：,2,）设好变元并列出不等式组和目标函数,3,）准确作图，准确计算,知识点：,技能点：,数学思想：,4,）还原成实际问题,学习了把实际问题转化成线性规划问题即建立数模的方法,渗透转换、化归思想，数形结合思想，用数学的意识、创新意识,作业,：,课本习题,0,A,B,C,（,图,2,）,0,A,B,C,如图,2,，问参考答案,:,z=,x+y,在,点,A,处有最大值,6,，在,边界,BC,处有最小值,1,；,z=,x+y,在,点,C,处有最大值,1,，在,点,B,处有最小值,-3,评述：,简单线性规划问题就是求线性目标函数在线性约束条件下的最优解，无论此类题目是以什么实际问题出，其求解的格式与步骤是不变的：,（,1,）,寻找线性约束条件，线性目标函数；,（,2,）,由二元一次不等式表示的平面区域做出可行域；,（,3,）,在可行域内求目标函数的最优解,四,.,课堂小结,用,图解法,解决简单的线性规划问题的基本步骤：,1,、首先，要根据线性约束条件画出可行域,（即画出不等式组所表示的公共区域）,2,、设,t,=0,，画出直线,l,0,3,、观察、分析，平移直线,l,0,，从而找到最优解,4.,最后求得目标函数的最大值及最小值,【,作业,】,五,.,课后作业,习题,例题分析,例,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+