简单线性规划3.ppt

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

1、xyo可行域上的最优解可行域上的最优解问题问题1:某工厂用某工厂用A,B两种配件生产甲两种配件生产甲,乙两种产品乙两种产品,每生产一件甲种产品使用每生产一件甲种产品使用4个个A配件耗时配件耗时1h,每生产一件乙种产品使用每生产一件乙种产品使用4个个B配件耗时配件耗时2h,该厂每天最多可从配件厂获得该厂每天最多可从配件厂获得16个个A配件和配件和12个个B配件配件,按每天工作按每天工作8小时小时计算计算,该厂所有该厂所有可能的日生产安排是什么可能的日生产安排是什么?若生产若生产1件甲种产品获利件甲种产品获利2万元万元,生产生产1 件乙件乙种产品获利种产品获利3万元万元,采用哪种生产安排利润最大采

2、用哪种生产安排利润最大?32利润利润(万元万元)821所需时间所需时间1240B种配件种配件1604A种配件种配件资源限额资源限额 乙产品乙产品 (1件件)甲产品甲产品 (1件件)产品产品消消 耗耗 量量资资 源源把问题把问题1的有关数据列表表示如下的有关数据列表表示如下:设甲设甲,乙两种产品分别生产乙两种产品分别生产x,y件件,0 xy4348将上面不等式组表示成平面上的区域将上面不等式组表示成平面上的区域,区域内区域内所有坐标为整数的点所有坐标为整数的点P(x,y),安排生产任务安排生产任务x,y都是有意义的都是有意义的.设甲设甲,乙两种产品分别生产乙两种产品分别生产x,y件件,由己知条件

3、可得由己知条件可得:问题：问题：求利润求利润2x+3y的最大值的最大值.若设利润为若设利润为z,则则z=2x+3y,这样上述问题转化为这样上述问题转化为:当当x,y在满足上述约束条件时在满足上述约束条件时,z的最大值为多少的最大值为多少?当点当点P在可允许的取值范围变化时在可允许的取值范围变化时,0 xy4348M（4，2）问题：问题：求利润求利润z=2x+3y的最大值的最大值.象这样关于象这样关于x,yx,y一次不等一次不等式组的约束条件称为式组的约束条件称为线性约束线性约束条件条件Z=2x+3yZ=2x+3y称为目标函数称为目标函数,因这里因这里目标函数为关于目标函数为关于x,yx,y的一

4、次式的一次式,又又称为称为线性目标函数线性目标函数 在线性约束下求线性目标函数在线性约束下求线性目标函数的最值问题的最值问题,统称为统称为线性规划线性规划问题问题满足线性约束的解满足线性约束的解(x,yx,y)叫做叫做可行解可行解,所有可行解组成的集合叫做所有可行解组成的集合叫做可行域可行域使目标函数使目标函数取得最值取得最值的可行解叫做这个的可行解叫做这个问题的问题的最优解最优解变式：变式：若生产一件甲产品获利若生产一件甲产品获利1万元万元，生产一件乙产品获利生产一件乙产品获利3万元万元，采用哪种采用哪种生产安排利润最大？生产安排利润最大？0 xy4348N N（2 2，3 3）变式：变式：

5、求利润求利润z=x+3y的最大值的最大值.练习练习解下列线性规划问题：解下列线性规划问题：1、求、求z=2x+y的最大值，使式中的的最大值，使式中的x、y满足约束条件：满足约束条件：xOyABCy=x x+y=1y=-12x+y=0B:(-1,-1)C:(2,-1)Zmin=-3Zmax=3 目标函数：目标函数：Z=2x+y解线性规划问题的步骤：解线性规划问题的步骤：（2 2）移：在线性目标函数所表示的一组平行线中，）移：在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线大或最小的直线 ；;（3 3）求：通

6、过解方程组求出最优解；）求：通过解方程组求出最优解；（4 4）答：作出答案。）答：作出答案。（1 1）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；体验体验:二、二、最优解最优解一般在可行域的一般在可行域的顶点顶点处取得处取得三、在哪个顶点取得不仅与三、在哪个顶点取得不仅与B B的符号有关，的符号有关，而且还与直线而且还与直线 Z=Z=Ax+ByAx+By的的斜率斜率有关有关一、一、先定先定可行域和平移方向，再找最优解。可行域和平移方向，再找最优解。例例2 2、一个化肥厂生产甲、乙两种混合肥料，生产一个化肥厂生产甲、乙两种混合肥料，生产1 1车车皮甲种肥料的主要原料

7、是磷酸盐皮甲种肥料的主要原料是磷酸盐4t4t、硝酸盐、硝酸盐18t18t；生产；生产1 1车皮乙种肥料需要的主要原料是磷酸盐车皮乙种肥料需要的主要原料是磷酸盐1t1t、硝酸盐、硝酸盐15t15t。现库存磷酸盐。现库存磷酸盐10t10t、硝酸盐、硝酸盐66t66t，在此基础上生，在此基础上生产这两种混合肥料。列出满足生产条件的数学关系式，产这两种混合肥料。列出满足生产条件的数学关系式，并画出相应的平面区域。并计算生产甲、乙两种肥料并画出相应的平面区域。并计算生产甲、乙两种肥料各多少车皮，能够产生最大的利润？各多少车皮，能够产生最大的利润？解：设解：设x x、y y分别为计划生产甲、乙两种混合分别

8、为计划生产甲、乙两种混合 肥料的车皮数，于是满足以下条件：肥料的车皮数，于是满足以下条件：xyo解：解：设生产甲种肥料设生产甲种肥料x x车皮、乙种肥料车皮、乙种肥料y y车皮，车皮，能够产生利润能够产生利润Z Z万元。目标函数为万元。目标函数为Z Zx x0.5y0.5y，可行域如图可行域如图：把把Z Zx x0.5y0.5y变形变形为为y y2x2x2z2z，它表示斜率，它表示斜率为为2 2，在，在y y轴上的截距为轴上的截距为2z2z的一组直线系。的一组直线系。xyo由图可以看出，当直线经过由图可以看出，当直线经过可行域上的点可行域上的点MM时，时，截距截距2z2z最大，即最大，即z z

9、最大。最大。答：答：生产甲种、乙种肥料各生产甲种、乙种肥料各 2 2车皮，能够产生最大利车皮，能够产生最大利 润，最大利润为润，最大利润为3 3万元。万元。M容易求得容易求得MM（2 2，2 2），），则则Z Zmaxmax3 3练习题练习题某厂拟生产甲、乙两种适销产品，每件销售收入分别为某厂拟生产甲、乙两种适销产品，每件销售收入分别为30003000元、元、20002000元，甲、乙产品都需要在元，甲、乙产品都需要在A A、B B两种设两种设备上加工，在每台备上加工，在每台A A、B B上加工上加工1 1件甲所需工时分别为件甲所需工时分别为1h1h、2h2h，加工，加工1 1件乙所需工时分别

10、为件乙所需工时分别为2h,1h.A2h,1h.A、B B两种设备两种设备每月有效使用台时数分别为每月有效使用台时数分别为400h400h和和500h500h。如何安排生。如何安排生产可使收入最大？产可使收入最大？解：解：设每月生产甲产品设每月生产甲产品x x件，生产乙产品件，生产乙产品y y件，每月收件，每月收入为入为Z Z千元，目标函数为千元，目标函数为Z Z3x3x2y2y，满足的条件是，满足的条件是 Z Z 3x3x2y2y 变形为变形为它表示斜率为它表示斜率为 的直线系，的直线系，Z Z与这条直线的截距有关。与这条直线的截距有关。XYO400200250500 当直线经过点当直线经过点

11、MM时，截距最大，时，截距最大，Z Z最大。最大。M解方程组解方程组可得可得MM（200200，100100）Z Z 的最大值的最大值ZmaxZmax 3x3x2y2y800800（千元）（千元）故生产甲产品故生产甲产品200200件，件，乙产品乙产品100100件，收入最大，件，收入最大，为为8080万元。万元。不等式组不等式组 表示的平表示的平面区域内面区域内的的整数点整数点共有（共有（）个）个巩固练习巩固练习:1 2 3 4 xy432104x+3y=12例例1 1、要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A A、B B、C C三三种种规规格格，每每张张钢钢板板可可同

12、同时时截截得得三三种种规格的小钢板的块数如下表所示规格的小钢板的块数如下表所示 ：规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A A规格规格B B规格规格C C规格规格2 21 12 21 13 31 1今需要今需要A,B,CA,B,C三种规格的成品分别为三种规格的成品分别为1515，1818，2727块，问各截这两种钢板多少张可得所需块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。三种规格成品，且使所用钢板张数最少。解：设需截第一种钢板解：设需截第一种钢板x x张、第二种钢板张、第二种钢板y y张，可得张，可得x0y2x+y=15x+3y=2

13、7x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xN*y0 yN*经经过过可可行行域域内内的的整整点点B(3,9)和和C(4,8)且且和和原原点点距距离离最近的直线是最近的直线是x+y=12，它们是最优解它们是最优解.答答:(略略)作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z=z=x+yx+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A A时时z=z=x+yx+y=11.4=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向

14、上平移继续向上平移,例例3:某某工工厂厂生生产产甲甲、乙乙两两种种产产品品.已已知知生生产产甲甲种种产产品品1t需需消消耗耗A种种矿矿石石10t、B种种矿矿石石5t、煤煤4t；生生产产乙乙种种产产品品1吨吨需需消消耗耗A种种矿矿石石4t、B种种矿矿石石4t、煤煤9t.每每1t甲甲种种产产品品的的利利润润是是600元元,每每1t乙乙种种产产品品的的利利润润是是1000元元.工工厂厂在在生生产产这这两两种种产产品品的的计计划划中中要要求求消消耗耗A种种矿矿石石不不超超过过300t、消消耗耗B种种矿矿石石不不超超过过200t、消消耗耗煤煤不不超超过过360t.甲甲、乙乙两两种种产产品品应应各各生生产

15、产多多少少(精确到精确到0.1t),能使利润总额达到最大能使利润总额达到最大?返回返回 甲产品甲产品 （1t）乙产品乙产品 （1t）资源限额资源限额 （t）A种矿石（种矿石（t）B种矿石（种矿石（t）煤（煤（t）利润（元）利润（元）产品产品消耗量消耗量资源资源列表：列表：51046004491000300200360设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x t、yt,利润总额为利润总额为z元元返回返回 甲产品甲产品 （1t）乙产品乙产品 （1t）资源限额资源限额 （t）A种矿石（种矿石（t）B种矿石（种矿石（t）煤（煤（t）利润（元）利润（元）产品产品消耗量消耗量资源资源列表：

16、列表：51046004491000300200360把题中限制条件进行把题中限制条件进行转化：转化：约束条件约束条件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.目标函数：目标函数：设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x t、yt,利润总额为利润总额为z元元xtyt解解:设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x t、yt,利润总额为利润总额为z元元,那么那么 10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.作出以上不等式组所表示的可行域作出以上不等式组所表示的可行域作作出

17、出一一组组平平行行直直线线 600 x+1000y=t，解得交点解得交点M的坐标为的坐标为(12.4,34.4)5x+4y=200 4x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:应生产甲产品约应生产甲产品约12.4吨，乙产品吨，乙产品34.4吨，能使利润总额达到最大。吨，能使利润总额达到最大。(12.4,34.4)返回返回经经过过可可行行域域上上的的点点M时时,目目标标函函数数在在y轴上截距最大轴上截距最大.9030 0 xy10 201075405040此时此时z=600 x+1000y取得最大值取得最大值.咖啡馆配制两种饮

18、料甲种饮料每杯含奶粉咖啡馆配制两种饮料甲种饮料每杯含奶粉9g、咖啡、咖啡4g、糖糖3g,乙种饮料每杯含奶粉乙种饮料每杯含奶粉4g、咖啡、咖啡5g、糖、糖10g已知每天已知每天原料的使用限额为奶粉原料的使用限额为奶粉3600g，咖啡，咖啡2000g糖糖3000g,如果如果甲种饮料每杯能获利甲种饮料每杯能获利0.7元，乙种饮料每杯能获利元，乙种饮料每杯能获利1.2元，每元，每天在原料的使用限额内饮料能全部售出，每天应配制两种天在原料的使用限额内饮料能全部售出，每天应配制两种饮料各多少杯能获利最大？饮料各多少杯能获利最大？解：将已知数据列为下表：解：将已知数据列为下表：消耗量消耗量资源资源甲产品甲产

19、品（1 杯）杯）乙产品乙产品(1杯杯)资源限额资源限额（g）奶粉奶粉（g g）9 94 436003600咖啡咖啡(g)(g)4 45 520002000糖糖(g)(g)3 3101030003000利润（元）利润（元）0.70.71.21.2产品产品设每天应配制甲种饮料设每天应配制甲种饮料x x杯，乙种饮料杯，乙种饮料y y杯，则杯，则作出可行域：作出可行域：目标函数为：目标函数为：z=0.7x+1.2yz=0.7x+1.2y作直线作直线l:0.7x+1.2y=0l:0.7x+1.2y=0，把直线把直线l l向右上方平移至向右上方平移至l l1 1的位置时，的位置时，直直线线经经过过可可行行

20、域域上上的的点点C C，且且与与原原点点距距离最大，离最大，此时此时z=0.7x+1.2yz=0.7x+1.2y取最大值取最大值解方程组解方程组 得点得点C C的坐标为（的坐标为（200200，240240）_0_ 9 x+4 y=3600_ C(200,240)_ 4 x+5 y=2000_ 3 x+10 y=3000_ 7 x+12 y=0_ 400_ 400_ 300_ 500_ 1000_ 900_ 0_ x_ yabO-4 -3 -2 -1 1 2 3 44 3 2 1 1 2 3 4-例例2、求、求z=4a2b在约束条件在约束条件1 ab 2,2 a+b 4下的最小值与最大值下的最

21、小值与最大值.ab=1ab=2a+b=4a+b=24a2b=0AC解解:作出可行域作出可行域(如右图如右图).作直线作直线:4a2b=0.把直线平移把直线平移,使其与可使其与可行域相交行域相交.当直线与可当直线与可行域分别相交于行域分别相交于A,C两点时两点时,所对应的所对应的z分分别最小与最大别最小与最大.例例2、求、求z=4a2b在约束条件在约束条件1 ab 2,2 a+b 4下的最小值与最大值下的最小值与最大值.abO-4 -3 -2 -1 1 2 3 44 3 2 1 1 2 3 4-ab=1ab=2a+b=4a+b=24a2b=0AC得得A(,);1232由由ab=1a+b=2得得 C(3,1).由由ab=2a+b=41232zmin=4 2 =1,zmax=4 32 1=10.