当前位置:首页 >> 数学 >>

线性规划常见题型及解法


线性规划常见题型及解法 由已知条件写出约束条件, 并作出可行域, 进而通过平移直线在可行域内求线性目标函 数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 一、求线性目标函数的取值范围

?x ? 2 ? 1、若 x、y 满足约束条件 ? y ? 2 ?x ? y ? 2 ?

,则 z ? x ? 2 y 的取值范围是 ( )

A、[2,6] B、[2,5] C、[3,6] D、 (3,5] 解:如图,作出可行域,作直线 l:x+2y=0,将 l 向右上方平移,过点 A(2,0)时,有最小值 2,过点 B(2,2)时,有最大值 6,故选 A (注:象这样目标是线性的选填题,可以代边界交点检验即可) 二、求可行域的面积

y 2

B A

y =2 x x + y =2 y

O

2 x=2

?2 x ? y ? 6 ? 0 ? 2、 不等式组 ? x ? y ? 3 ? 0 表示的平面区域的面积为 ?y ? 2 ?

( )

A、4 B、1 C、5 D、无穷大 解:如图,作出可行域,△ABC 的面积即为所求,由梯形 OMBC 的面积 减去梯形 OMAC 的面积即可,选 B 三、求可行域中整点个数 x ? y ? 2( x ? 0, y ? 0)

x+y – 3 = 0 M A B y =2

O C x 2x + y – 6= 0 y =5

3、满足|x|+|y|≤2 的点(x,y)中整点(横纵坐标都是整数)有( ) A、9 个 B、10 个 C、13 个 D、14 个 解:|x|+|y|≤2 等价于 x ? y ? 2( x ? 0, y ? 0) 或 x ? y ? 2( x ? 0, y ? 0) 或 ? x ? y ? 2( x ? 0, y ? 0) 或 ? x ? y ? 2( x ? 0, y ? 0) ,作出可行域如右图,是正方形内部(包括边界) , 容易得到整点个数为 13 个,选 D 四、求线性目标函数中参数的取值范围 (注:根据对称性作图要容易些)

O

x

?x ? y ? 5 ? 4、 已 知 x、 y 满 足 以 下 约 束 条 件 ?x ? y ? 5 ? 0 ?x ? 3 ?

y


x–y+5=0

x+y=5

使 z ? ? x ? ay(a ? 0) ) 取 得 最 小 值 的 最 优 解 有 无 数 个 , 则 a 的值为( ) A、 - 3 B、 3 C、 - 1

O

x=3 x

D、 1

解 :如 图 ,作 出 可 行 域 ,作 直 线 l :x + a y = 0 ,要 使 目 标 函 数 z = x + a y ( a > 0 ) 取 得 最 小 值 的 最 优 解 有 无 数 个 , 则 将 l 向 右 上 方 平 移 后 与 直 线 x+y = 5 重 合 , 故 a=1, 选 D 五、求非线性目标函数的最值

y A
,则

?2 x ? y ? 2 ? 0 ? 5 、 已 知 x 、 y 满 足 以 下 约 束 条 件 ?x ? 2 y ? 4 ? 0 ?3 x ? y ? 3 ? 0 ?

O x – 2y + 4 = 0 3x – y – 3 = 0

z ? x2 ? y2 的 最 大 值 和 最 小 值 分 别 是 (
A、 13, 1 C、 13, B、 13, 2 D、



x 2x + y - 2= 0 =5

4 5

13 ,

2 5 5

解 :如 图 ,作 出 可 行 域 ,

x 2 ? y 2 是 点 P( x , y ) 到 原 点 的 距 离 , 故 最 大
2

值 为 点 A( 2 , 3 ) 到 原 点 的 距 离 的 平 方 , 即 | A O | = 1 3 ; 最 小 值 为 原 点 到 直 线 2x+ y- 2=0 的 距 离 的 平 方 , 即 为

4 。选 C 5
x2 ? y2 表
表示点

(注:求非线性目标的最值,一般要用到目标函数的几何意义:如① 示点 P( x, y) 到原点的距离;② x ? 2 y ? 3 ?

5

x ? 2y ? 3 5

,其中

x ? 2y ? 3 5

P( x, y) 到直线 x ? 2 y ? 3 ? 0 的距离;③

y?2 表示点 P( x, y) 到 (?1,2) 的斜率; ) x ?1

六、求约束条件中参数的取值范围 6、 已 知 |2x- y+ m|< 3 表 示 的 平 面 区 域 包 含 点 ( 0,0) 和 ( - 1,1) , 则 m 的取值范围是 ( ) y A、 ( -3,6) B、 ( 0,6) C、 ( 0,3) D、 ( -3,3) 解 : |2x- y+ m|< 3 等 价 于 ?

2x – y + 3 = 0 2x – y = 0

?2 x ? y ? m ?3 ?0 ?2 x ? y ? m ?3 ?0
O

由右图可知 ?

?m ? 3 ? 3 ,故 0< m< 3, 选 C ?m ? 3 ? 0

线性规划的实际应用 在科学研究、工程设计、经济管理等方面,我们都会碰到最优化决策的实际问题,而解 决这类问题的理论基础是线性规划。利用线性规划研究的问题,大致可归纳为两种类型:第 一种类型是给定一定数量的人力、物力资源,问怎样安排运用这些资源,能使完成的任务量 最大,的效益最大,第二种类型是给定一项任务,问怎样统筹安排,能使完成这项任务的人 力、物力资源量最小。

例 1、 某木器厂生产圆桌和衣柜两种产品, 现有两种木料, 第一种有 72m , 第二种有 56m , 假设生产每种产品都需要用两种木料,生产一只圆桌和一个衣柜分别所需木料如下表所示. 每生产一只圆桌可获利 6 元,生产一个衣柜可获利 10 元.木器厂在现有木料条件下,圆桌和衣 柜各生产多少,才使获得利润最多? 木料(单位 m ) 产 品 圆 桌 衣 柜 第 种 0.18 0.09 一 第 二 种 0.08 0.28
3

3

3

?0.18x ? 0.09 y ? 72 ?0.08x ? 0.28y ? 56 ? 解: 设生产圆桌 x 只,生产衣柜 y 个,利润总额为 z 元,那么 ? ?x ? 0 ? ?y ? 0
z=6x+10y.



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

?0.18x ? 0.09y ? 72 ,得 M 点坐 ?0.08x ? 0.28y ? 56

标(350,100).答:应生产圆桌 350 只,生产衣柜 100 个,能使利润总额达到最大. 指出:资源数量一定,如何安排使用它们,使得效益最好,这是线性规划中常见的问题之 一 例 2、某养鸡场有 1 万只鸡,用动物饲料和谷物饲料混合喂养.每天每只鸡平均吃混合饲 料 0.5kg,其中动物饲料不能少于谷物饲料的

1 .动物饲料每千克 0.9 元,谷物饲料每千克 5

0.28 元,饲料公司每周仅保证供应谷物饲料 50000kg,问饲料怎样混合,才使成本最低. 解 : 设每周需用谷物饲料 x kg, 动物饲料 y kg, 每周总的饲料费用为 z 元 , 那么

? x ? y ? 35000 ? 1 ? ?y ? x ,而 z=0.28x+0.9y 5 ? ?0 ? x ? 50000 ? ? ?y ? 0
如下图所示,作出以上不等式组所表示的平面区域,即可行域. 作一组平行直线 0.28x+0.9y =t,其中经过可行域内的点且和原点最近的直线,经过直线

x+y=35000 和直线 y ?

1 87500 17500 87500 17500 x 的交点 A( , ) ,即 x ? ,y? 时,饲料费 5 3 3 3 3

用最低. 所以,谷物饲料和动物饲料应按 5:1 的比例混合,此时成本最低. 指出:要完成一项确定的任务,如何统筹安排,尽量做到用最少的资源去完成它,这是线 性规划中最常见的问题之一.

(例 3 图) (例 4 图) 例 3、下表给出甲、乙、丙三种食物的维生素 A、B 的含量及成本: 甲 维 生 素 A( 单 位 / 千 克) 维 生 素 B( 单 位 / 千 克) 成本(元/千克) 营养师想购这三种食物共 10 千克,使之所含维生素 A 不少于 4400 单位,维生素 B 不少于 4800 单位,问三种食物各购多少时,成本最低?最低成本是多少? 解:设所购甲、乙两种食物分别为 x 千克、y 千克,则丙种食物为(10?x?y)千克.x、y 应 满足线性条件为 400 800 7 600 200 6 400 400 5 乙 丙

?400x ? 600y ? 400(10 ? x ? y) ? 4400 ?y ? 2 ,化简得 ? ? ?800x ? 200y ? 400(10 ? x ? y) ? 4800 ?2 x ? y ? 4
作出可行域如上图中阴影部分 目标函数为 z=7x+6y+5(10?x?y)=2x+y+50,令 m=2x+y,作直线 l:2x+y=0,则直线 2x+y=m 经过可行域中 A(3,2)时,m 最小,即 mmin=2?3+2=8,∴zmin=mmin+50=58 答: 甲、乙、丙三种食物 各购 3 千克、2 千克、5 千克时成本最低,最低成本为 58 元. 指出:本题可以不用图解法来解,比如,由 ?

?y ? 2 得 ?2 x ? y ? 4

z=2x+y+50=(2x?y)+2y+50?4+2?2+50=58,当且仅当 y=2,x=3 时取等号
总结:(1)设出决策变量,找出线性规划的约束条件和线性目标函数; (2)利用图象,在线性约束条件下找出决策变量,使线性目标函数达到最大(或最小).

?a11 x1 ? a12 x 2 ? ? ? a1m x m ? b1 ?a x ? a x ? ? ? a x ? b ? 21 1 22 2 2m m 2 2.线性规划问题的一般数学模型是:已知 ? (这 n 个式 ??? ? ?a n1 x1 ? a n 2 x 2 ? ? ? a nm x m ? bn
子中的“?”也可以是“?”或“=”号)

其中 aij (i=1,2,…,n, j=1,2,…,m),bi (i=1,2,…,n)都是常量,xj (j=1,2,…,m) 是非 负变量,求 z=c1x1+c2x2+…+cmxm 的最大值或最小值,这里 cj (j=1,2,…,m)是常量. (3)线性规划的理论和方法主要在以下两类问题中得到应用:一是在人力、物力资金等 资源一定的条件下,如何使用它们来完成最多的任务; 二是给一项任务,如何合理安排和规划, 能以最少的人力、物力、资金等资源来完成该项任务. 线性规划中整点最优解的求解策略 在工程设计、经营管理等活动中,经常会碰到最优化决策的实际问题,而解决此类问题 一般以线性规划为其重要的理论基础。然而在实际问题中,最优解 (x,y) 通常要满足 x,y ∈N ,这种最优解称为整点最优解,下面通过具体例子谈谈如何求整点最优解 . 1.平移找解法 作出可行域后,先打网格,描出整点,然后平移直线 l,直线 l 最先经过或最后经过的 那个整点便是整点最优解. 3 3 例 1、 某木器厂生产圆桌和衣柜两种产品, 现有两种木料, 第一种有 72m , 第二种有 56m , 假设生产每种产品都需要用两种木料,生产一只圆桌和一个衣柜分别 所需木料如下表所示.每生产一只圆桌可获利 6 元,生产一个衣柜可获 利 10 元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得 利润最多? 产 品 圆 桌 衣 柜 木料(单位 m ) 第 一 种 0.18 0.09 第 二 种 0.08 0.28
3

?0.18x ? 0.09 y ? 72 ?0.08x ? 0.28y ? 56 ? 解: 设生产圆桌 x 只,生产衣柜 y 个,利润总额为 z 元,那么 ? ?x ? 0 ? ?y ? 0



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

?0.18x ? 0.09y ? 72 ,得 ?0.08x ? 0.28y ? 56

M 点坐标(350,100).答: 应生产圆桌 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

l1
A

?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
C

O

x
l2

B

,设 l1 与 l2 , l1 与 l3 , l2 与 l3 交点分 l3 : 3x ? 5 y ? 15 ? 0 所围成的三角形内部(不含边界) 别为 A, B, C ,则 A, B, C 坐标分别为 A(

15 3 75 12 , ) , B(0, ?3) , C ( , ? ) , 8 4 19 19

作一组平行线 l : x ? y ? t 平行于 l0 : x ? y ? 0 ,当 l 往 l0 右上方移动时, t 随之增大, ∴当 l 过 C 点时 x ? y 最大为

63 75 ,但不是整数解,又由 0 ? x ? 知 x 可取 1, 2,3 , 19 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 ? y 的最大整数解为 ?

?x ? 2 ?x ? 3 或? . ? y ? 0 ? y ? ?1

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%. 解线性规划问题的关键步骤是在图(可行域)上完成的,所以作图时应尽可能精确,图 上操作尽可能规范, 但考虑到作图时必然会有误差, 假如图上的最优点并不十分明显易辨时, 不妨将几个有可能是最优点的坐标都求出来,然后逐一进行校验,以确定整点最优解. 线性规划的实际应用 习题精选 1.某家俱公司生产甲、乙两种型号的组合柜,每种柜的制造白坯时间、油漆时间及有 关数据如下:

问该公司如何安排这两种产品的生产,才能获得最大的利润.最大利润是多少? 2.要将两种大小不同的钢板截成 A、B、C 三种规格,每张钢板可同时截得三种规格小 钢板的块数如下:

每张钢板的面积,第一种为 1m ,第二种为 2m ,今需要 A、B、C 三种规格的成品各 12, 15,17 块,问各截这两种钢板多少张,可得所需三种规格成品,且使所用钢板面积最小.

2

2

3.某人承揽一项业务,需做文字标牌 2 个,绘画标牌 3 个,现有两种规格的原料,甲种规 2 2 格每张 3m ,可做文字标牌 1 个,绘画标牌 2 个,乙种规格每张 2m ,可做文字标牌 2 个,绘 画标牌 1 个,求两种规格的原料各用多少张,才能使总的用料面积最小. 4.某蔬菜收购点租用车辆,将 100 吨新鲜黄瓜运往某市销售,可供租用的大卡车和农 用车分别为 10 辆和 20 辆,若每辆卡车载重 8 吨,运费 960 元,每辆农用车载重 2.5 吨,运 费 360 元,问两种车各租多少辆时,可全部运完黄瓜,且动费最低.并求出最低运费. 5.某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有 72 立方米,第二种 有 56 立方米, 假设生产每种产品都需要两种木料. 生产一只圆桌需用第一种木料 0.18 立方 米,第二种木料 0.08 立方米,可获利润 60 元,生产一个衣柜需用第一种木料 0.09 立方米, 第二种 0.28 立方米,可获利润 100 元,木器厂在现有木料情况下,圆桌和衣柜应各生产多 少,才能使所获利润最多. 解答提示: 1.设 x,y 分别为甲、乙两种柜的日产量,

目标函数 z=200x+240y, 线性约束条件:

作出可行

域. z 最大=200×4+240×8=2720 答:该公司安排甲、乙两种柜的日产量分别为 4 台和 8 台,可获最大利润 2720 元.

2.设需截第一种钢板 x 张,第二种钢板 y 张,所用钢板面积 zm2.

目标函数 z=x+2y, 平行直线 x+2y=t.

线性约束条件:

作出可行域.

作一组

的整点中,点(4,8)使 z 取得最小值. 答:应截第一种钢板 4 张,第二种钢板 8 张,能得所需三种规格的钢板,且使所用钢板 的面积最小. 2 3.设用甲种规格原料 x 张,乙种规格原料 y 张,所用原料的总面积是 zm ,目标函数 z=3x+2y,

线性约束条件,

作出可行域.作一组平等直线 3x+

2y=t.

A 不是整点,A 不是最优解.在可行域内的整点中,点 B(1,1)使 z 取得最小值. z 最小=3×1+2×1=5, 2 答:用甲种规格的原料 1 张,乙种原料的原料 1 张,可使所用原料的总面积最小为 5m . 4.设租用大卡车 x 辆,农用车 y 辆,最低运费为 z 元.z=960x+360y.

线性约束条件是:

作出可行域. 作直线 960x+360y=0. 即 8x+3y=0,向上平移至过点 B(10,8)时,z=960x+360y 取到最小值. z 最小=960×10+360×8=12480 答:大卡车租 10 辆,农用车租 8 辆时运费最低,最低运 费为 12480 元. 5.设圆桌和衣柜的生产件数分别为 x、y,所获利润为 z,则 z=6x+10y.

作出可行域.

即 M(350,100).当直线 6x+10y=0 即 3x+5y=0 平移到经过点 M(350,100)时,z=6x+10y 最大


相关文章:
必修五 线性规划常见题型及解法
必修五 线性规划常见题型及解法_高二数学_数学_高中教育_教育专区。线性规划常见题型及解法一、求线性目标函数的取值范围 ?x ? 2 ? 例 1、 若 x、 y 满足约...
线性规划常见题型及解法+均值不等式(含答案)
线性规划常见题型及解法+均值不等式(含答案)_高一数学_数学_高中教育_教育专区。习题精选精讲 线性规划常见题型及解法 一.基础知识: (一)二元一次不等式表示的区...
线性规划的常见题型及其解法(教师版,题型全,归纳好)
线性规划常见题型及其解法(教师版,题型全,归纳好)_数学_高中教育_教育专区。将简单的方法练到极致就是绝招! 课题 线性规划常见题型及其解法答案 线性规划问题...
线性规划常见题型及解法
线性规划常见题型及解法 由已知条件写出约束条件, 并作出可行域, 进而通过平移直线在可行域内求线性目标函 数的最优解是最常见的题型,除此之外,还有以下六类常见...
线性规划常见题型及解法(2)
线性规划常见题型及解法 四川省武胜飞龙中学校 梁洪斌 郑秋华( 638402 ) 线性规划是新教材中新增的内容之一,也是高考的必考内容之一,同 时也是同学们的易错题之...
线性规划常见题型及解法老师专用
线性规划常见题型及解法线性规划问题是高考的重点,也是常考题型,属于中等偏简单题,易得分,高考中要求 会从实际问题中建立一格二元线性规划的模型, 使实际问题得到...
高考数学线性规划常见题型及解法大全
高考数学线性规划常见题型及解法大全_数学_高中教育_教育专区。2015 年线性规划高考数学题型归类解析线性规划问题是解析几何的重点,每年高考必有一道小题。 一、已知...
线性规划的常见题型及其解法学生版(题型全面归纳好)
线性规划常见题型及其解法学生版(题型全面归纳好)_数学_高中教育_教育专区。题型全面归纳好 课题 线性规划常见题型及其解法题目 线性规划问题是高考的重点,而线性...
线性规划常见题型及解法
线性规划常见题型及解法由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性目标函数的最优解是 最常见的题型,除此之外,还有以下六类常见题型。...
更多相关标签: