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

简单线性规划整点最优解问题研究


简单线性规划整点最优解问题研究
宋永峰

随着中学数学教育的改革和发展, 简单线性规划问题已经逐渐成为中学数学 教学的一个基本内容。 简单线性规划问题与我们的日常生活息息相关,它主要涉 及人力、物力、资金等资源的最优配置。作为中学数学教学,整点最优解问题是 简单线性规划的核心内容, 但教材对于具体的验算过程并没有作过多的描述,以 致中学生在解题过程中对于具体的验算过程掌握还不够清晰。 在资料上也经常见 到有关简单线性规划整点最优解问题的求解方法, 如: 网格法, 穷举法, 筛选法, 最小距离法等。 本文将介绍利用平移法求整点最优解的几种具体的操作方法—平 移交轨法,平移换元法,平移近值法。

一 平移交轨法
该方法主要是在平移直线过程中, 利用直线间的交点来缩小最优值的存在范 围,因此其主要思想是联立方程求解交点,然后确定最优解可能的存在范围。 例 1 要将两种大小不同的钢板截成 A、B、 C 三种规格,每张钢板可同时截得 三种规格的小钢板的块数如下表所示: 规格类型 钢板类型 第一种钢板 A 规格 2 B 规格 1 C 规格 1

第二种钢板 1 2 3 今需要 A、B、C 三种规格的成品分别为 15、18、27 块,问各截这两种钢板多少 张可得所需三种规格成品,且使所用钢板张数最少? (新教材 63 页例 4) 分析:这类问题涉及物资的优化配置,在任务一定的条件下,使物资用量最少。 设需截第一种钢板 x 张,第二种钢板 y 张,设所用钢板的张数为 z 张,则: 2x+y≥15 Y y x+2y≥18 y y x+3y≥27 x≥0,y≥0 目标函数为:z=x+y 可行域如图所示(图 1) 根据目标函数作出一组平 行直线 :x+y=t 。这些直线 中经过可行域且和原点距 离最近的直线 , 此直线经 直线 x+3y=27 和 2x+y=15

1

的交点 A(

18 39 , ),此直线与原点的距离最近,z 取得最小值,即: 5 5 57 5

z=x+y= 显然

18 39 和 都不是整数,而最优解中,x 和 y 必须为整数,故 A 不是最优解,故将直 5 5 57 线 x+y= 向上平移到 x+y=12,最优解可能存在于此直线上。最优解必须在可行 5 域内,故应求出直线 2x+y=15 和 x+3y=27 与 x+y=12 的交点:

2x+y=15 x+y=12

x+3y=27 x+y=12

9 15 9 可得交点坐标为 B(3,9),D( , ),故有:3≤x≤ 2 2 2

这样便更进一步的缩小了 x 的范围,即 x=3 或 4,将其代入 x+y=12 ,可得 y=9 或 8。即(3,9)和(4,8)均为所求的最优解。 根据上述的分析解答过程, 我们可以看到利用平移交轨法解题对于一般的简 单线性规划问题都是适用的,其解题步骤如下: 1 2 3 4 5 设出所求的未知数,列出约束条件,建立目标函数; 作出可行域; 确定平移直线,寻找非整最优解; 联立方程求交点确定 x 或 y 的范围; 对 x,y 进行整点搜索,并确定整点解。

二 平移换元法
该方法仍然是以平移法为基础,主要是利用换元来减少线性约束条件的元 数,以得出参数的范围,从而确定出变量 x,y 的取值,再来确定最优解的可能 值。 例 2 某人有房子一幢, 室内面积共 180m2, 拟分隔成两类房间作为游客住房。 2 大房间每间面积为 18m ,可住游客 5 名,每名游客每天住宿费为 40 元;小房间 每间面积为 15m2,可住游客 3 名,每名游客每天住宿费为 50 元;装修大房间每 间需 1000 元,装修小房间每间需 600 元。如果他只能筹款 8000 元用于装修,且 游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益?(新教 材 65 页习题 4) 分析:这类问题涉及物资的优化运用,在物资一定的条件下,要求获利最 大。

2

设他应隔出大房间 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) 根据目标函数作一组平行 直线:4x+3y=t,这些直线 20 60 中经过 B( , )的直 7 7 线与原点的距离最大。此 时 z=200x+150y 取 最 大 20 60 13000 值 ,z=200× +150× = 。但此时 x,y 均不为整数,故不是最优解, 7 7 7 1 因此又要进行调整。故因将直线 4x+3y=37 ,向左下方平移,又 z 为整数,故 7 应平移至 4x+3y=37 (1) 由(1)知 y= 6x+5×
37 ? 4 x ,将其代入约束条件: 3

37 ? 4 x ≤60 3 37 ? 4 x 5x+3× ≤40 3 5 可得 ≤x≤3。又 x 为整数,则 x=3,此时 y 为非整数,故在直线 4x+3y=37 时 2 无最优解,又向下方平移一个单位:4x+3y=36(2)

由(2)知 y= 6x+5×

36 ? 4 x ,将其代入约束条件: 3

36 ? 4 x ≤60 3 36 ? 4 x 5x+3× ≤40 3 可得 0≤x≤4,x 为整数则 x=0,1,2,3 或 4,代入(2)求得它们对应的 y=12, 32 28 20 , ,8, 。故可得最优解有(0,12)和(3,8) ,此时 z=1800。 3 3 3

平移换元法对一般的简单线性规划问题也都适用, 根据上面的例题分析我们
3

将其一般步骤归纳如下: 1 设出所求的未知数,列出约束条件,建立目标函数; 2 作出可行域; 3 确定平移直线,寻找非整最优解; 4 由直线方程换元代入约束条件,并求变量范围: 5 对 x,y 进行整点搜索,并确定整点解。

三 平移近值法
该方法也是以平移直线为基础, 但它并非一步一步的平移, 而是在非整点最 优解附近搜索,同时结合网格(并非所有网格都打出) ,直接找出附近的整点来 减小搜索范围,从而求出整点最优解。 下面以例 2 求解介绍此法。 分析:设他应隔出大房间 x 间,小房间 y 间,能获得收益为 z 元。 6x+5y≤60 5x+3y≤40 x≥0,y≥0 目标函数:z=200x+150y 可行域如图所示(图 3) 作直线: 4x+3y=0 ,平 移到 B 点时, z 取得最大值, 20 60 但 B( , )并非整点, 7 7 故我们要进一步来搜索。由 20 60 于B ( , ) , 我们利用 B 7 7 附近的网格, 可在 B 附近找 到 A(2,9) 、C(2,8) 、D (3,8)这几个整点。此时 还必须从中选出一个最适 合 的 点 : z1=8+27=35 ; z2=8+24=32 ; z3=12+24=36 故在直线平移过程中, 必先过 D 点, 因此 A.C 两点 被淘汰,故过 D 作直线: 4x+3y=36 此后, 必需检验阴 影区域内有无整点,此时要利用阴影区的网格寻找整点。经检验无整点。故直线 4x+3y=36 上必存在最优整点解。利用网格知: (0,12) , (3,8)为最优整点解。 平移近值法可以克服在前两种方法中有可能要多次平移找解的缺陷, 适用范 围广泛。其一般步骤归纳如下: 1 设出所求的未知数,列出约束条件,建立目标函数;
4

2 作出可行域; 3 寻找非整点最优解 A,根据 A 点的坐标在其附近寻找最近的整点 B; 4 过 B 作平移直线,通过直线确定较小的搜索范围; 5 利用部分网格在确定的范围内求最优解。 总之, 以上三种基本方法都是以平移法为基础,对于一般的简单线性规划问 题都能够求解。前两种方法的相似点很多,首先它们的基点相同,适用范围几乎 相同,但对于目标函数 t=ax+by,若 t,a,b 经约分后仍较大时,运用以上两种 方法均要调整多次才可能达到最优。平移近值法弥补了前两种方法的不足,直接 在非整点最优解附近的小范围内搜索,借用部分网格得出整点最优解。三种方法 各有各的特点,因此有时要根据具体情况选择合理的方法。

5


赞助商链接

更多相关文章:
简单线性规划最优解
简单线性规划最优解 - 教你如何做出最佳选择 ——简单线性规划最优解 在线性约束条件下,求线性目标函数最值问题,称为“线性规划”。目标函 数 z ? ...
教你如何做出最佳选择——简单线性规划最优解
掌握造成了一定的困难,针对这一问题,总结两 种寻找最优整解的方法与大家探讨。...线性规划整数解问题的一般 处理方法是: 若区域 “顶点” 处恰为整点,那么它...
...教你如何做出最佳选择-简单线性规划最优解 苏教版...
构建一流优质合作探究课堂教你如何做出最佳选择——简单线性规划最优解在线...线性规划整数解问题的一般处理方法是:若区域“顶点”处 恰为整点,那么它的最...
线性规划常见题型及解法
利用线性规划研究问题,大致可归纳为两种类型:第 一种类型是给定一定数量的人力...线性规划整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
高二数学简单线性规划教案 人教版
渗透转 化的思想、数形结合的思想解决问题。 高二数学简单线性规划教案——...掌握寻找整点最优解的方法. 二、教学建议: ( 1 )对作业、思考题、研究性题...
人教版-高中数学必修5--简单线性规划问题教案
人教版-高中数学必修5--简单线性规划问题教案 - 简单线性规划问题 教学目标: 1.了解线性规划的意义,了解线性约束条件、线性目标函数、可行解、可行域和最优解...
简单线性规划教案一
表示的平面区域: 如图,图中的阴影部分的整点(坐标为整数的点)就代表所有可能...最大或最小值的可行解叫线性规划问题最优解. 1、 变换条件,加深理解 探究...
运筹学--线性规划问题最优解的确定与改进
⑤ 若迭代过程中发现问题的目标函数值无界,则终止迭代。 2006 年甘肃联合大学学报(自然科学版)第三期,在熊洪斌发表的论文《线性规划最优解的进一步 研究》 中研究...
线性规划最优整数解问题
线性规划最优整数解问题河北省景县梁集高中 张国营 线性规划是高中数学新教材...个端点之间(包含这两个端点)的整点只有 B(3,9) 、C(4,8)是最优整数解...
简单线性规划问题学案
简单线性规划问题学案 - 简单线性规划问题学案 单县一中:潘朋瑞 学习目标:了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解 等基本概念;了解...
更多相关标签:

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

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