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

例析线性规划中的整点最优解


例析线性规划中的整点最优解
浙江 徐志平 【大 中 小】【关闭】

在组织社会化生产、 经营管理活动 中, 我们经常会碰到最优决策的实际问 题。 而解决这类问题的现代管理科学以 线性规划为其重要的理论基础, 其本质 都是寻求整个问题的某项整体指标的 最优解。但在实际问题中,最优解 (x,y) 通常要满足 x,y∈N , 这种最优 解称为整点最优解, 下面通过具体例子 谈谈如何求整点最优解 . 1.平移找解法 作出可行域后,先打网格,描出整点,平移直线 整点最优解. 例 1 有一批钢管,长度都是 4000mm,要截成 500mm 和 600mm 两种毛坯,且这两种毛 坯按数量比不小于 配套,怎样截最合理? ,最先经过或最后经过的整点便是

分析:先设出未知数,建立约束条件和目标函数后,再通过平移直线,使它经过整点 的方法来求整点最优解.

设截 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)均为最优解.

答:略. 例 2 某运输公司接受了向抗洪抢险地区每天至

少送 180t 支援物资的任务。 该公司有 8 辆载重为 6t 的 A 型卡车与 4 辆载重为 10t 的 B 型卡车, 有 10 名驾驶员; 每辆卡车每天往返的次数为 A 型卡 车 4 次,B 型卡车 3 次;每辆卡车每天往返的成 本费 A 型车为 320 元,B 型车为 504 元。请你们 为该公司安排一下应该如何调配车辆,才能使公 司所花的成本费最低? 解: 设每天调出 A 型卡车 x 辆、B 型卡车 y 辆,公司所花的成本为 z 元,则

,目标函数 z=320x+504y, 作出可行域如图示阴影部分内的整点,打出网格,描出整点,网格上的交叉点为整点. 作 L0:320x+504y=0,往上平移直线 L0,当直线经过可行域内的点 A(7.5,0)时可使 Z 最小,但 A 不是整点,继续往上平移,最先经过的整点是(8,0). 即只调配 A 型卡车,所花最低成本费 z=320×8=2560(元). 答:略.这种方法首先要充分利用非整点最优解的信息,结合精确的作图才行,当其 可行域是有限区域且整点个数又较少,通常可行域是封闭的多边形,这时可以通过平 移直线找到最优解. 2.调整优值法 先求出非整点最优解及最优值,再借助不定方程的知识调整最优值, 最后筛选出整点最优解. 例 3 要将两种大小不同的钢板截成 A、B、C 三种规格,每张钢板可同时截得三种规格 的小钢板的块数如下表所示:
规格类型 钢板类型 第一种钢板 第二种钢板

A 规格 2 1

B 规格 1 2

C 规格 1 3

今需要 A、B、C 三种规格的成品分别为 15、18、27 块,问各截这两种钢板多少张可得

所需三种规格成品,且使所用钢板 张数最少? 解:设需截第一种钢板 x 张,第二 种钢板 y 张,共需 z 张则

作出可行域如图示阴影部分内的整点,目标函数 为 z =x+y.作出一组平行直线 x+y=t, 其中经过 可行域内的点且和原点距离最近的直线,经过直 线 x +3y=27 和直线 2x+y=15 的交点 A



),直线方程为 x+y=

. 由于

都不是整数,所以( 当 条件,可得 时, z=11 ,可知当 时,

)不是最优解 .

,令 x+y=12,y=12-x 代入约束

,所以 x=3 或 4 ,即经过可行域内的整点且与原点距离最近的

直线是 x+y=12, 经过的整点是 B(3,9) 和 C(4,8), 它们都是最优解. 答: 要截得所需三种规格的钢板,且使所截两种钢板的张数最少的方法有两种:第一种 截法是截第一种钢板 3 张.第二种钢板 9 张;第二种截法是截第一种钢板 4 张、第二种 钢板 8 张.两种方法都最少要截两种钢板共 12 张. 例4 某人承揽一项业务:需做文字标牌 2 个,绘画标牌 3 个。现有两种规格的原料, , 可做文字标牌 1 个、 绘画标牌 2 个; 乙种规格每张 2 ,可做文

甲种规格每张 3

字标牌 2 个、 绘画标牌 1 个。 求这两种规格的原料用多少张才能使总的用料面积最小? 解:设用甲种规格原料 x 张,乙种规格原料 y 张,则可做文字标牌 x+2y 个,绘画标牌

2x+y 个.由题意可得

,所用原材料的总面积

,作出可行域如

图示阴影部分内的整点,作直线 作一组与直线 平行的直线 。 当直线



通过 2x+y=3 与直线

x+2y=2 的交点 因为

时,t 取得最小值

不是整点,所以它不是最优解。当 时, ,可知当 时,

代入约束条件,可得

,即经过可行域内的整点,点 B(1,1)满足 3x+2y=5,使 t 最小, 所以最优解为 B(1,1).

答: 甲种规格的原料 1 张, 用 乙种规格的原料 1 张, 能使总的用料面积最小, 5 为



求整点最优解时,可先放松可行解必须为整点的要求,转化为普通线性规划求解。若 所求得的最优解不是整点时,再借助不定方程的知识调整最优值,最后求出整点最优 解,特别适用于可行域是一侧为开放的无限大的平面区域这类问题。3.逐一校验法 由 于作图有时有误差,有时仅有图象不一定就能准确而迅速地找到最优解,此时可将若 干个可能解逐一校验即可见分晓. 例5 某人有楼房一幢,室内面积共 180m2,拟分隔成两类房间作为旅游客房.大房

间每间面积为 18m2,可住游客 5 名,每名游客每天住宿费为 40 元;小房间每间面积为 15m2,可住游客 3 名,每名游客每天住宿费为 50 元;装修大房间每间需 1000 元,装 修小房间每间需 600 元。如果他只能筹款 8000 元用于装修,且游客能住满客房,他应 隔出大房间和小房间各多少间,能获得最大收益?最大收益是多少? 解:设隔出大、小房间分别为 x 间、 y 间,收益为 z 元,则目标函数 z=200x+150y.

其中 x 、y 满足约束条件

作出可行域 如图示阴影部分内 的整

点 , 由图解法易得 z=200x+150y 过点

时,目标函数 z 取得最大 值.但 x、y 必须是整数,还需在可行 区域内找出使目标函数 z 取得最大值 的整点。显然目标函数 z 取得最大值 的整点一定是分布在可行区域的右上 侧,则利用枚举法进行逐一校验即可求出整点最优解.这些整点有:(0 12) ,(1 10), (2 9) (3 8) (4 6) (5 5) (6 3) (7 1) (8 0) 分别代入 z=200x+150y,逐一校验, 可得取整点(0, 12) 或(3, 8)时, max=200×0+150×12=200×3+150×8=1800(元) . z 答: 要获得最大收益,有两种方案:(1)只隔出小房间 12 间;(2)隔出大房间 3 间,小 房间 8 间。最大收益为 1800 元. 例 6 一批长 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%. 解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确, 图上操作尽可能规范,但考虑到作图时必然会有误差,假如图上的最优点并不十分明 显易辨时,不妨将几个有可能是最优点的坐标都求出来,然后逐一进行校验,以确定 整点最优解. .


赞助商链接

更多相关文章:
简单线性规划整点最优解问题研究
在资料也经常见 到有关简单线性规划整点最优解问题的求解方法, 如: 网格法...下面以例 2 求解介绍此法。 分析:设他应隔出大房间 x 间,小房间 y 间,...
线性规划习题精选精讲(含答案)
这是线性规划中常见的问题之一 例 2、某养鸡场有 1 万只鸡,用动物饲料和...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
简单的线性规划最优解
有实 际意义,而当可行域中的最优解不是整数解时,需作出可行域的整点作出...总之,对于线性规划实际应用题,应采用数形结合的思想来分 析、解答,各种方法各...
浅析简单的线性规划的最优解问题
3.3.2 简单的线性规划问题 例 3: 某工厂用 A,B 两种配件生产甲,乙两 种...二是寻找最优整点解时可记住 “整点在整线”(整线:形如 x=k 或 y=k...
教你如何做出最佳选择——简单线性规划最优解
有实 际意义,而当可行域中的最优解不是整数解时,需作出可行域的整点作出...总之,对于线性规划实际应用题,应采用数形结合的思想来分 析、解答,各种方法各...
不等式线性规划知识点梳理及经典例题及解析
3. 整点:坐标为整数点叫做整点. 4.线性规划...为整数线性规划. 二、疑难知识导析 线性规划是一门...③线性规划问题: ④可行解、可行域和最优解: 【经典...
高二数学线性规划
说明:在例 4 中,线性规划问题的最优解( 满足 x∈N,y∈N.故最优解应是整点坐标. 三、巩固练习: 1、练习:课本 P64,1,2 2、小结:过本节学习,要求大家...
高二数学简单的线性规划教案 人教版
分析完题后,能够抓住问题的本质特征,从而将实际问题抽象概括为 线性规划问题.另外,利用计算机可以较快地帮助学生掌握寻找整点最优解的方法. 二、教学建议: ( 1 ...
线性规划问题的最优解
线性规划最优解的问题举例 2.1 图解法求解线性规划问题例 1 ?5 ? :求解...线性规划中的整点最优解 暂无评价 3页 ¥2.00 一类新的参数线性规划最....
线性规划常见题型及解法
这是线性规划中常见的问题之 一例 2、某养鸡场有 1 万只鸡,用动物饲料和...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...
更多相关标签:

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

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