简单的线性规划3课件修改

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,同学们好!,简单的线性规划,简单的线性规划,5x+4y=20,2x+3y=12,线性目标函数,Z的最大值为44,已知实数x,y满足下列条件:,5x+4y,20,2x+3y,12,x,0,y,0,求z=9x+10y的最大值.,最优解,可行域,9x+10y=0,线性约束条件,0,1,2,3,4,5,6,1,2,3,4,5,6,x,y,代数问题,(线性约束条件),图解法,一.复习,5x+4y=20,2x+3y=12,Z的最大值为44,9x+10y=0,0,1,2,3,4,5,6,1,2,3,4,5,6,x,y,图解法的步骤：,1。,画,可行域;,4。,求出最优解作,答.,3。,平,移,直线L,0,找最优解;,2。,作,Z=0时的直线L,0.,代数问题,图解法,三个转化,线性目标函数,线性约束条件,一组平行线,最优解,平行线在y轴上截距的最值,可行域,某工厂生产甲、乙两种产品.已知生产甲种产品1t需消,耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需,消耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润,是600元,每1t乙种产品的利润是1000元.工厂在生产这两,种产品的计划中要求消耗A种矿石不超过300t、消耗B种,矿石不超过200t、消耗煤不超过360t.你应如何安排甲乙,两种产品的产量(精确到0.1t),才能使利润总额达到最大?,二.实际应用,探索问题一:,分,析,问,题:,2.本问题给定了哪些原材料？,1.该工厂生产哪些产品?,3.每吨产品的原料消耗量各是多少?,4.对原材料有何限定条件?,5.每种产品的利润是多少?,原 材,料,每吨产品消耗的原材料,A种矿石,B种矿石,煤,甲产品(t),乙产品(t),10,5,4,4,4,9,原 材料,限 额,300,200,360,利 润,600,1000,x,y,某工厂生产甲、乙两种产品.已知生产甲种产品1t需消耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需消耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是600元,每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、消耗B种矿石不超过200t、消耗煤不超过360t.,你应如何安排甲乙两种产品的产量(精确到0.1t),才能使利润总额达到最大?,分,析,问,题:,原 材,料,每吨产品消耗的原材料,A种矿石,B种矿石,煤,甲产品(t),乙产品(t),10,5,4,4,4,9,原 材料,限 额,300,200,360,利 润,600,1000,x,y,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,目标函数,：,设生产甲、乙两种产品的产量分别为x t、yt,利润总额为z元,解:设生产甲、乙两种产品.分别为x t、yt,利润总额为z元,那么,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,画,出以上不等式组所表示的可行域,作,出直线L,600 x+1000y=0,.,解得交点M的坐标为,(12.4,34.4),5x+4y=200,4x+9y=360,由,10 x+4y=300,5x+4y=200,4x+9y=360,600 x+1000y=0,M,答,:,应生产甲产品约12.4吨，乙产品34.4吨，能使利润总额达到最大。,(12.41,34.48),经过可行域上的点M时,目标函数在y轴上截距最大.,90,30,0,x,y,10,20,10,75,40,50,40,把直线L向右上方平,移,(12.4,34.5),(12.4,34.4),实际问题,线性规划问题,列,出约束条件,建,立目标函数,分析问题(列表),设,立变量,转化,注意:,检验并调整,最,优,解,列约束条件时要注意实际问题中变量的范围(如x 0,y 0).,某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示,：,规格类型,钢板类型,第一种钢板,第二种钢板,A规格,B规格,C规格,2,1,2,1,3,1,某顾客需要A,B,C三种规格的成品分别为15，18，27块,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。,探索问题二:,解：,设需截第一种钢板x张，第二种钢板y张，,钢板,总,张数为Z,则,2x+y15,x+2y18,x+3y27,x0,y0,目标函数,:,z=x+y,x,0,y,2x+y=15,x+3y=27,x+2y=18,x+y=0,2x+y15,x+2y18,x+3y27,x0,y0,在可行域内直线x+y=12经过的,整点是B(3,9)和C(4,8)，它们是最优解.,作出直线L:,x+y=0，,目标函数,:,z=,x+y,B(3,9),C(4,8),A(3.6,7.8),当直线L经过点A时,z=x+y=11.4,但它不是最优整数解.,x+y=12,2,4,6,18,12,8,27,2,4,6,8,10,15,作直线,x+y=12,答（略）,约束条件:,画可行域,平移L找交点,及交点坐标,继续平移L,，,调整Z的值,，,找最优整数解,X+y=11.4,A,调整优值法,即先求,非整数条件下,的最优解，然后调整Z的值,，,使不定方程Ax+By=Z存在最大（小）的,整点值,，,再将整点的坐标代入线性约束条件检验,，,最后筛选出符合实际问题的整点最优解,即先打网格，平移直线L,0,，观察最先经过(或最后)经过的整点坐标即为最优整解,线性规划求最优整数解的一般方法:,2.平移找解法：,1,.调整优值法,：,咖啡馆配制两种饮料甲种饮料每杯含奶粉9g、咖啡4g、糖3g,乙种饮料每杯含奶粉4g、咖啡5g、糖10g已知每天原料的使用限额为奶粉3600g，咖啡2000g糖3000g,如果甲种饮料每杯能获利0.7元，乙种饮料每杯能获利1.2元每天在原料的使用限额内饮料能全部售出，每天应配制两种饮料各多少杯能获利最大,？,巩固练习,解:设每天应配制甲种饮料x杯，乙种饮料y杯，则,作出可行域：,目标函数为：,z=0.7x+1.2y,作直线l:0.7x+1.2y=0，,把直线l向右上方平移至l,1,的位置时，,直线经过可行域上的点C，且与原点距离最大，,此时z=0.7x+1.2y取最大值,解方程组,得点C的坐标为（200，240）,_,0,_,9,x,+,4,y,=,3600,_,C,(,200,240,),_,4,x,+,5,y,=,2000,_,3,x,+,10,y,=,3000,_,7,x,+,12,y,=,0,_,400,_,400,_,300,_,500,_,1000,_,900,_,0,_,x,_,y,目标函数为：z=0.7x+1.2y,答:每天配制甲种饮料200杯,乙种饮料240杯可获取最大利润.,小结:,实际问题,线性规划,问题,理论,最优解,实际,最优解,转化 建模,(约束条件，目标函数),三个转化,四个步骤,调整,(在可行域内，符合实际问题),(求整数最优解:调整优值法,网格法),(检验),(作答),课外思考:,探索问题一(课本例题3)的最优解是(12.4,34.4).它存在最优整数解吗?若存在,求出最优整数解.若不存在,请说明理由.,作业,:习题7.4 第3题;第4题,祝同学们学习进步！,谢谢！,