3.3.2简单的线性规划2.ppt

1、3xy1234567O-1-1123456BACx=1x-4y+3=03x+5y-25=00l1ll2l 若实数若实数x,y满足满足 ,求求z=2x+y的取值范围的取值范围.1255334xyxyx使使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最优解最优解线性约束条件线性约束条件复习引入复习引入:xy1234567O-1-1123456BACx=1x-4y+3=03x+5y-25=00l1ll2l解：不等式组表示的平解：不等式组表示的平面区域如图所示：面区域如图所示：，：0z-y2xl作斜率为作斜率为-2的直线的直线使之与平面区域有公共点使之与平面区域有公共点,minmax2 1 1 32 5 2 12zz A(5,2),B(1,1),。)522,1(C 若实

3、数若实数x,y满足满足 求求z=2x+y的取值范围的取值范围 1255334xyxyx由图可知由图可知,当当l过过B(1,1)时时的值最小，当的值最小，当l过过A(5,2)时，时，z的值最大的值最大.0l分析：目标函数变形为分析：目标函数变形为zxy2121把把z看成参数，同样是一组平行看成参数，同样是一组平行线，且平行线与可行域有交点。线，且平行线与可行域有交点。最小截距为过最小截距为过A(5,2)的直线的直线2l1l2l注意：直线取最大截距时，注意：直线取最大截距时，等价于等价于z21取得最大值，则取得最大值，则z取得最取得最小值小值53952221minz同理，当直线取最小截距时，同理，

4、当直线取最小截距时，z有最大值有最大值1225maxzy1234567O-1-1123456x3x+5y-25=0 x=1BACx-4y+3=0最大截距为过最大截距为过的直线的直线1l)522,1(C变题：变题：上例若改为求上例若改为求z=x-2y的最大值、最小值呢？的最大值、最小值呢？y1234567O-1-1123456变题：变题：若改为求若改为求z=3x+5y的最大值、最小值呢？的最大值、最小值呢？解：不等式组表示的平解：不等式组表示的平面区域如图所示：面区域如图所示：25255381513maxminzz作斜率为的直线作斜率为的直线，：0z-y53xl53x=1BACx3x+5y-25

5、=0 x-4y+3=0l使之与平面区域有公共点使之与平面区域有公共点,由图可知由图可知,当当z的值最小，的值最小，的值最小，当的值最小，当过过A(5,2)、时，时，l过过B(1,1)时，时，)522,1(C25522513zmax或或0l1ll2l本题以最大值解为坐本题以最大值解为坐标的点落在线段标的点落在线段AC上，上，即线段即线段AC上所有点的上所有点的坐标为最大值解坐标为最大值解例题分析：关于取整数解的问题关于取整数解的问题 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板截成A、B、C三种规格，每张三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示钢板可同时截得三种规

6、格的小钢板的块数如下表所示：解：解：设需截第一种钢板设需截第一种钢板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

7、=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答（略）答（略）例题分析x

8、0y2x+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(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移，1212182715978在可行

9、域内找出最优解、线性规划整数在可行域内找出最优解、线性规划整数解问题的一般方法是：解问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然后在可行域内适当，然后在可行域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果

10、没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解；还可以用调络、找整点、平移直线、找出整数最优解；还可以用调整最优值法。整最优值法。不等式组不等式组 表示的平面区域内的表示的平面区域内的整数点整数点共有共有（）个）个123400yxyx巩固练习巩固练习1:1 2 3 4 xy432104x+3y=12练习练习2：求满足：求满足|x|+|y|4 的整点（横、的整点（横、纵坐标为整数）的个数。纵坐标为整数）的个数。xyo4444 共有：共有：9+2(7+

11、5+3+1)=41 Xy084x=8y=47654321321x+y=104x+5y=30320 x+504y=03.某运输公司接受了向抗洪抢险地区每天至少运送某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资吨支援物资的任务，该公司有的任务，该公司有8辆载重量为辆载重量为6吨的吨的A型卡车和型卡车和4辆载重量为辆载重量为10吨吨的的B型卡车，有型卡车，有10名驾驶员；每辆卡车每天往返的次数为名驾驶员；每辆卡车每天往返的次数为A型卡车型卡车4次，次，B型卡车型卡车3次，每辆卡车每天往返的成本费次，每辆卡车每天往返的成本费A型卡车为型卡车为320元，元，B型卡车为型卡车为504元，问如何

12、安排车辆才能使该公司所花的成本费最元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？低，最低为多少元？(要求每型卡车至少安排一辆）要求每型卡车至少安排一辆）解：解：设每天调出的设每天调出的A型车型车x辆，辆，B型车型车y辆，公司所花的费用为辆，公司所花的费用为z元，则元，则x8y4x+y10 x,yN*4x+5y30Z=320 x+504y作出可行域中的整点，作出可行域中的整点，可行域中的整点（可行域中的整点（5，2）使）使Z=320 x+504y取得最取得最小值，且小值，且Zmin=2608元元作出可行域作出可行域1.1.在在x,yx,y的的值值都都是是不不小小于于0 0的的整整

13、数数点点（x,y)x,y)中中，满满足足x+yx+y4 4的的点点的的个个数数为为_1515课后练习课后练习:2.321 041 1,0,0 xyxyxyZxy。yxS的的最最大大值值求求45 ,x y设 变 量满 足 条 件3.深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥制品泥制品1吨，需矿石吨，需矿石4吨，煤吨，煤3吨；生产乙种水泥制品吨；生产乙种水泥制品1吨，需吨，需矿石矿石5吨，煤吨，煤10吨，每吨，每1吨甲种水泥制品的利润为吨甲种水泥制品的利润为7万元，每万元，每1吨乙种水泥制品的利润是吨乙种水泥制品的利润是12万元，工厂在生产这两种水泥制万元，工厂在生产这两种水泥制品的计划中，要求消耗的矿石不超过品的计划中，要求消耗的矿石不超过200吨，煤不超过吨，煤不超过300吨，吨，甲乙两种水泥制品应生产多少，能使利润达到最大值？甲乙两种水泥制品应生产多少，能使利润达到最大值？1yzx231yzxxyxy(2,4)(1,2)(1,0)6xy1xyxy(2,4)(1,2)(1,0)1x y 3x y