3.5.2简单线性规划.ppt

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

1、1一一.复习回顾复习回顾1.在同一坐标系上作出下列直线在同一坐标系上作出下列直线:2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7xYo2.作出下列不等式组的所表示的平面区域作出下列不等式组的所表示的平面区域255x=1x-4y+3=03x+5y-25=01ABCC:(1.00,4.40)A:(5.00,2.00)B:(1.00,1.00)Oxy问题问题1 1：x 有无最大（小）值？有无最大（小）值？问题问题2 2：y 有无最大（小）值？有无最大（小）值？问题问题3 3：2 2x+y 有无最大（小）值？有无最大（小）值？2.作出下列不作出下列不等式组的所表等式组的所表示的

2、平面区域示的平面区域3二二.提出问题提出问题把上面两个问题综合起来把上面两个问题综合起来:设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.455x=1x-4y+3=03x+5y-25=01ABCC:(1.00,4.40)A:(5.00,2.00)B:(1.00,1.00)Oxy直线直线L L越往右平移越往右平移,t,t随之增大随之增大.以经过点以经过点A(5,2)A(5,2)的的直线所对应的直线所对应的t t值值最大最大;经过点经过点B(1,1)B(1,1)的直线所对的直线所对应的应的t t值最小值最小.5线性规划问题：设z=2x+y，式中变量满足下列条件：求z的最

3、大值与最小值。目标函数目标函数（线性目标函数）（线性目标函数）线性约束条件象这样关象这样关于于x,yx,y一一次不等式次不等式组的约束组的约束条件称为条件称为线性约束线性约束条件条件Z=2x+yZ=2x+y称为目标函数称为目标函数,(,(因因这里目标函数为关于这里目标函数为关于x,yx,y的的一次式一次式,又称为又称为线性目标函线性目标函数数6线性规划线性规划：线性规划：求线性目标函数在线性约束条件下的最求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题大值或最小值的问题，统称为线性规划问题 可行解可行解：满足线性约束条满足线性约束条件的解件的解(x，y)叫可行解；叫可行

4、解；可行域可行域：由所有可行解组由所有可行解组成的集合叫做可行域；成的集合叫做可行域；最优解最优解：使目标函数取得使目标函数取得最大或最小值的可行解叫最大或最小值的可行解叫线性规划问题的最优解。线性规划问题的最优解。可行域可行域2x+y=32x+y=12(1,1)(5,2)7设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.线性目线性目标函数标函数线性约线性约束条件束条件线性规线性规划问题划问题任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域所有的所有的最优解最优解目标函数所表目标函数所表示的几何意义示的几何意义在在y轴上轴上的截距

5、。的截距。8A(-1,-1)B(2,-1)C(0.5,0.5)xyo图中三角形区域可用一次不等式组图中三角形区域可用一次不等式组表示，若设表示，若设z=2x+y,式中式中变量变量x、y满满足上面的一次不等式组，则此一次足上面的一次不等式组，则此一次不等式组叫做变量不等式组叫做变量x、y的的_，z=2x+y叫做叫做_;满足条件的解叫做满足条件的解叫做_;其中最优解为其中最优解为_,象这象这样样求目标函数在约束条件下的最值问题求目标函数在约束条件下的最值问题称为称为_.线性约束条件线性约束条件线性目标函数线性目标函数可行解可行解(2,-1)、(-1,-1)线性规划问题线性规划问题回答问题回答问题9

6、线性规划例例1 解下列线性规划问题：解下列线性规划问题：求求z=2x+y的最大值和最小值，使式中的最大值和最小值，使式中x、y满足下满足下列条件：列条件：解线性规划问题的一般步骤：解线性规划问题的一般步骤：第一步：在平面直角坐标系中作出可行域；第一步：在平面直角坐标系中作出可行域；第二步：在可行域内找到最优解所对应的点；第二步：在可行域内找到最优解所对应的点；第三步：解方程的最优解，从而求出目标函数第三步：解方程的最优解，从而求出目标函数的最大值或最小值。的最大值或最小值。探索结论2x+y=02x+y=-32x+y=3答案答案：当当x=-1,y=-1时，时，z=2x+y有最小值有最小值3.当当

7、x=2,y=-1时，时，z=2x+y有最大值有最大值3.10线性规划练习练习:解下列线性规划问题：解下列线性规划问题：求求z=300 x+900y的最大值和最小的最大值和最小值，使式中值，使式中x、y满足下列条件：满足下列条件：探索结论x+3y=0300 x+900y=0300 x+900y=112500答案答案：当当x=0,y=0时，时，z=300 x+900y有最小值有最小值0.当当x=0,y=125时，时，z=300 x+900y有最大值有最大值112500.11 问题：某工厂计划生产甲、乙两种产问题：某工厂计划生产甲、乙两种产品，这两种产品都需要两种原料。生产品，这两种产品都需要两种原

8、料。生产甲产品甲产品1工时需要工时需要A原料原料3kg，B原料原料1kg；生产；生产乙产品乙产品1工时需要工时需要A原料原料2kg，B原原料料2kg。现有。现有A原料原料1200kg，B原料原料800kg。如果生产甲产品每工时的如果生产甲产品每工时的平均利润是平均利润是30元元，生产乙产品每工时的，生产乙产品每工时的平均利润是平均利润是40元，元，问同时生产两种产品，各多少工时问同时生产两种产品，各多少工时能使能使利润的总额最大利润的总额最大？最大利润是多少？最大利润是多少？12解：依题意，可列表如下：解：依题意，可列表如下：产产品品原料原料A数量数量(kg)原料原料B数量数量(kg)利利润润

9、(元元)生生产产甲种甲种产产品品1工工时时3130生生产产乙种乙种产产品品1工工时时2240限限额额数量数量1200800 设计划生产甲种产品设计划生产甲种产品x工时，计划生产乙工时，计划生产乙种产品种产品y工时，工时，13则获得的利润总额为则获得的利润总额为f=30 x+40y。其中其中x,y满足下列条件满足下列条件：于是问题转化为，在于是问题转化为，在x，y满足条件满足条件的情况下，求式子的情况下，求式子30 x+40y的的最大值最大值。14画出不等式组画出不等式组表示的表示的平面区域平面区域OABC。15画出不等式组画出不等式组表示的表示的平面区域平面区域OABC。问题又转化为，在不等式

10、组问题又转化为，在不等式组表示的平表示的平面区域内面区域内找一点找一点，把它的坐标代入式子，把它的坐标代入式子30 x+40y时，使该式时，使该式取得取得最大值最大值。16 令令30 x+40y=0，则此方程表示通过原点，则此方程表示通过原点的一条直线，记为的一条直线，记为l0，易知：在区域，易知：在区域OABC内有内有 30 x+40y0。考察这个区域内任意一点考察这个区域内任意一点P(x,y)到到l0距离距离 于是于是17 这就是说，点这就是说，点P(x，y)到直线到直线l0的的距离距离d越大，式子越大，式子30 x+40y的值也越大的值也越大。因此问题因此问题转化转化为：在不等式组为：在

11、不等式组表示表示的平面区域内找一点，使它到直线的平面区域内找一点，使它到直线l0的距的距离最大。离最大。为在区域为在区域OABC内精确地找到这一点，内精确地找到这一点，我们平移直线我们平移直线l0的位置到的位置到l，使，使l通过通过OABC内的某点，内的某点，18 且且OABC内的其它各点都在内的其它各点都在l的的包含直线包含直线l0的同一侧的同一侧，很容易证明该点到，很容易证明该点到l0的距离最的距离最大，用此法区域大，用此法区域OABC内的点内的点B为所求。为所求。解方程组解方程组 得点得点B的坐标为的坐标为(200，300)。19将将x=200，y=300代入式子代入式子:30 x+40

12、y，得，得Fmax=30200+40300=18000.答：用答：用200工时生产甲种产品，用工时生产甲种产品，用300工工时生产乙种产品，能获得利润时生产乙种产品，能获得利润18000元，元，此时利润总额最大。此时利润总额最大。20令令z=30 x+40y,你有其他方法求最大值吗你有其他方法求最大值吗?自学课本自学课本90页问题页问题21 在上述问题中，我们把要求最大值或在上述问题中，我们把要求最大值或最小值的最小值的函数函数f=30 x+40y叫做叫做目标函数目标函数，目标函数中的变量所要满足的目标函数中的变量所要满足的不等式不等式组组称为称为约束条件约束条件。如果如果目标函数目标函数是关

13、于变量的是关于变量的一次函数一次函数，则称为则称为线性目标函数线性目标函数，如果，如果约束条件约束条件是关是关于变量的于变量的一次不等式一次不等式（或等式），则称为（或等式），则称为线性约束条件线性约束条件。22 在线性约束条件下求线性目标函数的最在线性约束条件下求线性目标函数的最大值或最小值问题，称为大值或最小值问题，称为线性规划问题线性规划问题。使目标函数达到最大值或最小值的使目标函数达到最大值或最小值的点的坐点的坐标标，称为问题的，称为问题的最优解最优解。一般地，满足线性约束条件的一般地，满足线性约束条件的解解(x，y)叫做叫做可行解可行解，由所有可行解组成的，由所有可行解组成的集合集合

14、叫叫做做可行域可行域。23运用平移法运用平移法总结总结解线性规划应用题的一般步骤解线性规划应用题的一般步骤?列出约束条件列出约束条件,建立目标函数建立目标函数注意注意：另外：另外,建模时要考虑数据、变量、建模时要考虑数据、变量、不等式的实际含义及计量单位的统一不等式的实际含义及计量单位的统一.1 1、设、设设出所求的未知量设出所求的未知量2 2、列、列3 3、画、画画出可行域画出可行域4、移移6 6、答、答理清题意，列出表格理清题意，列出表格作出直线作出直线L：Ax+By=0,作一组与作一组与L 平行的直线平行的直线Ax+By=z，经过可行域，经过可行域,找出与可行域有公共点且纵截距最大找出与

15、可行域有公共点且纵截距最大或最小的直线或最小的直线(准确作图，准确计算准确作图，准确计算)5 5、求、求通过解方程组求出最优解通过解方程组求出最优解24例例1下表给出甲、乙、丙三种食物中维下表给出甲、乙、丙三种食物中维生素生素A、B的含量及单价：的含量及单价：甲甲乙乙丙丙维维生素生素A(单单位位/千克千克)400600400维维生素生素B(单单位位/千克千克)800200400单单价价(元元/千克千克)765营养师想购买这三种食品共营养师想购买这三种食品共10千克，使它千克，使它们所含的维生素们所含的维生素A不少于不少于4400单位，维生单位，维生素素B不少于不少于4800单位，而且要使付出的

16、金单位，而且要使付出的金额最低，这三种食物应各购买多少千克？额最低，这三种食物应各购买多少千克？25解：设购买甲种食物解：设购买甲种食物x千克，乙种食物千克，乙种食物y千克，则购买丙种食物千克，则购买丙种食物(10 xy)千克，千克，又设总支出为又设总支出为z元，由题意得元，由题意得 z=7x+6y+5(10 xy)，化简得化简得 z=2x+y+50，x，y应满足的应满足的约束条件约束条件 26化简得化简得 根据上述不等式组，作根据上述不等式组，作出表示可行域的平面区出表示可行域的平面区域，如图阴影部分所示。域，如图阴影部分所示。27化简得化简得 根据上述不等式组，作根据上述不等式组，作出表示

17、可行域的平面区出表示可行域的平面区域，如图阴影部分所示。域，如图阴影部分所示。28画直线画直线l0：2x+y=0，平行移动，平行移动l0到直线到直线l的的位置，使位置，使l过可行域中的某点，并且可行过可行域中的某点，并且可行域内的其它各点域内的其它各点都在都在l的不包含直线的不包含直线l0的另的另外一侧。外一侧。29画直线画直线l0：2x+y=0，平行移动，平行移动l0到直线到直线l的的位置，使位置，使l过可行域中的某点，并且可行过可行域中的某点，并且可行域内的其它各点域内的其它各点都在都在l的不包含直线的不包含直线l0的另的另外一侧外一侧.该点到直线该点到直线l0的距离最的距离最小，则这一点

18、的坐标使小，则这一点的坐标使目标函数取最小值目标函数取最小值.3031 容易看出，点容易看出，点M符合上述条件，点符合上述条件，点M是是直线直线y=2与直线与直线2xy=4的交点。的交点。解方程组解方程组 得点得点M(3，2)。因此，当因此，当x=3，y=2时，时，z取得最小值取得最小值z=23+2+50=58.此时，此时，10 xy=5.答：购买甲食物答：购买甲食物3千克，乙食物千克，乙食物2千克，千克，丙食物丙食物5千克，付出的金额最低为千克，付出的金额最低为58元。元。32例例2某货运公司拟用集装箱托运甲、乙某货运公司拟用集装箱托运甲、乙两种货物，一个大集装箱能够所托运的货两种货物，一个

19、大集装箱能够所托运的货物的总体积不能超过物的总体积不能超过24m3，总重量不能低，总重量不能低于于650千克。甲、乙两种货物每袋的体积、千克。甲、乙两种货物每袋的体积、重量和可获得的利润，列表如下：重量和可获得的利润，列表如下：货货物物每袋体每袋体积积(单单位：位：m3)每袋重量每袋重量(单单位：百千克位：百千克)每袋利每袋利润润(单单位：百元位：百元)甲甲5120乙乙42.510问：在一个大集装箱内，这两种货物各装问：在一个大集装箱内，这两种货物各装多少袋多少袋(不一定都是整袋不一定都是整袋)时，可获得最大时，可获得最大利润？利润？33解：设托运甲种货物解：设托运甲种货物x袋，乙种货物袋，乙

20、种货物y袋，袋，获得利润获得利润z百元。百元。则则 z=20 x+10y。依题意可得关于依题意可得关于x，y的的约束条件约束条件 34 根据上述不等式组，作出表示可行域的根据上述不等式组，作出表示可行域的平面区域，如图阴影部分所示。平面区域，如图阴影部分所示。画直线画直线l0：20 x+10y=0，平行移动，平行移动l0到直线到直线l的的位置，使位置，使l过可行域中过可行域中的某点，并且可行域内的某点，并且可行域内的其它各点都在的其它各点都在l的包的包含直线含直线l0的的同一侧同一侧。3536 该点到直线该点到直线l0的距离最大，则这一点的距离最大，则这一点的坐标使的坐标使目标函数取最大值目标

21、函数取最大值。容易看出，容易看出，点点M符合上述条件符合上述条件，点，点M是是直线直线2x+5y=13与直线与直线5x+4y=24的交点。的交点。解方程组解方程组 得点得点M(4，1)。因此当因此当x=4，y=1时，时，z取得最大值，此取得最大值，此时时zmax=204+101=90.37答：在一个大集装箱内装甲种货物答：在一个大集装箱内装甲种货物4袋，袋，乙种货物乙种货物1袋，可获得最大利润袋，可获得最大利润9000元。元。38练习一课本94页1（2）求z=3x+5y的最大值和最小值，使x，y满足约束条件39练习一课本94页1（2）40551Oxy1-15x+3y=15X-5y=3y=x+1

22、A(-2,-1)B(3/2,5/2)练习一:课本94页1（2）41总结结论结论1：线性目标函数的最大值、最小值线性目标函数的最大值、最小值一般在可行域的一般在可行域的 处取得处取得.如：上如：上例例.顶点42变式一求求z=5x+3y的最大值的最大值和最小值，使和最小值，使x，y满满足约束条件足约束条件43总结结论2：线性目标函数的最大值、最小值一线性目标函数的最大值、最小值一般在可行域的般在可行域的 上取得，即满足条件上取得，即满足条件的最优解有的最优解有 .如：变式一如：变式一；边界边界无数多个无数多个44变式二求z=3x5y的最大值和最小值，使x，y满足约束条件45总结结论3：求线性目标函

23、数的最优解，要注意求线性目标函数的最优解，要注意分析线性目标函数所表示的几何含义。分析线性目标函数所表示的几何含义。46变式三求z=3x5y的最大值和最小值，使x，y满足约束条件47小结1.线性规划问题的有关概念；线性规划问题的有关概念；2.解线性规划问题的一般步骤解线性规划问题的一般步骤;3.解线性规划应用题的一般步骤解线性规划应用题的一般步骤4.几个结论几个结论、注意事项（画图要准确）、注意事项（画图要准确）(1)(1)线性目标函数的最大（小）值一般在可行域的线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得顶点处取得，也可能在边界处取得.(2)(2)求线性目标函数的最优解，要注意分析线性目求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义标函数所表示的几何意义在在y y轴上的截距或其相反数轴上的截距或其相反数.48