



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、72.线性规划中最优整解的一种求解方法(陕西省小学教师培训中心王凯成 710600)正如文1 所说,“在线性规划问题中,最令学生、教师头疼的莫过于如何寻找最优整解. 通常作法是用网格法,即把可行域中的整点标出,再通过代点检验来完成最优整解寻找;不 过这种方法要经过大量繁复的运算才能保证结果的正确性.”笔者经过研究,找到了一种快 速求解线性规划中最优整解的方法,这种方法不需要作出可行域,简化了作图这一步骤,而 且计算量小,更容易掌握.例1 (文1例2)某人有楼房一幢,室内面积共180m2,拟分割成两类房间作为旅游 客房,大房间每间面积为18m2,可住游客5名,每名游客每天住宿费为40元;小房间每
2、 间面积为15m2,可住游客3名,每名游客每天住宿费为50元;装修大房间每间需1000 元,装修小房间每间需600元.如果他只能筹款8000元用于装修,且游客能住满客房,他应 隔出大房间和小房间各多少间,能获得最大收益?(人教社编高中数学第二册p65习题7.4 第4题)解 设隔出大房间x间,小房间y间,收益为z元,z = 200 x+150y = 50 (4x+3y)= 50z,Z = 4x+3y,使z尽可能地大,x、y满足约束条件:8x+15y 1801000 x+600y 8000 x N、y N4x+3y=z,的通解为:尸,一河 N)y = - z + 4t (t Z)18x+15y 1
3、80f z + 2t 60 1000 x+600y 80002z- 3t 40 x3 + x 2 有:7 z 260 n z 371 n Z 37.7由及知:奖-也 t (t Z)32当z = 37时,由知:11上 t 111,但t 乙无解.322当z = 36时,由知:10 t 12,但t 乙所以t=11或t=12.当z = 36且t = 11时,由4x+3y = z的通解知:x = 3, y = 8.当 z = 36 且 t = 12 时,由 4x+3y = z的通解知:x = 0, y = 12.注意到x30,y30.所以,z的最大值为36,z的最大值为50X36=1800.答:应隔出大
4、房间3间,小房间8间;或者隔出小房间12间.这都能获得最大效益.例2 某工厂生产甲、乙两种产品.已知生产甲种产品1t需耗A种矿石10t、B种矿石 5t、煤4t;生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是 600元,每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿 石不超过300t、B种矿石不超过200t、煤不超过360t.甲、乙两种产品应各生产多少(精确 到0.1t),能使利润总额达到最大?(人教社编高中数学第二册p61例3)解设甲种产品生产x个0.1t,乙种产品生产y个0.1t,利润总额为z元则z = 60 x +100y =
5、20 (3x + 5y) = 20z, z = 3x + 5y,应使z尽可能地大.x、y满足约束条件:x + 0.4y 3000.5x + 0.4y 2000.4x + 0.9y 360 x e N,y e N3 x + 5 y = z的通解为:x = 2Z-5t(Z e N) y = -z,+ 3t(t e Z)x + 0.4y 300 0.5x + 0.4y 200 n 0.4x + 0.9y 36010 x + 4y 3000 5x + 4y 20004x + 9y 360016z- 38t v 6z- 13t 2000-z+ 7t 3600 x 7 + x 13有:29Z 60800
6、n Z 2096(Z e N).由、知:166二3000 t 迎土 (t e Z) TOC o 1-5 h z 387且竺* t 迎土 (t e Z您13775z的最大可能值为2096.当z= 2096时,由知:813 t 813,但是t e Z,无解;13714z的最大可能值为2095.当z = 2095时,由知:813 t 813,但是t e Z,无解;137z的最大可能值为2094.当z = 2094时,由知:812 t 8133,但是t e Z,只有t=813.137注意到t=813也满足.所以当z=2094且t=813时,由3x+5y=z的通解知:x=123,y=345.注意到x 3
7、0,y 30.故知z的最大值为2094,z的最大值为20X2094 =41880.答:应生产甲产品约12.3t,乙产品约34.5t,能使利润总额达到最大.(注:例2解法说明中学数学教材给出的解法是不妥的)例3 本公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告,广告 总费用不超过9万元,甲、乙电视台的广告收费标准分别为500元/分钟和200元/分钟,规 定甲、乙两个电视台为该公司所做的每分钟广告,能给公司带来的收益分别为0.3万元和0.2 万元。问该公司如何分配在甲、乙两个电视台的广告时间,才能使公司的收益最大,最大收 益是多少万元? (2007年山东省高考数学文科第19题)
8、解:设公司在甲电视台和乙电视台做广告的时间分别为x分钟和y分钟,总收益为z元. 由题意得目标函数为 z = 3000 x + 2000y = 1000 (3x + 2y) = 1000 z,z = 3x + 2y,应使x + y 300z尽可能地大.整数x、y满足约束条件:v 500 x + 200y 0, y 03x + 2y = z的通解为 = z-2了 e N).y = - z3t (t e N)x + y 300 x + y 300v 500 x + 200y 90000n 5x + 2y x 0, y 0 x 0, y 0t 3003 z - 4t 900故 3z 4t + 900
9、4 x 300 + 900 = 2100,所以 z 700.当 z取最大值 700 时,t 取最大 值 300,此时 x = 100,y = 200. z 的最大值为 1000 x 700 = 700000.答:该公司在甲电视台做100分钟广告,在乙电视台做200分钟广告,公司的收益最大, 最大收益是70万元.例4 某公司招收男职员x名,女职员y名,x和y须满足约束条件 TOC o 1-5 h z 5 x - 1 Ay- 2 22x + 3y,9则z = x H0的最大值是2x -222x + 3y 92x -225z-16t-22 9x=矿 t, y=t_ 92x 112 Z - 2t 11
10、 II + ( -8)x 有:-11z,3 - 110 n z,W 10 .由及有:z-11 t 22 + 55 (t e Z)216当 z,= 10 时,由知:4.5W t W 4.5 (tZ),无解.当 z,= 9 时,由知:3.5W t W 4.1875 (tZ), n t = 4 .当z,= 9及t = 4时也满足,由知:x = 5, y = 4.注意到x = 5,y = 4及xN、yN,故知2,的最大值为9, z的最大值为9X10 = 90 . 选择C.根据以上例题可见,快速准确地寻找线性规划问题的整点最优解的一般步骤为:(1)设线性目标函数z = Ax + By = d (ax+b
11、y) = d z,其中d是A与B的最大公约 数,z,= ax+by, (a, b) =1.x=x z,-bt。(t e Z).y=y z,+at(3)将x=x0z,-bt,y=y0z,+at (t e Z )代入线性约束条件化简,并消去参数t, 得到z,Wc (或z,3c),c是整数.(4)由约束条件得到不等式g (z,)WtWh (z,).(5)依次将 z,=c、c-1、c-2、(或依次将 z,=c、c+1、c+2、)代入 g (z,)W t W h ( z,),将第一次得到满足所有约束条件的整数t及相应的z,的值代入 x=x z-bt =0z,+at(t e Z)中就可以得到该整数规划问题的最优解.I 0参考文献1贾耕、张弢,线性规划中最优整解的一种寻找方法J,数学通报,2005, 12.2王凯成,充分利用目标函数解整数规划问题J,数学教学,2004,9.3全日制普通高级中学教科书(必修)数学第二册(上),人民教育出版社,2004年6 月第1版.4安培录,如何寻找线性规划问题的整点最优解J,数学通报,2000,3.5 文吉华,对“如何寻找线性规划问题的整点最优解”一文具体操作中的补充和 完善J,数学通报,200
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 甲供材料合同范本
- 幼儿园托管协议合同8篇
- 居间合同居间合同
- 2025年克拉玛依c1货运从业资格证考试内容
- 工程施工监理合同
- 专项工程承包合同文本
- 建筑工程项目分包合同
- 增加附录条款鱼种购销合同
- 运输水合同范本
- 卷烟战略市场规划报告
- VTE防治在临床科室的落地
- 2025年度个人住房买卖合同(带家居家具)
- 生产车间布局优化与现场改善的策略研究
- 文化自信-最炫中国风(2024年内蒙古赤峰中考语文试卷非连续性文本阅读试题)
- 中央2025年中国作家协会所属单位招聘11人笔试历年参考题库附带答案详解
- 2025年南京信息职业技术学院高职单招职业适应性测试近5年常考版参考题库含答案解析
- 《餐饮业发展》课件 - 探索美食世界的奥秘
- (新版)广电全媒体运营师资格认证考试复习题库(含答案)
- 2024年法律职业资格考试(试卷一)客观题试卷与参考答案
- 安全生产重大事故隐患排查报告表
- 小学音乐课后服务教学设计方案计划
评论
0/150
提交评论