9512.net
甜梦文库
当前位置:首页 >> 高二数学 >>

谈一类简单线性规划问题最优解的发现


谈一类简单线性规划问题最优解的发现
湖北省麻城实验高级中学 阮 晓 锋
摘要: 本文介绍了一种发现简单线性规划问题非负整数最优解的普适方法。 它是在图解 平移法基础上先对最优解在可行域中的位置进行搜索定位, 再根据题意和不定方程知识进行 估值处理,通过调整目标函数值并借助解不等式组筛选出最优解的办法。 关键词:简单线性规划;整点最优解 作为新课标增加内容,高中数学教材对简单线性规划这一部分的叙述不够清晰,甚至 其描述有偏离,导致师生对它普遍缺乏认识,特别是对“当求得的理论最优解为非整数解时 如何得到符合实际的非负整数最优解” 普遍认识不足或认识有误。 为达成真正理解并解决问 题,下面结合教材例、习题谈谈我的发现。 由高中数学课本知,在可行域内与原点距离最近(或最远)的整点对应的解为整数最优 解。 但此法理论上可行, 实践上却严重依赖于作图和观察, 这就往往造成因误差而判断出错, 甚至会造成因相关整点太多而无从下手的情况。 因此, 我们迫切希望能找到一种可操作性强 的解决办法。其实,当理论最优解不是整数解时,我们可利用整数最优解的必要条件---目 标函数值为整数, 在目标函数理论最优值基础上通过逐步调整目标函数值, 再将其代入约束 条件通过解不等式组筛选出符合实际的最优解来。

例 1 要将两种大小不同的钢板截成 A、B、C 三种规格,每张钢板可同时截得三种规格的 小钢板的块数如下表所示: 规格类型 钢板类型 A 规格 2 1 B 规格 1 2 3 C 规格 1 第一种钢板 第二种钢板

今需要 A、B、C 三种规格的成品分别为 15、18、27 块,问各截这两种钢板多少张可得所需三 种规格成品,且使所用钢板张数最少? (新教材 63 页例 4) y 解:设需截第一种钢板 x 张,第二种钢板 y 张, 设所用钢板的张数为 z 张,则约束条件为: 2x+y≥15 x+2y≥18 x+3y≥27 x≥0,y≥0 目标函数为:z=x+y 可行域如上图所示(图 1) 根据目标函数向可行域方向作出一组平行直线:x+y=t, Y y y 1 1 8 1 6 1 4 1 2 8 0 6 4 2

A

X+3y=2 7 x

0 2 4 6 8 1 1214 1 18 2 22 24 26 2x+y=15 0 6X+2y= 0 我们发现:在这些直线中,过直线 x+3y=27 和直线 2x+y=15 交点 A(3.6,7.8)的直线经过 18

可行域且与原点的距离最近。此时 z 取得理论上的最小值 11.4。 显然 3.6 和 7.8 都不是整数,而最优解中,x 和 y 必须为整数,故(3.6,7.8)不是最优解。 由 x 和 y 必须为整数知 z 为整数,又要求的是 z 的最小值,故可先将 z 调整为 12,从而可 将直线 x+y=11.4 向上平移到 x+y=12,最优解就可能存在于此直线上。

? x ? 12 ? 15 ?24 ? x ? 18 9 ? 由 x+y=12 变形得 y=12-x,将它代入约束条件得 ? ,解之得 3 ? x ? 。 2 ?36 ? 2 x ? 27 ? x ? 0,12 ? x ? 0 ?
∴x=3 或 4,将它们代入 x+y=12 检验,得(3,9)(4,8)均为符合题意的最优整数解。 、 答:略 根据上面解答过程,我们可得到对一般的简单线性规划问题其解题步骤如下: 1.根据题意设出变量 x、y,再列出约束条件、建立线性目标函数; 2 利用约束条件画出可行域(即各约束条件所示区域的公共区域) ; 3 根据线性目标函数向可行域方向作一组平行直线 ax+by=t(t 为参数),再观察图形以找 到当直线 ax+by=t 移动时使 t 取到欲求最值的位置,然后通过联立方程解方程组求得其 数学理论上的最优解,并求出相应的目标函数理论最优值; 4 若上述数学理论上的最优解不是符合实际要求的非负整数最优解,则需先通过分析 调整目标函数取值(即参数 t 的值) ,再据此将 y 用 x 表示出来,将它代入约束条件 通过解不等式组得到缩小的 x 的取值范围,然后再在此基础上筛选得出符合实际要 求的非负整数最优解。

? 说明:在分析调整参数t的值时可能要用到下述《初等数论》中的定理 ? ? ? ? 定理:设二元一次方程ax ? by ? c, 其中a、b、c是整数,且a、b都不为0, ? ? ? 则此方程有整数解的充要条件为(a, b) c. | ? ?
例 2 某人有房子一幢,室内面积共 180m ,拟分隔成两类房间作为游客住房。大房间每间 2 2 面积为 18m ,可住游客 5 名,每名游客每天住宿费为 40 元;小房间每间面积为 15m ,可住 游客 3 名,每名游客每天住宿费为 50 元;装修大房间每间需 1000 元,装修小房间每间需 600 元。如果他只能筹款 8000 元用于装修,且游客能住满客房,他应隔出大房间和小房间 各多少间,能获得最大收益?(新教材 65 页习题 4) 解:设他应隔出大房间 x 间,小房间 y 间,能获得收益为 z 元。 18x+15y≤180 1000x+600y≤8000 x≥0,y≥0 目标函数:z=200x+150y 约束条件化简: 6x+5y≤60 5x+3y≤40 x≥0,y≥0 可行域如图所示(图 2)
2

再根据目标函数作一组平行直线:4x+3y=t

20 60 , )时直线与原点的距离最大。此时 z 取得理论上的 7 7 20 60 13000 1 最大值 z=200× +150× = =1857 ,但 x,y 均不为整数,故不是所求最优解。 7 7 7 7
由图知当这些直线中经过点 B( ∵(200,150)=50 且 50|1850 ∴可将 z 先调整为 1850,得 200x+150y=1850 即 4x+3y=37. 由 4x+3y=37 得 y=

37 ? 4 x (1) ,将它代入约束条件得: 3

37 ? 4 x ≤60 3 5 37 ? 4 x 5x+3× ≤40 ,解之得 ≤x≤3。 2 3 25 ∵x 为整数∴x=3,代入(1)得 y= 为非整数,故无符合题意最优解,因此还要进行调整。 3
6x+5× 再将 t 调整为 1800,则得 200x+150y=1800 即 4x+3y=36 由 4x+3y=36 得 y=

36 ? 4 x (2) ,又将其代入约束条件得: 3

36 ? 4 x ≤60 3 36 ? 4 x 5x+3× ≤40 再解之得 0≤x≤4, 3
6x+5× 又 x 为整数则 x=0,1,2,3 或 4,代入(2)求得它们对应的 y=12,

32 28 20 , ,8, 。 3 3 3

故此时可得最优解(0,12)和(3,8) ,它们对应的 z 的最大值为 z=1800。 答:略。 附若干练习题及提示 题 1:某人承揽一项业务,需做文字标牌 4 个,绘画标牌 6 个。现有两种规格材料,甲种规 格每张 3 平方米,可做文字标牌 1 个,绘画标牌 2 个;乙种规格每张 2 平方米,可做文字标 牌 2 个,绘画标牌 1 个.求两种规格的原料各有多少张,才能使总的用料面积最少? 说明:此题的非整点最优解为 ( , ) ,由非整点最优解在可行域内的对应点调整到可行域 内离该点最近的点,并不能得到整点最优解。否则得到的整点最优解为(3,1) ,而实际上本 体的整点最优解应为(2,2). 题 2:某工厂有一批长为 2.5m 的条形钢材,要截成长为 60cm 和 42cm 两种规格的零件 毛坯,试找出最佳方案,并计算材料的利用率。 提示:分别截成 60,42 的零件毛坯 2 根、3 根最合理,其利用率为 98%。 题 3:医院用甲、乙两种药片为手术后的病人配营养餐,已知甲种药片每片含 5 单位的 蛋白质和 10 单位的铁质,售价为 3 元,乙种药片每片含 5 单位的蛋白质和 4 单位的铁质, 售价为 2 元。若病人每餐至少需要 35 单位的蛋白质和 40 单位的铁质,则应使用甲、乙两种 药片各几片,才能既满足营养要求又使费用最省?

8 2 3 3

提示:可得 A ?

? 14 ? , 3 ? 是数学意义上的最优解,但 A’(3,3)才为符合要求的最优解。 ? 5 ?

题 4:某纺织厂生产甲、乙两种棉纱,已知生产甲种棉纱 1 吨需消耗一级子棉 2 吨、二 级子棉 1 吨,生产乙种棉纱 1 吨需消耗一级子棉 1 吨、二级子棉 2 吨,每一吨甲种棉纱的利 润是 600 元, 每一吨乙种棉纱的利润是 900 元, 工厂在生产这两种棉纱的计划中要求消耗一 级子棉不超过 300 吨、二级子棉不超过 250 吨,甲、乙两种棉纱各应生产多少吨能使利润总 额最大?(精确到吨) 提示:当生产甲种棉纱 116 吨、乙种棉纱 67 吨时,能使利润总额最大。 题 5:甲、乙、丙三种食物的维生素 A、维生素 B 含量及成本如下表.某食物营养研究所 想用这三种食物配制出 100kg 混合物, 并使混合物至少含 4600 单位维生素 A 和 5300 单位维 生素 B,问当三种食物各取多少 kg 时,配制的 100kg 混合物的成本最低?(精确到 1kg) 甲 维生素 A(单位/kg) 维生素 B(单位/kg) 成本(元/kg) 600 800 11 乙 700 600 9 丙 400 500 4

提示:本题数学最优解为 ?

? 30 120 ? , ? ,调整后的最优解为(4,,18) ,此时 Z min ? 518 . ? 7 7 ?

参考文献 [1]徐国文. 谈线性规划中的 “整点最优解” 处理方法. 中学生数学, 2003 年 1 月(上):4-5. [2]陈淦浩.从线性规划整点解问题的一种错误解法谈起.中学数学月刊,2004 年第 7 期:32-33. [3]侯宝坤.线性规划中求整点最优解的五种方法.数学通讯,2004 年第 24 期:10-11. [4]孙汉纯,温琦.线性规划中最优整点解的三种求法.高中数学教与学,2010 年第 1 期:11-12.


赞助商链接

更多相关文章:
浅析简单的线性规划的最优解问题
浅析简单的线性规划的最优解问题云南省普洱市,景谷县景谷一中 肖陆秀 引言:线性规划是运筹学的一个基础分枝,其应用及其广泛,其作用也越来越多的人重视,从历 年...
浅谈解简单线性规划问题的图解法
浅谈解简单线性规划问题的图解法 - 龙源期刊网 http://www.qikan.com.cn 浅谈解简单线性规划问题的图解法 作者:文香丹 来源:《教育教学论坛》2014 年第 39 期...
线性规划简单线性规划问题的向量解法
2.线性约束条件、线性目标函数、可行解、可行域、最优解等基本概念. 3.线性规划问题的图解方法. (二)能力训练要求 1.了解简单的线性规划问题. 2.了解线性规划...
简单线性规划问题教案
有公共点且纵截距最大或最小的直线; (3)求:通过解方程组求出最优解; (4...课堂小结 用图解法解决简单的线性规划问题的基本步骤: (1)画:画出线性约束条件...
简单的线性规划问题》教学设计
简单线性规划指的是目标函数含两个变量的线性规划, 其最优解可以用数形...发现、发展的过程,获得问题的解 决,这有助于培养学生的科学素养 3、反思过程,...
用Excel解决简单线性规划问题
用Excel解决简单线性规划问题_理学_高等教育_教育专区...一类常见问题,也是高中数学中的一个重点和难点问题,...多最优解的问题,该方法只能给出其中的一 个解,这...
教育部参赛_简单的线性规划问题_范谢艳
求有实际背景的简单线性规划问题最优解 的基本方法...组的学习情况,鼓励学生探究的积极性, 发现其中的...因此,教师应以问题驱动,创设恰当的问题情景,类似“...
简单线性规划教学设计
五、教学重点、难点重点:求简单线性规划问题的最优解。 难点: 学生对为什么要...性规划问题的步 骤 四、 课堂小结 学生思维的最近 发现区是上节的 相关知识,...
浅谈《简单的线性规划问题》与图形计算器的整合
学生多动手、多实践、鼓励学生应 用计算机、计算器等进行自主探索,并且创新发现...区域与相应直线的位置关系,如何用 图解法寻找线性规划问题中的最优解是该节课...
简单线性规划问题
课堂小结 用图解法解决简单的线性规划问题的基本步骤: 第 2 课时 前面我们学习了目标函数、线性目标函数、线性规划问题、可行解、可行域、最优解等概念 . 下用...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图