《简单的线性规划问题》课件(4)

1、简单线的性规划问题想一想想一想？问题问题1:点的集合点的集合(x，y)x + y1=0表示什么图形？表示什么图形？YXO11集合表示的图形是一集合表示的图形是一条直线。该直线在条直线。该直线在Y轴和在轴和在x轴上的截距轴上的截距都是都是1。问题问题2:2:点的集合点的集合A=A=（x x，y y）|x|xy y1010在在 平面直角坐标系中表示什么图形？平面直角坐标系中表示什么图形？分析分析:在平面直角坐标系中，所有的点被直线在平面直角坐标系中，所有的点被直线x + y- 1= 0（如图所示）分成三类：（如图所示）分成三类：1、在直线上。、在直线上。2 2、在直线的左下方的平面区域内、在直线的

2、左下方的平面区域内( ()。3、在直线的右上方的平面区域内、在直线的右上方的平面区域内() 。YOX11取右上方的平面区域内的点取右上方的平面区域内的点(1,1),(1,2),(2,2),我们发现这些点这些我们发现这些点这些点都满足点都满足xy110。若我们取左下。若我们取左下方平面区域内的点方平面区域内的点(0,0),(1,1),我们我们发现这些点都满足发现这些点都满足xy10。(1,1)(1,2)(2,2)(0,0)(-1,-1)(1)猜想猜想:（1）对直线）对直线L右上方的点（右上方的点（x，y），），x+y-10 成立。成立。（2）对直线）对直线L左下方的点（左下方的点（x，y），），

3、x+y-10 成立。成立。),(yxy=y0Y1OX1000 (2): xy 10P(x ,y ) PXyy , P(x,y), 证明在直线上任取一点，过点 作平行于 轴的直线在直线上点 右侧的任意一点. 01yx 01yx1yx ,yxyx,yy,xx 000000即，所以，都有都成立。右上方任意点对于直线所以上的任意点是直线因为点01yx),y, x( 01yx ,01yx )y,xP( 00),(00yxP。01yx ),y, x( 01yx , 都成立左下方任意点对于直线同理问题问题2:2:点的集合点的集合A=A=（x,yx,y）|x|xy y1010在平面直角坐标系中是在平面直角坐标

4、系中是YOX11直线直线x xy y1=01=0右上方的右上方的平面区域平面区域x xy y1=01=0OXY1(3)(3)结论结论: :二元一次不等式二元一次不等式Ax+By+C0在平面直角坐标系中表示直在平面直角坐标系中表示直线线Ax+By+C=0某一侧所有点组成的平面区域。某一侧所有点组成的平面区域。这时直线上的点不这时直线上的点不包含在区域内包含在区域内,要把直线要把直线Ax+By+C0画成虚线画成虚线,而画而画Ax+By+C0表示的区域时表示的区域时,此区域包括直线此区域包括直线,要把直线要把直线Ax+By+C0画成实线画成实线. 在确定区域时，由于在直线在确定区域时，由于在直线Ax

5、+By+C=0同一侧的所有点同一侧的所有点(x,y),把它代入把它代入Ax+By+C,所得的实数符号都相同所得的实数符号都相同,在直线的在直线的某一侧取一个特殊点某一侧取一个特殊点 (x0,y0) ，从，从Ax0+By0+C的正负可以判断出的正负可以判断出Ax+By+C0表示哪一侧的区域。一般当表示哪一侧的区域。一般当C0时，取时，取原点原点作为特殊点。当作为特殊点。当C=0时时,取取(0,1)或或 (1,0)点作点作为特殊点为特殊点我们可以通过以下方法来判断我们可以通过以下方法来判断A+By+C0到底是哪个区域的到底是哪个区域的:OXY例例1：画出不等式画出不等式2x+y-60 表示的平面区

6、域。表示的平面区域。)(06yx2) 1 (画成虚线先画出直线的区域。用阴影部分表示不等式)3(xyo63说明说明:画二元一次不等式画二元一次不等式的平面区域常用的方法是的平面区域常用的方法是“直线定界，特殊点定域直线定界，特殊点定域”06yx22x+y-60不等式化为不等式化为x+2y4 0,取取(0.0)代入代入x+2y4,得得0+0 4= 404-2课堂小结:1、二元一次不等式、二元一次不等式Ax+By+C0在平面直角在平面直角坐标系中表示什么图形坐标系中表示什么图形3、熟记、熟记“直线定界、特殊点定域直线定界、特殊点定域”方法的方法的内涵。内涵。2、若不等式中不含、若不等式中不含0（

7、Ax+By+C0） ，则，则边界应画成虚线，否则应画成实线。边界应画成虚线，否则应画成实线。实例分析：实例分析：设设x,y满足以下条件：满足以下条件： 求求z=2x+y的最大值与最小值。的最大值与最小值。 133065yxyyx线性约束条件 目标函数（线性目标函数）如图，分别作出如图，分别作出 三条三条直线，直线，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+6y=30 再找出不等式组再找出不等式组所表示的平面区域的公所表示的平面区域的公共区域。共区域。可行域可行域x设设z=0,画出直线画出直线l0，即即l0:2x+y=0。o5x+6y=30y=1y=3xyxl0:2x+y=0因

8、为因为z=2x+y, 令令x=0则则z=y（纵截距）（纵截距），如图，平移直线如图，平移直线l0， 所对应的所对应的z随之增大；随之增大； 所对应的所对应的z随之减小。随之减小。当直线当直线l0向上平移时，向上平移时， 当直线当直线l0向下平向下平移移时时, o5x+6y=30y=1y=3xyl0:2x+y=0l1:2x+y=2l2:2x+y=4l3:2x+y=-3(13,1) 此时所对应的此时所对应的Z最小；最小；(245,1)此时所对应的此时所对应的Z最大。最大。从而得到：从而得到：zminzmax=2 +1= =2 +1= 1324553535o5x+6y=30y=1y=3xyxABCl

9、0:2x+y=0如图，在把如图，在把l0向上平移过程中，直线与平面区向上平移过程中，直线与平面区域首先相交于点域首先相交于点A ，当相交于点当相交于点B ，l1l2解线性规划问题的一般步骤：解线性规划问题的一般步骤：第一步：根据线性约束条件在平面直角坐标系第一步：根据线性约束条件在平面直角坐标系中画出可行域（即画出不等式组所表示的公共中画出可行域（即画出不等式组所表示的公共区域）；区域）；第二步：设第二步：设z=0,画出直线画出直线l0；第三步：观察、分析，平移直线第三步：观察、分析，平移直线l0，从而找到最，从而找到最优解；优解；第四步：最后求得目标函数的最大值或最小第四步：最后求得目标函数

10、的最大值或最小值。值。 一般地求线性目标函数在线性约束条件下的一般地求线性目标函数在线性约束条件下的 最大值或最小值的问题，统称为线性规划问题。最大值或最小值的问题，统称为线性规划问题。 满足线性约束条件的解满足线性约束条件的解( (x，y) )叫可行解。叫可行解。 由所有可行解组成的集合叫做可行域。由所有可行解组成的集合叫做可行域。 使目标函数取得最大或最小值的可行解叫线使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。性规划问题的最优解。 线性规划：线性规划：可行解可行解 ：可行域可行域 ：最优解最优解 ：目标函数：目标函数： 如果两个变量如果两个变量x,y满足一组一次不等式，求满

11、足一组一次不等式，求两个变量的一个线性函数（如两个变量的一个线性函数（如z=2x+y）的最大值或最）的最大值或最小值，那么就称这个线性函数为目标函数。小值，那么就称这个线性函数为目标函数。总结：总结： 从这个问题的求解过程可以从这个问题的求解过程可以看出，最优解一般在可行域的看出，最优解一般在可行域的边边界上界上，而且通常在可行域的，而且通常在可行域的顶点顶点处（或边界上）处（或边界上）取得。取得。例题：例题：1.x、y满足约束条件满足约束条件：11yyxxy求求z=2x+y的最大值的最大值xoyy=xx+y=1y=1A(2,-1)在点在点A(2，-1)处处z=2x+y最大最大 zmax=22

12、+(-1)=311yyxxyy=-2x设设z=0,画出直线画出直线l0，即即l0:y=-2x。1255334xyxyx求求z=2xy的最大值。的最大值。2.已知已知x、y满足满足Ax-4y+3=0yxO(5，2)3x+5y-25=0B (1，1)(1，4.4 )Cx=1L0:y=2x答案：在点答案：在点A（5，2）处取得最大值）处取得最大值Zmax2528因为因为z=2x-y, 令令x=0则则z=-y（纵截距的相反数），（纵截距的相反数），思考：这里思考：这里z的的几何意义是什么？几何意义是什么？也代表直线的纵截距吗？也代表直线的纵截距吗？1255334xyxyx 如果如果z=ax+y取取到最

13、大到最大 值的最优值的最优解有无数个，解有无数个，求求a的值的值3.已知已知x、y满足满足yxAOx-4y+3=0(5，2)3x+5y-25=0B (1，1)(1，4.4 )Cx=1yaxz 讨论（1）a0答案：答案：53aN N求：求： (1).最大值和最小值最大值和最小值; (2).222yxxz最大值和最小值最大值和最小值; 22yxz22yxz解解: (1)表示可行域内任一点表示可行域内任一点),(yx到原点到原点)0 , 0 (O的距离的平方的距离的平方.过过O向直线向直线ACBC、作垂线作垂线,垂足非别为垂足非别为.A、N易知易知,)9, 3(C到到O距离最大距离最大,此时此时,9

14、09322maxz. 00022minz例例3已知已知 满足不等式满足不等式yx,3006xyxyxB BC CA A0 yx06 yx3xP P3. (2).解解:1) 1(22222yxyxxz表示可行域内任一点到定点表示可行域内任一点到定点距离距离的平方再减去的平方再减去1.过过M作直线作直线AB的垂线的垂线,垂足是垂足是P由直角三角形直角边与斜边关系由直角三角形直角边与斜边关系,容易容易判断出判断出z的最小值是的最小值是,21|MPz的最大值为的最大值为.96|MC点评：点评：此类问题转化为可行域内的点到定点的距离此类问题转化为可行域内的点到定点的距离.M MB BC CA A0 yx06 yx3xQ Q已知已知 满足不等式满足不等式yx,3006xyxyx求：求： (1).xyz3的范围的范围;(2).12xyz的范围的范围.解解: (1)表示可行域内任一点与定点表示可行域内任一点与定点Q（0,-3）连线的斜率）连线的斜率,因为因为, 0,2QBQAkk所以所以z的范围为的范围为. ),02,(例例4B B