tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

线性规划中的整点最优解


线性规划中的整点最优解
在组织社会化生产、经营管理活动中,我 们经常会碰到最优决策的实际问题。 而解决这 类问题的现代管理科学以线性规划为其重要 的理论基础, 其本质都是寻求整个问题的某项 整体指标的最优解。但在实际问题中,最优解 (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)均为最优 解.
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 块,问各截这两种钢板多少张可得所需三 种规格成品,且使所用钢板张数最少?
2

解:设需截第一种钢板 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 ,可做文字标牌 2 个、

格每张 3

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

,所用原材料的总面积

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

3

线

,作一组与直线 。 当直线

平行的直线

通过 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 满足约束条件

作出可行域 如图示阴影部分内 的整点 ,由图解

4

法易得 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)时, zmax=200×0+150×12=200×3+150×8=1800(元) .答:要获得最大收益,有两种方案:(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, (6, (7, 2), 1), 0)都有可能是最优解, 将它们的坐标逐一代入②进行校验, 可知当 x=5,y=2 时, .

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

5

6


推荐相关:

线性规划习题精选精讲(含答案)

习题精选精讲 线性规划常见题型及解法线 性规划是新教材中新增的内容之一 ,由...线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最...


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

简单线性规划整点最优解问题研究黄建华 摘要: 本文主要介绍简单线性规划整点最优解的几种搜索方法,它们都是在图解平移法的基础上运用交轨,换元,近值的方法来对...


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

谈一类简单线性规划问题最优解的发现_高二数学_数学_高中教育_教育专区。本文介绍...否则得到的整点最优解为(3,1) ,而实际上本 体的整点最优解应为(2,2)....


线性规划中的整点问题求解方法

线性规划中的整点问题求解方法宜昌市一中 祝海燕 线性规划是运筹学的一个重要...由于实际问 题中线性规划问题的最优解多为整数解,也是学生学习线性规划的难点,...


破解线性规划中的整点问题

破解线性规划中的整点问题河南省三门峡市卢氏一高(472200)赵建文 Email:zhaojw...求整点最优解 5 5 36 38 , ) 附近的所有整点,接着平移直线 l : 5 5...


线性规划中的整点问题求解方法

线性规划中整点最优解的求... 3页 1财富值 用线性规划方法求解运输问... 8页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...


线性规划中整点问题的求解策略

线性规划中整点问题的求解策略_高一数学_数学_高中教育_教育专区。线性规划中整...然而在实际求解中,对于最优解 (x,y) 通常要满足 x,y∈N ,这种最优解称...


线性规划在实际生活中的应用

并从数学角度有条理地表述出来. 线性规划中寻找整点最优解的问题, 教材中提供了利用作图解决问题的方法, 这种方法简单 方便,学生容易掌握,体现了数形结合的数学...


简单的线性规划求最优解

点评:在解线性规划问题时,常有一些实际问题需要变量取整数解时才有实 际意义,而当可行域中的最优解不是整数解时,需作出可行域的整点作出判断。 当直接观察比较...


教你如何做出最佳选择——简单线性规划求最优解

点评: 在解线性规划问题时,常有一些实际问题需要变量取整数解时才有实 际意义,而当可行域中的最优解不是整数解时,需作出可行域的整点作出判断。 当直接观察...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com