线性规划.ppt

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

1、道路交通规划道路交通规划与规划有关的例子生产安排规划生产安排规划资源调配资源调配科学配餐科学配餐教学目标教学目标: 1.了解线性规划的意义了解线性规划的意义,了解线性约束条件了解线性约束条件,线性目标函数线性目标函数,可行解可行解,可行域可行域,最优解等基本概念最优解等基本概念; 2.能用图解法解决线性规划问题及一些实际能用图解法解决线性规划问题及一些实际生活中简单的最优化问题生活中简单的最优化问题.教学重点教学重点: 用图解法解决简单的线性规划问题用图解法解决简单的线性规划问题.教学难点教学难点: 用线性规划求实际生活中简单的最优化问题用线性规划求实际生活中简单的最优化问题给定下列命题给定下

2、列命题:在线性规划中在线性规划中,最优解指的是使目标函数取得最大值的变最优解指的是使目标函数取得最大值的变量量x或或y的值的值;最优解指的是目标函数的最大值或最小值最优解指的是目标函数的最大值或最小值;最优解指的是目标函数取得最大值或最小最优解指的是目标函数取得最大值或最小值的可行域值的可行域;最优解指的是使目标函数取得最大值或最最优解指的是使目标函数取得最大值或最小值的可行解小值的可行解.其中正确命题的序号是其中正确命题的序号是 . 营养学家指出，成人日常饮食每天至少要营养学家指出，成人日常饮食每天至少要摄入摄入7575克碳水化合物、克碳水化合物、6060克蛋白质和克蛋白质和6060克脂肪。

3、克脂肪。现有甲乙两种食物，在每千克甲中含现有甲乙两种食物，在每千克甲中含105105克碳克碳水化合物，水化合物，7070克蛋白质、克蛋白质、140140克脂肪，花费为克脂肪，花费为2828元，在每千克乙中含元，在每千克乙中含105105克碳水化合物，克碳水化合物，140140克蛋白质、克蛋白质、7070克脂肪，花费为克脂肪，花费为2121元，请设计出元，请设计出符合营养学家要求并且花费最少的营养配餐。符合营养学家要求并且花费最少的营养配餐。 例例1 1：（配餐问题）：（配餐问题）整理数据，列表得：食物（千克）碳水化合物（千克）蛋白质（千克）脂肪（千克）甲0.1050.070.14乙0.1050

4、.140.07最少摄入量0.0750.060.06xy解：设每天选择甲千克，乙 千克。根据条件得不等式组 0006. 007. 014. 006. 014. 007. 0075. 0105. 0105. 0yxyxyxyx即： 0067146147577yxyxyxyx7676757574747373727271710 06147 yx577 yx6714 yx作出二元一次不等式组所表示的平面区域 0067146147577yxyxyxyxxy76767574747373727271710 0设z=28x+21y，求z的最小值。第一步：点（x，y）在此平面区域内运动时，如何求z=28x+21y

5、的最小值。第二步：由z=28x+21y得：2134zxy 直线与此平面区域有公共点，求z的最小值。，当这族第三步：在区域内找一点，使直线经过该点时在y轴上的截距最小。6147 yx75577 yx6714 yxMyxN解方程组： 6714577yxyx571. 074,143. 071 yx162128min yxz得M 点的坐标为所以答：每天食用食物A 143g，食物B 571g，能够满足日常饮食要求，又使花费最低，最低成本为16元。例1变式：若在上题条件之下想要食物总量最少，应怎样找到符合医生要求且摄入食物总量最少的营养配餐？ 讨论：相对于例1，只有目标函数发生变化，yxz 设z为进食总量

6、 76767574747373727271710 0设z=x+y，求z的最小值。6147 yx75577 yx6714 yx当直线z=x+y与直线7x+7y=5重合时在y轴上的截距最小，所以线段MN上所有点表示的解都是最优解。xyMN思考：n 实际的线性规划问题中可能还会出现其他情况，比如要求解为整数等等，我们该怎么处理呢？ 例题分析例例2 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板截成A、B、C三种规格，每三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，

7、第一种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图作出可行域（如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问各截这两种块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。钢板多少张可得所需三种规格成品，且使所用钢板张数最少。返回返回X张张y张张例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y

8、27,x0, xN*y0 yN*直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解. 作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z= x+y返回返回B(3,9)C(4,8)A(18/5,39/5)当直线经过点当直线经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x

9、+y15,x+2y18,x+3y27,x0, xN*y0 yN*经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)且和原点距离最近的直线是且和原点距离最近的直线是x+y=12，它们是最优解，它们是最优解.答答:(略略)作出一组平行直线作出一组平行直线t = x+y，目标函数目标函数t = x+y返回返回B(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，12121827159

10、78不等式组不等式组 表示的平面区域内表示的平面区域内的的整数点整数点共有（共有（ ）个）个123400yxyx巩固练习巩固练习1:1 2 3 4 xy432104x+3y=12在可行域内找出最优解、线性规划在可行域内找出最优解、线性规划整数解问题的一般方法是：整数解问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然后在可行域内适当，然后在可行

11、域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解络、找整点、平移直线、找出整数最优解yxz 2yx,11yyxxy的最大值，使满足约束条件：求yx-1-1-1-11 11 1y = xx+y = 1y = -10M作图，由二元一次不等式组表示的平面区域作出可行域；平移目

12、标函数的图象，求出最优解；yxz 211yyxxy作图，由二元一次不等式组表示的平面区域作出可行域；平移目标函数的图象，求出最优解；检验，考虑实际意义。 寻找线性约束条件，线性目标函数；练习：课本104页练习第一题的第一小题： 模型建立模型建立一、设目标函数一、设目标函数z=ax+by,当当b0时时,把直线把直线l0向上向上平移时平移时,所对应的所对应的z随之随之增大增大;把直线把直线l0向下向下平移时平移时,所对应的所对应的z随之随之减小减小.二、当二、当b0时，求目标函数时，求目标函数z=ax+by的最大的最大值或最小值的求解程序为值或最小值的求解程序为:(1)作出可行域作出可行域;(2)

13、作出直线作出直线l0:ax+by=0;(3)确定确定l0的平移方向的平移方向,依可行域判断取得最优依可行域判断取得最优 解的点解的点;(4)解相关方程组解相关方程组,求出最优解求出最优解,从而得出目标从而得出目标 函数的最大值或最小值函数的最大值或最小值.请写出请写出:在线性约束条件下在线性约束条件下,当当b0时时,(1)直线直线l0:ax+by=0的平移方向与的平移方向与z=ax+by函函数值的变化趋势的关系数值的变化趋势的关系;(2)求求z=ax+by的最小值或最大值的求解程序的最小值或最大值的求解程序.模型建立模型建立一、设目标函数一、设目标函数z=ax+by,当当b0时时,把直线把直线

14、l0向上向上平移时平移时,所对应的所对应的z随之随之减小减小;把直线把直线l0向下向下平移时平移时,所对应的所对应的z随之随之增大增大.二、当二、当b0时，求目标函数时，求目标函数z=ax+by的最大的最大值或最小值的求解程序为值或最小值的求解程序为:(1)作出可行域作出可行域;(2)作出直线作出直线l0:ax+by=0;(3)确定确定l0的平移方向的平移方向,依可行域判断取得最优依可行域判断取得最优 解的点解的点;(4)解相关方程组解相关方程组,求出最优解求出最优解,从而得出目标从而得出目标 函数的最大值或最小值函数的最大值或最小值.abO-4 -3 -2 -1 1 2 3 44 3 2 1

15、 1 2 3 4-例例8、求、求z=4a2b在约束条件在约束条件1 ab 2,2 a+b 4下的最小值与最大值下的最小值与最大值.ab= 1ab= 2a+b= 4a+b= 24a2b= 0AC解解:作出可行域作出可行域(如右图如右图).作直线作直线 : 4a2b=0.把直线平移把直线平移,使其与可使其与可行域相交行域相交.当直线与可当直线与可行域分别相交于行域分别相交于A,C两点时两点时,所对应的所对应的z分分别最小与最大别最小与最大.例例8、求、求z=4a2b在约束条件在约束条件1 ab 2,2 a+b 4下的最小值与最大值下的最小值与最大值.abO-4 -3 -2 -1 1 2 3 44

16、3 2 1 1 2 3 4-ab= 1ab= 2a+b= 4a+b= 24a2b= 0AC得得A( , ); 1232由由ab= 1a+b= 2得得 C(3,1). 由由ab= 2a+b= 41232zmin=4 2 = 1,zmax=4 32 1=10.作业 1.课本65页第2题 2.名师对话42页1、2、6、7、9、 例例1、解下列线性规划问题：求、解下列线性规划问题：求z=2x+y的最大的最大值值,使式中使式中x、y满足下列条件：满足下列条件：可删可删, 0, 1yxyyxxyO-3 -2 -1 1 2 33 2 1 1 2 3-答案答案:当当x=1，y=0时，时，z=2x+y有最大值有

17、最大值2。x+y=1y=x y=02x+y=0(2004高考全国卷高考全国卷4数学试题（必修数学试题（必修+选修选修甘肃青海甘肃青海宁夏贵州新疆等地区）第宁夏贵州新疆等地区）第16题题) (步骤步骤:画、移、求、答画、移、求、答)zxy2z=2x+y 例例2 、在约束条件、在约束条件x+2y 4,x+2 0 xy 1,下，求目标函数下，求目标函数z=3xy的最小值和最大值。的最小值和最大值。可删可删xyO-4 -3 -2 -1 1 2 3 44 3 2 1 1 2 3 4-x= 2x+2y=4xy =1解解:作出可行域作出可行域(如右图如右图).作直线作直线l0 : 3xy=0.把直线平移把直

18、线平移,使其与使其与可行域相交可行域相交.当直线当直线与可行域分别相交与可行域分别相交于于A,B两点时两点时,所对所对应的应的z分别最小与最大分别最小与最大.l0ABzxy 3xyO-4 -3 -2 -1 1 2 3 44 3 2 1 1 2 3 4-x= 2x+2y=4xy =1l0AB顶点顶点A是直线是直线x+2y=4与直线与直线x+2=0的交点的交点,解方程组解方程组x+2y=4x+2=0可求出顶点可求出顶点A的坐标的坐标(2,3),zmin=3 (2)3= 9.顶点顶点B是直线是直线x+2y=4与与直线直线xy=1的交点的交点,解方解方程组程组 可删可删x+2y=4xy=1可求出顶点可求出顶点B的坐标的坐标(2,1),代入目标函数代入目标函数,即可得最大值即可得最大值zmax=3 21= 5.代入目标函数代入目标函数,即可得最小值即可得最小值