简单的线性规划问题最新版本

1、3.3.2 简单的线性规划问题简单的线性规划问题(1)一一.问题情境问题情境1.在同一坐标系上作出下列直线，你能得到什么结论？在同一坐标系上作出下列直线，你能得到什么结论？2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7.02)0(2:平平行行的的直直线线与与形形如如结结论论 yxttyxxYo问题：你知道问题：你知道2x+y=t中中t的几何意义么？的几何意义么？2x-y=t中中t的的几何意义呢？几何意义呢？55x=1x-4y+3=03x+5y-25=01ABCC: (1, 4.4)A: (5, 2)B: (1, 1)Oxy问题问题1 1：x 有无最大（小）值？有无最大（

2、小）值？问题问题2 2：y 有无最大（小）值？有无最大（小）值？问题问题3 3：z=2z=2x+y 有无最大（小）值？有无最大（小）值？1255334xyxyx2.作出下列不作出下列不等式组的所表等式组的所表示的平面区域示的平面区域二二.提出问题提出问题把上面的问题综合起来把上面的问题综合起来:1255334xyxyx设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.55x=1x-4y+3=03x+5y-25=01ABCC: (1, 4.4)A: (5, 2)B: (1, 1)Oxy.1255334. 1所表示的区域所表示的区域先作出先作出 xyxyx02 yx02:

3、0. 20yxlz作直线令Rzzyxll,2:. 30直线平行的作一组与直线直线直线L L越往上平越往上平移移,z,z随之增大随之增大. .以经过点以经过点A(5,2)A(5,2)的的直线所对应的直线所对应的t t值值最大最大; ;经过点经过点B(1,1)B(1,1)的直线所对应的的直线所对应的t t值最小值最小. .3112,12252minmax ZZ 可以通过比较可行域顶点的可以通过比较可行域顶点的目标函数值大小得到。目标函数值大小得到。思考：还可以运用怎样的方法得到目标函数思考：还可以运用怎样的方法得到目标函数的最大、最小值？的最大、最小值？线性规划问题：设z=2x+y，式中变量满足下

4、列条件： 求z的最大值与最小值。 1255334xyxyx 目标函数目标函数（线性目标函数）（线性目标函数）线性约线性约束条件束条件象这样对象这样对变量变量x,yx,y的约束条的约束条件称为件称为线线性约束性约束条条件件Z=2x+yZ=2x+y称为目标函数称为目标函数,( ,(因因这里目标函数为关于这里目标函数为关于x,yx,y的的一次式一次式, ,又称为又称为线性目标函线性目标函数数线性规划定义线性规划定义线性规划：线性规划：求线性目标函数在线性约束条件下的最求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题大值或最小值的问题，统称为线性规划问题 可行解可行解 ：满足线

5、性约束条满足线性约束条件的解件的解(x，y)叫可行解；叫可行解； 可行域可行域 ：由所有可行解组由所有可行解组成的集合叫做可行域；成的集合叫做可行域； 最优解最优解 ：使目标函数取得使目标函数取得最大或最小值的可行解叫最大或最小值的可行解叫线性规划问题的最优解。线性规划问题的最优解。 可行域可行域2x+y=32x+y=12(1,1)(5,2)1255334xyxyx设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.线性目线性目标函数标函数线性约线性约束条件束条件线性规线性规划问题划问题任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域

6、所有的所有的最优解最优解目标函数所表目标函数所表示的几何意义示的几何意义在在y轴上轴上的截距或与其的截距或与其相关。相关。线性规划相关名称线性规划相关名称求线性规划最优解的方法：求线性规划最优解的方法：图解法图解法图解法图解法的一般步骤：的一般步骤：第一步：第一步：画画：在平面直角坐标系中画出可行域；：在平面直角坐标系中画出可行域；第二步：第二步：移移：平移初始直线：平移初始直线L0，在可行域内找到最优，在可行域内找到最优解所对应的点；解所对应的点；第三步：第三步：求求：通过解方程组求出最优解。：通过解方程组求出最优解。整理ppt10线性规划例例1 解下列线性规划问题： 求z=2x+y的最大值

7、和最小值，使式中x、y满足下列条件：11yyxxy2x+y=02x+y=-32x+y=3答案：当x=-1,y=-1时，z=2x+y有最小值3.当x=2,y=-1时，z=2x+y有最大值3. 也可以通过比较可行域顶点也可以通过比较可行域顶点的目标函数值大小得到。的目标函数值大小得到。例例2.2.营养学家指出营养学家指出, ,成人良好的日常饮食应该至少提供成人良好的日常饮食应该至少提供0.075kg0.075kg的碳水化合物的碳水化合物,0.06kg,0.06kg的蛋白质的蛋白质,0.06kg,0.06kg的脂肪的脂肪.1kg.1kg食物食物A A含有含有0.105kg0.105kg碳水化合物碳水

8、化合物,0.07 kg,0.07 kg的蛋白质的蛋白质, 0.14kg, 0.14kg的脂肪的脂肪, ,花费花费2828元元; ;而而1kg1kg食物食物B B含有含有0.105kg0.105kg碳水化合物碳水化合物,0.14 kg,0.14 kg的蛋白质的蛋白质, , 0.07kg0.07kg的脂肪的脂肪, ,花费花费2121元元. .为了满足营养学家指出的日常饮食要为了满足营养学家指出的日常饮食要求求, ,同时使花费最低同时使花费最低, ,需要同时食用食物需要同时食用食物A A和食物和食物B B多少多少kg?kg?分析分析: :将已知数据列成下表将已知数据列成下表0.070.140.105

9、0.140.070.105BA脂肪脂肪/kg蛋白质蛋白质/kg碳水化合物碳水化合物/kg食物食物/kg解解:设每天食用设每天食用xkg食物食物A, ykg食物食物B, 总成本为总成本为z元元. 那么那么x,y满足的约束条件是满足的约束条件是:0 1050 1050 0750 070 140 060 140 070 06 00.x.y.,.x.y.,.x.y.,x,y.目标函数为目标函数为z=28x+21y . 0, 0 , 6714, 6147, 577yxyxyxyx二元一次不等式组二元一次不等式组等价于等价于作出二元一次不等式组作出二元一次不等式组所所表示的平面区域，即可行域表示的平面区域

10、，即可行域. . 775xy1476xy7146xy42821321zzxyyx 可化为34 这是斜率为这是斜率为 、在、在y轴上的截距为轴上的截距为 的一组平行直线的一组平行直线. .21zxyo737475761737576由图知由图知,当直线当直线经过可行域上点经过可行域上点M时时,截距截距21z最小最小, 即即z最小最小.解方程组解方程组7751476xy,xy, 得得M的坐标为的坐标为14()77,.所以所以zmin=28x+21y=16.答：每天食用食物答：每天食用食物A约为约为143g，食物，食物B约约571g，能够满足日常，能够满足日常饮食要求，又使花费最低，最低成本为饮食要求

11、，又使花费最低，最低成本为16元元.4321zyx 775xy1476xy7146xyxyo737475761737576M法法2 2：算线性目标函数的最大（小）值：算线性目标函数的最大（小）值一般一般在可行域的顶点处取在可行域的顶点处取得得. .法法1 1：移在线性目标函数所表示的一组平行线中，利用平移的：移在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；方法找出与可行域有公共点且纵截距最大或最小的直线； 解线性规划应用题的一般步骤解线性规划应用题的一般步骤：2）列列：列出约束条件和目标函数：列出约束条件和目标函数3）解解：利用：利用图解法图解

12、法寻求最优解对应的点寻求最优解对应的点4）联联：联立方程组解出最优解联立方程组解出最优解1）设设：设好变量设好变量5) 答答：回答实际问题：回答实际问题画出线性约束条件所表示的可行域，画图力保准确；画出线性约束条件所表示的可行域，画图力保准确；5315,1,53.xyyxxy 351ABxyo5315xy1yx53xy(1.5,2.5)(-2,-1)Z max=17Z min=-11求求z=3x+5y的最大值和最小值的最大值和最小值,使使x、y满足约束条件满足约束条件C3x+5y=0练习练习351ABxyo5315xy1yx53xy(1.5,2.5)(-2,-1)C变式变式1.若求若求z=x-

13、2y的最大值和最小值呢？的最大值和最小值呢？1222zz xyyx -z/2最小时，最小时，z最大最大 -z/2最大时，最大时，z最小最小故过点故过点C时，时，z最大，最大， 过点过点B时，时，z最小最小.zmax=3zmin=-3.5练习练习变式变式2.使使z=x-y取得最小值的最优解有几个取得最小值的最优解有几个?5315,1,53.xyyxxy 注：一般，目标函数的最优解是唯一的（在可行域的顶点处取得）注：一般，目标函数的最优解是唯一的（在可行域的顶点处取得），有时是不唯一的（在可行域的边界取得）。，有时是不唯一的（在可行域的边界取得）。02 yx0 yx练习练习2：已知已知(1)求求z=2x+y的最优解。的最优解。(2)求求z=2x-y的最优解。的最优解。01y01-yx0y-x整理ppt18法法2 2：算线性目标函数的最大（小）值：算线性目标函数的最大（小）值一般一般在可行域的顶点处取在可行域的顶点处取得得. .法法1 1：移在线性目标函数所表示的一组平行线中，利用平移的：移在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；方法找