3.3.2简单的线性规划2

1、2008、10、25,课题：简单的线性规划（2）-调整最优解,汉寿县第三中学,艾镇南,B,A,C,若实数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),12,3,最优解,线性约束条件,复习引入:,B,A,C,解：不等式组表示的平面区域

2、如图所示：,作斜率为-2的直线,使之与平面区域有公共点,A(5,2), B(1,1),例1.若实数x , y满足 求z=2x+y的取值范围,由图可知,当l过B(1,1)时的值最小，当l过A(5,2)时， z的值最大.,分析：目标函数变形为,把z看成参数，同样是一组平行线，且平行线与可行域有交点。,最小截距为过A(5,2) 的直线,同理，当直线取最小截距时，z有最大值,最大截距为过 的直线,变题：上例若改为求z=x-2y的最大值、最小值呢？,变题：若改为求z=3x+5y的最大值、最小值呢？,解：不等式组表示的平面区域如图所示：,作斜率为的直线,或,本题以最大值解为坐标的点落在线段AC上，即线段A

3、C上所有点的坐标为最大值解,例题分析：关于取整数解的问题,例2 要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 ：,解：设需截第一种钢板x张，第一种钢板y张，则,2x+y15,x+2y18,x+3y27,x0,y0,作出可行域（如图）,目标函数为 z=x+y,今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。,X张,y张,例题分析,2x+y=15,x+3y=27,x+2y=18,x+y =0,直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.,作出一

4、组平行直线z=x+y，,目标函数z= x+y,当直线经过点A时z=x+y=11.4,x+y=12,解得交点B,C的坐标B(3,9)和C(4,8),调整优值法,2,4,6,18,12,8,27,2,4,6,8,10,15,但它不是最优整数解.,作直线x+y=12,答（略）,例题分析,2x+y=15,x+3y=27,x+2y=18,x+y =0,经过可行域内的整点B(3,9)和C(4,8)时，t=x+y=12是最优解.,答:(略),作出一组平行直线t = x+y，,目标函数t = x+y,打网格线法,在可行域内打出网格线，,当直线经过点A时t=x+y=11.4,但它不是最优整数解，,将直线x+y=

5、11.4继续向上平移，,1,2,1,2,18,27,15,9,7,8,在可行域内找出最优解、线性规划整数解问题的一般方法是：,1.若区域“顶点”处恰好为整点，那么它就是最优解；（在包括边界的情况下） 2.若区域“顶点”不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值Z，然后在可行域内适当放缩目标函数值，使它为整数，且与Z最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。 3.在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解；还可以用调整最优值法。,不等式组 表示的平面区域内的整数点共有（ ）个,巩固练习1:,1 2

6、 3 4 x,y 4 3 2 1 0,4x+3y=12,练习2：求满足 | x | + | y | 4 的整点（横、纵坐标为整数）的个数。,共有： 9 + 2 ( 7 + 5 + 3 + 1 ) = 41,4,x=8,y=4,x+y=10,4x+5y=30,320 x+504y=0,3.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务，该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车4次，B型卡车3次，每辆卡车每天往返的成本费A型卡车为320元，B型卡车为504元，问如何安排车辆才能使该公司所花的成本费最低，最低

7、为多少元？(要求每型卡车至少安排一辆）,解：设每天调出的A型车x辆，B型车y辆，公司所花的费用为z元，则,Z=320 x+504y,作出可行域中的整点，,可行域中的整点（5，2）使Z=320 x+504y取得最小值，且Zmin=2608元,作出可行域,15,课后练习:,2.,3.深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥制品1吨，需矿石4吨，煤3吨；生产乙种水泥制品1吨，需矿石5吨，煤10吨，每1吨甲种水泥制品的利润为7万元，每1吨乙种水泥制品的利润是12万元，工厂在生产这两种水泥制品的计划中，要求消耗的矿石不超过200吨，煤不超过300吨，甲乙两种水泥制品应生产多少，能使利润达到最大值？,（图1）,【练习4】 如图1所示，已知ABC中的三顶点 A(2,4) ,B(-1,2),C(1,0),点P(x,y),在ABC内部及边界运动， 请你探究并讨论以下问题：,在_处有最大值_，在_处有最小值_；, 你能否设计一个目标函数，使得其取最优解的 情况有无穷多个？ 请你分别设计目标函数，使得最值点分别 在A处、B处、C处取得？ (课后思考题）若目标函数是,你知道其几何意义吗？,？如果是,或,在_处有最大值_，在_处有最小值_；,呢？,你能否借助其几何意义求得,z=x+y,z=x-y,z=x2+y2 ，,zmin和zmax,A(2,4