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

线性规划中整点最优解的求解策略1


线性规划中整点最优解的求解策略 线性规划中整点最优解的求解策略
在工程设计、经营管理等活动中,经常会碰到最优化决策的实际问题,而解决此类问题一般以 线性规划为其重要的理论基础。然而在实际问题中,最优解 (x,y) 通常要满足 x,y∈N ,这种最优解 称为整点最优解,下面通过具体例子谈谈如何求整点最优解 . 1.平移找解法 . 作出可行域后,先打网格,描出整点,然后平移直线 l,直线 l 最先经过或最后经过的那个整点 便是整点最优解. 例 1、某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有 72m3,第二种有 56m3,假 设生产每种产品都需要用两种木料,生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只 圆桌可获利 6 元,生产一个衣柜可获利 10 元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获 得利润最多? 木料(单位 m3) 产 品 第 一 种 圆 桌 衣 柜 0.18 0.09 第 二 种 0.08 0.28

解:设生产圆桌 x 只,生产衣柜 y 个,利润总额为 z 元,那么

?0.18 x + 0.09 y ≤ 72 ?0.08 x + 0.28 y ≤ 56 ? ? ?x ≥ 0 ?y ≥ 0 ?

而 z=6x+10y.

如图所示,作出以上不等式组所表示的平面区域,即可行域. 作直线 l:6x+10y=0,即 l:3x+5y=0,把直线 l 向右上方平移至 l1 的位置时,直线经过可行域上点 M,且 与原点距离最大,此时 z=6x+10y 取最大值。 解方程组 ?

?0.18 x + 0.09 y = 72 ,得 M 点坐标(350,100). 0.08 x + 0.28 y = 56 ?

答:应生产圆桌 350 只,生产衣柜 100 个,能使利润总额达到最大.

点评:本题的最优点恰为直线 0.18x+0.09y=72 和 0.08x+0.28y=56 的交点 M。 点评:

例 2 有一批钢管,长度都是 4000mm,要截成 500mm 和 600mm 两种毛坯,且这两种 1 毛坯按数量比不小于 配套,怎样截最合理? 3 设截 500mm 的钢管 x 根, 600mm 解: 的 y 根,总数为 z 根。根据题意,得

,目标函数为 ,
作出如图所示的可行域内的整点, 作一组平行直线 x+y=t,经过可行域内的 点且和原点距离最远的直线为过 B(8,0) 的直线,这时 x+y=8.由于 x,y 为正整数,知 (8,0)不是最优解。显然要往下平移该直线,在可行域内找整点,使 x+y=7,可知点(2,5)(3, , 4)(4,3)(5,2)(6,1)均为最优解. , , , 答:略. 点评: 点评:本题与上题的不同之处在于,直线 x+y=t 经过可行域内且和原点距离最远的点 B(8,0) 并不符合题意,此时必须往下平移该直线,在可行域内找整点,比如使 x+y=7,从而求得最优解。 从这两例也可看到,平移找解法一般适用于其可行域是有限区域且整点个数又较少,但作图要 求较高。

二、整点调整法
先按“平移找解法”求出非整点最优解及最优值,再借助不定方程的知识调整最优值,最后筛 选出整点最优解.

y

?2 x ? y ? 3 > 0 ? 例 3.已知 x, y 满足不等式组 ? 2 x + 3 y ? 6 < 0 ,求使 x + y ?3 x ? 5 y ? 15 < 0 ? 取最大值的整数 x, y . 解 : 不 等 式 组 的 解 集 为 三 直 线 l1 : 2 x ? y ? 3 = 0 , l2 :
2 x + 3 y ? 6 = 0 , l3 : 3 x ? 5 y ? 15 = 0 所围成的三角形内部(不

l1
A

l3
C

O

x l2

B

含边界) 设 l1 与 l2 ,1 与 l3 , 2 与 l3 交点分别为 A, B, C , A, B, C 坐标分别为 A( , l l 则

15 3 , ) ,B (0, ?3) , 8 4

C(

75 12 ,? ) , 19 19

作一组平行线 l : x + y = t 平行于 l0 : x + y = 0 , 当 l 往 l0 右上方移动时, t 随之增大,

∴当 l 过 C 点时 x + y 最大为

63 ,但不是整数解, 19

75 知 x 可取 1, 2,3 , 19 当 x = 1 时,代入原不等式组得 y = ?2 , ∴ x + y = ?1 ; 当 x = 2 时,得 y = 0 或 ?1 , ∴ x + y = 2 或 1 ; 当 x = 3 时, y = ?1 , ∴ x + y = 2 , ?x = 2 ?x = 3 或? . 故 x + y 的最大整数解为 ? ? y = 0 ? y = ?1
又由 0 < x < 3.逐一检验法 逐一检 逐一 由于作图有时有误差,有时仅有图象不一定就能准确而迅速地找到最优解,此时可将若干个可 能解逐一校验即可见分晓. 例 4 一批长 4000mm 的条形钢材,需要将其截成长分别为 518mm 与 698mm 的甲、乙两种毛坯, 求钢材的最大利用率. 解:设甲种毛坯截 x 根,乙种毛坯截 y 根,钢材

的利用率为 P ,则

①,目

标函数为 ②,线性约束条 件①表示的可行域是图中阴影部分的整点.②表示 与直线 518x+698y=4000 平行的直线系。 所以使 P 取 得最大值的最优解是阴影内最靠近直线 518x+698y=4000 的整点坐标.如图看到(0,5),(1, 4),(2,4),(3,3),(4,2),(5,2),(6,1),(7, 0)都有可能是最优解, 将它们的坐标逐一代入②进行 校验,可知当 x=5,y=2 时, .

答:当甲种毛坯截 5 根,乙种毛坯截 2 根,钢材的利用率最大,为 99.65%. 解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确,图上操作尽 可能规范,但考虑到作图时必然会有误差,假如图上的最优点并不十分明显易辨时,不妨将几个有 可能是最优点的坐标都求出来,然后逐一进行校验,以确定整点最优解.


赞助商链接

更多相关文章:
简单线性规划整点最优解问题研究
在资料上也经常见 到有关简单线性规划整点最优解问题的求解方法, 如: 网格法...一 平移交轨法该方法主要是在平移直线过程中, 利用直线间的交点来缩小最优值...
线性规划中的整点问题求解方法
线性规划中整点最优解的求... 3页 1财富值 用线性规划方法求解运输问... 8页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...
线性规划类型及策略改编
线性规划类型及策略改编_数学_自然科学_专业资料。线性规划基本类型及策略一.线性...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
第二讲 线性规划 教师
3 ? 0 O 七、线性规划中整点最优解的求解策略 1.平移找解法 例 有一批钢管,长度都是 4000mm,要截成 500mm 和 600mm 两种毛坯,且这两种毛坯按数量比不...
例析线性规划中的整点最优解
例析线性规划中的整点最优解浙江 徐志平 【大中小】【关闭】 在组织社会化生产、 经营管理活动 中, 我们经常会碰到最优决策的实际问 题。 而解决这类问题的...
线性规划 说课稿(定稿)江西省新余市第四中学 聂清平
1.建立数学模型.把实际问题转化为线性规划问题; 2.寻找整点最优解.线性规划中寻找整点最优解的问题,教材中提供 了利用作图解决问题的方法,这种方法简单方便,学生...
线性规划 说课稿(定稿)
1.建立数学模型.把实际问题转化为线性规划问题; 2.寻找整点最优解.线性规划中寻找整点最优解的问题,教材中提供 了利用作图解决问题的方法,这种方法简单方便,学生...
谈一类简单线性规划问题最优解的发现
关键词:简单线性规划;整点最优解 作为新课标增加内容,高中数学教材对简单线性规划部分的叙述不够清晰,甚至 其描述有偏离,导致师生对它普遍缺乏认识,特别是对...
线性规划习题精选精讲(含答案)
习题精选精讲 线性规划常见题型及解法线 性规划是新教材中新增的内容之一 ,由...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
线性规划
直线与线性规划问题题型一:求线性目标函数的最值 ?...题型三:寻找线性规划问题整点最优解 4. 某...卷第 18 题 题型四:非线性规划问题的求解策略 ?...
更多相关标签:

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

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