简单的线性规划问题（二）.ppt

《简单的线性规划问题（二）.ppt》由会员分享，可在线阅读，更多相关《简单的线性规划问题（二）.ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、xyo简单的线性规划问题（二）简单的线性规划问题（二）复习回顾：二元一次不等式二元一次不等式表示平面区域表示平面区域直线定界，直线定界，特殊点定域特殊点定域简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解应应用用求解方法：画、求解方法：画、移、求、答移、求、答例例1、湖南电视台、湖南电视台“我是歌手我是歌手”节目正在热播，现节目正在热播，现其赞助商其赞助商“立白洗衣液立白洗衣液”要求增加歌手来增加不低要求增加歌手来增加不低于于66万的收视率，以达到其广告的期望效益，而万的收视率，以达到其广告的期望效益，而赞助总费用不能超过赞助总费用不能超过10万

2、。若增加万。若增加1名男歌手可增名男歌手可增加加18万的收视率，相应费用增加万的收视率，相应费用增加4万；增加万；增加1名女名女歌手收视率可增加歌手收视率可增加15万，相应费用增加万，相应费用增加1万。由于万。由于播出时间限制，电视台要求尽量少增加歌手，问应播出时间限制，电视台要求尽量少增加歌手，问应该如何安排增加男女歌手各自的人数该如何安排增加男女歌手各自的人数?解：设解：设x、y分别为增加男女歌手的人数，于是满足以下条分别为增加男女歌手的人数，于是满足以下条件件:x N*y N*目标函数为目标函数为Zxy，把把Zxy变形为变形为yxz，它表示斜率为，它表示斜率为1，在，在y轴上的截距为轴上

3、的截距为z的一组直线系。的一组直线系。容易求得容易求得M点的坐标为（点的坐标为（2，2），则），则Zmin4x0M(2，2)y18x+15y=664x+y=10例例2 2、要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A A、B B、C C三三种种规规格格，每每张张钢钢板板可可同同时时截截得得三三种种规格的小钢板的块数如下表所示规格的小钢板的块数如下表所示 ：规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A A规格规格B B规格规格C C规格规格2 21 12 21 13 31 1今需要今需要A,B,CA,B,C三种规格的成品分别为三种规格的成品分别为1

4、515，1818，2727块，问各截这两种钢板多少张可得所需块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。三种规格成品，且使所用钢板张数最少。解：设需截第一种钢板解：设需截第一种钢板x x张、第二种钢板张、第二种钢板y y张，可得张，可得2x+y=15x+3y=27x+2y=18x+y=0直线直线x+yx+y=12=12经过的整点是经过的整点是B(3,9)B(3,9)和和C(4,8)C(4,8)，它们是最优解，它们是最优解.作出一组平行直线作出一组平行直线z z =x+yx+y，目标函数目标函数z=z=x+yx+yB(3,9)C(4,8)A(18/5,39/5)当当直直

5、线线经经过过点点A A时时z=z=x+yx+y=11.4=11.4,但但它它不不是是最最优优整整数数解解.作直线作直线x+yx+y=12=12x+y=12解得解得交点交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值法调整优值法2x+y15,x+2y18,x+3y27,x0,xN*y0 yN*x0yx0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xN*y0 yN*经经过过可可行行域域内内的的整整点点B(3,9)和和C(4,8)且且和和原原点点距距离离最近的直线是最近的直线是x+y=12，它们是最优解它们是最优解.答答:(略略)作

6、出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z=z=x+yx+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A A时时z=z=x+yx+y=11.4=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移,变式：第一种钢板100元一块，第二种钢板200元一块，各截这两种钢板多少张，可得所需三种规格的成品且所花费最小？小结：小结：求线性规划问题的最优整数解时，常求线性规划问题的最优整数解时，常用用打网格线打网格线和和调整优值调整优值的方法的方法.要求作图必要求作图必须精确，线性目标函数对应的直线斜率与其须精确，线性目标函数对应的直线斜率与其他直线的斜率关系要把握准确。他直线的斜率关系要把握准确。