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%. 解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确,图上操作尽 可能规范,但考虑到作图时必然会有误差,假如图上的最优点并不十分明显易辨时,不妨将几个有 可能是最优点的坐标都求出来,然后逐一进行校验,以确定整点最优解.



更多相关文章:
简单线性规划整点最优解问题研究
在资料上也经常见 到有关简单线性规划整点最优解问题的求解方法, 如: 网格法...一 平移交轨法该方法主要是在平移直线过程中, 利用直线间的交点来缩小最优值...
线性规划中整点问题的求解策略
线性规划中整点问题的求解策略_高一数学_数学_高中教育_教育专区。线性规划中整...(6,1)均为最优解.答:略. 点评:本题与上题的不同之处在于,直线 x+y=t...
线性规划类型及策略改编
线性规划类型及策略改编_数学_自然科学_专业资料。线性规划基本类型及策略一.线性...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
第二讲 线性规划 教师
3 ? 0 O 七、线性规划中整点最优解的求解策略 1.平移找解法 例 有一批钢管,长度都是 4000mm,要截成 500mm 和 600mm 两种毛坯,且这两种毛坯按数量比不...
线性规划
其中例 6 是一个求 整点最优解的问题,更是线性规划问题的一个难点中的难点...但总得来说本质都 是以平移法为基础,对于一般的简单线性规划问题都能够求解。 ...
线性规划中的整点问题求解方法
线性规划中的整点问题求解方法宜昌市一中 祝海燕 线性规划是运筹学的一个重要...由于实际问 题中线性规划问题的最优解多为整数解,也是学生学习线性规划的难点,...
例析线性规划中的整点最优解
例析线性规划中的整点最优解浙江 徐志平 【大中小】【关闭】 在组织社会化生产、 经营管理活动 中, 我们经常会碰到最优决策的实际问 题。 而解决这类问题的...
线性规划习题精选精讲(含答案)
习题精选精讲 线性规划常见题型及解法线 性规划是新教材中新增的内容之一 ,由...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
可行域内整点的最优解
线性规划中整点最优解的求解策略 线性规划中整点最优解的求解策略在工程设计,...木料(单位 m3) 产品第一种圆桌衣柜 0.18 0.09 第二种 0.08 0.28 解:...
线性规划习题精选精讲
一,求线性目标函数的取值范围 例 1, 若 x,y 满足约束条件 x ≤ 2 y ≤...线性规划中整点最优解的求解策略 线性规划中整点最优解的求解策略 在工程设计...
更多相关标签:

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

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