简单的线性规划问题.ppt

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

1、-可行域上的最优解,3.3.2 简单的线性规划问题(1),一.问题情境,1.在同一坐标系上作出下列直线，你能得到什么结论？,2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7,x,Y,o,问题：你知道2x+y=t中t的几何意义么？2x-y=t中t的几何意义呢？,y,问题1：x 有无最大（小）值？,问题2：y 有无最大（小）值？,问题3：z=2x+y 有无最大（小）值？,2.作出下列不等式组的所表示的平面区域,二.提出问题,把上面的问题综合起来:,设z=2x+y,求满足,时,求z的最大值和最小值.,y,直线L越往上平移,z随之增大.,以经过点A(5,2)的直线所对应的t值最大

2、;经过点B(1,1)的直线所对应的t值最小.,可以通过比较可行域顶点的目标函数值大小得到。,思考：还可以运用怎样的方法得到目标函数的最大、最小值？,线性规划,问题： 设z=2x+y，式中变量满足 下列条件： 求z的最大值与最小值。,目标函数 （线性目标函数）,线性约 束条件,象这样对变量x,y的约束条件称为线性约束条件,Z=2x+y称为目标函数,(因这里目标函数为关于x,y的一次式,又称为线性目标函数,线性规划定义,线性规划：求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题,可行解 ：满足线性约束条件的解(x，y)叫可行解；,可行域 ：由所有可行解组成的集合叫做可行域；

3、,最优解 ：使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。,可行域,2x+y=3,2x+y=12,(1,1),(5,2),线性目标函数,线性约束条件,线性规划问题,任何一个满足不等式组的（x,y）,可行解,可行域,所有的,最优解,目标函数所表示的几何意义在y轴上的截距或与其 相关。,线性规划相关名称,求线性规划最优解的方法：图解法 图解法的一般步骤： 第一步：画：在平面直角坐标系中画出可行域； 第二步：移：平移初始直线L0，在可行域内找到最优解所对应的点； 第三步：求：通过解方程组求出最优解。,画-移-求,10,线性规划,例1 解下列线性规划问题： 求z=2x+y的最大值和最小值，

4、使式中x、y满足下 列条件：,2x+y=0,2x+y=-3,2x+y=3,答案：当x=-1,y=-1时，z=2x+y有最小值3.,当x=2,y=-1时，z=2x+y有最大值3.,也可以通过比较可行域顶点的目标函数值大小得到。,例2.营养学家指出,成人良好的日常饮食应该至少提供0.075kg的碳水化合物,0.06kg的蛋白质,0.06kg的脂肪.1kg食物A含有0.105kg碳水化合物,0.07 kg的蛋白质, 0.14kg的脂肪,花费28元;而1kg食物B含有0.105kg碳水化合物,0.14 kg的蛋白质, 0.07kg的脂肪,花费21元.为了满足营养学家指出的日常饮食要求,同时使花费最低,

5、需要同时食用食物A和食物B多少kg?,分析:将已知数据列成下表,0.07,0.14,0.105,0.14,0.07,0.105,解:设每天食用xkg食物A, ykg食物B, 总成本为z元. 那么x,y满足的约束条件是:,目标函数为z=28x+21y,二元一次不等式组等价于,作出二元一次不等式组所 表示的平面区域，即可行域.,这是斜率为 、在y轴上的截距为 的一组平行直线.,解方程组,得M的坐标为,所以zmin=28x+21y=16.,答：每天食用食物A约为143g，食物B约571g，能够满足日常饮食要求，又使花费最低，最低成本为16元.,法2：算线性目标函数的最大（小）值一般在可行域的顶点处取

6、得.,法1：移在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；,解线性规划应用题的一般步骤：,2）列：列出约束条件和目标函数,3）解：利用图解法寻求最优解对应的点,4）联：联立方程组解出最优解,1）设：设好变量,5) 答：回答实际问题,画出线性约束条件所表示的可行域，画图力保准确；,设-列-解-联-答,3,5,1,A,B,(1.5,2.5),(-2,-1),Z max=17 Z min=-11,求z=3x+5y的最大值和最小值,使x、y满足约束条件,C,3x+5y=0,练习,变式1.若求z=x-2y的最大值和最小值呢？, -z/2最小时，z最大

7、-z/2最大时，z最小,故过点C时，z最大， 过点B时，z最小.,zmax=3 zmin=-3.5,练习,变式2.使z=x-y取得最小值的最优解有几个?,注：一般，目标函数的最优解是唯一的（在可行域的顶点处取得） ，有时是不唯一的（在可行域的边界取得）。,练习2：,已知 (1)求z=2x+y的最优解。 (2)求z=2x-y的最优解。,18,法2：算线性目标函数的最大（小）值一般在可行域的顶点处取得.,法1：移在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；,解线性规划应用题的一般步骤：,2）列：列出约束条件和目标函数,3）解：利用图解法寻求最优解对应的点,4）联：联立方程组解出最优解,1）设：设好变量,5) 答：回答实际问题,画出线性约束条件所表示的可行域，画图力保准确；,设-列-解-联-答,小结,