《线性规划一课时(可用)课件》由会员分享,可在线阅读,更多相关《线性规划一课时(可用)课件(12页珍藏版)》请在金锄头文库上搜索。
1、人生路上甜苦和喜忧人生路上甜苦和喜忧愿与你分担所有愿与你分担所有难免曾经跌倒和等候难免曾经跌倒和等候要勇敢的抬头要勇敢的抬头谁愿常躲在避风的港口谁愿常躲在避风的港口宁有波涛汹涌的自由宁有波涛汹涌的自由愿是你心中灯塔的守候愿是你心中灯塔的守候在迷雾中让你看透在迷雾中让你看透阳光总在风雨后阳光总在风雨后乌云上有睛空乌云上有睛空珍惜所有的感动珍惜所有的感动每一份希望在你手中每一份希望在你手中阳光总在风雨后阳光总在风雨后请相信有彩虹请相信有彩虹风风雨雨都接受风风雨雨都接受我一直会在你的左右我一直会在你的左右线性规划一课时(可用)2.线性规划线性规划l例题设z=2x+y,式中的变量x,y满足下列条件:
2、求z的最大值和最小值X-4y-33x+5y25x1X=1X-4y+3=03x+5y-25=0l0l1ll2A从图中可知,点(0,0)不在公共区域内当x=0,y=0时,Z=2x+y=0.点(0,0)在直线l0:2x+y=0上作一组与直线l0平行的直线L:2x+y=t,tR.可知,当l在l0的右上方时,直线l上的点(x,y)满足2x+y0,即t0,而且l往右平移时,t随之增大在经过不等式组所表示的区域内的点且平行于l的直线中,以经过点(5,2)的直线l2所对应的t值最大,经过点B(1,1)的直线l1所对应的t值最小所以Zmax=25+2=12,zmin=21+1=3BB:X-4Y+3=0X=1A:
3、X-4Y+3=03X+5Y-25=0线性规划一课时(可用)l:l 不等式组(不等式组(A)是一组对变量)是一组对变量x、y的约束条件,这组约束条的约束条件,这组约束条件都是关于件都是关于x、y的一次不等式,就称为的一次不等式,就称为 。z=2x+y是是要达到最大值或最小值的涉及变量要达到最大值或最小值的涉及变量x、y解析式,叫做目标函数。解析式,叫做目标函数。由于由于z=2x+y又是又是x、y的一次解析式,所以又叫做的一次解析式,所以又叫做 。求线性目标函数求线性目标函数z=2x+y在线性约束条件在线性约束条件(A)下的最大值问题,统下的最大值问题,统称为称为 。满足线性约束条件的解(。满足线
4、性约束条件的解(x,y)叫做)叫做可行解可行解,由所有可行解组成的集合叫做可行域。在上述问题中,可行域就由所有可行解组成的集合叫做可行域。在上述问题中,可行域就是阴影部分表示的区域。其中可行解(是阴影部分表示的区域。其中可行解(5,2)和()和(1,1)分别使)分别使目标函数取得最大值和最小值,它们都叫做这个问题的目标函数取得最大值和最小值,它们都叫做这个问题的最优解最优解。线性约束条件线性目标函数线性规划问题形成概念线性规划一课时(可用)实例分析:实例分析:设设x,y满足以下条件:满足以下条件: 求求z=2x+y的最大值与最小值。的最大值与最小值。线性约束条件 目标函数(线性目标函数)上一页
5、上一页线性规划一课时(可用)如图,分别作出如图,分别作出 三条三条直线,直线,上一页上一页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线性规划一课时(可用)上一页上一页如图,平移直线如图,平移直线l0, 所对应的所对应的z随之增大;随之增大; 所对应的所对应的z随之减小。随之减小。当直线当直线l0向上平移时,向上平移时, 当直
6、线当直线l0向下平移向下平移时时, o5x+6y=30y=1y=3xyl0:2x+y=0l1:2x+y=2l2:2x+y=4l3:2x+y=-3线性规划一课时(可用) 此时所对应的此时所对应的Z最小;最小;此时所对应的此时所对应的Z最大。最大。从而得到:从而得到:zminzmax=2 +1= =2 +1= o5x+6y=30y=1y=3xyxABCl0:2x+y=0如图,在把如图,在把l0向上平移过程中,直线与平面区向上平移过程中,直线与平面区域首先相交于点域首先相交于点A ,当相交于点当相交于点B ,l1l2线性规划一课时(可用)l用图解法解决简单的线性规划问题的基本步骤:l 简记为:简记为
7、:画画移移求求答答 1、根据线性约束条件画出可行域、根据线性约束条件画出可行域 (即画出不等式组所表示的公共区域);(即画出不等式组所表示的公共区域);2、设、设z=0,画出直线,画出直线 l 0 ;3、观察、分析,平移直线、观察、分析,平移直线 l 0 ,从而找到,从而找到 最优解;最优解;4、利用最优解得出最大值及最小值。、利用最优解得出最大值及最小值。线性规划一课时(可用) 一般地求线性目标函数在线性约束条件下的一般地求线性目标函数在线性约束条件下的 最大值或最小值的问题,统称为线性规划问题。最大值或最小值的问题,统称为线性规划问题。 满足线性约束条件的解满足线性约束条件的解( (x,y
8、) )叫可行解。叫可行解。 由所有可行解组成的集合叫做可行域。由所有可行解组成的集合叫做可行域。 使目标函数取得最大或最小值的可行解叫线使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。性规划问题的最优解。 上一页上一页抽象概括抽象概括线性规划:线性规划:可行解可行解 :可行域可行域 :最优解最优解 :目标函数:目标函数: 如果两个变量如果两个变量x,y满足一组一次不等式,求满足一组一次不等式,求两个变量的一个线性函数(如两个变量的一个线性函数(如z=2x+y)的最大值或最)的最大值或最小值,那么就称这个线性函数为目标函数。小值,那么就称这个线性函数为目标函数。线性规划一课时(可用)l
9、用图解法解决简单的线性规划问题的基本步骤:l 简记为:简记为:画画移移求求答答 1、根据线性约束条件画出可行域、根据线性约束条件画出可行域 (即画出不等式组所表示的公共区域);(即画出不等式组所表示的公共区域);2、设、设z=0,画出直线,画出直线 l 0 ;3、观察、分析,平移直线、观察、分析,平移直线 l 0 ,从而找到,从而找到 最优解;最优解;4、利用最优解得出最大值及最小值。、利用最优解得出最大值及最小值。线性规划一课时(可用)总结:总结: 从这个问题的求解过程可以从这个问题的求解过程可以看出,最优解一般在可行域的看出,最优解一般在可行域的边边界上界上,而且通常在可行域的,而且通常在可行域的顶点顶点处处取得。取得。上一页上一页线性规划一课时(可用)