5简单的线性规划问题.ppt

1、简单的线性规划问题,一、二元一次不等式表示的平面区域：,若B0， ，则点P在直线的上方， 此时不等式 表示直线 的上方的区域；,（注：若B为负，则可先将其变为正）,由此可知，二元一次不等式 在平面直角坐 标系中表示直线 某一侧所有点组成的 平面区域。我们把直线画成虚线以表示区域不含边界直线.当我 们在坐标系中画不等式 所表示的平面区 域时，此区域应包括边界直线，则把边界直线画成实线.,由于对在直线Ax+By+C=0同一侧的所有点(x,y)，把它的坐标(x,y)代入Ax+By+C，所得到的实数的符号都相同，所以只需在此直线的某一侧取一个特殊点(x0,y0),从Ax0+By0+C的正负情况，即可判

2、断Ax+By+C0表示直线哪一侧的平面区域。特殊地，当C0时，直线不过原点，能常把原点作为特殊点,二.线性规划: 求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题. 满足线性约束条件的解（x，y）叫做可行解，由所有可行解组成的集合叫做可行域（类似函数的定义域）；使目标函数取得最大值或最小值的可行解叫做最优解。生产实际中有许多问题都可以归结为线性规划问题. 线性规划问题一般用图解法，其步骤如下： （1）根据题意，设出变量x、y； （2）找出线性约束条件； （3）确定线性目标函数z=f（x，y）； （4）画出可行域（即各约束条件所示区域的公共区域）； （5）利用线性目标函数

3、作平行直线系f（x，y）=t（t为参数）； （6）观察图形，找到直线f（x，y）=t在可行域上使t取得欲求最值的位置，以确定最优解，给出答案。,例. 画出不等式 表示的平面区域.,思路分析：遵循直线定界，特殊点定域的方法即可.,不等式 表示的区域如图,点评与感悟：这是处理线性规划问题的基础，必须仔细体会.,例.在平面直角坐标系中，不等式组 表示的平面区域的面积是（ ）,(A) (B) 4 (C) (D) 2,思路分析：本题考查简单的线性规划的可行域、三角形的面积.,于是，三角形 的面积为 故选（B）.,【答案】 B,例.设x,y满足约束条件 ， 分别求：(1)z=6x+10y；(2)z=2x-

4、y；(3)z=2x-y， (x,y均为整数)的最大值，最小值。,解：（1）先作出可行域，如图所示中 的区域，,图7.4-7,且求得A(5,2),B(1,1),C(1, ),作出直线L0：6x+10y=0，再将直线L0平移 当L0的平行线过B点时，可使z=6x+10y达到最小值 当L0的平行线过A点时，可使z=6x+10y达到最大值 所以zmin=16;zmax=50 作出直线L0：6x+10y=0，再将直线L0平移 当L0的平行线过B点时，可使z=6x+10y达到最小值 当L0的平行线过A点时，可使z=6x+10y达到最大值 所以zmin= 16;zmax=50,（3）同上，作出直线L0：2x

5、-y=0，再将直线L0平移，,当L0的平行线过C点时，可使z=2x-y达到最小值 ,当L0的平行线过A点时，可使z=2x-y达到最大值8,点评与感悟： (1)线性目标函数的最大（小）值一般在可行域的顶点处取得，也 可能在边界处取得。(如：上题第一小题中z=6x+10y的最大值可以 在线段AC上任一点取到)。（2）求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义在y轴上的截距或其相反数。,但由于 不是整数，而最优解（x,y）中，x,y必须都是整数， 所以可行域内的点C(1, )不是最优解，当L0的平行线经过可 行域内的整点(1,4)时，可使z=2x-y达到最小值，所以zmin=-2

6、,解：由题得 ,由于乘汽车、摩托车所需的时间和 应满足：,，因此满足上述条件的 点（x,y）的范围是图中的阴影部分 （包括边界）,（2） P=100+3(5-x)+2(8-y),要使p最小，则131-p最大。在图中的阴影部分区域（包括边界） 且斜率为 的直线 中，使k值最大的直,线必通过点（10，4），即当x=10, y=4时p最小。 此时，v=12.5. w=30, p的最小值为39元。,点评与感悟：要能从实际问题中，建构有关线性规划问题的 数学模型,例.某厂拟生产甲、乙两种适销产品，每件销售收入分别 为3千元、2千元.甲、乙产品都需要在A，B两种设备上加工 ，在每台A，B上加工一件甲所需工时分别为1小时、2小时， 加工一件乙所需工时分别为2小时、1小时，A，B两种设备 每月有效使用台时数分别为400和500.如何安排生产可使收 入最大？,思路分析:这个问题的数学模型是二元线性规划.为此，需要确定线性约束条件和线性目标函数.,解:设甲、乙两种产品的产量分别为x、y则约束,点评与感悟：线性规划的实际问