简单的线性规划
●知识梳理
1.二元一次不等式表示平面区域
在平面直角坐标系中,已知直线Ax +By +C =0,坐标平面内的点P (x 0,y 0).
B >0时,①Ax 0+By 0+
C >0,则点P (x 0,y 0)在直线的上方;②Ax 0+By 0+C <0,则点P (x 0,y 0)在直线的下方.
对于任意的二元一次不等式Ax +By +C >0(或<0),无论B 为正值还是负值,我们都可以把y 项的系数变形为正数.
当B >0时,①Ax +By +C >0表示直线Ax +By +C =0上方的区域;②Ax +By +C <0表示直线Ax +By +C =0下方的区域. 2.线性规划
求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题. 满足线性约束条件的解(x ,y )叫做可行解,由所有可行解组成的集合叫做可行域(类似函数的定义域);使目标函数取得最大值或最小值的可行解叫做最优解.生产实际中有许多问题都可以归结为线性规划问题.
线性规划问题一般用图解法,其步骤如下:
(1)根据题意,设出变量x 、y ; (2)找出线性约束条件;
(3)确定线性目标函数z =f (x ,y );
(4)画出可行域(即各约束条件所示区域的公共区域);
(5)利用线性目标函数作平行直线系f (x ,y )=t (t 为参数);
(6)观察图形,找到直线f (x ,y )=t 在可行域上使t 取得欲求最值的位置,以确定最优解,给出答案.
●点击双基
1.下列命题中正确的是
A.点(0,0)在区域x +y ≥0内
B.点(0,0)在区域x +y +1<0内
C.点(1,0)在区域y >2x 内
D.点(0,1)在区域x -y +1>0内 解析:将(0,0)代入x +y ≥0,成立. 答案:A
2.(2005年海淀区期末练习题)设动点坐标(x ,y )满足 (x -y +1)(x +y -4)≥0, x ≥3,
A.5
B.10
C.
2
17 D.10
解析:数形结合可知当x =3,y =1时,x 2
+y 2
的最小值为10. 答案:D
2x -y +1≥0,
x -2y -1≤0,
x +y ≤1
则x 2+y 2的最小
3.不等式表示的平面区
A.正三角形及其内部
B.等腰三角形及其内部
C.在第一象限内的一个无界区域
D.不包含第一象限内的点的一个有界区域
解析:将(0,0)代入不等式组适合C ,不对;将(
2
1,
2
1)代入不等式组适合D ,不
对;又知2x -y +1=0与x -2y -1=0关于y =x 对称且所夹顶角α满足
t an α=|
2
121||212|?
+-
=
4
3.
∴α≠
3
π.
答案:B
4.点(-2,t )在直线2x -3y +6=0的上方,则t 的取值范围是________________. 解析:(-2,t )在2x -3y +6=0的上方,则2×(-2)-3t +6<0,解得t >3
2.
答案:t >
3
2
5.不等式组??
?
??<+>>1234,0,
0y x y x 表示的平面区域内的整点(横坐标和纵坐标都是整数的点)共
有____________个.
解析:(1,1),(1,2),(2,1),共3个.
答案:3 ●典例剖析
【例1】 求不等式|x -1|+|y -1|≤2表示的平面区域的面积. 剖析:依据条件画出所表达的区域,再根据区域的特点求其面积. 解:|x -1|+|y -1|≤2可化为
x ≥1, x ≥1, x ≤1, x ≤1, y ≥1, y ≤1, y ≥1, y ≤1, x +y ≤4 x -y ≤2 y -x ≤2 x +y ≥0. 其平面区域如图.
O
x
y
∴面积S =
2
1×4×4=8.
评述:画平面区域时作图要尽量准确,要注意边界.
或 或 或
深化拓展
若再求:①
1
2-+x y ;②22)2()1(++-y x 的值域,你会做吗?
答案: ①(-∞,-2
3]∪[2
3,+∞);②[1,5].
【例2】 某人上午7时,乘摩托艇以匀速v n mi l e/h (4≤v ≤20)从A 港出发到距50 n
mi l e 的B 港去,然后乘汽车以匀速w km/h (30≤w ≤100)自B 港向距300 km 的C 市驶去.应该在同一天下午4至9点到达C 市.设乘汽车、摩托艇去所需要的时间分别是x h 、y h.
(1)作图表示满足上述条件的x 、y 范围; (2)如果已知所需的经费
p =100+3×(5-x )+2×(8-y )(元),
那么v 、w 分别是多少时走得最经济?此时需花费多少元?
剖析:由p =100+3×(5-x )+2×(8-y )可知影响花费的是3x +2y 的取值范围. 解:(1)依题意得v =
y
50,w =
x
300,4≤v ≤20,30≤w ≤100.
∴3≤x ≤10,2
5≤y ≤2
25. ①
由于乘汽车、摩托艇所需的时间和x +y 应在9至14个小时之间,即9≤x +y ≤14.② 因此,满足①②的点(x ,y )的存在范围是图中阴影部分(包括边界).
x
y O
149
2.53
91014
2+3=38
y x
(2)∵p =100+3·(5-x )+2·(8-y ),
∴3x +2y =131-p .
设131-p =k ,那么当k 最大时,p 最小.在通过图中的阴影部分区域(包括边界)且斜率为-
2
3的直线3x +2y =k 中,使k 值最大的直线必通过点(10,4),即当x =10,y =4时,p 最小. 此时,v =12.5,w =30,p 的最小值为93元.
评述:线性规划问题首先要根据实际问题列出表达约束条件的不等式.然后分析要求量
的几何意义.
【例3】 某矿山车队有4辆载重量为10 t 的甲型卡车和7辆载重量为6 t 的乙型卡车,有9名驾驶员.此车队每天至少要运360 t 矿石至冶炼厂.已知甲型卡车每辆每天可往返6次,乙型卡车每辆每天可往返8次.甲型卡车每辆每天的成本费为252元,乙型卡车每辆每天的成本费为160元.问每天派出甲型车与乙型车各多少辆,车队所花成本费最低?
剖析:弄清题意,明确与运输成本有关的变量的各型车的辆数,找出它们的约束条件,列出目标函数,用图解法求其整数最优解.
解:设每天派出甲型车x 辆、乙型车y 辆,车队所花成本费为z 元,那么 x +y ≤9,
10×6x +6×8x ≥360, 0≤x ≤4, 0≤y ≤7.
z =252x +160y ,
其中x 、y ∈N .
作出不等式组所表示的平面区域,即可行域,如图.
x
x x y
y y O
l l 0
1`
++= = 95 4 30
作出直线l 0:252x +160y =0,把直线l 向右上方平移,使其经过可行域上的整点,且使在y 轴上的截距最小.观察图形,可见当直线252x +160y =t 经过点(2,5)时,满足上述要求.
此时,z =252x +160y 取得最小值,即x =2,y =5时,z min =252×2+160×5=1304. 答:每天派出甲型车2辆,乙型车5辆,车队所用成本费最低.
评述:用图解法解线性规划题时,求整数最优解是个难点,对作图精度要求较高,平行直线系f (x ,y )=t 的斜率要画准,可行域内的整点要找准,最好使用“网点法”先作出可行域中的各整点.
●闯关训练 夯实基础
1.(x -1)2+(y -1)2=1是|x -1|+|y -1|≤1的__________条件. A.充分而不必要 B.必要而不充分
C.充分且必要
D.既不充分也不必要 解析:数形结合. 答案:B 2.(x +2y +1)(x -y +4)≤0表示的平面区域为
x
x
x
x
y y y y 1
1222
2
33444
4-1
-1
-2-2-2
-2-3-3-4-4-4-4 A
B
C D
O O O O
解析:可转化为
x +2y +1≥0, x +2y +1≤0, x -y +4≤0 x -y +4≥0.
答案:B
3.(2004年全国卷Ⅱ,14)设x 、y 满足约束条件
x ≥0, x ≥y ,
2x -y ≤1,则z =3x +2y 的最大值是____________.
或
解析:如图,当x =y =1时,z max =5.
y
y y x
x x O
1 1 1 1
2 2
=
= -
答案:5
x -4y +3≤0,
3x +5y -25≤0, x ≥1,
_________.
解析:作出可行域,如图.当把z 看作常数时,它表示直线y =zx 的斜率,因此,当直线y =zx 过点A 时,z 最大;当直线y =zx 过点B 时,z 最小.
x
x x y
y
y 3 +5 =0
-255
12345678
9
-3-4 +3=0
A
B O
x =1,
3x +5y -25=0,得A (1,5
22
).
x -4y +3=0,
3x +5y -25=0, ∴z max =1
522
=522
,z min =5
2.
答案:
5
2
5
22
5.画出以A (3,-1)、B (-1,1)、C (1,3)为顶点的△ABC 的区域(包括各边),写出该区域所表示的二元一次不等式组,并求以该区域为可行域的目标函数z =3x -2y 的最大值和最小值.
分析:本例含三个问题:①画指定区域;②写所画区域的代数表达式——不等式组; ③求以所写不等式组为约束条件的给定目标函数的最值.
解:如图,连结点A 、B 、C ,则直线AB 、BC 、CA 所围成的区域为所求△ABC 区域.
x
y
O
A
B C P (1,1)
-2
31
2
直线AB 的方程为x +2y -1=0,BC 及CA 的直线方程分别为x -y +2=0,2x +y -5=0.
在△ABC 内取一点P (1,1),分别代入x +2y -1,x -y +2,2x +y -5得x +2y -1>0,x
由 得B (5,
4.变量x 、y 满足设z =x
y ,则z 的最小值为_______,
由
-y +2>0,2x +y -5<0.
因此所求区域的不等式组为 x +2y -1≥0, x -y +2≥0, 2x +y -5≤0.
作平行于直线3x -2y =0的直线系3x -2y =t (t 为参数),即平移直线y =2
3x ,观察图形
可知:当直线y =
2
3x -
2
1t 过A (3,-1)时,纵截距-2
1
t 最小.此时t 最大,t max =3×3-2
× (-1)=11;
当直线y =
2
3x -
2
1t 经过点B (-1,1)时,纵截距-2
1
t 最大,此时t 有最小值为t min =
3×(-1)-2×1=-5.
因此,函数z =3x -2y 在约束条件
x +2y -1≥0, x -y +2≥0,
2x +y -5≤0
6.某校伙食长期以面粉和大米为主食,面食每100 g 含蛋白质6个单位,含淀粉4个单位,售价0.5元,米食每100 g 含蛋白质3个单位,含淀粉7个单位,售价0.4元,学校要求给学生配制盒饭,每盒盒饭至少有8个单位的蛋白质和10个单位的淀粉,问应如何配制盒饭,才既科学又费用最少?
解:设每盒盒饭需要面食x (百克),米食y (百克),
x
y
O
A
6+3=8x y 4+7=10
x y
所需费用为S =0.5x +0.4y ,且x 、y 满足 6x +3y ≥8, 4x +7y ≥10, x ≥0, y ≥0,
由图可知,直线y =-4
5x +
2
5S 过A (
15
13,
15
14)时,纵截距
2
5S 最小,即S 最小.
故每盒盒饭为面食15
13百克,米食15
14百克时既科学又费用最少.
培养能力
7.配制A 、B 两种药剂,需要甲、乙两种原料,已知配一剂A 种药需甲料3 mg ,乙料5 mg ;配一剂B 种药需甲料5 mg ,乙料4 mg.今有甲料20 mg ,乙料25 mg ,若A 、B 两种药至少各配一剂,问共有多少种配制方法?
解:设A 、B 两种药分别配x 、y 剂(x 、y ∈N ),则 x ≥1, y ≥1,
3x +5y ≤20,
下的最大值为11,最小
5x +4y ≤25.
上述不等式组的解集是以直线x =1,y =1,3x +5y =20及5x +4y =25为边界所围成的区域,这个区域内的整点为(1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(3,1)、(3,2)、(4,1).所以,在至少各配一剂的情况下,共有8种不同的配制方法.
8.某公司计划在今年内同时出售变频空调机和智能洗衣机,由于这两种产品的市场需求量非常大,有多少就能销售多少,因此该公司要根据实际情况(如资金、劳动力)确定产品的月供应量,以使得总利润达到最大.已知对这两种产品有直接限制的因素是资金和劳动力,通过调查,得到关于这两种产品的有关数据如下表:
资 金 单位产品所需资金(百元) 月资金供应量(百元)
空调机 洗衣机 成 本 30 20 300 劳动力(工资)
5 10 110 单位利润
6
8
试问:怎样确定两种货物的月供应量,才能使总利润达到最大,最大利润是多少? 解:设空调机、洗衣机的月供应量分别是x 、y 台,总利润是P ,则P =6x +8y ,由题意有
y O M
10
15x
1020
30x +20y ≤300,
5x +10y ≤110, x ≥0, y ≥0, x 、y 均为整数. 由图知直线y =-
4
3x +8
1P 过M (4,9)时,纵截距最大.这时P 也取最大值P max =6×4+8
×9=96(百元).
故当月供应量为空调机4台,洗衣机9台时,可获得最大利润9600元.
探究创新
9.实系数方程f (x )=x 2+ax +2b =0的一个根在(0,1)内,另一个根在(1,2)内,求: (1)
1
2--a b 的值域;
(2)(a -1)2+(b -2)2的值域; (3)a +b -3的值域.
f (0)>0
f (1)<0 f (2)>0
b >0,
a +
b +1<0,
a +
b +2>0.
如图所示. A (-3,1)、B (-2,0)、C (-1,0).
解:由题意
?
O A
B
C
a b +=-1a b +=-2
b =0a
b
又由所要求的量的几何意义知,值域分别为(1)(
4
1,1);(2)(8,17);(3)(-5,-4).
●思悟小结
简单的线性规划在实际生产生活中应用非常广泛,主要解决的问题是:在资源的限制下,如何使用资源来完成最多的生产任务;或是给定一项任务,如何合理安排和规划,能以最少的资源来完成.如常见的任务安排问题、配料问题、下料问题、布局问题、库存问题,通常解法是将实际问题转化为数学模型,归结为线性规划,使用图解法解决.
图解法解决线性规划问题时,根据约束条件画出可行域是关键的一步.一般地,可行域可以是封闭的多边形,也可以是一侧开放的非封闭平面区域.第二是画好线性目标函数对应的平行直线系,特别是其斜率与可行域边界直线斜率的大小关系要判断准确.通常最优解在可行域的顶点(即边界线的交点)处取得,但最优整数解不一定是顶点坐标的近似值.它应是目标函数所对应的直线平移进入可行域最先或最后经过的那一整点的坐标.
●教师下载中心 教学点睛
线性规划是新增添的教学内容,应予以足够重视.
线性规划问题中的可行域,实际上是二元一次不等式(组)表示的平面区域,是解决线性规划问题的基础,因为在直线Ax +By +C =0同一侧的所有点(x ,y )实数Ax +By +C 的符号相同,所以只需在此直线的某一侧任取一点(x 0,y 0)〔若原点不在直线上,则取原点(0,0)最简便〕,把它的坐标代入Ax +By +C =0,由其值的符号即可判断二元一次不等式Ax +By +C >0(或<0)表示直线的哪一侧.这是教材介绍的方法.
在求线性目标函数z =ax +by 的最大值或最小值时,设ax +by =t ,则此直线往右(或左)平移时,t 值随之增大(或减小),要会在可行域中确定最优解. 解线性规划应用题步骤:(1)设出决策变量,找出线性约束条件和线性目标函数; (2)利用图象在线性约束条件下找出决策变量,使线性目标函数达到最大(或最小).
拓展题例
【例1】 已知f (x )=px 2
-q 且-4≤f (1)≤-1,-1≤f (2)≤5,求f (3)的范围. 解:∵-4≤f (1)≤-1,-1≤f (2)≤5, p -q ≤-1,
p -q ≥-4,
4p -q ≤5,
4p -q ≥-1. 求z =9p -q 的最值.
O
(0,1)
(1,5)
(2,3)
(3,7)4-=-1
p q p q -=-4p q -=-1
4-=5
p q p
q
∴
p =0, q =1,
z min =-1, p =3, q =7, ∴-1≤f (3)≤20.
【例2】 某汽车公司有两家装配厂,生产甲、乙两种不同型号的汽车,若A 厂每小时可完成1辆甲型车和2辆乙型车;B 厂每小时可完成3辆甲型车和1辆乙型车.今欲制造40辆甲型车和20辆乙型车,问这两家工厂各工作几小时,才能使所费的总工作时数最少?
解:设A 厂工作x h ,B 厂工作y h ,总工作时数为t h ,则t =x +y ,且x +3y ≥40,2x +y ≥20,x ≥0,y ≥0,可行解区域如图.而符合问题的解为此区域内的格子点(纵、横坐标都是整数的点称为格子点),于是问题变为要在此可行解区域内,找出格子点(x ,y ),使t =x +y 的值为最小.
x
y
O
P
Q R
2+=20
x y x y +3=40
由图知当直线l :y =-x +t 过Q 点时,纵、横截距t 最小,但由于符合题意的解必须是格子点,我们还必须看Q 点是否是格子点.
x +3y =40,
2x +y =20,
得Q (4,12)为格子点.
故A 厂工作4 h ,B 厂工作12 h ,可使所费的总工作时数最少.
如图,
z max
=2
解方程