文档介绍：简单线性规划
宿城一中王美忠
x
y
o
复****画出不等式(组)表示的平面区域:
⑴ 4x-3y>9
⑵
x
o
1
2
3
-1
-2
-3
y
4x-3y=9
y
o
x
图一
图二
问题:设
满足以下条件:
求
的最小值和最大值。
中
的变化规律?
能否找出
观察:
解:作出不等式组所表示的平面区域。在把
向上平移
过程中,直线与平面区域先相
交的顶点
所对应的最小。
最后相交的顶点
所对应的
最大。
从而得到
线性约
束条件
目标函数
(线性目标函数)
y
o
x
可行域
最优解
有关概念
使目标函数取得最大值或最小值的可行解称为最优解。
由x,y 的不等式(或方程)组成的不等式组称为x,y 的约束条件。
关于x,y 的一次不等式或方程组成的不等式组称为x,y 的
线性约束条件。
欲达到最大值或最小值所涉及的变量x,y 的解析式称为
目标函数。
关于x,y 的一次目标函数称为线性目标函数。
求线性目标函数在线性约束条件下的最大值或最小值问题称为
线性规划问题。
满足线性约束条件的解(x,y)称为可行解。
所有可行解组成的集合称为可行域。
例1、已知x,y满足条件:
x-y+3≥0
x+y-5≤0
2x-y-4≤0
x ≥0
y ≥0
求z=x+2y的最大值。
解:画出满足x,y的条件所表示的区域,即五边形OABCD(如图)
z=x+2y
y = +
x
z
2
2
表示一组平行直线系,纵截距为b=z/2,
当直线经过C时,b有最大值。
D
A
B
C
1
2
3
4
5
1
2
3
4
5
O
x
y
x-y+3=0 x=1
x+y-5=0 y=4
∴ C点坐标为(1,4) ,即
当x=1,y=4时,Zmax=9。
由
得
解线性规划问题的一般步骤:
(2)作出直线
依可行域判断取得最优解的点;
(4)解相关方程组,求出最优解,从而得出目标函数的
最小值或最大值。
(1)作出可行域;
;
(3)平移
D
A
1
2
3
4
5
1
2
3
4
5
O
B
C
解作直线当把直线向下平移时,它在y轴上的截距随之减少,由图知当直线过A点时,z取得最小值。有由AB: ,令,得A(2,0)此时;
求z=y-x最大值和最小值。
变形1 已知x,y满足条件:
x-y+3≥0
x+y-5≤0
2x-y-4≤0
x ≥0
y ≥0
而直线平行于直线CD: ,故当把直线向上平移到时,它与可行域的交点不止一个,而是线段CD上的所有点,此时。
X
Y
D
A
1
2
3
4
5
1
2
3
4
5
O
B
C
求z=x-2y最大值和最小值。
变形2 已知x,y满足条件:
x-y+3≥0
x+y-5≤0
2x-y-4≤0
x ≥0
y ≥0
解由x-2y=z得y=
,令b=
当直线向上平移时,b逐渐增大由图知,当直线经过C时,b达到最大,也即z最小。
x-y+3=0 x=1
x+y-5=0 y=4
∴ C点坐标为(1,4) ,即
当x=1,y=4时,Zmin=-7
当直线向下平移时,b逐渐减小。
由
得
由图知,当直线经过A(2,0)时,b达到最小,也即Z最大, ∴Zmax=2.
X
Y
已知:
(2)求z=2x+y的最大值
练****br/>(1)画出不等式组所表示的平面区域.
5
5
x=1
x-4y+3=0
3x+5y-25=0
1
A
B
C
C:
(, )
A:
(, )
B:
(, )
O
x
y
y=-2x+z
z=2x+y, 即y=-2x+z