线性规划课件.ppt

线性规划,复习引入,例题分析,课堂练习,课堂总结,课题：线性规划,使z=2x+y取得最大值的可行解，且最大值为；,复习引入,1.已知二元一次不等式组,（1）画出不等式组所表示的平面区域；,满足的解(x,y)都叫做可行解；,z=2x+y叫做；,（2）设z=2x+y，则式中变量x,y满足的二元一次不等式组叫做x,y的；,y=-1,x-y=0,x+y=1,2x+y=0,(-1,-1),(2,-1),3,使z=2x+y取得最小值的可行解，且最小值为；这两个可行解都叫做问题的。,例题分析,分析（1）线性规划问题大致可以分为两种类型:一种是给定一定数量的人力、物力资源，问怎样安排这些资源能使完成任务量最大，收到的效益最大；第二类是给定一项任务，问怎样统筹安排，能使完成这项任务的人力，物力资源量最小。解决这两类问题的共同点是寻求在约束条件下，某项整体指标的最大值。,（2）线性规划问题可以按照下列步骤求解：,找出全约束条件,列出目标函数,作出可行域,求出最优解,回答实际问题,例1:某工厂生产甲、乙两种产品.已知生产甲种产品1吨需消耗A种矿石10吨、B种矿石5吨、煤4吨；生产乙种产品1吨需消耗A种矿石4吨、B种矿石4吨、煤9吨.每1吨甲种产品的利润是600元,每1吨乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300吨、消耗B种矿石不超过200吨、消耗煤不超过360吨.甲、乙两种产品应各生产多少(精确到0.1吨),能使利润总额达到最大?,例题分析,解:设生产甲、乙两种产品.分别为x吨、y吨,利润总额为z元,那么,10 x+4y300,5x+4y200,4x+9y360,x0,y0,z=600 x+1000y.,作出以上不等式组所表示的可行域,作出一组平行直线600 x+1000y=t，,10 x+4y=300,5x+4y=200,4x+9y=360,600 x+1000y=0,M,答:(略),(12.4,34.4),经过可行域上的点M时,目标函数在y轴上截距最大.此时z=600 x+1000y取得最大值.,例题分析,例2要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：,解：设需截第一种钢板x张，第一种钢板y张，则,作出可行域（如图）,目标函数为z=x+y,今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。,例题分析,2x+y=15,x+3y=27,x+2y=18,x+y=0,经过可行域内的整点B(3,9)和C(4,8)且和原点距离最近的直线是x+y=12，它们是最优解.,答:(略),作出一组平行直线t=x+y，,目标函数t=x+y,打网格线法,在可行域内打出网格线，,当直线经过点A时t=x+y=11.4,但它不是最优整数解，,将直线x+y=11.4继续向上平移，,例题分析,2x+y=15,x+3y=27,x+2y=18,x+y=0,直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.答（略）,作出一组平行直线t=x+y，,目标函数t=x+y,当直线经过点A时t=x+y=11.4,但它不是最优整数解.作直线x+y=12,x+y=12,解得交点B,C的坐标B(3,9)和C(4,8),调整优值法,巩固练习,300,600,A(100,400),1.某家具厂有方木材90m3，五合板600m3，准备加工成书桌和书橱出售，已知生产每张书桌需要方木料0.1m3、五合板2m3；生产每个书橱需要方木料0.2m3，五合板1m3，出售一张书桌可以获利80元，出售一张书橱可以获利120元；,（1）怎样安排生产可以获利最大？,（2）若只生产书桌可以获利多少？,（3）若只生产书橱可以获利多少？,解（1）设生产书桌x张，书橱y张，利润为z元，则约束条件为,Z=80 x+120y,作出不等式表示的平面区域，,当生产100张书桌，400张书橱时利润最大为z=80100+120400=56000元,（2）若只生产书桌可以生产300张，用完五合板，可获利24000元；,（3）若只生产书橱可以生产450张，用完方木料，可获利54000元。,将直线z=80 x+120y平移可知：,900,450,巩固练习,4,x=8,y=4,x+y=10,4x+5y=30,320 x+504y=0,2.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务，该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车4次，B型卡车3次，每辆卡车每天往返的成本费A型卡车为320元，B型卡车为504元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？(要求每型卡车至少安排一辆）,解：设每天调出的A型车x辆，B型车y辆，公司所花的费用为z元，则,Z=320 x+504y,作出可行域中的整点，,可行域中的整点（5，2）使Z=320 x+504y取得最小值，且Zmin=2608元,答（略）,作出可行域,小结,1.在解线性规划应用问题时，其一般思维过程如下：,（1）设出决策变量，找出线性规划的约束条件和线性目标函数；,（2）利用图像，在线性约束条件下找出决策变量，使目标函数达到最大或最小；,2.解线性规划应用问题的一般模型是：先列出约束条件组,再求c1x1+c2x2+cnxn的最大值或最小值；,3.线性规划的讨论范围：教材中讨论了两个变量的线性规划问题，这类问