3.3.2《二元一次不等式组与简单的线性规划问题》1.ppt

应该注意的几个问题： 在可行域内找出最优解、线性规划整数解问题的一般方法是： 1.若区域“顶点”处恰好为整点，那么它就是 最优解；（在包括边界的情况下） 2.若区域“顶点”不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值Z，然后在可行域内适当放缩目标函数值，使它为整数，且与Z最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。 3.在可行域内找整数解，一般采用平移找解法， 即打网络、找整点、平移直线、找出整数最优解 1、若不等式中不含0，则边界应画成虚线， 2、画图时应非常准确，否则将得不到正确结果。 3、技巧：直线定界、特殊点定域。 否则应画成实线。 x y o 第二节 一.复习回顾 1.在同一坐标系上作出下列直线: 2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7 x Y o 2.作出下列不等式组的所表示的平面区域 5 5 x=1 x-4y+3=0 3x+5y-25=0 1 A B C C: (1.00, 4.40) A: (5.00, 2.00) B: (1.00, 1.00) O x y 问题1：x 有无最大（小）值？ 问题2：y 有无最大（小）值？ 问题3：2x+y 有无最大（小）值？ 二.提出问题 把上面两个问题综合起来: 设z=2x+y,求满足 时,求z的最大值和最小值. 5 5 x=1 x-4y+3=0 3x+5y-25=0 1 A B C C: (1.00, 4.40) A: (5.00, 2.00) B: (1.00, 1.00) O x y 直线L越往右平移,t随之增大. 以经过点A(5,2)的直线所对应的t值最大;经过点B(1,1)的直线所对应的t值最小. 设z=2x+y,求满足 时,求z的最大值和最小值. 线性目标函数 线性约束条件 线性规划问题 任何一个满足不等式组的（x,y） 可行解 可行域 所有的 最优解 1、由x，y 的不等式(或方程)组成的不等式组称为x，y 的约束条件。 2、关于x，y 的一次不等式或方程组成的不等式组称为x，y 的线性约束条件。 3、欲达到最大值或最小值所涉及的变量x，y 的解析式称为目标函数。 4、关于x，y 的一次目标函数称为线性目标函数。 5、求线性目标函数在线性约束条件下的最大值或最小值问题称为线性规划问题。 6、满足线性约束条件的解（x，y）称为可行解。 7、所有可行解组成的集合称为可行域。 8、使目标函数取得最大值或最小值的可行解称为最优解。 三、课堂练习 (1)已知 求z=2x+y的最大值和最小值。 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=2x+y的最优解。 （2）、已知 求z=300x+900y取得最大值时整点的坐标 及相应Z的最大值。 使z=2x+y取得最大值的可行解为 　 ， 且最大值为 ； 复习引入 1.已知二元一次不等式组 { x-y≥0 x+y-1≤0 y≥-1 （1）画出不等式组所表示的平面区域； 满足 　　　 的解(x,y)都叫做可行解； z=2x+y 叫做 　　 ； （2）设z=2x+y，则式中变量x,y满足的二元一次不等式组叫做x,y的 　　　　 ； y=-1 x-y=0 x+y=1 2x+y=0 返回 (-1,-1) (2,-1) 使z=2x+y取得最小值的可行解 　 ， 且最小值为 ； 这两个最值都叫做问题的 。 线性约束条件 线性目标函数 线性约束条件 (2,-1) (-1,-1) 3 -3 最优解 x y 0 1 1 解线性规划问题的步骤： （2）令Z=0,画直线l0; （3）观察、分析，平移直线l0,求出最优解； （4）求出目标函数的最大值或最小值。 （1）根据线性约束条件画出可行域； （2）、 （1）、已知 求z=3x+5y的最大值和最小值。 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) 不等式组 表示的平面区域内的整数点共有（ ）个 1 2 3 4 x y 4 3 2 1 0 4x+3y=12 1、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得。 2、求线性目标函数的最优解，要注意