简单线性规划精选课件.ppt

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

1、关于简单线性规划第一页，本课件共有30页 二元一次不等式二元一次不等式ax+by+c0在平面直角在平面直角坐标系中表示坐标系中表示 _ 确定区域步骤：确定区域步骤：_、_若若c0，则，则 _、_.直线定界直线定界特殊点定域特殊点定域原点定域原点定域直线定界直线定界 直线直线ax+by+c=0某一侧所某一侧所有点组成的平面区域。有点组成的平面区域。二元一次不等式表示的区域及判定方法：二元一次不等式表示的区域及判定方法：复习回顾复习回顾第二页，本课件共有30页画出不等式组画出不等式组 表示的平面区域。表示的平面区域。3x+5y 25 x-4y-3x1第三页，本课件共有30页3x+5y25x-4y-

2、3x1在该平面区域上 问题 1 1：有无最大(小)值？问题：有无最大(小)值？xyox-4y=-33x+5y=25x=1问题：2 2+有无最大(小)值？CAB第四页，本课件共有30页xyox=1CB设z z2 2+,式中变量、满足下列条件，求的最大值和最小值。3x+5y25x-4y-3x1x-4y=-3x-4y=-33x+5y=253x+5y=25第五页，本课件共有30页线性规划例：设z=2x+y，式中变量满足下列条件：求z的最大值与最小值。目标函数（线性目标函数）线性约束条件第六页，本课件共有30页约束条件约束条件线性约束条件线性约束条件目标函数目标函数线性目标函数线性目标函数线性规划问题线

3、性规划问题可行解可行解可行域可行域最优解最优解 有关概念有关概念第七页，本课件共有30页x-4y-33x+5y25x1例例1 1：求求Z=2x+yZ=2x+y的最小值，的最小值，使使x,yx,y满足满足约束条件约束条件x-1=0 x=1 x-1=0 x=1 X-4y+3=0 y=1X-4y+3=0 y=1 B(1,1)B(1,1)当当x=1,y=1x=1,y=1时，时，Z Zminmin=3=3解解：画画出出满满足足x,yx,y的的条条件件所所表表示示的的区区域域，即即阴阴影影部部分（如图）分（如图）其其表表示示斜斜率率为为-2-2的的一一组组平平行行直直线线系系，截截距距为为z z。从从图图

4、上上可可知知：当当直直线线经经过过点点B B时时，z z有最小值。有最小值。由由Z=2x+yZ=2x+y变形得变形得y=-2x+zy=-2x+z解解得得第八页，本课件共有30页解线性规划问题的步骤：解线性规划问题的步骤：2 2、在线性目标函数所表示的一组平行线在线性目标函数所表示的一组平行线 中，用平移的方法找出与可行域有公中，用平移的方法找出与可行域有公 共点且纵截距最大或最小的直线；共点且纵截距最大或最小的直线；3 3、通过解方程组求出最优解；通过解方程组求出最优解；4 4、作出答案。作出答案。1 1、画出线性约束条件所表示的可行域；画出线性约束条件所表示的可行域；画画移移求求答答第九页，

5、本课件共有30页3x+5y=25 例例2：已知：已知x、y满足满足 ，设，设zaxy(a0)，若若 取得最大值时，对应点有无数个，求取得最大值时，对应点有无数个，求a 的值。的值。3x+5y25 x 4y3x1xyox-4y=-3x=1CB B解：解：当直线当直线 l l：y ax z 与直与直线重合时，有无数个点，使函数线重合时，有无数个点，使函数值取得最大值，此时有：值取得最大值，此时有：k l l kAC kACk l l=-a -a=a=第十页，本课件共有30页例例3：满足线性约束条件：满足线性约束条件 的可行域中共有的可行域中共有 多少个整数解。多少个整数解。x+4y113x+y10

6、 x0y01223314455xy03x+y=10 x+4y=11解：解：由题意得可行域如图由题意得可行域如图:由图知满足约束条件的由图知满足约束条件的可行域中的整点为可行域中的整点为(1,1)、(1,2)、(2,1)、(2,2)故有四个整点可行解故有四个整点可行解.第十一页，本课件共有30页误区解密凭空而想，没抓住问题本质致误误区解密凭空而想，没抓住问题本质致误第十二页，本课件共有30页第十三页，本课件共有30页因因为为x、y为为整数，而离点整数，而离点A最近的整点是最近的整点是C(1,2)，这这时时S13，所以所求的最大，所以所求的最大值为值为13.错因分析错因分析：显然整点：显然整点B(

7、2,1)满足约束条件，且此时满足约束条件，且此时S14，故上述解法不正确，故上述解法不正确对于整点解问题，其最优解不一定是离边界点最近的对于整点解问题，其最优解不一定是离边界点最近的整点整点而要先对边界点作目标函数而要先对边界点作目标函数tAxBy的图象，则最的图象，则最优解是在可行域内离直线优解是在可行域内离直线tAxBy最近的整点最近的整点第十四页，本课件共有30页正解正解：与错解中第一段解题过程相同：与错解中第一段解题过程相同因为因为x，y为整数，所以当直线为整数，所以当直线5x4yt平行移动时，平行移动时，从点从点A起第一个通过的可行域的整点是起第一个通过的可行域的整点是B(2,1)，

8、此时，此时Smax14.第十五页，本课件共有30页1常常见见的几种目的几种目标标函数的最函数的最值值的求法：的求法：利用截距的利用截距的几何意几何意义义；利用斜率的几何意利用斜率的几何意义义；利用距离的几何意利用距离的几何意义义往往是根据往往是根据题题中中给给出的不等式，求出出的不等式，求出(x，y)的可行域，利的可行域，利用用(x，y)的条件的条件约约束，数形束，数形结结合求得目合求得目标标函数的最函数的最值值课堂总结课堂总结第十六页，本课件共有30页小结小结:1线性规划问题的有关概念;2.用图解法解线性规划问题的一般步骤;3.求可行域中的整点可行解。第十七页，本课件共有30页第十八页，本课件共有30页首先将目标函数变形，明确它的几何意义，再利用解析几何相关知识求最值第十九页，本课件共有30页第二十页，本课件共有30页第二十一页，本课件共有30页第二十二页，本课件共有30页第二十三页，本课件共有30页第二十四页，本课件共有30页第二十五页，本课件共有30页第二十六页，本课件共有30页第二十七页，本课件共有30页第二十八页，本课件共有30页 已知变量x，y满足约束条件1xy4，2xy2.若目标函数zaxy(其中a0)仅在点(3,1)处取得最大值，求a的取值范围第二十九页，本课件共有30页2022/12/9感感谢谢大大家家观观看看第三十页，本课件共有30页