3.5.2《简单线性规划》2

Dingchangwen5x+4y=202x+3y=12线性目标函数),(M720712Z的最大值为44已知实数x,y满足下列条件:5x+4y≤202x+3y≤12x≥0y≥0求z=9x+10y的最大值.最优解可行域9x+10y=0想一想:线性约束条件．．．．．．．．．．．．．0123456123456xy代数问题(线性约束条件)图解法转化线性约束条件可行域转化线性目标函数Z=Ax+By一组平行线BZxy转化最优解寻找平行线组的纵截距最值四个步骤：1、画4、答2、移3、求三个转化一.复习转化转化转化四个步骤：1。画（画可行域）三个转化4。答2。移（平移直线L。寻找使纵截距取得最值时的点）3。求（求出点的坐标，并转化为最优解）图解法想一想(结论):线性约束条件可行域线性目标函数Z=Ax+By一组平行线BZxy最优解寻找平行线组的最大（小）纵截距3x+5y=25例1：已知x、y满足，设z＝ax＋y(a0)，若ｚ取得最大值时，对应点有无数个，求a的值。3x+5y≤25x－4y≤－3x≥1xyox-4y=-3x=1CBＡ解：当直线l：y＝－ax＋z与直线重合时，有无数个点，使函数值取得最大值，此时有：kl＝kAC535124.4∵kAC＝kl=-a53∴-a=∴a=53例2：满足线性约束条件的可行域中共有多少个整数解。x+4y≤113x+２y≤10x0y01223314455xy03x+２y=10x+4y=11解：由题意得可行域如图:由图知满足约束条件的可行域中的整点为(1,1)、(1,2)、(2,1)、(2,2)故有四个整点可行解.给定一定量的人力.物力,资金等资源完成的任务量最大经济效益最高给定一项任务所耗的人力.物力资源最小降低成本获取最大的利润精打细算最优方案统筹安排最佳方案实际应用六个步骤：3、画6、答4、移5、求1、设2、列例4.某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：设需截第一种钢板x张，第二种钢板y张，钢板总张数为Z,则规格类型钢板类型第一种钢板第二种钢板A规格B规格C规格2121312x+y≥15,x+2y≥18,x+3y≥27,x≥0y≥0某顾客需要A,B,C三种规格的成品分别为15，18，27块，若你是经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。x张y张分析问题:求目标函数:z=x+y取最小值时的x,y,xyNx0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,y≥0直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.作出直线L:x+y=0，目标函数: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)246181282724681015但它不是最优整数解.作直线x+y=12答（略）约束条件:画可行域平移L找交点及交点坐标)Ny,x(调整优解法1.满足哪些条件的解才是最优解?2.目标函数经过A(3.6,7.8)时Z的值是多少?你能否猜测一下Z的最小值可能是多少?3.最优解的几何意义是什么(最优解可以转化为什么几何意义)?例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈Ny≥0y∈N直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.作出一组平行直线z=x+y，目标函数z=x+yB(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)调整优值法246181282724681015但它不是最优整数解.作直线x+y=12答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*经过可行域内的整点B(3,9)和C(4,8)时，z=x+y=12是最优解.答:(略)作出一组平行直线z=x+y，目标函数z=x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法在可行域内打出网格线，当直线经过点A时z=x+y=11.4,但它不是最优整数解，将直线x+y=11.4继续向上平移，12121827159781.平移找解法：其解题思路：找整点，验证算，选优解法2（特值验证法）：由法1知目标函数取得最小值的整点应分布在可行域的左下侧靠近边界的整点，依次取满足条件的整点A0（0，15），A1（1，13），A2（2，11），A3（3,9），A4（4,8），…，A27（27，0），将这些点的坐标分别z=x+y，经检验可知在整点A3（3,9），A4（4,8）处z最小。2.特值验证法：法3:根据非整点最优解,,,可知,当,都是整数时,.令,,代入约束条件整理可得:所以或,这样便知道了最优整点解.518x539y557zxy12z12yxxy12293x3x4x这种寻求整点最优解的方法可简述为调整优值法,即先求非整点最优解及最优值,再借助不定方程的知识调整最优值,最后筛选出整点最优解.3.调整优解法：即先求非整数条件下的最优解，调整Z的值使不定方程Ax+By=Z存在最大（小）的整点值，最后筛选出整点最优解．即先打网格，描出可行域内的整点，平移直线，最先经过或最后经过的整点坐标即为最优整解．线性规划求最优整数解的一般方法:1.平移找解法：3.调整优解法：结论找整点，验证算，选优解2.特值验证法：不等式组表示的平面区域内的整数点共有（）个123400yxyx巩固练习1:1234xy432104x+3y=12练习2：求满足|x|+|y|≤4的整点（横、纵坐标为整数）的个数。xyo44－4－4共有：9+2(7+5+3+1)=41Xy084x=8y=47654321321x+y=104x+5y=30320x+504y=03.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务，该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车4次，B型卡车3次，每辆卡车每天往返的成本费A型卡车为320元，B型卡车为504元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？(要求每型卡车至少安排一辆）解：设每天调出的A型车x辆，B型车y辆，公司所花的费用为z元，则x≤8{y≤4x+y≤10x,y∈N*4x+5y≥30Z=320x+504y作出可行域中的整点，可行域中的整点（8，0）时,Z=320x+504y取得最小值，且Zmin=2608元画出可行域画直线l0:320x+504y=0,平移直线l0到l的位置,直线l过小结:实际问题列表设出变量寻找约束条件建立目标函数转化建模线性规划问题图解法最优解三个转化四个步骤作答调整最优整数解平移找解法调整优值法常用方法目标函数距离,斜率等小结：1。这节课,我们学习了把实际问题转化成线性规划问题即建立数模的方法,以及求解整点最优解的两种方法.建模主要分清已知条件中,哪些属于约束条件,哪些与目标函数有关.2。求解整点最优解有两种方法:平移求解法与调整优值法.前者主要依赖作图后者主要依赖推理,但一般都应充分利用非整点最优解及最优值.1.在x,y的值都是不小于0的整数点（x,y)中，满足x+y≤4的点的个数为_______15课后练习:2.3210411,0,0xyxyxyZxy。yxS的最大值求45,xy设变量满足条件3.深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥制品1吨，需矿石4吨，煤3吨；生产乙种水泥制品1吨，需矿石5吨，煤10吨，每1吨甲种水泥制品的利润为7万元，每1吨乙种水泥制品的利润是12万元，工厂在生产这两种水泥制品的计划中，要求消耗的矿石不超过200吨，煤不超过300吨，甲乙两种水泥制品应生产多少，能使利润达到最大值？1yzx231yzx0xy（图1）【练习4】如图1所示，已知△ABC中的三顶点A(2,4),B(-1,2),C(1,0),点P(x,y)在△ABC内部及边界运动，请你探究并讨论以下问题：①在_____处有最大值___，在____处有最小值____；③你能否设计一个目标函数，使得其取最优解的情况有无穷多个？④请你分别设计目标函数，使得最值点分别在A处、B处、C处取得？⑤(课后思考题）若目标函数是你知道其几何意义吗？？如果是或②在___处有最大值____，在____处有最小值____；呢？你能否借助其几何意义求得z=x+yz=x-yz=x2+y2，zmin和zmaxA(2,4)C(0,1)B(-1,2)0ABCxy(2,4)(1,2)(1,0)6xy1xy（图2）0ABCxy(2,4)(1,2)(1,0)1xy3xy(如图2，①②问参考答案:①z=x+y在点A处有最大值6，在边界BC处有最小值1；②z=x+y在点C处有最大值1，在点B处有最小值-3)