简单的线性规划问题绵竹中学2

《简单的线性规划问题绵竹中学2》由会员分享，可在线阅读，更多相关《简单的线性规划问题绵竹中学2（34页珍藏版）》请在装配图网上搜索。

1、xyo 2、确定步骤确定步骤：回顾回顾: :直线定界（注意虚、实线），直线定界（注意虚、实线），特殊点定域特殊点定域1、重要重要 结论结论：直线直线Ax+By+C=0同侧的所有点的坐标（同侧的所有点的坐标（x,y）代）代入入Ax+By+C，所得实数的符号相同。，所得实数的符号相同。二元一次不等式二元一次不等式Ax+By+C0表示直线表示直线Ax+By+C=0的某一侧所有点组成的平面区域，此的某一侧所有点组成的平面区域，此区域不包括边界，把边界画成区域不包括边界，把边界画成虚线虚线；不等式不等式Ax+By+C0表示平面区域时，此区域包表示平面区域时，此区域包括边界，把边界画成括边界，把边界画成实

2、线实线。3、思想方法思想方法：特殊到一般、数形结合、函数思想：特殊到一般、数形结合、函数思想例例3：满足线性约束条件：满足线性约束条件 的可行域中共有的可行域中共有 多少个整数解。多少个整数解。x+4y113x +y10 x0y01223314455xy03x +y=10 x +4y=11解：解：由题意得可行域如图由题意得可行域如图: 由图知满足约束条件的由图知满足约束条件的可行域中的整点为可行域中的整点为(1,1)、(1,2)、(2,1)、(2,2) 故有四个整点可行解故有四个整点可行解.不等式组不等式组 表示的平面区域内表示的平面区域内的的整数点整数点共有（共有（ ）个）个123400yx

3、yx巩固练习巩固练习1:1 2 3 4 xy432104x+3y=12123400yxyx例题分析 例例2 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示格的小钢板的块数如下表所示 ： 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格212131 今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，用数学关系式和图形表示上述要求。块，用数学关系式和图形表示上述要求。X张张y张张 例例3:一个化肥

4、厂生产甲、乙两种混合肥一个化肥厂生产甲、乙两种混合肥料，生产料，生产1车皮车皮甲甲种肥料需要的主要原料是种肥料需要的主要原料是磷酸盐磷酸盐4t、硝酸盐、硝酸盐18t；生产生产1车皮车皮乙乙种肥料种肥料需要的主要原料是磷酸盐需要的主要原料是磷酸盐1t、硝酸盐、硝酸盐15t。现库存磷酸盐现库存磷酸盐10t、硝酸盐、硝酸盐66t，在此基础上，在此基础上生产这两种混合肥料。列出满足生产条件的生产这两种混合肥料。列出满足生产条件的数学关系式，并画出相应的平面区域。数学关系式，并画出相应的平面区域。例题分析 在生产与营销活动中，我们常常需要在生产与营销活动中，我们常常需要考虑：怎样利用现有的资源（人力、物

5、考虑：怎样利用现有的资源（人力、物力、资金力、资金），取得），取得最大的收益最大的收益。或。或者，怎样以者，怎样以最少的资源最少的资源投入去完成一项投入去完成一项给定的任务。我们把这一类问题称为给定的任务。我们把这一类问题称为“最优化最优化”问题。问题。 不等式的知识是解决不等式的知识是解决“最优化最优化”问题的问题的得力工具。得力工具。 我们将借助我们将借助二元一次不等式二元一次不等式（组）的（组）的几何表示，学习几何表示，学习“最优化最优化”问题问题中的简中的简单单“线性规划线性规划”问题问题。画出不等式组画出不等式组 表示的平面区域。表示的平面区域。3x+5y 25 x -4y - 3x

6、13x+5y25x- -4y- -3x1在该平面区域上 问题 1 1：有无最大(小)值？问题：有无最大(小)值？xyox-4y=-33x+5y=25x=1问题：2 2+ +有无最大(小)值？CABxyox=1CB设z z2 2+ +, ,式中变量、满足下列条件，求的最大值和最小值。3x+ +5y25x- -4y- -3x1x-4y=-3x-4y=-33x+5y=253x+5y=25xyox-4y=-3x=1C 设z z2 2+ +, ,式中变量、满足下列条件 ， 求的最大值和最小值。3x+5y253x+5y25x-4y-3x-4y-3x1x1B3x+5y=25问题问题 1: 将z z2 2+

7、+变形?问题问题 2: z几何意义是_。斜率为斜率为-2的直线在的直线在y轴上的截距轴上的截距为为Z 则直线 l： 2 2+ +=z=z是一簇与 l0平行的直线,故 直线 l 可通过平移直线l0而得，当直 线往右上方平移时z 逐渐增大： 当l 过点 B(1,1)时,z 最小,即zmin=3 当l 过点A(5,2)时，最大,即 zmax25+212 。 析析: 作直线l0 ：2 2+ +=0 ,=0 , -2-2+ z+ z 在上述问题中，我们把要求最大值或在上述问题中，我们把要求最大值或最小值的最小值的函数函数f 2+叫做叫做目标函数目标函数， 目标函数中的变量所要满足的目标函数中的变量所要满

8、足的不等式不等式组组称为称为约束条件约束条件。 如果如果目标函数目标函数是关于变量的是关于变量的一次函数一次函数，则称为则称为线性目标函数线性目标函数，如果，如果约束条件约束条件是关是关于变量的于变量的一次不等式一次不等式（或等式），则称为（或等式），则称为线性约束条件线性约束条件。 在线性约束条件下求线性目标函数的最在线性约束条件下求线性目标函数的最大值或最小值问题，称为大值或最小值问题，称为线性规划问题线性规划问题。使目标函数达到最大值或最小值的使目标函数达到最大值或最小值的点的坐点的坐标标，称为问题的，称为问题的最优解最优解。 一般地，满足线性约束条件的一般地，满足线性约束条件的解解(x

9、，y)叫做叫做可行解可行解，由所有可行解组成的，由所有可行解组成的集合集合叫叫做做可行域可行域。最优解最优解：使使目标函数达到目标函数达到最大值最大值或或 最小值最小值 的可的可 行行 解。解。 线性约束条件：线性约束条件：约束条件中均为关于约束条件中均为关于x、y的的一次一次不等式或方程。不等式或方程。有关概念有关概念约束条件约束条件：由、的不等式（方程）构成的不等式组。由、的不等式（方程）构成的不等式组。目标函数：目标函数：欲求最值的关于欲求最值的关于x、y的解析式的解析式。线性目标函数：线性目标函数：欲求最值的解析式是关于欲求最值的解析式是关于x、y的的一次一次解析式。解析式。线性规划：

10、线性规划：求线性目标函数在线性约束条件下的最大值或最小值求线性目标函数在线性约束条件下的最大值或最小值。可行解：可行解：满足线性约束条件的解（满足线性约束条件的解（x，y）。）。 可行域：可行域：所有可行解组成的集合。所有可行解组成的集合。xyox-4y=-3x=1CB3x+5y=25 设Z2+,式中变量、 满足下列条件 ， 求的最大值和最小值。3x+5y25x-4y-3x1使使z=2x+y取得取得最大值最大值的可行解为的可行解为 ，且最大值为且最大值为 ；1.已知二元一次不等式组已知二元一次不等式组x-y0 x+y-10y-1（1）画出不等式组所表示的平面区域；）画出不等式组所表示的平面区域

11、；满足满足 的的解解(x,y)都叫做可行解；都叫做可行解；z=2x+y 叫做叫做 ；（2）设）设z=2x+y，则式中变量，则式中变量x,y满足的二元一满足的二元一次不等式组叫做次不等式组叫做x,y的的 ；y=-1x-y=0 x+y=12x+y=0返回返回(-1,-1)(2,-1)使使z=2x+y取得取得最小值最小值的可行解的可行解 ，且最小值为且最小值为 ；这两个这两个可行解可行解都叫做问题的都叫做问题的 。线性线性约束条件约束条件线性线性目标函数目标函数线性约束条件线性约束条件(2,-1)(-1,-1)3-3最优解最优解xy011结论结论:1、线性目标函数的最大值、最小值一般在可行、线性目标

12、函数的最大值、最小值一般在可行域的顶点处取得域的顶点处取得,所以，通常通过解方程组，求所以，通常通过解方程组，求出要用的顶点坐标。出要用的顶点坐标。2、线性目标函数的最大值、最小值也可能在可行、线性目标函数的最大值、最小值也可能在可行域的边界上取得，即满足条件的最优解有无个。域的边界上取得，即满足条件的最优解有无个。3、求线性目标函数的最优解，要注意分析线性、求线性目标函数的最优解，要注意分析线性目标函数所表示的目标函数所表示的几何意义几何意义 -与与y轴上的截轴上的截距相关的数。距相关的数。B Cxyox4y=33x+5y=25x=1 例例1：设：设z2xy,式中变量式中变量x、y满足下列条

13、件满足下列条件 求的最大值和最小值。求的最大值和最小值。3x+5y25x 4y3x1解：作出可行域如图解：作出可行域如图：当当0时，设直线时，设直线 l l0 0：2xy0 当当l l0 0经过可行域上点经过可行域上点A时，时，z 最小，即最小，即最大。最大。 当当l l0 0经过可行域上点经过可行域上点C时，时，最大，即最大，即最小。最小。由由 得得A点坐标点坐标_； x4y3 3x5y25由由 得得C点坐标点坐标_； x=1 3x5y25zmax2528 zmin214.4 2.4(5,2)(5,2)(1,4.4)(1,4.4)平移平移l l0 0，平移平移l l0 0 ，(5,2)2xy

14、0(1,4.4)(5,2)(1,4.4)解线性规划问题的步骤：解线性规划问题的步骤： 2 2、 在线性目标函数所表示的一组平行线在线性目标函数所表示的一组平行线 中，用平移的方法找出与可行域有公中，用平移的方法找出与可行域有公 共点且纵截距最大或最小的直线；共点且纵截距最大或最小的直线； 3 3、 通过解方程组求出最优解；通过解方程组求出最优解； 4 4、 作出答案。作出答案。 1 1、 画出线性约束条件所表示的可行域；画出线性约束条件所表示的可行域；画画移移求求答答3x+5y=25 例例2：已知：已知x、y满足满足 ，设，设zaxy (a0)， 若若 取得最大值时，对应点有无数个，求取得最大

15、值时，对应点有无数个，求a 的值。的值。3x+5y25 x 4y3x1xyox-4y=-3x=1CB B解：解：当直线当直线 l l ：y ax z 与与AC直线重合时，有无数个点，直线重合时，有无数个点，使函数值取得最大值，此时有：使函数值取得最大值，此时有： k l l kAC 535124 . 4 kACk l l = -a53 -a = a =53练习：练习： 设Z Z+3+3,式中变量、满足下列条件，求的最大值和最小值。 x - y 7 2x+3y24 x0y 6y 0例题分析例题分析例例1:某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产已知生产甲甲种产品种产品1t需消耗

16、需消耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产；生产乙乙种产品种产品1吨需消耗吨需消耗A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t.每每1t甲种产品的利润是甲种产品的利润是600元元,每每1t乙种产品的利润是乙种产品的利润是1000元元.工工厂在生产这两种产品的计划中要求消耗厂在生产这两种产品的计划中要求消耗A种矿石不超过种矿石不超过300t、消耗、消耗B种种矿石不超过矿石不超过200t、消耗煤不超过、消耗煤不超过360t.甲、乙两种产品应各生产多少甲、乙两种产品应各生产多少(精精确到确到0.1t),能使利润总额达到最大能使利润总额达到最大?返回返回 甲产品甲产品 （1

17、t） 乙产品乙产品 （1t） 资源限额资源限额 （t）A种矿石（种矿石（t） B种矿石（种矿石（t） 煤（煤（t） 利润（元）利润（元） 产品产品消耗量消耗量资源资源列表列表：51046004491000300200360设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x t、yt,利润总额为利润总额为z元元例题分析例题分析返回返回 甲产品甲产品 （1t） 乙产品乙产品 （1t） 资源限额资源限额 （t）A种矿石（种矿石（t） B种矿石（种矿石（t） 煤（煤（t） 利润（元）利润（元） 产品产品消耗量消耗量资源资源列表列表：51046004491000300200360把题中限制条件进行

18、把题中限制条件进行转化：转化：约束条件约束条件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.作出以上不等式组所表示的可行域作出以上不等式组所表示的可行域作出一组平行直线作出一组平行直线 600 x+1000y=t，解得交

19、点解得交点M的坐标为的坐标为(12.4,34.4)5x+4y=2004x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:应生产甲产品约应生产甲产品约12.4吨，乙产品吨，乙产品34.4吨，能使利润总额达到最大。吨，能使利润总额达到最大。(12.4,34.4)返回返回经过可行域上的点经过可行域上的点M时时,目标函数目标函数在在y轴上截距最大轴上截距最大.ll l9030 0 xy10 201075405040此时此时z=600 x+1000y取得最大值取得最大值.例题分析例例2 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板

20、截成A、B、C三种规格，每三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，第一种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图）作出可行域（如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问各截这两种块，问各截这两种钢板多少张可得所需三种规格成品

21、，且使所用钢板张数最少。钢板多少张可得所需三种规格成品，且使所用钢板张数最少。返回返回X张张y张张例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解. 作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z= x+y返回返回B(3,9)C(4,8)A(18/5,39/5)当直线经过点当直线经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值

22、法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)且和原点距离最近的直线是且和原点距离最近的直线是x+y=12，它们是最优解，它们是最优解.答答:(略略)作出一组平行直线作出一组平行直线t = x+y，目标函数目标函数t = x+y返回返回B(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打

23、出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，1212182715978在可行域内找出最优解、线性规划在可行域内找出最优解、线性规划整数解问题的一般方法是：整数解问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然

24、后在可行域内适当，然后在可行域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解络、找整点、平移直线、找出整数最优解二二:给定一项任务，问怎样统筹安排，能使给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源最小。完成这项任务的人力、物力资源最小。一一:给定一定数

25、量的人力、物力资源，问怎给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量样安排运用这些资源，能使完成的任务量最大，收到的效益最大。最大，收到的效益最大。线性规划研究的两类重要实际问题：线性规划研究的两类重要实际问题：巩固练习巩固练习2：咖啡馆配制两种饮料甲种饮料每杯含奶粉咖啡馆配制两种饮料甲种饮料每杯含奶粉9g 、咖啡、咖啡4g、糖糖3g,乙种饮料每杯含奶粉乙种饮料每杯含奶粉4g 、咖啡、咖啡5g、糖、糖10g已知每天已知每天原料的使用限额为奶粉原料的使用限额为奶粉3600g ，咖啡，咖啡2000g糖糖3000g,如果如果甲种饮料每杯能获利甲种饮料每杯能获利0.7元，乙种

26、饮料每杯能获利元，乙种饮料每杯能获利1.2元，每元，每天在原料的使用限额内饮料能全部售出，每天应配制两种天在原料的使用限额内饮料能全部售出，每天应配制两种饮料各多少杯能获利最大饮料各多少杯能获利最大？解：将已知数据列为下表：解：将已知数据列为下表： 消耗量消耗量资源资源甲产品甲产品（1 杯）杯）乙产品乙产品(1杯杯)资源限额（资源限额（g）奶粉（奶粉（g g）9 94 436003600咖啡咖啡(g)(g)4 45 520002000糖糖(g)(g)3 3101030003000利润（元）利润（元）0.70.71.21.2 产品产品设每天应配制甲种饮料设每天应配制甲种饮料x x杯，乙种饮料杯，

27、乙种饮料y y杯，则杯，则003000103200054360049yxyxyxyx作出可行域：作出可行域：目标函数为：目标函数为：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的位置时，的位置时，直线经过可行域上的点直线经过可行域上的点C C，且与原点，且与原点距离最大，距离最大，此时此时z =0.7x +1.2yz =0.7x +1.2y取最大值取最大值解方程组解方程组 得点得点C C的坐标为（的坐标为（200200，240240）,3000103,200054

28、yxyx_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_ y二元一次不等式二元一次不等式表示平面区域表示平面区域直线定界，直线定界，特殊点定域特殊点定域简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解应用应用求解方法：画、求解方法：画、移、求、答移、求、答小结：小结：解线性规划应用问题的一般步骤：解线性规划应用问题的一般步骤：1）理清题意，列出表格：）理清题意，列出表格：2）设好变元并列出不等式组和目标函数）设好变元并列出不等式组和目标函数3）准确作图，准确计算）准确作图，准确计算知识点：知识点：技能点：技能点：数学思想：数学思想：4）还原成实际问题）还原成实际问题学习了把实际问题转化成线性学习了把实际问题转化成线性规划问题即建立数模的方法规划问题即建立数模的方法 渗透转换、化归思想，数形结合思渗透转换、化归思想，数形结合思想，用数学的意识、创新意识想，用数学的意识、创新意识 作业作业：课本习题课本习题