简单的线性规划(2).ppt

xyo线性规划的简单应用线性规划的简单应用 使使z=2x+y取得取得最大值最大值的可行解为的可行解为 ，且最大值为且最大值为 ；复习引入复习引入1.已知二元一次不等式组已知二元一次不等式组x-y0 x+y-10y-1（1）画出不等式组所表示的平面区域；）画出不等式组所表示的平面区域；满足满足 的的解解(x,y)都叫做都叫做可行解可行解；z=2x+y 叫做叫做 ；（2）设设z=2x+y，则则式式中中变变量量x,y满满足足的的二二元元一一次不等式组叫做次不等式组叫做x,y的的 ；y=-1x-y=0 x+y=12x+y=0(-1,-1)(2,-1)使使z=2x+y取得取得最小值最小值的可行解的可行解 ，且最小值为且最小值为 ；线性约束条件线性约束条件线性目标函数线性目标函数线性约束条件线性约束条件(2,-1)(-1,-1)3-3xy011例、营养学家指出，成人良好的日常饮食应该至少提例、营养学家指出，成人良好的日常饮食应该至少提供供0.075kg0.075kg的碳水化合物，的碳水化合物，0.06kg0.06kg的蛋白质，的蛋白质，0.06kg0.06kg的的脂肪，脂肪，1kg1kg食物食物A A含有含有0.105kg0.105kg碳水化合物，碳水化合物，0.07kg0.07kg蛋白蛋白质，质，0.14kg0.14kg脂肪，花费脂肪，花费2828元；而元；而1 1食物食物B B含有含有0.105kg0.105kg碳碳水化合物，水化合物，0.14kg0.14kg蛋白质，蛋白质，0.07kg0.07kg脂肪，花费脂肪，花费2121元。为元。为了满足营养专家指出的日常饮食要求，了满足营养专家指出的日常饮食要求，同时使花费最低，同时使花费最低，需要同时食用食物需要同时食用食物A A和食物和食物B B多少多少kgkg？食物kg碳水化合物kg蛋白质/kg脂肪kgA0.1050.070.14B0.1050.140.07分析：将已知数据列成表格分析：将已知数据列成表格典例分析典例分析解：设每天食用解：设每天食用xkgxkg食物食物A A，ykgykg食物食物B B，总成本为总成本为z z，目标函数为：目标函数为：z z28x28x21y21y可行域如图所示可行域如图所示把目标函数把目标函数z z28x28x21y 21y 变形为变形为xyo5/75/76/73/73/76/7M当直线当直线z z28x28x21y 21y 经经过点过点MM时，截距最小，时，截距最小，即即z z最小。最小。解方程组解方程组得得MM点的坐标为：点的坐标为：所以所以z zminmin28x28x21y21y1616所以，每天食用食物所以，每天食用食物A143gA143g，食物食物B B约约571g571g，能够能够满足日常饮食要求，又使花费最低，最低成本为满足日常饮食要求，又使花费最低，最低成本为1616元。元。例咖啡屋配制两种饮料，成分配比和单价如下表咖啡屋配制两种饮料，成分配比和单价如下表：饮料饮料奶粉（杯）奶粉（杯）咖啡（杯）咖啡（杯）糖（杯）糖（杯）利润（杯）利润（杯）甲种甲种9(g)9(g)4(g)4(g)3(g)3(g)0.70.7（元）（元）乙种乙种4(g)4(g)5(g)5(g)10(g)10(g)1.21.2（元）（元）每天使用限额为奶粉3600g,咖啡2000g,糖3000g，若每天在原料的使用限额内饮料能全部售出，应配制两种饮料各多少杯获利最大？典例分析典例分析解：设配制甲种饮料杯，乙种饮料杯，则解：设配制甲种饮料杯，乙种饮料杯，则9x+4y=36003x+10y=30004x+5y=2000O OA AB BC CD D200200解：线性约束条件为：解：线性约束条件为：9x+4y3600 9x+4y3600 4x+5y2000 4x+5y2000 3x+10y30003x+10y3000 xN xN yNyN 当当 l l 过点过点C C时，时，y y轴截距轴截距b b最大，最大，z z最大最大Z Zmaxmax=0.7=0.7200+1.2200+1.2240=428240=428（元）元）答：每天应配制甲种饮料答：每天应配制甲种饮料200200杯，乙种饮料杯，乙种饮料240240杯时，获杯时，获利最大。利最大。3x+10y=3000 y=2403x+10y=3000 y=240 由由 4x+5y=2000 4x+5y=2000 得得 x=200 x=200 C(200,240)C(200,240)l l说明：约束条件要写全，求解过程要细心，说明：约束条件要写全，求解过程要细心，解题格式要规范。解题格式要规范。z=0.7x+1.2y z=0.7x+1.2y，由图可知，由图可知作出直线：作出直线：y yx x可行域如图：可行域如图：结论：结论：用线性规划的方法解题的用线性规划的方法解题的一般步骤一般步骤是：是：(1)设未知数、列出约束条件及目标函数设未知数、列出约束条件及目标函数.(2)作图作图.作出可行域、求出最优解作出可行域、求出最优解.(3)根据实际意义写出答案根据实际意义写出答案.某运输公司接受了向抗洪抢险地区每天至少运送某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务，该公司有吨支援物资的任务，该公司有8辆载重量为辆载重量为6吨的吨的A型卡车和型卡车和4辆载重量为辆载重量为10吨的吨的B型卡车，有型卡车，有10名驾驶员；每辆卡车每天往返的次数为名驾驶员；每辆卡车每天往返的次数为A型卡型卡车车4次，次，B型卡车型卡车3次，每辆卡车每天往返的成本次，每辆卡车每天往返的成本费费A型卡车为型卡车为320元，元，B型卡车为型卡车为504元，问如何安元，问如何安排车辆才能使该公司所花的成本费最低，最低为排车辆才能使该公司所花的成本费最低，最低为多少元？多少元？(要求每型卡车至少安排一辆）要求每型卡车至少安排一辆）练习练习:Xy084x=8y=47654321321x+y=104x+5y=30320 x+504y=0解：解：设每天调出的设每天调出的A型车型车x辆，辆，B型车型车y辆，辆，公司所花的费用为公司所花的费用为z元，则元，则Z=320 x+504y作出可行域中的整点，作出可行域中的整点，可行域中的整点（可行域中的整点（5，2）使）使Z=320 x+504y取得最取得最小值，且小值，且Zmin=2608元元作出可行域作出可行域4x+5y30 x8y4x+y10 x,yN*例例 要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A、B、C三三种种规规格格，每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，第一种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图）作出可行域（如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问块，问各截这两种钢板多少张可得所需三种规格成品，且使所各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。用钢板张数最少。X张张y张张例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xNy0 yN直线直线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)调整优值法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xN*y0 yN*经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)时，时，t=x+y=12是最优解是最优解.答答:(略略)目标函数目标函数t=x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移，1212182715978不等式组不等式组 表示的平面区域内的表示的平面区域内的整数点整数点共有共有（）个）个巩固练习巩固练习1:1 2 3 4 xy432104x+3y=12在可行域内找出整数最优解的方法是：在可行域内找出整数最优解的方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时不是整点或不包括边界时，应先求出，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，在可行域内适当，在可行域内适当放缩放缩目标函数值，使它为整数，且与目标函数值，使它为整数，且与Z最接近，在这条对应最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法在可行域内找整数解，一般采用平移找解法打网络、找整点、平移直线、找出整数最优解打网络、找整点、平移直线、找出整数最优解例、某工厂用例、某工厂用A、B两种配件生产甲、乙两种产品，两种配件生产甲、乙两种产品，每生产一件甲产品使用每生产一件甲产品使用4个个A配件耗时配件耗时1h，每生产一件，每生产一件乙产品使用乙产品使用4个个B配件耗时配件耗时2h，该厂每天最多可从配件，该厂每天最多可从配件厂获得厂获得16个个A配件和配件和12个个B配件，按每天工作配件，按每天工作8h计算，计算，该厂所有可能的日生产安排是什么？该厂所有可能的日生产安排是什么？解：设甲、乙两种产品分别生产解：设甲、乙两种产品分别生产x、y件，由已知条件件，由已知条件可得二元一次不等式组：可得二元一次不等式组：xyxy引申引申1 1：若生产一件甲产品获利：若生产一件甲产品获利2 2万元，生产一件乙产品万元，生产一件乙产品获利获利3 3万元，采用哪种生产安排利润最大？万元，采用哪种生产安排利润最大？可能的日生产安排是：可能的日生产安排是：（0，0），（），（1，0），（），（2，0），（），（3，0），（），（4，0），），（0，1），（），（1，1），（），（2，1），（），（3，1），（），（4，1），），（0，2），（），（1，2），（），（2，2），（），（3，2），（），（4，2），），（0，3），（），（1，3），（），（2，3）设生产甲产品设生产甲产品x件，乙产品件，乙产品y件时，件时，工厂获得的利润为工厂获得的利润为z，则，则Z=2x+3yM且且x,y满足：满足：二元一次不等式二元一次不等式表示平面区域表示平面区域直线定界，直线定界，特殊点定域特殊点定域简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解应应用用求解方法：画、求解方法：画、移、求、答移、求、答1某某工工厂厂制制造造甲甲、乙乙两两种种产产品品，已已知知制制造造甲甲产产品品1kg要要用用煤煤9吨吨，电电力力4kw，劳劳力力(按按工工作作日日计计算算)3个个；制制造造乙乙产产品品1kg要要用用煤煤4吨吨，电电力力5kw，劳劳力力10个个.又又知知制制成成甲甲产产品品1kg可可获获利利7万万元元，制制成成乙乙产产品品1kg可可获获利利12万万元元，现现在在此此工工厂厂只只有有煤煤360吨吨，电电力力200kw，劳劳力力300个个，在在这这种种条条件件下下应应生生产产甲甲、乙乙两两种种产产品品各多少千克，才能获得最大经济效益各多少千克，才能获得最大经济效益?【解题回顾解题回顾】(1)用用线线性性规规划划的的方方法法解解题题的的一一般般步步骤骤是是：设设未未知知数数、列列出出约约束束条条件件及及目目标标函函数数、作作出出可可行行域域、求求出出最优解、写出答案最优解、写出答案.(2)本例的关键是分析清楚在哪一个点取最大值本例的关键是分析清楚在哪一个点取最大值.