《332简单的线性规划问题》由会员分享,可在线阅读,更多相关《332简单的线性规划问题(45页珍藏版)》请在金锄头文库上搜索。
1、回顾知识回顾知识 上一小节我们已经学过了,现实生活中有很上一小节我们已经学过了,现实生活中有很多问题可以转化成解二元一次不等式组多问题可以转化成解二元一次不等式组. 一个一元二次方程表示的应为直线一个一元二次方程表示的应为直线Ax+By+C=0某一侧所有的点组成的平面区域某一侧所有的点组成的平面区域.如如何何确确定定直线定界,特殊点定域直线定界,特殊点定域想想是怎么具体操作想想是怎么具体操作的?的?新课导入新课导入 在现实生产、生活中,经常会遇到在现实生产、生活中,经常会遇到资源利用资源利用、人力调配人力调配、生产安排生产安排等问题等问题 . .利用我们今天所学利用我们今天所学的知识,可以解决
2、很多现实生活中简单的线性规的知识,可以解决很多现实生活中简单的线性规划问题划问题. . 下面我们看一个线型规划知识解决实际问题下面我们看一个线型规划知识解决实际问题的一个小例子的一个小例子. .X XO OY YA AB BC C教学目标教学目标知识与能力知识与能力 1.了解线性规划的意义,了解线性约束条件、了解线性规划的意义,了解线性约束条件、线性目标函数、可行解、可行域、最优解等概念;线性目标函数、可行解、可行域、最优解等概念;2.理解线性规划的图解法理解线性规划的图解法;3.会利用图解法求线性目标函数的最优解会利用图解法求线性目标函数的最优解.过程与方法过程与方法 1.在应用图解法解题的
3、过程中培养学生的在应用图解法解题的过程中培养学生的观察能力、理解能力观察能力、理解能力 ; 2.在变式训练的过程中,培养学生的分析在变式训练的过程中,培养学生的分析能力、探索能力能力、探索能力; 3.在对具体事例的感性认识上升到对线性在对具体事例的感性认识上升到对线性规划的理性认识过程中,培养学生运用数形结规划的理性认识过程中,培养学生运用数形结合思想解题的能力和化归能力合思想解题的能力和化归能力.情感态度与价值观情感态度与价值观 1.让学生体验数学来源于生活又服务于生让学生体验数学来源于生活又服务于生活,体验数学在建设节约型社会中的作用,品活,体验数学在建设节约型社会中的作用,品尝学习数学的
4、乐趣尝学习数学的乐趣; 2.让学生体验数学活动充满着探索与创造,让学生体验数学活动充满着探索与创造,培养学生勤于思考、勇于探索的精神;培养学生勤于思考、勇于探索的精神; 3.让学生学会用运动观点观察事物,了解让学生学会用运动观点观察事物,了解事物之间从一般到特殊、从特殊到一般的辩证事物之间从一般到特殊、从特殊到一般的辩证关系关系.重点重点难点难点教学重难点教学重难点 建立线性规划模型建立线性规划模型 . .根据实际问题中的已知根据实际问题中的已知条件,找出约束条件和目标函数,利用图解法求条件,找出约束条件和目标函数,利用图解法求得最优解为突出重点,突破难点,本节教学应得最优解为突出重点,突破难
5、点,本节教学应指导学生紧紧抓住化归、数形结合的数学思想方指导学生紧紧抓住化归、数形结合的数学思想方法将实际问题数学化、代数问题几何化法将实际问题数学化、代数问题几何化 如何把实际问题转化为简单的线性规划问题,如何把实际问题转化为简单的线性规划问题,并准确给出解答并准确给出解答引例引例 某工厂有某工厂有A、B两种配件生产甲、乙两种产两种配件生产甲、乙两种产品,每生产一件甲产品使用品,每生产一件甲产品使用4个个A配件耗时配件耗时1h,每每生产一件乙产品使用生产一件乙产品使用4个个B配件耗时配件耗时2h,该厂每,该厂每天最多可从配件厂获得天最多可从配件厂获得16个个A配件和配件和12个个B配件,配件
6、,按每天按每天8h计算,该厂所有可能的日生产安排是什计算,该厂所有可能的日生产安排是什么?么? (1)用不等式组表示问题中的限制条件)用不等式组表示问题中的限制条件 ; (2)画出不等式组所表示的平面区域:画出不等式组所表示的平面区域:如上图,图中的阴影部分的整点(坐标为整数如上图,图中的阴影部分的整点(坐标为整数的点)就代表所有可能的日生产安排;的点)就代表所有可能的日生产安排; (3)提出新问题:)提出新问题: 进一步,若生产一件甲产品获利进一步,若生产一件甲产品获利2万元,生万元,生产一件乙产品获利产一件乙产品获利3万元,采用哪种生产安排利万元,采用哪种生产安排利润最大?润最大?(4)尝
7、试解答:)尝试解答: 分析:分析:设生产甲产品设生产甲产品x件,乙产品件,乙产品y件时,件时,工厂获得的利润为工厂获得的利润为z,则则z=2x+3y.这样,上述问题这样,上述问题就转化为:当就转化为:当x,y满足上不等式组并且为非负整满足上不等式组并且为非负整数时,数时,z的最大值是多少?的最大值是多少?把把z=2x+3y变形为变形为 这是斜率为这是斜率为截距为截距为的直线的直线.当当z变化时,可以得到一族变化时,可以得到一族互相平行的直线,如图,由于这些直线的斜率互相平行的直线,如图,由于这些直线的斜率是确定的,因此只要给定一个点,(例如(是确定的,因此只要给定一个点,(例如(1,2),就能
8、确定一条直线),就能确定一条直线这说明,这说明,截距可以由平面内的一个点的坐标唯一确定截距可以由平面内的一个点的坐标唯一确定.可以看到,直线可以看到,直线 与不等式组的与不等式组的区域的交点满足这个不等式组,而且当截距区域的交点满足这个不等式组,而且当截距 最大时,最大时,z取得最大值取得最大值.因此,问题可以转化为当直线因此,问题可以转化为当直线 与不等式组确定的平面区域有公共点时,在与不等式组确定的平面区域有公共点时,在区域内找一个点区域内找一个点P,使直线经过点,使直线经过点P时截距最时截距最大大 .(5)获得结果:)获得结果:由图中可以看出,当实现由图中可以看出,当实现 x=4与直线与
9、直线x+2y-8=0的交点的交点M(4,2)时,截)时,截与直线与直线距的值最大,最大值为距的值最大,最大值为这时这时2x+3y=14. 所以,每天生产甲产品所以,每天生产甲产品4件,乙产品件,乙产品2件时,工件时,工厂可获得最大利润厂可获得最大利润14万元万元 . 1、像上题求最大利润的这种问题,可以、像上题求最大利润的这种问题,可以转化成求二元一次不等式组与一族直线相交转化成求二元一次不等式组与一族直线相交点的问题点的问题. 2、遇到没有学过的问题时,一定要认、遇到没有学过的问题时,一定要认真思考,看看能不能用平时的知识去解决真思考,看看能不能用平时的知识去解决.概念概念 (1)线性约束条
10、件:线性约束条件:在上述问题中,不等式在上述问题中,不等式组是一组变量组是一组变量x、y的约束条件,这组约束条件的约束条件,这组约束条件都是关于都是关于x、y的一次不等式,故又称线性约束的一次不等式,故又称线性约束条件条件 (2)线性目标函数线性目标函数;关于关于x、y的一次式的一次式z=2x+y是欲达到最大值或最小值所涉及的变量是欲达到最大值或最小值所涉及的变量x、y的解析式,叫线性目标函数的解析式,叫线性目标函数 . (3)线性规划问题:线性规划问题:一般地,求线性目标函一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,数在线性约束条件下的最大值或最小值的问题,统称为线性规划问
11、题统称为线性规划问题 .(4)可行解、可行域和最优解:可行解、可行域和最优解:满足线性约束条件的解(满足线性约束条件的解(x,y)叫可行解)叫可行解由所有可行解组成的集合叫做可行域由所有可行解组成的集合叫做可行域 . 使目标函数取得最大或最小值的可行解叫使目标函数取得最大或最小值的可行解叫线性规划问题的最优解线性规划问题的最优解 (1) 在上述问题中,如果生产一件甲产品获在上述问题中,如果生产一件甲产品获3万元,每生产一件乙产品获利万元,每生产一件乙产品获利2万元,有应当万元,有应当如何安排生产才能获得如何安排生产才能获得最大利润最大利润?在换几组数?在换几组数据试试据试试. (2)有上述过程
12、,你能得出有上述过程,你能得出最优解最优解与与可行域可行域之间的关系吗之间的关系吗 ?相同的思路,留给同学相同的思路,留给同学们自己思考!们自己思考!实地演练实地演练变量变量x、y满足下列条件满足下列条件,求,求z的最大值和最小值的最大值和最小值.讨论下面的问题,讨论下面的问题,设设z=2x+y+50,式中的式中的目标函数目标函数(线性目标函数)(线性目标函数)约束条件约束条件(线性约束条件)(线性约束条件)最优解最优解 求线性目标函数求线性目标函数z的最值的步骤的最值的步骤: 画画 求求 移移 作作l。(3,2)(8,2)解:解:yX01234567123458 由上图可得当直线由上图可得当
13、直线z=2x+y+50过点(过点(3,2)时,目标函数取最小值时,目标函数取最小值;当直线过点(当直线过点(8,2)时,)时,目标函数取的最大值目标函数取的最大值. 答:目标函数答:目标函数z=2x+y+50的最小值为的最小值为58,最大值为最大值为58.解线性规划问题的步骤:解线性规划问题的步骤: (1)画画:画出线性约束条件所表示的可行域;:画出线性约束条件所表示的可行域; (2)移移:在线性目标函数所表示的一组平行:在线性目标函数所表示的一组平行线中,利用平移的方法找出与可行域有公共点且纵线中,利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线;截距最大或最小的直线;(3)求求:
14、通过解方程组求出最优解;:通过解方程组求出最优解;(4)答答:作出答案:作出答案. 若需在长为若需在长为4000mm的圆钢上的圆钢上 ,截出长,截出长为为698mm和和518mm两种毛坯,问怎样截取才两种毛坯,问怎样截取才能使残料最少?能使残料最少? 初步分析初步分析 : 可以先考虑两种可以先考虑两种“极端极端”的情的情况:全部截出长为况:全部截出长为698mm的甲件,一共可截出的甲件,一共可截出 5件,残料长为件,残料长为510mm;全部截出长为;全部截出长为518mm的乙件,一共可截出的乙件,一共可截出 7件,残料长为件,残料长为374mm.从从而而x与与y应搭配使用应搭配使用.解:解:截
15、截x个甲件,个甲件,y个乙件,则截取条件数个乙件,则截取条件数学化地表示出来就是学化地表示出来就是698 x + 518y 4000同时同时x与与y都是非负整数;都是非负整数;目标函数为目标函数为约束条件为约束条件为698 x + 518y 4000x0,y0,xN,yNXOYL:698 x + 518y =4000 将目标函数代表的直线族画出,然后寻找将目标函数代表的直线族画出,然后寻找使目标函数最大的点即可使目标函数最大的点即可. x和和y都是整数!都是整数! 要将两种大小不同的钢板截成要将两种大小不同的钢板截成A、B、C三三种规格,每张钢板可同时截得三种规格的小钢种规格,每张钢板可同时截
16、得三种规格的小钢板的块数如下表所示:板的块数如下表所示:规格类型规格类型钢板类型钢板类型A规格规格B规格规格C规格规格第一种钢第一种钢板板211第二种钢第二种钢板板123 今需要今需要A A、B B、C C三种规格的成品分别为三种规格的成品分别为1515、1818、2727块,问各截这两种钢板多少张可得所需三种规块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少?格成品,且使所用钢板张数最少? 分析:本题是给定一项任务,如何合理安排分析:本题是给定一项任务,如何合理安排和规划,能以最少的资源来完成该项任务和规划,能以最少的资源来完成该项任务 . .我们我们应该搞清各量之间的关
17、系,建立线性规划的模型应该搞清各量之间的关系,建立线性规划的模型. .第一种钢板第一种钢板x张,第二种钢板张,第二种钢板y张,所用张,所用解:解:钢板数为钢板数为z张,则张,则z=x+y ;由题中表格得由题中表格得 作出以上不等式组所表示的平面区域作出以上不等式组所表示的平面区域,即可行域即可行域. 作直线作直线L: x+y=0, 把直线把直线L向右上方平移至直线经过可行域向右上方平移至直线经过可行域上的点上的点A,且与原点距离最近,此时,且与原点距离最近,此时z=x+y取取最小值最小值. oxy816248162x+y=15x+2y=18x+2y=18A解方程组解方程组 得交点得交点A的的由
18、于两个坐标都不是由于两个坐标都不是整数,所以这个解不是最优解;整数,所以这个解不是最优解; 将直线向可行域内平移,最先到将直线向可行域内平移,最先到达的整点为达的整点为B(3,9)和和C(4,8)它们是最优它们是最优解,此时解,此时z取得最小值取得最小值12 .坐标坐标 答:要截得所需规格的三种钢板,且使所截答:要截得所需规格的三种钢板,且使所截两种钢板的张数最少的方法有两种,第一种截法两种钢板的张数最少的方法有两种,第一种截法是截第一种钢板是截第一种钢板3张、第二种钢板张、第二种钢板9张;第二种截张;第二种截法是截第一种钢板法是截第一种钢板4张、第二种钢板张、第二种钢板8张,两种方张,两种方
19、法都最少要截得两种钢板共法都最少要截得两种钢板共12张张.2x+y=15oxy81624816x+2y=18x+2y=18A 某某工工厂厂生生产产甲甲、乙乙两两种种产产品品,生生产产甲甲种种产产品品1t需需耗耗A种种矿矿石石10t、B种种矿矿石石5t、煤煤4t;生生产产乙乙种种产产品品1t需需耗耗A种种矿矿石石4t、B种种矿矿石石4t、煤煤9t每每1t甲甲种种产产品品的的利利润润是是600元元,每每1t乙乙种种产产品品的的利利润润是是1000元元工工厂厂在在生生产产这这两两种种产产品品的的计计划划中中要要求求消消耗耗A种种矿矿石石不不超超过过300 t、B种种矿矿石石不不超超过过200 t、煤
20、煤不不超超过过360 t甲甲、乙乙两两种种产产品品各各生生产产多多少少(精精确确到到1 t),能能使使利利润润总总额额达达到到最大?最大? 分析:分析:这是线性规划的理论和方法的应用这是线性规划的理论和方法的应用中的第一类问题即在人力、物力资源一定的中的第一类问题即在人力、物力资源一定的条件下,如何使用它们来完成最多任务解题条件下,如何使用它们来完成最多任务解题一般步骤为:一般步骤为:设出所求的未知数;设出所求的未知数;列出约束条件列出约束条件建立目标函数;建立目标函数;作出可行域;作出可行域;运用图解法求出最优解运用图解法求出最优解 依据题中已知条件,列表如下:依据题中已知条件,列表如下:甲
21、产品甲产品(1t)乙产品乙产品(1t)资源限额资源限额(t)A种矿石种矿石(t)104300B种矿石种矿石(t)54200煤(煤(t)49360利润(元)利润(元)6001000资源资源消耗品消耗品产品产品解:解: 生产甲、乙两种产品分别为生产甲、乙两种产品分别为xt,yt,利润利润总额为总额为z,由题意可得,由题意可得已知变量已知变量x与与y满足约束条件满足约束条件利用图解法可求出最大值利用图解法可求出最大值.此时,此时,课堂小结课堂小结 1、线性目标函数的最大(小)值一般在可、线性目标函数的最大(小)值一般在可行域的顶点处取得,也可能在边界处取得行域的顶点处取得,也可能在边界处取得. 2、
22、求线性目标函数的最优解,要注意分析、求线性目标函数的最优解,要注意分析线性目标函数所表示的几何意义线性目标函数所表示的几何意义在在y轴上的截轴上的截距或其相反数距或其相反数.3、解线性规划问题的步骤:、解线性规划问题的步骤:画、移、求、答画、移、求、答. (2005 广东)求广东)求z=3x+5y的最大值和最小的最大值和最小值,使式中的值,使式中的x、y满足约束条件满足约束条件 :解:不等式组所表示的平面区域解:不等式组所表示的平面区域如图所示如图所示 高考链接高考链接 从图示可知,直线从图示可知,直线3x+5y=t在经过不等式在经过不等式组所表示的公共区域内的点时,以经过点(组所表示的公共区
23、域内的点时,以经过点(-2,-1)的直线所对应的)的直线所对应的t最小,以经过点最小,以经过点的直线所对应的的直线所对应的t最大最大. 所以所以zmin=3(-2)+(-1)=-11;zmax=3 +5 =14.课堂练习课堂练习 1、求、求z=2x+y的最大值,使式中的的最大值,使式中的x、y满足满足约束条件约束条件解:用图形表示出不等式组表示的平面区域;解:用图形表示出不等式组表示的平面区域;当当x=0,y=0时,时,z=2x+y=0作一组与直线平行的直线作一组与直线平行的直线:2x+y=t,tR. 可知,在经过不等式组所表示的公共区域内可知,在经过不等式组所表示的公共区域内的点且平行于的直
24、线中,以经过点的点且平行于的直线中,以经过点A(2,-1)的)的直线所对应的直线所对应的t最大最大. 2、某公司承担了每天至少搬运、某公司承担了每天至少搬运280t水泥水泥的任务,已知该公司有的任务,已知该公司有6辆辆A型卡车和型卡车和B型卡型卡车,已知车,已知A型卡车每天每辆的运载量为型卡车每天每辆的运载量为30t,成本费为成本费为0.9千元,千元,B型卡车每天每辆的运载型卡车每天每辆的运载量为量为40t,成本费为,成本费为1千元千元. (1)假如你是公司的调度员,请你按要求)假如你是公司的调度员,请你按要求设计出公司每天的派车方案设计出公司每天的派车方案; (2)设每天派出)设每天派出A型
25、卡车型卡车x辆,辆,B型卡车型卡车y辆,辆,公司每天所花成本费公司每天所花成本费z千元,写出千元,写出x、y应满足应满足的条件以及的条件以及z与与x、y之间的函数关系式;之间的函数关系式; (3)如果你是公司的经理,为使公司所花如果你是公司的经理,为使公司所花的成本费最小,每天应派出的成本费最小,每天应派出A型卡车、型卡车、B型卡型卡车各为多少辆?车各为多少辆?解:解: 由已知条件可知,由已知条件可知, Z =0.9x + y式中式中x与与y变量应满足:变量应满足:3x+4y280x60y4从而求出从而求出z的最小值即可的最小值即可.不等式组所表示的平面区域如图所示不等式组所表示的平面区域如图所示ABC0.9 x+ y = 0246810246810xoy 如上图所示,作一组平行直线如上图所示,作一组平行直线0.9x+y=t,直直线经过点线经过点A(4,4)时,对应的时,对应的t的值最小,经过点的值最小,经过点B(6,4)时,对应的时,对应的t的值最大,所以的值最大,所以z的最小值为的最小值为0.94+4=7.6. 答:公司派出答:公司派出4辆辆A型卡车、型卡车、4 辆辆B型卡车时型卡车时每天所支出的费用最少每天所支出的费用最少.习题答案习题答案o1xy-22xoy2