简单线性规划ppt课件习题课.ppt

《简单线性规划ppt课件习题课.ppt》由会员分享，可在线阅读，更多相关《简单线性规划ppt课件习题课.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、表示平面区域。表示平面区域。（即不等式即不等式式式半平面内的点满足不等半平面内的点满足不等另一个另一个不等式不等式一个半平面内的点满足一个半平面内的点满足两侧的两个半平面内，两侧的两个半平面内，另外两类分居在另外两类分居在上，上，一类在直线一类在直线内所有的点分为三类：内所有的点分为三类：将平面将平面直线直线在平面直角坐标系中，在平面直角坐标系中，)00, 0, 0000)1( CByAxCByAxCByAxCByAxCByAxCByAx知识要点知识要点1. 1.二元一次不等式（组）表示平面区域二元一次不等式（组）表示平面区域一一.线性规划线性规划(3)(3)画法画法: :画二元一次不等式画二

2、元一次不等式AxAx+ +ByBy+ +C C 00或或AxAx+ +ByBy+ +C C 0 0 表示的平面区域常采用表示的平面区域常采用“直线定界，特殊点定域直线定界，特殊点定域”的的方法。当方法。当C0C0时，常把原点作为此特殊点。有等号画时，常把原点作为此特殊点。有等号画实线（包括边界）实线（包括边界）, ,无等号画虚线（不包括边界）。无等号画虚线（不包括边界）。(2)(2)判断方法判断方法: :由于对在直线由于对在直线AxAx+ +ByBy+ +C C=0=0同一侧的所有点同一侧的所有点(x(x，y)y)，把它的坐标（，把它的坐标（x x，y)y)代入代入AxAx+ +ByBy+ +

3、C C，所得到实数，所得到实数的符号都相同，所以的符号都相同，所以只需在此直线的某一侧取一特殊点只需在此直线的某一侧取一特殊点（x x0 0, ,y y0 0) )，从，从AxAx0 0+ +ByBy0 0+ +C C 的正负即可判断的正负即可判断AxAx+ +ByBy+ +C C0 0表表示直线哪一侧的平面区域示直线哪一侧的平面区域. . （特殊地，当（特殊地，当C C00时，常把时，常把原点原点作为此特殊点）作为此特殊点）(1)线性约束条件线性约束条件：由由x,y的一次不等式（或方程）组成的不等式组。的一次不等式（或方程）组成的不等式组。(2)目标函数目标函数：要求最大值（或最小值）的函数

4、。：要求最大值（或最小值）的函数。(3)线性目标函数线性目标函数：如果：如果目标函数目标函数是是x,y的一次解的一次解析式，则目标函数又称为线性目标函数。析式，则目标函数又称为线性目标函数。2.线性规划(4)线性规划线性规划：求线性目标函数在线性约束条件下求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题的最大值或最小值的问题，统称为线性规划问题 (5)可行解可行解 ：满足线性约束条件的解满足线性约束条件的解(x，y)叫可叫可 行解；行解； (6)可行域可行域 ：由所有可行解组成的集合叫做可行域；由所有可行解组成的集合叫做可行域； (7)最优解最优解 ：使目标函数取得最大

5、或最小值的可行解使目标函数取得最大或最小值的可行解 叫线性规划问题的最优解。叫线性规划问题的最优解。 (2) (2)移：在线性目标函数所表示的一组平行线中，利移：在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；或最小的直线； (3)(3)求：通过解方程组求出最优解；求：通过解方程组求出最优解； (4)(4)答：作出答案。答：作出答案。(1)(1)画：画出线性约束条件所表示的可行域；画：画出线性约束条件所表示的可行域；3.3.用图解法解线性规划问题的步骤用图解法解线性规划问题的步骤典型题例典型题例:题型题

6、型1. 1.求目标函数的最值问题求目标函数的最值问题: zaxby截距型目标函数D3 3(2008(2008 全国全国卷文、理卷文、理) ) 设变量设变量 xy， 满足约束满足约束 条件：条件：222yxxyx，则，则yxz3的最小值为的最小值为（ ） A A 2 B B 4 C C 6 D D 8 例例11 1 （20082008 北京理）北京理）若实数若实数 xy， 满足满足1000 xyxyx ， 则则23xyz的最小值是（的最小值是（ ） A A0 0 B B1 1 C C3 D D9 9 B变式练习变式练习:C0222xyxy若求取值范围呢？若求取值范围呢？xyyxsyxszxy3.

7、00,2(0435,36)2在在约约束束条条件件下下当当时时目目标标函函数数的的最最大大值值的的变变化化范范围围是是().().A.6,15 B.7,15 C.6,8 D.A.6,15 B.7,15 C.6,8 D.东东7,87,8广广 DC2 2. .( (0808 福建理福建理) ) 若实数若实数x x、y y满足满足100 xyx ， 则则yx的取值范围是（的取值范围是（ ） A.(0,1) A.(0,1) B.B.0,1 C.C.(1,+(1,+) ) D.D.1, 例例200:yyzxx斜率型目标函数222040 ,2502111210253.xyxyxyyzxzxyy 求求：（ ）

8、例例的的范范围围; ;（ ）的的最最大大值值. . 2200:zxxyy距距离离型型目目标标函函数数-6例例.题型题型2.2.已知目标函数的最值，求参数的取值问题已知目标函数的最值，求参数的取值问题A1yxymxxyD5 5 （0 07 7 北京卷）北京卷）若不等式组若不等式组220 xyxyyxya ， ，表示的平面表示的平面 区域是一个三角形，则区域是一个三角形，则a的取值范围是的取值范围是 43a 01a 413a 01a或或43a 1.变式练习变式练习AxyO 1 1A, 5 1B, 4 2C,53311.ZxayaA.B.C.D.在在如如右右图图所所示示的的坐坐标标平平面面的的可可行

9、行域域内内（阴阴影影部部分分且且包包括括边边界界），目目标标函函数数取取得得最最小小值值的的最最优优解解有有无无数数个个，则则 的的一一个个可可能能值值为为（）. .2. 1 0A,xy 0 1B,2 43 5C,B61051233 121233125101055 10如右图目标函数的可行域为四2 4边形(含边界),若(, )是该目标函3 5数的最优解,则 的取值范围是().,K = ax - yOACBaA.,B.,C.,D., 3.题型题型3.3.平面区域的面积问题平面区域的面积问题C03434xxyxyA变式练习变式练习:BD4. 4. 在平面直角坐标系在平面直角坐标系xOy中，已知平面

10、区域中，已知平面区域A=(x,y)|x+y1,且且x0,y0,求平面区域求平面区域B=(x+y,x- -y)|(x,y)A的面积？的面积？11221S画出关于画出关于u，v的可行域的可行域12;002uvxyuxuvuvyuv则解析令u=x+y，v=x-y，方法规律小结方法规律小结1、线性规划问题是数形结合思想的重要体现，、线性规划问题是数形结合思想的重要体现，通过画简便直观图求最值。通过画简便直观图求最值。2、常见目标函数有、常见目标函数有截距型截距型 ,距离距离型型 ，斜率型，斜率型 几几种，截距型要注意种，截距型要注意y的系数的正负号。的系数的正负号。3、最优解一般在可行域的顶点或边界处

11、取得，、最优解一般在可行域的顶点或边界处取得，要注意边界的虚实。要注意边界的虚实。4、解选择、填空题常常可先求可行域的顶点，、解选择、填空题常常可先求可行域的顶点，再代人目标函数验算即可。再代人目标函数验算即可。 byaxz 2020yyxxz 00 xxyyz 1 1(2008(2008 广东理广东理) )若变量若变量 x,yx,y 满足满足, 0, 0,502,402yxyxyx， 则则 z=3x+2yz=3x+2y 的最大值是的最大值是 ( ( ) ) A A90 90 B. 80 B. 80 C.C. 70 70 D. 40D. 40 C巩固练习巩固练习2 2、(2008(2008 中

12、山一模理中山一模理) )若若 622yxyx，则目标，则目标 函函数数yxz3的取值范围是的取值范围是 14, 8例例 1 1 设设 x、y满足约束条件满足约束条件5,3212,03,04.xyxyxy则使得则使得 目标函数目标函数65zxy的最大的点的最大的点( , )x y是是_. . 3 , 23.2 2(2008(2008 陕西理陕西理) )已知实数已知实数xy，满足满足121yyxxym ， 如如果目标函数果目标函数 zxy的的最小值为最小值为 1 ，则实数，则实数m 等于（等于（ ） A A7 7 B B5 5 C C4 4 D D3 3 B4.二是二是给定一项任务，问怎样统筹安排

13、，能给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源最小。使完成这项任务的人力、物力资源最小。一是一是给定一定数量的人力、物力资源，问给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务怎样安排运用这些资源，能使完成的任务量最大，收到的效益最大。量最大，收到的效益最大。1.线性规划研究的两类重要实际问题：线性规划研究的两类重要实际问题：二二.线性规划的实际应用线性规划的实际应用2.解线性规划应用问题的一般步骤解线性规划应用问题的一般步骤：线性规划问题一般用图解法，其步骤如下：线性规划问题一般用图解法，其步骤如下： （1）根据题意，设出变量）根据题意，设出变量 x、

14、y； （2）找出线性约束条件；）找出线性约束条件； （3）确定线性目标函数）确定线性目标函数 z=f（x，y） ；） ； （4） 画出可行域 （即各约束条件所示区域的公共） 画出可行域 （即各约束条件所示区域的公共区域） ；区域） ； （5）利用线性目标函数作平行直线系）利用线性目标函数作平行直线系 f（x，y）=t（t为参数） ；为参数） ；根据根据图形图形求求最优解最优解及及目标目标函数函数的的最值最值； （6）根据根据结果结果，还原还原成成实际实际问题问题的的解解。 3.若若实实际际问问题题要要求求的的最最优优解解是是整整数数解解, ,而而利利用用图图解解法法得得到到的的解解是是, ,应

15、应作作适适当当的的调调整整, ,其其方方法法应应以以与与在在直直线线的的附附近近寻寻求求与与此此直直线线实实际际应应用用问问题题距距离离最最近近的的整整线线性性目目标标函函数数的的直直线线的的距距离离为为依依据据, ,如如果果可可行行域域中中的的整整点点数数目目很很点点少少中中最最优优解解的的调调整整, ,采采用用逐逐个个试试验验非非解解. .整整数数法法也也可可. .解：设公司在甲电视台和乙电视台做广告的时间分别为解：设公司在甲电视台和乙电视台做广告的时间分别为x分钟分钟和和y分钟，总收益为分钟，总收益为z元，由题意得元，由题意得3005002009000000.xyxyxy， ， 例例 3

16、 3、 （、 （20072007 山东）山东）本公司计划本公司计划 20082008 年在甲、乙两个电视台做年在甲、乙两个电视台做总时间不超过总时间不超过 300300 分钟的广告， 广告总费用不超过分钟的广告， 广告总费用不超过 9 9 万元， 甲、万元， 甲、乙电视台的广告收费标准分别为乙电视台的广告收费标准分别为500元元/ /分钟和分钟和 200200 元元/ /分钟，分钟，规定甲、乙两个电视台为该公司所做的每分钟广告，能给公司规定甲、乙两个电视台为该公司所做的每分钟广告，能给公司事来的收益分别为事来的收益分别为 0.30.3 万元和万元和 0.20.2 万元问该公司如何分配在万元问该

17、公司如何分配在甲、乙两个电视台的广告时间，才能使公司的收益最大，最大甲、乙两个电视台的广告时间，才能使公司的收益最大，最大收益是收益是多少万元？多少万元？ 【例【例1】 某公司计划某公司计划2013年年0100200300100200300400500yxlM 目标函数为目标函数为30002000zxy 二元一次不等式组等价于二元一次不等式组等价于3005290000.xyxyxy， ， 作出二元一次不等式组所表示的平面区域，作出二元一次不等式组所表示的平面区域， 即可行域即可行域如图：如图： 作直线作直线:300020000lxy， 即即320 xy 平移直线平移直线l，从图中可知，当直线，

18、从图中可知，当直线l过过M点时，点时， 目标函数取得最大值目标函数取得最大值 联立联立30052900.xyxy，解得解得100200 xy， 点点M的坐标为的坐标为(100 200)， max30002000700000zxy（元）（元） 答：该公司在甲电视台做答：该公司在甲电视台做 100100 分钟广告，在乙电视台做分钟广告，在乙电视台做 200200 分分钟广告，公司的收益最大，钟广告，公司的收益最大，最大收益是最大收益是 7070 万元？万元？ 点评点评 画出可行域后，再把目标函数平行平移，要画出可行域后，再把目标函数平行平移，要比较斜率的大小，注意目标函数的意义比较斜率的大小，注意

19、目标函数的意义.【练习【练习1】（】（2010广东文、理）广东文、理） 某营养师要为某个儿童预定午餐和晚餐某营养师要为某个儿童预定午餐和晚餐.已知一个已知一个单位的午餐含单位的午餐含12个单位的碳水化合物个单位的碳水化合物6个单位蛋白质个单位蛋白质和和6个单位的维生素个单位的维生素C；一个单位的晚餐含；一个单位的晚餐含8个单位的个单位的碳水化合物，碳水化合物，6个单位的蛋白质和个单位的蛋白质和10个单位的维生素个单位的维生素C.另外，该儿童这两餐需要的营养中至少含另外，该儿童这两餐需要的营养中至少含64个单位的个单位的碳水化合物，碳水化合物，42个单位的蛋白质和个单位的蛋白质和54个单位的维生

20、素个单位的维生素C.如果一个单位的午餐、晚餐的费用分别是如果一个单位的午餐、晚餐的费用分别是2.5元和元和4元，元，那么要满足上述的营养要求，并且花费最少，应当为该那么要满足上述的营养要求，并且花费最少，应当为该儿童分别预定多少个单位的午餐和晚餐？儿童分别预定多少个单位的午餐和晚餐？ 作出可行域如图所示：作出可行域如图所示： 变换目标函数：变换目标函数：584zyx x+y=73x+2y=16xy3x+5y=27A当目标函数经过点当目标函数经过点A时，时，z取得最小值取得最小值;由由x+ y =73 x+5 y =27解得点解得点A（4，3）即当即当x=4,y=3时，花费最少时，花费最少,为为

21、z=2.5x+4y=2.54+43=22(元元)答：要满足营养要求，并且花费最少，答：要满足营养要求，并且花费最少，应当为儿童分别预订应当为儿童分别预订4个单位的午餐和个单位的午餐和3个单位的晚餐。个单位的晚餐。ABC,:要要将将两两种种大大小小不不同同的的钢钢板板截截成成 、 、 三三种种规规格格每每张张钢钢板板可可同同时时截截得得三三种种规规格格的的小小钢钢板板的的块块数数如如下下 例例2 2表表所所示示 规格类型规格类型钢板类型钢板类型 A规格规格 B规格规格 C规格规格第一种钢板第一种钢板 2 1 1第二种钢板第二种钢板 1 2 315 18 27ABC,.今今需需要要 、 、 三三种

22、种规规格格的的成成品品分分别别为为、 、 块块问问各各截截这这两两种种钢钢板板多多少少张张可可得得所所需需三三种种规规格格成成品品且且使使用用钢钢板板张张数数量量最最小小27x,yx yxyxyxyN设设需需截截第第一一种种钢钢板板 张张 第第二二种种钢钢板板 张张, ,依依题题意意有有2 +152 +15+218+218+ +解解3 3、 000395573955395Zxy,l : xy,lx yxyA,Zxyx y,A,xy,xy,A,. 目目标标函函数数如如图图作作出出可可行行域域作作直直线线将将 平平移移到到经经过过直直线线2 2 + + = =1 15 5与与 + +3 3 = =

23、2 27 7的的交交点点 时时2 2 + + = =1 15 51 18 8取取得得最最小小值值 由由方方程程组组得得+ +3 3 = =2 27 75 51 18 8此此时时但但与与都都不不是是整整数数5 51 18 8所所以以点点不不是是最最优优解解5 55751212minxyxy,Z.: 经经过过可可行行域域内内的的整整点点且且与与直直线线距距离离最最近近的的直直线线当当它它经经过过可可行行域域内内的的点点(3,9)(3,9)和和(4,8)(4,8)时时, ,答答：截截取取钢钢板板有有两两种种截截法法 第第一一种种截截法法是是截截第第一一种种钢钢板板3 3张张, ,第第二二种种钢钢板板

24、9 9张张; ;第第二二种种截截法法是是截截第第一一种种钢钢板板4 4张张, ,第第二二种种钢钢板板8 8张张. .两两种种方方法法最最少少要要截截两两种种钢钢板板共共1212张张. . 练习练习2.某实验室需购某种化工原料某实验室需购某种化工原料106千克千克.现现在市场上该原料有两种包装，一种是每袋在市场上该原料有两种包装，一种是每袋35千千克，价格为克，价格为140元；另一种是每袋元；另一种是每袋24千克，价千克，价格为格为120元元.在满足需要的条件下，最少需花费在满足需要的条件下，最少需花费多少元？多少元？ 练习练习3.某工厂用某工厂用A、B两种配件生产甲，乙两种产品，两种配件生产甲

25、，乙两种产品，每生产一件甲种产品使用每生产一件甲种产品使用4个个A配件，耗时配件，耗时1h；每生产；每生产一件乙产品使用一件乙产品使用4个个B配件耗时配件耗时2h。该厂每天最多可从。该厂每天最多可从配件厂获得配件厂获得16个个A配件和配件和12个个B配件，按每天工作配件，按每天工作8h计算，该厂所有可能的日生产安排是什么？计算，该厂所有可能的日生产安排是什么？问问:若生产一件甲若生产一件甲产品获利产品获利2万元万元,生产一件乙产品获生产一件乙产品获利利3万元万元,采用哪种采用哪种日生产安排获得的日生产安排获得的利润最大利润最大?yx4843oM在可行域内找出最优解、线性规划整数解在可行域内找出

26、最优解、线性规划整数解问题的一般方法是：问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然后在可行域内适当，然后在可行域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网格、找整点、平移直线、找出整数最优解。格、找整点、平移直线、找出整数最优解。