简单的线性规划.pptxVIP

简单的线性规划（2）-调整最优解

xy1234567O-1-1123456??BA?Cx=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取得最小值的可行解，且最小值为；这两个最值都叫做问题的。线性目标函数线性约束条件(5,2)(1,1)123最优解线性约束条件复习引入:

xy1234567O-1-1123456??BA?Cx=1x-4y+3=03x+5y-25=0解：不等式组表示的平面区域如图所示：作斜率为-2的直线使之与平面区域有公共点,?A(5,2),B(1,1),若实数x,y满足求z=2x+y的取值范围由图可知,当l过B(1,1)时ｚ的值最小，当l过A(5,2)时，z的值最大.

分析：目标函数变形为把z看成参数，同样是一组平行线，且平行线与可行域有交点。最小截距为过A(5,2)的直线注意：直线取最大截距时，等价于取得最大值，则z取得最小值同理，当直线取最小截距时，z有最大值y1234567O-1-1123456x3x+5y-25=0?x=1??BAC?x-4y+3=0最大截距为过的直线变题：上例若改为求z=x-2y的最大值、最小值呢？

y1234567O-1-1123456变题：若改为求z=3x+5y的最大值、最小值呢？解：不等式组表示的平面区域如图所示：作斜率为的直线x=1??BA?Cx3x+5y-25=0x-4y+3=0?使之与平面区域有公共点,由图可知,当z的值最小，ｚ的值最小，当过A(5,2)、时，过B(1,1)时，或本题以最大值解为坐标的点落在线段AC上，即线段AC上所有点的坐标为最大值解

例题分析：关于取整数解的问题要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：设需截第一种钢板x张，第一种钢板y张，则规格类型钢板类型第一种钢板第二种钢板A规格B规格C规格2121312x+y≥15,{x+2y≥18,x+3y≥27,x≥0y≥0作出可行域（如图）目标函数为z=x+y今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。X张y张

例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈Ny≥0y∈N直线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)调整优值法246181282724681015但它不是最优整数解.作直线x+y=12答（略）

例题分析x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*经过可行域内的整点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

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