《3.3.2简单的线性规划2》由会员分享，可在线阅读，更多相关《3.3.2简单的线性规划2（15页珍藏版）》请在金锄头文库上搜索。
1、20082008、1010、25251xy1234567O-1-1123456BACx=1x-4y+3=03x+5y-25=0 若实数若实数x , y满足满足 ,求求z=2x+y的取值范围的取值范围.使使z=2x+y取取得得最最大大值值的的可可行行解为解为 ，且最大值为且最大值为 ；（1）画出不等式组所表示的平面区域；）画出不等式组所表示的平面区域；满满足足 的的解解(x,y)都叫做都叫做可行解可行解；z=2x+y 叫做叫做 ；（2）设设z=2x+y，则则式式中中变变量量x,y满满足足的的二二元元一一次次不不等等式式组组叫叫做做x,y的的 ；使使z=2x+y取得取得最小值最小值的可行解的可行解
2、 ，且最小值为且最小值为 ；这两个这两个最值最值都叫做问题的都叫做问题的 。线性目标函数线性目标函数线性约束条件线性约束条件(5,2)(1, 1)123最优解最优解线性约束条件线性约束条件复习引入复习引入:2xy1234567O-1-1123456BACx=1x-4y+3=03x+5y-25=0解：不等式组表示的平解：不等式组表示的平面区域如图所示：面区域如图所示：作斜率为作斜率为-2的直线的直线使之与平面区域有公共点使之与平面区域有公共点,A(5,2), B(1,1),例例1.若实数若实数x , y满足满足 求求z=2x+y的取值范围的取值范围由图可知由图可知,当当l过过B(1,1)时时的值
3、最小，当的值最小，当l过过A(5,2)时，时， z的值最大的值最大.3分析：目标函数变形为分析：目标函数变形为把把z看成参数，同样是一组平行看成参数，同样是一组平行线，且平行线与可行域有交点。线，且平行线与可行域有交点。最小截距为过最小截距为过A(5,2)的直线的直线注意：直线取最大截距注意：直线取最大截距时，等价于时，等价于取得最大值，则取得最大值，则z取得取得最小值最小值同理，当直线取最小截距时，同理，当直线取最小截距时，z有最大值有最大值y1234567O-1-1123456x3x+5y-25=0x=1BACx-4y+3=0最大截距为过最大截距为过的直线的直线变题：变题：上例若改为求上例
4、若改为求z=x-2y的最大值、最小值呢？的最大值、最小值呢？4y1234567O-1-1123456变题：变题：若改为求若改为求z=3x+5y的最大值、最小值呢？的最大值、最小值呢？解：不等式组表示的平解：不等式组表示的平面区域如图所示：面区域如图所示：作斜率为的直线作斜率为的直线x=1BACx3x+5y-25=0x-4y+3=0使之与平面区域有公共点使之与平面区域有公共点,由图可知由图可知,当当z的值最小，的值最小，的值最小，当的值最小，当过过A(5,2)、时，时，过过B(1,1)时，时，或或本题以最大值解为坐本题以最大值解为坐标的点落在线段标的点落在线段AC上，上，即线段即线段AC上所有点
5、的上所有点的坐标为最大值解坐标为最大值解5例题分析：关于取整数解的问题关于取整数解的问题例例2 要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A、B、C三三种种规规格格，每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第二种钢板张，第二种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图）作出可行域（如图）目标函数为目标函数为
6、z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问块，问各截这两种钢板多少张可得所需三种规格成品，且使所各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。用钢板张数最少。X张张y张张6例题分析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)当
7、直线经过点当直线经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）7例题分析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+y，目标函数目标函数t = x+yB
8、(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移，12121827159788在可行域内找出最优解、线性规划整数在可行域内找出最优解、线性规划整数解问题的一般方法是：解问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包
9、括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然后在可行域内适当，然后在可行域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解；还可以用调络、找整点、平移直线、找出整数最优解；还可以用调整最优值法。整最优值法。9不等式组不等式组 表示的平面区域
10、内的表示的平面区域内的整数点整数点共有共有（ ）个）个巩固练习巩固练习1:1 2 3 4 xy432104x+3y=1210练习练习2：求满足：求满足 | x | + | y | 4 的整点（横、的整点（横、纵坐标为整数）的个数。纵坐标为整数）的个数。xyo4444共有：共有：9 + 2 ( 7 + 5 + 3 + 1 )= 41 11Xy084x=8y=47654321321x+y=104x+5y=30320x+504y=03.某运输公司接受了向抗洪抢险地区每天至少运送某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资吨支援物资的任务，该公司有的任务，该公司有8辆载重量为辆载重量为6
11、吨的吨的A型卡车和型卡车和4辆载重量为辆载重量为10吨吨的的B型卡车，有型卡车，有10名驾驶员；每辆卡车每天往返的次数为名驾驶员；每辆卡车每天往返的次数为A型卡车型卡车4次，次，B型卡车型卡车3次，每辆卡车每天往返的成本费次，每辆卡车每天往返的成本费A型卡车为型卡车为320元，元，B型卡车为型卡车为504元，问如何安排车辆才能使该公司所花的成本费最元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？低，最低为多少元？(要求每型卡车至少安排一辆）要求每型卡车至少安排一辆）解：解：设每天调出的设每天调出的A型车型车x辆，辆，B型车型车y辆，公司所花的费用为辆，公司所花的费用为z元，则元，
12、则x8y4x+y10x,yN*4x+5y30Z=320x+504y作出可行域中的整点，作出可行域中的整点，可行域中的整点（可行域中的整点（5，2）使）使Z=320x+504y取得最取得最小值，且小值，且Zmin=2608元元作出可行域作出可行域121515课后练习课后练习:2.3.深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥制品泥制品1吨，需矿石吨，需矿石4吨，煤吨，煤3吨；生产乙种水泥制品吨；生产乙种水泥制品1吨，需吨，需矿石矿石5吨，煤吨，煤10吨，每吨，每1吨甲种水泥制品的利润为吨甲种水泥制品的利润为7万元，每万元，每1吨乙种水泥
13、制品的利润是吨乙种水泥制品的利润是12万元，工厂在生产这两种水泥制万元，工厂在生产这两种水泥制品的计划中，要求消耗的矿石不超过品的计划中，要求消耗的矿石不超过200吨，煤不超过吨，煤不超过300吨，吨，甲乙两种水泥制品应生产多少，能使利润达到最大值？甲乙两种水泥制品应生产多少，能使利润达到最大值？130 0 0 0（图（图（图（图1 1 1 1）【练习【练习【练习【练习4 4 4 4】 如图如图如图如图1 1 1 1所示，已知所示，已知所示，已知所示，已知ABCABC中的三顶点中的三顶点中的三顶点中的三顶点A(2,4) ,B(-1,2),C(1,0),A(2,4) ,B(-1,2),C(1,0
14、),点点点点P(x,y)P(x,y)在在在在ABCABC内部及边界运动，内部及边界运动，内部及边界运动，内部及边界运动，请你探究并讨论以下问题：请你探究并讨论以下问题：请你探究并讨论以下问题：请你探究并讨论以下问题： 在在在在_处有最大值处有最大值处有最大值处有最大值_，在，在，在，在_处有最小值处有最小值处有最小值处有最小值_； 你能否设计一个目标函数，使得其取最优解的你能否设计一个目标函数，使得其取最优解的你能否设计一个目标函数，使得其取最优解的你能否设计一个目标函数，使得其取最优解的情况有无穷多个？情况有无穷多个？情况有无穷多个？情况有无穷多个？ 请你分别设计目标函数，使得最值点分别请你
15、分别设计目标函数，使得最值点分别请你分别设计目标函数，使得最值点分别请你分别设计目标函数，使得最值点分别在在在在A A处、处、处、处、B B处、处、处、处、C C处取得？处取得？处取得？处取得？ ( ( ( (课后思考题）课后思考题）课后思考题）课后思考题）若目标函数是若目标函数是若目标函数是若目标函数是你知道其几何意义吗？你知道其几何意义吗？你知道其几何意义吗？你知道其几何意义吗？如果是？如果是？如果是？如果是或或或或 在在在在_处有最大值处有最大值处有最大值处有最大值_，在，在，在，在_处有最小值处有最小值处有最小值处有最小值_；呢呢呢呢？你能否借助其几何意义求得你能否借助其几何意义求得你
16、能否借助其几何意义求得你能否借助其几何意义求得z=x+yz=x+yz=x-yz=x-yz=xz=x2 2+y+y2 2 ，z zminmin和和和和z zmaxmaxA(2,4)A(2,4)C(0,1)C(0,1)B(-1,2)B(-1,2)140 0A AB BC C（ 图图图图2 2 2 2 ）0 0A AB BC C( ( ( (如图如图如图如图2 2 2 2，问参考答案问参考答案问参考答案问参考答案: : z=x+yz=x+y在在在在 点点点点A A A A 处有最大值处有最大值处有最大值处有最大值 6 6 6 6 ，在，在，在，在边界边界边界边界BCBCBCBC处有最小值处有最小值处有最小值处有最小值 1 1 1 1 ；z=x+yz=x+y 在在在在 点点点点C C C C 处有最大值处有最大值处有最大值处有最大值 1 1 1 1 ，在，在，在，在 点点点点 B B B B 处有最小值处有最小值处有最小值处有最小值 -3 -3 -3 -3) ) ) ) 15
