19.3线性规划问题的图解法.pptVIP

19.3线性规划问题的图解法 丁学福 在19.1的问举例中线性目标函数z=2x+3y 线性约束条件为 ① 提出问题 当x,y满足不等式①且为整数时，如何求z的最大值呢？ 问题探究 x y X+2y-8=0 M O X=4 y=3 ● 1.首先，画出①表示的平面区域； 2.把z=2x+3y变形为 3.将z看成常数，这是一条直线，当z变化时，可以得到一组平行的直线； 4.当直线 经过 不等式组①表示的平面区域内一个点时， 被唯一确定；当 取最大值时，z取最大值，当 取最小值时，z取最小值。 5.令z=0，画出直线2x+3y=0,然后平移这条直线，如图可知当经过点M（4，2）时 ，取得最大值，此时，z=2*4+3*2=14. 2.一般地，满足线性约束条件的解（x,y)叫做可行解， 所有可行解组成的集合叫做可行域。 在可行域中，使目标函数取得最大值（或最小值）的可行解叫做这个问题的最优解。 1.在线性规划问题中，画出线性约束条件所表示的平面区域，在平面区域上找出线性目标孙子函数值的方法，叫做线性规划问题的图解法。 学习新知 例 题 解 析 例1：已知线性约束条件为 求线性目标函数z=x+2y满足线性约束条件的最优解及最大值、最小值。 解:（1）在直角坐标系中，画出可行域。 x y x-4y+11=0 A O 2x+y-5=0 x-y-1=0 C B ● ● ● （2）将目标函数变形为 当z/2取得最大值时，z取得最大值； 当z/2取得最小值时，z取得最小值。 （3）令z=0在直角坐标系中，画出直线 x+2y=0,然后平移这条直线，如图可知当直线过A时z/2取得最小值；当直线过B时，z/2取得最大值。 （4）由方程组解得A(2,1),B(5,4)就是线性目标函数的最优解。从而，Zmin=2+2*1=4,Zmax=5+2*4=13. 例 题 解 析 例2：求函数z=2x+4y的最大值和最小值，其中x,y满足线性约束条件 解:（1）在直角坐标系中，画出可行域并找出整数点。 x y x+y+-10=0 A O 2x+y-8=0 x-y+3=0 B （2）将目标函数变形为 当z/4取得最大值时，z取得最大值； 当z/4取得最小值时，z取得最小值。 （3）令z=0在直角坐标系中，画出直线 x+2y=0,然后平移这条直线，如图可知当直线过A时z取得最小值；当直线过B时，z取得最大值。 （4）由方程组解得A(4,0),B(4,6)就 是线性目标函数的最优解。从而，Zmin=2*4+4*0=8,Zmax=2*4+4*6=32. ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 自 我 总 结 任 务 线性规划图解法 -----三步曲 画可行域 平移直线寻找最优解 变形目标函数画出直线 作业： P223 2 * * * *