简单的线性规划

《简单的线性规划》由会员分享，可在线阅读，更多相关《简单的线性规划（16页珍藏版）》请在装配图网上搜索。

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.每每1t甲种产品的利润是甲种产

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

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

6、为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)经过可行域上的点经过可行域上的点M时时,目标函数目标函数

7、在在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张，张，钢板钢板总总张数张数为为Z,则则 2x+y15,x+2y18,x+3

9、y27,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但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）约束条件约

10、束条件:画可行域画可行域平移平移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向右上方平移至向右上方平移至l l1 1的位置时，的位置时，直线经过可行域上的点直线经过可行域上的点C C，且与原点，且与原点距离最大，距离最大，此时此时z=0.7x+1.2yz=0.7x+1.2y取最

13、大值取最大值解方程组解方程组 得点得点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杯杯,乙种饮料乙种饮料240杯可获取最大利润杯可获取最大利润.小结小结小结:实际问题实际问题分析问题分析问题设出变量设出变量列出约束条件列出约束条件建立目标函数建

14、立目标函数转化转化建模建模线性规划线性规划问题问题图解法图解法理论理论最优解最优解三个转化三个转化四个步骤四个步骤调整调整实际实际最优解最优解平移找解法平移找解法调整优值法调整优值法常用方法常用方法整数整数最优解最优解作作答答思考问题一思考问题一:探索问题一探索问题一(课本例题课本例题3)的最优解是的最优解是(12.4,34.4).它存在最优整数解吗它存在最优整数解吗?若存在若存在,求出最优整数解求出最优整数解.若不存在若不存在,请说明理由请说明理由.例3.gsp图形作业:习题7.4 第3题;第4题结束某货运公司拟用集装箱托运甲某货运公司拟用集装箱托运甲.乙两种货物乙两种货物,一个大集装一个大

15、集装箱所装托运货物的总体积不能超过箱所装托运货物的总体积不能超过24 ,总重量不能总重量不能超过超过1500kg,甲甲.乙两种货物每袋的体积乙两种货物每袋的体积.重量和可获得重量和可获得的利润的利润,列表如下列表如下:思考问题思考问题 二二3m货物货物每袋体积每袋体积(立方米立方米)每袋重量每袋重量(100kg)每袋利润每袋利润(单位百元单位百元)甲甲5220乙乙4315问在一个大集装箱内这两种问在一个大集装箱内这两种(不能只装一种不能只装一种)货物各装多货物各装多少袋时少袋时,可获得最大的利润可获得最大的利润?解解:设托运甲货物设托运甲货物x袋袋,托运乙货物托运乙货物y袋袋,获得利润为获得利润为z(百元百元)图象Z=20 x+15y (x,y )N5x+4y 242x+3y 15 X0Y0