简单的线性规划ppt课件

1、简单的线性规划( (第三课时第三课时) )5x+4y=202x+3y=12线性目的函数),(M720712Z的最大值为的最大值为44知实数知实数x,y满足以下条件满足以下条件:5x+4y 202x+3y 12x 0y0求求z=9x+10y的最大值的最大值.最优解可行域9x+10y=0想一想想一想: :线性约束条件 01 2345 6123456xy代数问题代数问题(线性约束线性约束条件条件)图解法图解法转化转化线性约线性约束条件束条件可行域可行域转化转化线性目线性目标函数标函数Z=Ax+By一组平行线一组平行线B BZ Zx xy y 转化转化最优解最优解图解法的步骤：图解法的步骤：1。画可行

2、域。画可行域;4。求出最优解作答。求出最优解作答.3。平移直线。平移直线L0找最优解找最优解;2。作。作Z=0时的直线时的直线L0.三个转化三个转化一一. .复习复习平行线在平行线在y轴上轴上的截距的截距 最值最值B BZ Z 某工厂消费甲、乙两种产品某工厂消费甲、乙两种产品.知消费甲种产品知消费甲种产品1t需消需消耗耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；消费乙种产品；消费乙种产品1t需需耗费耗费A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t. 每每1t甲种产品的利润甲种产品的利润是是600元元,每每1t乙种产品的利润是乙种产品的利润是1000元元.工厂在消费这两工厂在消

3、费这两种产品的方案中要求耗费种产品的方案中要求耗费A种矿石不超越种矿石不超越300t、 耗费耗费B种种矿石不超越矿石不超越200t、耗费煤不超越、耗费煤不超越360t.他应如何安排甲乙他应如何安排甲乙两种产品的产量两种产品的产量(准确到准确到0.1t),才干使利润总额到达最大才干使利润总额到达最大?二二. .实践运用实践运用探求问题一探求问题一: : 某工厂消费甲、乙两种产品某工厂消费甲、乙两种产品.知消费甲种产品知消费甲种产品1t需耗费需耗费A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；消费乙种产品；消费乙种产品1t需耗费需耗费A种矿石种矿石4t、B种矿石种矿石4t、煤、煤9t.每每

4、1t甲种产品的利润是甲种产品的利润是600元元,每每1t乙种产品的利润是乙种产品的利润是1000元元.工厂在消费这两种工厂在消费这两种产品的方案中要求耗费产品的方案中要求耗费A种矿石不超越种矿石不超越300t、 耗费耗费B种种矿石不超越矿石不超越200t、耗费煤不超越、耗费煤不超越360t. 他应如何安排甲乙他应如何安排甲乙两种产品的产量两种产品的产量(准确到准确到0.1t),才干使利润总额到达最大才干使利润总额到达最大?分分析析问问题题:2.本问题给定了哪些原资料？本问题给定了哪些原资料？1.该工厂消费哪些产品该工厂消费哪些产品?3.每吨产品对原资料的耗费量各是多少每吨产品对原资料的耗费量各

5、是多少?4.该工厂对原资料有何限定条件该工厂对原资料有何限定条件?5.每种产品的利润是多少每种产品的利润是多少? 原原 材材料料每吨产品耗费的原资料每吨产品耗费的原资料A种矿石种矿石B种矿石种矿石煤煤甲产品甲产品(t)乙产品乙产品(t)1054449原原 资料资料限限 额额300200360利利 润润6001000 xtyt10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目的函数：目的函数：设消费甲、乙两种产品的产量分别为设消费甲、乙两种产品的产量分别为x t、yt,利润总额为利润总额为z元元解解:设消费甲、乙两种产品设消费甲、乙两种产品.分别为分

6、别为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+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:应消费甲产品约应消费甲产品约12.4吨，乙产品吨，乙产品34.4吨，能吨，能使利润总额到达最大。使利润总额到达最大。(12.4,34.4)经过可行域上的点经过

7、可行域上的点M时时,目的函数目的函数在在y轴上截距最大轴上截距最大.9030 0 xy10 201075405040此时此时z=600 x+1000y获得最大值获得最大值.4834291000411229360.y.x把直线把直线L向右上方平移向右上方平移实践问题实践问题线性规划问题线性规划问题列出约束条件列出约束条件建立目的函数建立目的函数分析问题分析问题(列表列表)设立变量设立变量转化转化列约束条件时要留意到变量的范围列约束条件时要留意到变量的范围.留意留意: :处理处理问题问题最最优优解解某工厂现有两种大小不同规格的钢板可截成某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，三种

8、规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格212131某顾客需求某顾客需求A,B,C三种规格的废品分别为三种规格的废品分别为15，18，27块，假设他是块，假设他是消费部经理消费部经理,问各截这两种钢板多少张既能满足顾客要求又使所用问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。钢板张数最少。探求问题二探求问题二: :解：设需截第一种钢板解：设需截第一种钢板x张，第二种钢板张，第二种钢板y张，张，钢板总张数为钢板

9、总张数为Z,那么那么 2x+y15,x+2y18,x+3y27,x0y0 目的函数目的函数: z=x+y) )N Ny y, ,x x( ( x0y2x+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，目的函数目的函数:z= x+yB(3,9)C(4,8)A(3.6,7.8)当直线当直线L经过点经过点A时时z=x+y=11.4,x+y=122 4 6181282724681015但它不是

10、最优整数解但它不是最优整数解.作直线作直线x+y=12答略答略约束条件约束条件:画可行域画可行域平移平移L找交点找交点及交点坐标及交点坐标) )N Ny y, ,x x( ( 图例题4.gsp示继续平移继续平移L找最优整数解找最优整数解调整调整Z的值的值,X+y=11.4A调整优值法调整优值法 即先求非整数条件下的最优解，即先求非整数条件下的最优解，调整调整Z的值使不定方程的值使不定方程Ax+By=Z存在最大小存在最大小的整点值，最后挑选出整点最优解的整点值，最后挑选出整点最优解 即先打网格，描出可行域内的即先打网格，描出可行域内的整点，平移直线，最先经过整点，平移直线，最先经过(或最后或最后

11、)经过的整点经过的整点坐标即为最优整解坐标即为最优整解线性规划求最优整数解的普通方法线性规划求最优整数解的普通方法:1. 1.平移找解法：平移找解法：2. 2.调整优值法：调整优值法：小结咖啡馆配制两种饮料甲种饮料每杯含奶粉咖啡馆配制两种饮料甲种饮料每杯含奶粉9g 、咖啡、咖啡4g、糖、糖3g,乙种饮料每杯含乙种饮料每杯含奶粉奶粉4g 、咖啡、咖啡5g、糖、糖10g知每天原料的运用限额为奶粉知每天原料的运用限额为奶粉3600g ，咖啡，咖啡2000g糖糖3000g,假设甲种饮料每杯能获利假设甲种饮料每杯能获利0.7元，乙种饮料每杯能获利元，乙种饮料每杯能获利1.2元每天在原料的元每天在原料的运

12、用限额内饮料能全部售出，每天应配制两种饮料各多少杯能获利最大？运用限额内饮料能全部售出，每天应配制两种饮料各多少杯能获利最大？练习一.gsp -稳定练习一稳定练习一解解: :设每天应配制甲种饮料设每天应配制甲种饮料x x杯，乙种饮料杯，乙种饮料y y杯，那么杯，那么003000103200054360049yxyxyxyx作出可行域：作出可行域：目的函数为：目的函数为：z =0.7x +1.2yz =0.7x +1.2y作直线作直线l:0.7x+1.2y=0l:0.7x+1.2y=0，把直线把直线l l向右上方平移至向右上方平移至l1l1的位置时，的位置时，直线经过可行域上的点直线经过可行域上

13、的点C C，且与原点，且与原点间隔最大，间隔最大，此时此时z =0.7x +1.2yz =0.7x +1.2y取最大值取最大值解方程组解方程组 得点得点C C的坐标为的坐标为200200，240240,3000103,200054yxyx_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杯杯,乙种饮料乙

14、种饮料240杯可获取最大利润杯可获取最大利润.小结小结小结: :实践问题实践问题分析问题分析问题设出变量设出变量列出约束条件列出约束条件建立目的函数建立目的函数转化转化建模建模线性规划线性规划问题问题图解法图解法实际实际最优解最优解三个转化三个转化四个步骤四个步骤调整调整实践实践最优解最优解平移找解法平移找解法调整优值法调整优值法常用方法常用方法整数整数最优解最优解作作答答思索问题一思索问题一: :探求问题一探求问题一(课本例题课本例题3)的最优解是的最优解是(12.4,34.4).它存在最优整数解吗它存在最优整数解吗?假设存在假设存在,求出最优整数解求出最优整数解.假设不存在假设不存在,请阐明理由请阐明理由.例3.gsp图形作业:习题7.4 第3题;第4题终了某货运公司拟用集装箱托运甲某货运公司拟用集装箱托运甲.乙两种货物乙两种货物,一个大集装一个大集装箱所装托运货物的总体积不能超越箱所装托运货物的总体积不能超越24 ,总分量不能总分量不能超越超越1500kg,甲甲.乙两种货物每袋的体积乙两种货物每袋的体积.分量和可获得分量和可获得的利润的利润,列表如下列表如下:思索问题思索问题 二二3m