《简单线性规划ppt课件习题课》由会员分享,可在线阅读,更多相关《简单线性规划ppt课件习题课(40页珍藏版)》请在金锄头文库上搜索。
1、知识要点知识要点1.1.二元一次不等式(组)表示平面区域二元一次不等式(组)表示平面区域一一.线性规划线性规划(3)(3)画法画法: :画二元一次不等式画二元一次不等式AxAx+ +ByBy+ +C C 00或或AxAx+ +ByBy+ +C C 0 0 表示的平面区域常采用表示的平面区域常采用“直线定界,特殊点定域直线定界,特殊点定域”的的方法。当方法。当C0C0时,常把原点作为此特殊点。有等号画时,常把原点作为此特殊点。有等号画实线(包括边界)实线(包括边界), ,无等号画虚线(不包括边界)。无等号画虚线(不包括边界)。(2)(2)判断方法判断方法: :由于对在直线由于对在直线AxAx+
2、+ByBy+ +C C=0=0同一侧的所有点同一侧的所有点(x(x,y)y),把它的坐标(,把它的坐标(x x,y)y)代入代入AxAx+ +ByBy+ +C C,所得到实数,所得到实数的符号都相同,所以的符号都相同,所以只需在此直线的某一侧取一特殊点只需在此直线的某一侧取一特殊点(x x0 0, ,y y0 0) ),从,从AxAx0 0+ +ByBy0 0+ +C C 的正负即可判断的正负即可判断AxAx+ +ByBy+ +C C0 0表表示直线哪一侧的平面区域示直线哪一侧的平面区域. . (特殊地,当(特殊地,当C C00时,常把时,常把原点原点作为此特殊点)作为此特殊点)(1)线性约束
3、条件线性约束条件:由由x,y的一次不等式(或方程)组成的不等式组。的一次不等式(或方程)组成的不等式组。(2)目标函数目标函数:要求最大值(或最小值)的函数。:要求最大值(或最小值)的函数。(3)线性目标函数线性目标函数:如果:如果目标函数目标函数是是x,y的一次解的一次解析式,则目标函数又称为线性目标函数。析式,则目标函数又称为线性目标函数。2.线性规划(4)线性规划线性规划:求线性目标函数在线性约束条件下的求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题最大值或最小值的问题,统称为线性规划问题 (5)可行解可行解 :满足线性约束条件的解满足线性约束条件的解(x,y)
4、叫可叫可 行解;行解; (6)可行域可行域 :由所有可行解组成的集合叫做可行域;由所有可行解组成的集合叫做可行域; (7)最优解最优解 :使目标函数取得最大或最小值的可行解使目标函数取得最大或最小值的可行解 叫线性规划问题的最优解。叫线性规划问题的最优解。 (2) (2)移:在线性目标函数所表示的一组平行线中,移:在线性目标函数所表示的一组平行线中,利用平移的方法找出与可行域有公共点且纵截距最利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线;大或最小的直线; (3)(3)求:通过解方程组求出最优解;求:通过解方程组求出最优解; (4)(4)答:作出答案。答:作出答案。(1)(1)画:
5、画出线性约束条件所表示的可行域;画:画出线性约束条件所表示的可行域;3.3.用图解法解线性规划问题的步骤用图解法解线性规划问题的步骤典型题例典型题例:题型题型1.1.求目标函数的最值问题求目标函数的最值问题D例例1B变式练习变式练习:C若求取值范围呢?若求取值范围呢?DC例例2-6例例.题型题型2.2.已知目标函数的最值,求参数的取值问题已知目标函数的最值,求参数的取值问题AD1.变式练习变式练习2. 3.题型题型3.3.平面区域的面积问题平面区域的面积问题CA变式练习变式练习:BD4. 4. 在平面直角坐标系在平面直角坐标系xOy中,已知平面区域中,已知平面区域A=(x,y)|x+y1,且且
6、x0,y0,求平面区域求平面区域B=(x+y,x- -y)|(x,y)A的面积?的面积?画出关于画出关于u,v的可行域的可行域解析令u=x+y,v=x-y,方法规律小结方法规律小结1、线性规划问题是数形结合思想的重要体现,、线性规划问题是数形结合思想的重要体现,通过画简便直观图求最值。通过画简便直观图求最值。2、常见目标函数有、常见目标函数有截距型截距型 ,距离距离型型 ,斜率型,斜率型 几几种,截距型要注意种,截距型要注意y的系数的正负号。的系数的正负号。3、最优解一般在可行域的顶点或边界处取得,、最优解一般在可行域的顶点或边界处取得,要注意边界的虚实。要注意边界的虚实。4、解选择、填空题常
7、常可先求可行域的顶点,、解选择、填空题常常可先求可行域的顶点,再代人目标函数验算即可。再代人目标函数验算即可。 C巩固练习巩固练习3.B4.二是二是给定一项任务,问怎样统筹安排,能给定一项任务,问怎样统筹安排,能使完成这项任务的人力、物力资源最小。使完成这项任务的人力、物力资源最小。一是一是给定一定数量的人力、物力资源,问给定一定数量的人力、物力资源,问怎样安排运用这些资源,能使完成的任务怎样安排运用这些资源,能使完成的任务量最大,收到的效益最大。量最大,收到的效益最大。1.线性规划研究的两类重要实际问题:线性规划研究的两类重要实际问题:二二.线性规划的实际应用线性规划的实际应用2.解线性规划
8、应用问题的一般步骤解线性规划应用问题的一般步骤: 【例【例1】 某公司计划某公司计划2013年年0100200 300100200300400500yxlM 点评点评 画出可行域后,再把目标函数平行平移,要画出可行域后,再把目标函数平行平移,要比较斜率的大小,注意目标函数的意义比较斜率的大小,注意目标函数的意义.【练习【练习1】(】(2010广东文、理)广东文、理) 某营养师要为某个儿童预定午餐和晚餐某营养师要为某个儿童预定午餐和晚餐.已知一个已知一个单位的午餐含单位的午餐含12个单位的碳水化合物个单位的碳水化合物6个单位蛋白质个单位蛋白质和和6个单位的维生素个单位的维生素C;一个单位的晚餐含
9、;一个单位的晚餐含8个单位的个单位的碳水化合物,碳水化合物,6个单位的蛋白质和个单位的蛋白质和10个单位的维生素个单位的维生素C.另外,该儿童这两餐需要的营养中至少含另外,该儿童这两餐需要的营养中至少含64个单位的个单位的碳水化合物,碳水化合物,42个单位的蛋白质和个单位的蛋白质和54个单位的维生素个单位的维生素C.如果一个单位的午餐、晚餐的费用分别是如果一个单位的午餐、晚餐的费用分别是2.5元和元和4元,元,那么要满足上述的营养要求,并且花费最少,应当为该那么要满足上述的营养要求,并且花费最少,应当为该儿童分别预定多少个单位的午餐和晚餐?儿童分别预定多少个单位的午餐和晚餐? 作出可行域如图所
10、示:作出可行域如图所示: 变换目标函数:变换目标函数:x+y=73x+2y=16xy3x+5y=27A当目标函数经过点当目标函数经过点A时,时,z取得最小值取得最小值;由由x+ y =73 x+5 y =27解得点解得点A(4,3)即当即当x=4,y=3时,花费最少时,花费最少,为为z=2.5x+4y=2.54+43=22(元元)答:要满足营养要求,并且花费最少,答:要满足营养要求,并且花费最少,应当为儿童分别预订应当为儿童分别预订4个单位的午餐和个单位的午餐和3个单位的晚餐。个单位的晚餐。 规格类型规格类型钢板类型钢板类型 A规格规格 B规格规格 C规格规格第一种钢板第一种钢板 2 1 1第
11、二种钢板第二种钢板 1 2 3 练练习习2.某某实实验验室室需需购购某某种种化化工工原原料料106千千克克.现现在在市市场场上上该该原原料料有有两两种种包包装装,一一种种是是每每袋袋35千千克克,价价格格为为140元元;另另一一种种是是每每袋袋24千千克克,价价格格为为120元元.在在满满足足需需要要的的条条件件下下,最最少少需需花花费费多少元?多少元? 练习练习3.某工厂用某工厂用A、B两种配件生产甲,乙两种产品,两种配件生产甲,乙两种产品,每生产一件甲种产品使用每生产一件甲种产品使用4个个A配件,耗时配件,耗时1h;每生产;每生产一件乙产品使用一件乙产品使用4个个B配件耗时配件耗时2h。该
12、厂每天最多可从。该厂每天最多可从配件厂获得配件厂获得16个个A配件和配件和12个个B配件,按每天工作配件,按每天工作8h计算,该厂所有可能的日生产安排是什么?计算,该厂所有可能的日生产安排是什么?问问:若生产一件甲若生产一件甲产品获利产品获利2万元万元,生产一件乙产品获生产一件乙产品获利利3万元万元,采用哪种采用哪种日生产安排获得的日生产安排获得的利润最大利润最大?yx4843oM在可行域内找出最优解、线性规划整数解在可行域内找出最优解、线性规划整数解问题的一般方法是:问题的一般方法是:1.若区域若区域“顶点顶点”处恰好为整点,那么它就是最优解;处恰好为整点,那么它就是最优解;(在包括边界的情
13、况下)(在包括边界的情况下)2.若区域若区域“顶点顶点”不是整点或不包括边界时,应先求出不是整点或不包括边界时,应先求出该点坐标,并计算目标函数值该点坐标,并计算目标函数值Z,然后在可行域内适当,然后在可行域内适当放缩目标函数值,使它为整数,且与放缩目标函数值,使它为整数,且与Z最接近,在这条最接近,在这条对应的直线中,取可行域内整点,如果没有整点,继续对应的直线中,取可行域内整点,如果没有整点,继续放缩,直至取到整点为止。放缩,直至取到整点为止。3.在可行域内找整数解,一般采用平移找解法,即打网在可行域内找整数解,一般采用平移找解法,即打网格、找整点、平移直线、找出整数最优解。格、找整点、平移直线、找出整数最优解。