运筹学基础线性规划2.ppt

§ 线性规划问题的图解法
对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。
图解法即是用图示的方法来求解线性规划问题。图解法简单直观,有助于了解线性规划问题求解的基本原理。
一个二维的线性规划问题,可以在平面图上求解,三维的线性规划则要在立体图上求解,这就比较麻烦,而维数再高以后就不能图示了。
线性规划
1
一、图解法的基本步骤
满足所有约束条件的解叫可行解,解的集合称之为可行域。即所有约束条件共同围成的区域。
1、可行域的确定
例1的数学模型为:
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4
8
12
3
6
9
0
A
B
C(4,6)
D
五边形OABCD内(含边界)的任意一点(x1,x2) 都是满足所有约束条件的一个解,称之可行解。
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0, x2 ≥0
线性规划
2
2、最优解的确定
确定x1、x2希望目标函数 Z= 3x1 +5 x2达到最大,图形中Z= 3x1 +5 x2 代表以Z为参数的一族平行线,即等值线。
等值线:位于同一直线上的点的目标函数值相同。
Z=3x1+5x2=0
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4
8
12
3
6
9
0
A
B(8,3)
C(4,6)
D
最优解:可行解中使目标函数最优(极大或极小)的解
本题中:满足目标函数最大的极点是离原点距离最远的点(4,6)
Z=3x1+5x2=24
Z=3x1+5x2=30
Z=39
Z=42
即x1=4,x2=6时
Z的值最大为42。
C(4,6)为最优解
线性规划
3
二、解的几种可能性
唯一最优解:只有一个最优点。如上题的最优解(4,6)
多重最优解:无穷多个最优解。若在两个顶点同时得到最优解,则它们连线上的每一点都是最优解。
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4
8
12
3
6
9
0
A
B
C(4,6)
D
如例1的数学模型变为
maxZ= 3x1 +4 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0, x2 ≥0
.
Z=24
Z=36
Z=12
线性规划
4
线性规划问题的可行域无界,使目标函数无限增大而无界。(缺乏必要的约束条件)
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≤2
x1 -3 x2 ≤3
x1 ≥0, x2 ≥0
-2x1 + x2 =2
x1 -3 x2 =3
x2
1
2
3
-1
x1
1
2
3
-1
Z=6
Z=12
.
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≥2
x1 -3 x2 ≥3
x1 ≥0, x2 ≥0
-2x1 + x2 =2
x1 -3 x2 =3
x2
1
2
3
-1
x1
1
2
3
-1
.
无界解:
无可行解:
若约束条件相互矛盾,则可行域为空集。
线性规划
5
【例】求最大值问题
数学模型为:
四边形OBQC内(含边界)的任意一点(x1,x2) 都是满足所有约束条件的一个解,称之可行解。
maxZ= 8x1 +6x2
4x1 +2 x2 ≤60
2x1 +4 x2 ≤48
2x1 +3 x2 ≤36
x1 ≥0, x2 ≥0
2x1 +3 x2 =36
x1
x2
5
10
5
10
15
0
C(0,12)
4x1 +2 x2 =60
2x1 +4x2 =48
B(15,0)
Z=0
Z=72
Z=120
Z=126
Q (,3)
结论:在Q(,3)处利润最大为126, Q(,3)为最优解
线性规划
6
【例】求最小值问题
设有某林场需配制某种灭虫药水500公斤,该药水系由甲与乙两种药水混合而成。甲种药水每公斤5元,乙种药水每公斤8元。按照两种药水的化学性质,在混合时,500公斤混合药水中含甲种药水最多不能超过400公斤,含乙种药水最少不能少于200公斤。问如何配制可使该药水配制成本最低?.
minZ= 5x1 +8x2
x1 ≤400
x2 ≥200
x1+x2 =500
x1 ≥0, x2 ≥0
则数学模型为:
设:500公斤混合药水中,甲种药水x1公斤,乙种药水x2公