简单的线性规划问题zst教程课件.ppt

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

1、3.3.3简单的线性规划问题简单的线性规划问题 实际应用实际应用二、二、Ax+By+C0(A2+B20)一、直线一、直线y=kx+by=kx+b把平面分成两个区域把平面分成两个区域 ykx+bykx+b表示直线表示直线 方的平面区域；方的平面区域；ykx+bykx+b表示直线表示直线 方的平面区域方的平面区域.上下直线定界，特殊点定域直线定界，特殊点定域画出不等式组画出不等式组 表示的平面区域。表示的平面区域。OXYx+y=0 x=3x-y+5=0注：不等式组表示的平面区域是各不等式所表示注：不等式组表示的平面区域是各不等式所表示 平面区域的公共部分。平面区域的公共部分。例例1某工厂生产甲、乙

2、两种产品，生产某工厂生产甲、乙两种产品，生产1t甲两甲两种产品需要种产品需要A种原料种原料4t、B种原料种原料12t，产生的，产生的利润为利润为2万元；生产乙种产品需要万元；生产乙种产品需要A种原料种原料1t、B种原料种原料9t，产生的利润为，产生的利润为1万元。现有库存万元。现有库存A种原料种原料10t、B种原料种原料60t，如何安排生产才能，如何安排生产才能使利润最大？使利润最大？分析：在关数据列表如下：分析：在关数据列表如下：A种原料 B种原料利润甲种产品4 122 乙种产品1 9 1现有库存10 60 设生产甲种产品x吨，乙种产品y吨。设生产甲、乙两种产品的吨数分别为设生产甲、乙两种产

3、品的吨数分别为x、y利润利润何时达到最大？何时达到最大？xYo4x4xy=10y=1012x12x9y=609y=602x+y=02x+y=0转化转化转化转化转化转化四个步骤四个步骤：1。画画（画可行域）（画可行域）三个转化三个转化4。答答（求出点的坐标，并转化为最优解）（求出点的坐标，并转化为最优解）3。移移（平移直线（平移直线L。寻找使纵截距取得最值时的点）。寻找使纵截距取得最值时的点）2。作作（作（作z=Ax+By=0时的直线时的直线L。）。）图图解解法法想一想想一想(结论结论):):线性约束条件线性约束条件可行域可行域线性目标函数线性目标函数Z=Ax+By一组平行线一组平行线最优解最优

4、解寻找平行线组的寻找平行线组的 最大（小）纵截距最大（小）纵截距例2.某厂拟生产甲、乙两种适销产品，每件销售收入分某厂拟生产甲、乙两种适销产品，每件销售收入分别为别为3000元、元、2000元，甲、乙产品都需要在元，甲、乙产品都需要在A、B两种两种设备上加工，在每台设备上加工，在每台A、B上加工上加工1件甲所需工时分别为件甲所需工时分别为1h、2h，A、B两种设备每月有效使用台数分别为两种设备每月有效使用台数分别为400h和和500h。如何安排生产可使收入最大？。如何安排生产可使收入最大？解：设每月生产甲产品设每月生产甲产品x件，生产乙产品件，生产乙产品y件，每月件，每月收入为收入为z，目标函

5、数为，目标函数为Z3x2y，满足的条件是，满足的条件是 Z 3x2y 变形为变形为它表示斜率为它表示斜率为 的直线系，的直线系，Z与这条直线的截距有关。与这条直线的截距有关。XYO400200250500 当直线经过点当直线经过点M时，截距最大，时，截距最大，Z最大。最大。M解方程组解方程组可得可得M（200，100）Z 的最大值的最大值Z 3x2y800故生产甲产品故生产甲产品200件，件，乙产品乙产品100件，收入件，收入最大，为最大，为80万元。万元。给定一定量的给定一定量的人力人力.物力物力,资金等资源资金等资源完成的任务量最大完成的任务量最大经济效益最高经济效益最高给定一项任务给定一

6、项任务所耗的人力所耗的人力.物力资源最小物力资源最小降低成本降低成本获取最大的利润获取最大的利润精打细算精打细算最优方案最优方案统筹安排统筹安排最佳方案最佳方案实际应用实际应用三、练习题三、练习题：1、求求z2xy的最大值，使的最大值，使x、y满足约束条件满足约束条件：2、求求z3x5y的最大值，使的最大值，使x、y满足约束条件：满足约束条件：1.解：作出平面区域解：作出平面区域xyABCoz2xy 作出直线作出直线y=2xz的图的图像，可知像，可知z要求最大值，即要求最大值，即直线经过直线经过C点时。点时。求得求得C点坐标为（点坐标为（2，1），），则则Zmax=2xy32.解：作出平面区域

7、解：作出平面区域xyoABCz3x5y 作出直线作出直线3x5y z 的图的图像，可知直线经过像，可知直线经过A点时，点时，Z取最大值；直线经过取最大值；直线经过B点点时，时，Z取最小值。取最小值。求得求得A（1.5，2.5），），B（2，1），），则则Zmax=17，Zmin=11。课堂练习课堂练习课本P80,练习14转化转化转化转化转化转化四个步骤四个步骤：1。画画（画可行域）（画可行域）三个转化三个转化4。答答（求出点的坐标，并转化为最优解）（求出点的坐标，并转化为最优解）3。移移（平移直线（平移直线L。寻找使纵截距取得最值时的点）。寻找使纵截距取得最值时的点）2。作作（作（作z=Ax+

8、By=0时的直线时的直线L。）。）图图解解法法小结小结:线性约束条件线性约束条件可行域可行域线性目标函数线性目标函数Z=Ax+By一组平行线一组平行线最优解最优解寻找平行线组的寻找平行线组的 最大（小）纵截距最大（小）纵截距课后作业课后作业双测双测P53,P54 例例2某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产甲种产品已知生产甲种产品1t需需消耗消耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产乙种产品；生产乙种产品1吨需消耗吨需消耗A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t.每每1t甲种产品甲种产品的利润是的利润是600元元,每每1t乙种产品的利润是乙种产

9、品的利润是1000元元.工厂在工厂在生产这两种产品的计划中要求消耗生产这两种产品的计划中要求消耗A种矿石不超过种矿石不超过300t、消耗消耗B种矿石不超过种矿石不超过200t、消耗煤不超过、消耗煤不超过360t.若你是若你是厂长厂长,你应如何安排甲乙两种产品的产量你应如何安排甲乙两种产品的产量(精确到精确到0.1t),才能使利润总额才能使利润总额达到最大达到最大?某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产甲种产品已知生产甲种产品1t需消耗需消耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产乙种产品；生产乙种产品1吨需消耗吨需消耗A种矿石种矿石4t、B种矿石种矿石4t

10、、煤、煤9t.每每1t甲种产品的利润是甲种产品的利润是600元元,每每1t乙种产品的利润乙种产品的利润是是1000元元.工厂在生产这两种产品的计划中要求消耗工厂在生产这两种产品的计划中要求消耗A种矿石不超种矿石不超过过300t、消耗消耗B种矿石不超过种矿石不超过200t、消耗煤不超过、消耗煤不超过360t.若你是若你是厂长厂长,你应如何安排甲乙两种产品的产量你应如何安排甲乙两种产品的产量(精确到精确到0.1t),才能使利润才能使利润总额达到最大总额达到最大?分分析析问问题题:1.本问题给定了哪些原材料本问题给定了哪些原材料(资源资源)?2.该工厂生产哪些产品该工厂生产哪些产品?3.各种产品对原

11、材料各种产品对原材料(资源资源)有怎样的要求有怎样的要求?4.该工厂对原材料该工厂对原材料(资源资源)有何限定条件有何限定条件?5.每种产品的利润是多少每种产品的利润是多少?利润总额如何计算利润总额如何计算?解解:设生产甲、乙两种产品设生产甲、乙两种产品.分别为分别为x t、yt,利润总额为利润总额为z元元,那么那么10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.画画出以上不等式组所表示的可行域出以上不等式组所表示的可行域作作出直线出直线L 600 x+1000y=0.解得交点解得交点M的坐标为的坐标为(12.4,34.4)5x+4y=2004x+9

12、y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:应生产甲产品约应生产甲产品约12.4吨，乙产品吨，乙产品34.4吨，能使利润总额达到最大。吨，能使利润总额达到最大。(12.4,34.4)经经过过可可行行域域上上的的点点M时时,目目标标函函数数在在y轴上截距最大轴上截距最大.9030 0 xy10 201075405040此时此时z=600 x+1000y取得最大值取得最大值.例3.gsp图形把直线把直线L向右上方平向右上方平移移实际问题实际问题线性规划问题线性规划问题寻找约束条件寻找约束条件建立目标函数建立目标函数列表列表设立变量设立变

13、量转转化化1.约束条件要写全约束条件要写全;3.解题格式要规范解题格式要规范.2.作图要准确作图要准确,计算也要准确计算也要准确;注意注意:结论结论1:1:例例3.某某工工厂厂现现有有两两种种大大小小不不同同规规格格的的钢钢板板可可截截成成A、B、C三三种种规规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：解：设需截第一种钢板设需截第一种钢板x张，第二种钢板张，第二种钢板y张，张，钢板钢板总总张数为张数为Z,则则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格212131

14、2x+y15,x+2y18,x+3y27,x0y0 某顾客需要某顾客需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，块，若你是若你是经理经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。数最少。x张张y张张分分析析问问题题:目标函数目标函数:z=x+yx0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,y0直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解.作出直线作出直线L:x+y=0，目标函数目

15、标函数:z=x+yB(3,9)C(4,8)A(3.6,7.8)当直线当直线L经过点经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）约束条件约束条件:画可行域画可行域平移平移L找交点及交点坐标找交点及交点坐标调整优解法调整优解法1.满足哪些条件的解才是最优解满足哪些条件的解才是最优解?2.目标函数经过目标函数经过A(3.6,7.8)时时Z的值是多少的值是多少?你能否猜测一下你能否猜测一下Z的最小值可能是多少的最小值可能是

16、多少?3.最优解的几何意义是什么最优解的几何意义是什么(最优解可以转化为什么几何意义最优解可以转化为什么几何意义)?图例题4.gsp示x0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xN*y0 yN*经经过过可可行行域域内内的的整整点点B(3,9)和和C(4,8)且且和和原原点点距距离离最最近近的的直直线线是是x+y=12，它们是最优解，它们是最优解.作出一组平行直线作出一组平行直线t=x+y，目标函数目标函数t=x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线

17、经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，1212182715978把把实际问题实际问题转化成转化成线性规划问题线性规划问题即建立数学即建立数学模型的方法。大致可分为以下三个模型的方法。大致可分为以下三个步骤：步骤：（1）准确建立数学模型，即根据题意找）准确建立数学模型，即根据题意找出约束条件，确定线性目标函数；出约束条件，确定线性目标函数；（2）用图解法求得数学模型的解，即画）用图解法求得数学模型的解，即画出可行域，在可行域内求得使目标函数取得出可行域，在可行域内求得使目标函数取得最值的解；最

18、值的解；（3）根据实际意义将数学模型的解转化）根据实际意义将数学模型的解转化为实际问题的解，即结合实际情况求得最优为实际问题的解，即结合实际情况求得最优解。解。即先求非整数条件下的最优解，即先求非整数条件下的最优解，调整调整Z的值使不定方程的值使不定方程Ax+By=Z存在最大（小）存在最大（小）的整点值，最后筛选出整点最优解的整点值，最后筛选出整点最优解 即先打网格，描出可行域内的即先打网格，描出可行域内的整点整点，平移直线，最先经过或最后经过的整点坐平移直线，最先经过或最后经过的整点坐标即为最优整解标即为最优整解线性规划求最优整数解的一般方法线性规划求最优整数解的一般方法:1.1.平移找解法

19、：平移找解法：2.2.调整优解法调整优解法：结论结论2:2:小结小结:实际问题实际问题列表列表设出变量设出变量寻找约束条件寻找约束条件建立目标函数建立目标函数转化转化建模建模线性规划问题线性规划问题图解法图解法最优解最优解三三个个转转化化四个步骤四个步骤作作答答调调整整最优整数解最优整数解平移找解法平移找解法调整优值法调整优值法常用方法常用方法目目标标函函数数距离距离,斜率等斜率等5x+4y=202x+3y=12线性目标函数Z的最大值为的最大值为44已知实数已知实数x,y满足下列条件满足下列条件:5x+4y 202x+3y 12x 0y0求求z=9x+10y的最大值的最大值.最优解可行域9x+10y=0想一想想一想:线性约束条件 01 2345 6123456xy代数问题代数问题(线性约束条件线性约束条件)图解法图解法转化转化线性约线性约束条件束条件可行域可行域转化转化线性目线性目标函数标函数Z=Ax+By一组平行线一组平行线转化转化最优解最优解寻找平行线组寻找平行线组的纵截距的纵截距 最值最值四个步骤：四个步骤：1、画画4、答答3、移移2、作作三个转化三个转化一一.复习复习