简单的线性规划(一)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,简单的线性规划,x,y,o,简单的线性规划xyo,1,复习：,把直线画成,虚线,以表示区域,不包括边界,直线；,把直线画成,实线,以表示区域,包括边界,直线。,一般的,，,二元一次不等式,Ax+By+C0,在平面坐标系中表示,直线Ax+By+C=0某一侧所有点组成的区域。,在直线的某一侧,取,一个特殊,点（x,0,y,0,）,，从,Ax,0,+By,0,+C,的,正负,可以,判断Ax+By+C0表示直线哪一侧的平面区域,。,特殊的，当,C0,时，可以,取（0，0）,作为特殊点。,复习：把直线画成虚线以表示区域不包括边界直线；把直线画成实,2,线性规划有关概念,由,x，y,的不等式(或方程)组成的不等式组称为,x，y,的,约束条件,。关于,x，y,的一次不等式或方程组成的不等式组称为,x，y,的,线性约束条件,。欲达到最大值或最小值所涉及的变量x，y 的解析式称为,目标函数,。关于x，y 的一次目标函数称为,线性目标函数,。求线性目标函数在线性约束条件下的最大值或最小值问题称为,线性规划问题,。满足线性约束条件的解（x，y）称为,可行解,。所有可行解组成的集合称为,可行域,。使目标函数取得最大值或最小值的可行解称为,最优解,。,线性规划有关概念由x，y 的不等式(或方程)组成的不等式组称,3,基本概念：,z=2x+y,象此问题一样，,求线性目标函数在线性约束条件下的最值,的问题,统称为,线性规划问题,。,满足约束条件的解（x，y）,叫做,可行解,。,可行解,组成的集合,叫做,可行域,。（,阴影部分,）,使,目标函数,取,得,最值,的,可行解,叫做,最优解,。,目标函数,，,也叫,线性目标函数,。,线性约束条件,。,x-4y+3=0,3x+5y-25=0,x=1,2x+y=t,1,x,y,o,可行域,A（5，2）,B（1，1）,基本概念：z=2x+y象此问题一样，求线性目标函数在线性,4,例题,(1)已知,求z=2x+y的最大值和最小值。,例题(1)已知,5,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,6,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,7,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,8,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,9,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,10,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,11,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),Z,max,=2x+y=2,x2+(-1)=3,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,12,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,13,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,14,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,15,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,16,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,17,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,18,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),Z,min,=2x+y=2,x(-1)+(-1)=-3,3.根据y=-2x平移到区域的最后一个点时有最大（小）值,2.将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,551Oxyy-x=0 x+y-1=01-1y+1=0A(2,19,实例分析：,设x,y满足以下条件：,求,z=2x+y,的最大值与最小值。,线性约,束条件,目标函数,（线性目标函数）,上一页,实例分析：设x,y满足以下条件：线性约 目标函数上一页,20,如图，分别作出,三条直线，,上一页,o,5x+6y=30,y=1,y=3x,y,y=1,y=3x,5x+6y=30,再找出不等式组,所表示的平面区域的公,共区域。,可行域,x,如图，分别作出上一页o5x+6y=30y=1y=3xyy=1,21,将直线方程化为：y=-2x+z,且令z=0,画出直线l,0，,l,0,:y=-2x,上一页,o,5x+6y=30,y=1,y=3x,y,x,l,0,:2x+y=0,将直线方程化为：y=-2x+z,且令z=0,画出直线l0，l,22,上一页,如图，平移直线l,0,，,所对应的z随之增大；,所对应的z随之减小。,当直线l,0,向上平移时，,当直线l,0,向下平移,时,o,5x+6y=30,y=1,y=3x,y,上一页如图，平移直线l0，,23,此时所对应的Z最小；,此时所对应的Z最大。,从而得到：,z,min,z,max,=2 +1=,=2 +1=,o,5x+6y=30,y=1,y=3x,y,x,A,B,C,l,0,:y=-,2x,如图，在把l,0,向上平移过程中，直线与平面区,域首先相交于点A ，,当相交于点B ，,l,1,l,2,此时所对应的Z最小；此时所对应的Z最大。从而得到：zmin,24,解线性规划问题的步骤：,（2）移：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；,（3）求：通过解方程组求出最优解；,（4）答：作出答案。,（1）画：画出线性约束条件所表示的可行域；,解线性规划问题的步骤：（2）移：在线性目标函数所表示的一组,25,总结：,从这个问题的求解过程可以,看出，最优解一般在可行域的,边,界上,，而且通常在可行域的,顶点,处,取得。,上一页,总结：上一页,26,课堂练习,(1)已知,求z=2x+y的最大值和最小值。,课堂练习(1)已知,27,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),551Oxyy-x=0 x+y-1=01-1y+1=0A(2,28,（2）已知,求z=3x+5y的最大值和最小值。,（2）已知,29,5,5,1,O,x,y,1,-1,5x+3y=15,X-5y=3,y=x+1,A(-2,-1),B(3/2,5/2),551Oxy1-15x+3y=15X-5y=3y=x+1A(,30,巩固练习,设满足约束条件,求,的最大值,。,巩固练习 设满足约束条件,31,例:营养学家指出，成人良好的日常饮食应该至少提供0.075kg的碳水化合物，0.06kg的蛋白质，0.06kg的脂肪，1kg食物A含有0.105kg碳水化合物，0.07kg蛋白质，0.14kg脂肪，花费28元；而1食物B含有0.105kg碳水化合物，0.14kg蛋白质，0.07kg脂肪，花费21元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物A和食物B多少kg？,食物kg,碳水化合物kg,蛋白质/kg,脂肪kg,A,0.105,0.07,0.14,B,0.105,0.14,0.07,分析：将已知数据列成表格,例:营养学家指出，成人良好的日常饮食应该至少提供0.075k,32,解：设每天食用xkg食物A，ykg食物B，总成本为z，那么,目标函数为：z28x21y,作出二元一次不等式组所表示的平面区域，即可行域,解：设每天食用xkg食物A，ykg食物B，总成本为z，那么目,33,把目标函数,z28x21y,变形为,x,y,o,5/7,5/7,6/7,3/7,3/7,6/7,它表示斜率为,随z变化的一组平行直线系.,是直线在y轴上的截距，当截距最小时，z的值最小。,M,如图可见，当直线z28x21y,经过可行域上的点M时，截距最小，即z最小。,把目标函数z28x21y 变形为xyo5/75/76/7,34,M点是两条直线的交点，解方程组,得M点的坐标为：,所以z,min,28x21y16,由此可知，每天食用食物A143g，食物B约571g，能够满足日常饮食要求，又使花费最低，最低成本为16元。,M点是两条直线的交点，解