《简单线性规划》

1、课题：简单的线性规划（2）-调整最优解,五莲县第一中学,Dingchangwen,线性目标函数,Z的最大值为44,想一想:,线性约束条件,代数问题 (线性约束条件),图解法,线性约 束条件,可行域,线性目 标函数 Z=Ax+By,最优解,寻找平行线组 的纵截距 最值,四个步骤：,1、画,4、答,2、移,3、求,三个转化,一.复习,四个步骤：,1。画（画可行域）,三个转化,4。答,2。移（平移直线L 。寻找使纵截距取得最值时的点）,3。求（求出点的坐标，并转化为最优解）,图解法,想一想(结论):,线性约束条件,可行域,线性目标函数 Z=Ax+By,最优解,寻找平行线组的 最大（小）纵截距,3x+

2、5y=25,例1：已知x、y满足 ，设zaxy (a0)， 若 取得最大值时，对应点有无数个，求a 的值。,x,y,o,x-4y=-3,x=1,C,B,解：当直线 l ：y ax z 与直线重合时，有无数个点，使函数值取得最大值，此时有： k l kAC, kAC,k l = -a, -a =, a =,例2：满足线性约束条件 的可行域中共有 多少个整数解。,1,2,2,3,3,1,4,4,5,5,x,y,0,解：由题意得可行域如图:,由图知满足约束条件的 可行域中的整点为(1,1)、 (1,2)、(2,1)、(2,2) 故有四个整点可行解.,给定一定量的 人力.物力, 资金等资源,完成的任务

3、量最大 经济效益最高,给定一项任务,所耗的人力. 物力资源最小,降低成本,获取最大的利润,实际应用,六个步骤：,3、画,6、答,4、移,5、求,1、设,2、列,例3A、B两个居民小区的居委会组织本小区的中学生，利用双休日去市郊的敬老院参加献爱心活动，两个小区都有同学参加。已知A区的每位同学往返车费是3元，每人可为5位老人服务；B区的每位同学往返车费是5元，每人可为3位老人服务。如果要求B区参与活动的同学比A区的同学多，且去敬老院的往返总车费不超过37元。怎样安排参与活动同学的人数，才能使受到服务的老人最多？受到服务的老人最多是多少人？,解：设A、B两区参与活动的人数分别为x，y受到服务的老人人

4、数为z，,则z=5x+3y， 应满足的约束条件是,化简得,根据上述不等式组，作出表示可行域的平面区域，如图阴影部分所示。,画直线l0：5x+3y=0，平行移动l0到直线l的位置，使l过可行域中的某点，并且可行域内的其它各点都在l的包含直线l0的同一侧。,该点到直线l0的距离最大，则这一点的坐标使目标函数取最大值。 容易看出，点M符合上述条件，点M是直线x5y+1=0与直线3x+3y=37的交点。,解方程组,得点M(4，5).,因此，当x=4，y=5时，z取得最大值，并且zmax=54+35=35.,答：A、B两区参与活动同学的人数分别为4，5时，受到服务的老人最多，最多为35人。,例4.某工厂

5、现有两种大小不同规格的钢板可截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 ：,解：设需截第一种钢板x张，第二种钢板y张，钢板总张数为Z,则,2x+y15,x+2y18,x+3y27,x0,y0,某顾客需要A,B,C三种规格的成品分别为15，18，27块，若你是经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。,x张,y张,分 析 问 题:,求目标函数: z=x+y取最小值时的x,y,2x+y=15,x+3y=27,x+2y=18,x+y =0,直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.,作出直线L:x+y=0，,目标函数

6、:z= x+y,A(3.6,7.8),当直线L经过点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,答（略）,约束条件:,画可行域,平移L找交点及交点坐标,调整优解法,1.满足哪些条件的解才是最优解?,2.目标函数经过A(3.6,7.8)时Z的值是多少? 你能否猜测一下Z的最小值可能是多少?,3.最优解的几何意义是什么 (最优解可以转化为什么几何意义)?,例题分析,2x+y=15,x+3y=27,x+2y=18,x+y =0,直线x+y=12经过的整点

7、是B(3,9)和C(4,8)，它们是最优解.,作出一组平行直线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)时，z=x+y=12是最优解.,答:(略),作出一组平行直线z = x+y，,目标函数z = x+y,打网格线法,在可行域内打出网格线，,当直线经过点A时z=x

8、+y=11.4,但它不是最优整数解，,将直线x+y=11.4继续向上平移，,1,2,1,2,18,27,15,9,7,8,1.平移找解法：,其解题思路：找整点，验证算，选优解,法2（特值验证法）： 由法1知目标函数取得最小值的整点应分布在 可行域的左下侧靠近边界的整点，依次取满足 条件的整点A0（0，15），A1（1，13），A2 （2，11），A3（3,9），A4（4,8），A27 （27，0），将这些点的坐标分别z=x+y，经检 验可知在整点A3（3,9），A4（4,8）处z最小。,2. 特值验证法：,法3:根据非整点最优解 , , , 可知,当 , 都是整数时, . 令 , ,代入约束条

9、件整理可得: 所以 或 ,这样便知道了最优整点解.,这种寻求整点最优解的方法可简述为调整优值法, 即先求非整点最优解及最优值,再借助不定方程的 知识调整最优值,最后筛选出整点最优解.,3.调整优解法：,即先求非整数条件下的最优解，调整Z的值使不定方程Ax+By=Z存在最大（小）的整点值，最后筛选出整点最优解,即先打网格，描出可行域内的整点，平移直线，最先经过或最后经过的整点坐标即为最优整解,线性规划求最优整数解的一般方法:,1.平移找解法：,3.调整优解法：,结论,找整点，验证算，选优解,2. 特值验证法：,不等式组 表示的平面区域内的整数点共有 （ ）个,巩固练习1:,1 2 3 4 x,y

10、 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元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？(要求

11、每型卡车至少安排一辆）,解：设每天调出的A型车x辆，B型车y辆，公司所花的费用为z元，则,Z=320 x+504y,作出可行域中的整点，,可行域中的整点（8，0）时,Z=320 x+504y取得最小值，且Zmin=2608元,画出可行域,画直线l0:320 x+504y=0,平移直线l0到l的位置,直线l过,小结:,实际问题,线性规划问题,图解法,最优解,最优整数解,平移找解法,调整优值法,距离,斜率等,小结： 1。这节课,我们学习了把实际问题转化成线性规划问题即建立数模的方法,以及求解整点最优解的两种方法.建模主要分清已知条件中,哪些属于约束条件,哪些与目标函数有关.,2。求解整点最优解有两

12、种方法: 平移求解法与调整优值法.前者主要依赖 作图后者主要依赖推理,但一般都应充 分利用非整点最优解及最优值.,复习回顾：,二元一次不等式 表示平面区域,直线定界， 特殊点定域,简单的线性规划,约束条件,目标函数,可行解,可行域,最优解,求解方法：画、移、求、答,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处取得？ (课后思考题）若目标函