简单线性规划

5x+4y=202x+3y=12线性目标函数Z的最大值为44已知实数x,y满足下列条件:5x+4y≤

202x+3y≤12x≥0y≥0求z=9x+10y的最大值.最优解可行域9x+10y=0想一想:线性约束条件．．．．．．．．．．．．．0123456123456xy代数问题(线性约束条件)图解法转化线性约束条件可行域转化线性目标函数Z=Ax+By一组平行线转化最优解寻找平行线组的纵截距最值四个步骤：1、画4、答2、移3、求三个转化一.复习转化转化转化四个步骤：1。画（画可行域）三个转化4。答2。移（平移直线L。寻找使纵截距取得最值时的点）3。求（求出点的坐标，并转化为最优解）图解法想一想(结论):线性约束条件可行域线性目标函数Z=Ax+By一组平行线最优解寻找平行线组的

最大（小）纵截距3x+5y=25

例1：已知x、y满足，设z＝ax＋y(a>0)，若ｚ取得最大值时，对应点有无数个，求a的值。3x+5y≤25x

－4y≤－3x≥1xyox-4y=-3x=1CBＡ解：当直线

l

：y

＝－ax＋z与直线重合时，有无数个点，使函数值取得最大值，此时有：k

l

＝kAC

∵

kAC＝k

l

=-a∴

-a=∴

a=例2：满足线性约束条件的可行域中共有多少个整数解。x+4y≤113x+２y≤10x>0y>01223314455xy03x+２y=10x+4y=11解：由题意得可行域如图:

由图知满足约束条件的可行域中的整点为(1,1)、(1,2)、(2,1)、(2,2)

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

则z=5x+3y，应满足的约束条件是化简得

根据上述不等式组，作出表示可行域的平面区域，如图阴影部分所示。

画直线l0：5x+3y=0，平行移动l0到直线l的位置，使l过可行域中的某点，并且可行域内的其它各点都在l的包含直线l0的同一侧。

该点到直线l0的距离最大，则这一点的坐标使目标函数取最大值。容易看出，点M符合上述条件，点M是直线x－5y+1=0与直线3x+3y=37的交点。解方程组得点M(4，5).

因此，当x=4，y=5时，z取得最大值，并且zmax=5×4+3×5=35.答：A、B两区参与活动同学的人数分别为4，5时，受到服务的老人最多，最多为35人。例4.某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：设需截第一种钢板x张，第二种钢板y张，钢板总张数为Z,则

规格类型钢板类型第一种钢板第二种钢板A规格B规格C规格2121312x+y≥15,x+2y≥18,x+3y≥27,x≥0y≥0

某顾客需要A,B,C三种规格的成品分别为15，18，27块，若你是经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少。x张y张分析问题:求目标函数:z=x+y取最小值时的x,yx0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,y≥0直线x+y=12经过的整点是B(3,9)和C(4,8)，它们是最优解.

作出直线L:x+y=0，目标函数:z=

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

=

x+y，目标函数z

=

x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法在可行域内打出网格线，当直线经过点A时z=x+y=11.4,但它不是最优整数解，将直线x+y=11.4继续向上平移，12121827159781.平移找解法：其解题思路：找整点，验证算，选优解法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:根据非整点最优解,,,可知,当,都是整数时,.令,,代入约束条件整理可得:所以或,这样便知道了最优整点解.这种寻求整点最优解的方法可简述为调整优值法,即先求非整点最优解及最优值,再借助不定方程的知识调整最优值,最后筛选出整点最优解.3.调整优解法：

即先求非整数条件下的最优解，调整Z的值使不定方程Ax+By=Z存在最大（小）的整点值，最后筛选出整点最优解．

即先打网格，描出可行域内的整点，平移直线，最先经过或最后经过的整点坐标即为最优整解．线性规划求最优整数解的一般方法:1.平移找解法：

3.调整优解法：结论找整点，验证算，选优解

2.特值验证法：不等式组表示的平面区域内的整数点共有

（）个巩固练习1:1234xy432104x+3y=12练习2：求满足|x|+|y|≤4的整点（横、纵坐标为整数）的个数。xyo44－4－4共有：9+2(7+5+3+1)=41Xy084x=8y=47654321321x+y=104x+5y=30320x+504y=03.某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务，该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车，有10名驾驶员；每辆卡车每天往返的次数为A型卡车4次，B型卡车3次，每辆卡车每天往返的成本费A型卡车为320元，B型卡车为504元，问如何安排车辆才能使该公司所花的成本费最低，最低为多少元？(要求每型卡车至少安排一辆）解：设每天调出的A型车x辆，B型车y辆，公司所花的费用为z元，则x≤8{y≤4x+y≤10x,y∈N*4x+5y≥30Z=320x+504y作出可行域中的整点，可行域中的整点（8，0）时,Z=320x+504y取得最小值，且Zmin=2608元画出可行域画直线l0:320x+504y=0,平移直线l0到l的位置,直线l过小结:实际问题列表设出变量寻找约束条件建立目标函数转化建模线性规划问题图解法最优解三个转化四个步骤作答调整最优整数解平移找解法调整优值法常用方法目标函数距离,斜率等

小结：1。这节课,我们学习了把实际问题转化成线性规划问题即建立数模的方法,以及求解整点最优解的两种方法.建模主要分清已知条件中,哪些属于约束条件,哪些与目标函数有关.2。求解整点最优解有两种方法:平移求解法与调整优值法.前者主要依赖作图后者主要依赖推理,但一般都应充分利用非整点最优解及最优值.复习回顾：二元一次不等式

表示平面区域直线定界，

特殊点定域简单的线性规划约束条件目标函数可行解可行域最优解应用求解方法：画、移、求、答15课后练习:2.3.深圳市福田区水泥制品厂生产两种水泥，已知生产甲种水泥制品1吨，需矿石4吨，煤3吨；生产乙种水泥制品1吨，需矿石5吨，煤10吨，每1吨甲种水泥制品的利润为7万元，每1吨乙种水泥制品的利润是12万元，工厂