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

上节小结:线性规划的单纯形解法
单纯形法(Simplex Method)是美国人丹捷格()1947年创建的这种方法简捷、规范,是举世公认的解决线性规划问题行之有效的方法。
单纯形法的表现形式:
表格法
矩阵法-改良的单纯形法
表格型单纯形法的解题流程
构建初始单纯形表,求初始解
求得最优解,求解结束
更换基变量
求新的基础可行解
检查是否为
最优解?
是
否
初始单形表的构建方法
Cj
比
值
CB
XB
b
检验数j
检验数s:初始时是目标函数的系数(随基的调整变化)
变量符号
基变量符号
(随基的调整变化)
基变量在目标函数中的系数(变化)
约束方程的常数项
约束方程的变量系数
有一个检验数sj>=0,此时基解不是最优;
所有检验数sj<0,此时基解为最优
目标函数的系数
初始值为0
一、表格单纯形法的计算步骤
maxZ=3x1 +5 x2
x1 ≤ 8
2x2 ≤ 12
3x1 +4 x2 ≤ 36
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
maxZ=3x1 +5 x2 +0x3 +0x4+0x5
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
标准型
取基变量为x3, x4, x5,
1、建立初始单纯形表
则非基变量为x1, x2
2、求初始基可行解并进行最优性检验
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
令非基变量x1=0,x2=0,找到一个初始基可行解:
x1=0,x2 =0,x3 =8,x4 =12,x5 =36,
σj>0,(因为 z=3x1+5x2 +0x3 +0x4+0x5 )
可求基可行解的状态
即X0=(0,0,8,12,36) T
此时利润Z=0
此解不是最优
初始基可行解图示
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
X0=(0,0,8,12,36) T
说明:一个可行解就是一个生产方案,上述方案表明两种产品都不生产x1=0,x2=0 ,利润Z=0 。
3、寻找另一基可行解
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
-
12/2=6
36/4=9
交叉元素称为主元
首先确定进基变量
再确定出基变量
检验数j
8
1
0
1
0
0
6
0
1
0
1/2
0
12
3
0
0
-2
1
x3
x2
x5
0
5
0
-30
3
0
0
-5/2
0
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
5
0
0
0
8
1
0
1
0
0
12
0
2
0
1
0
36
3
4
0
0
1
x3
x4
x5
0
0
0
0
3
5
0
0
0
-
12/2=6
36/4=9
令 x1=0,x4=0得 x2=6,x3=8,x5 =12
σ1 =3>0,此解不是最优
迭代
可求基可行解的状态
即得基可行解X1=(0,6,8,0,12) T
此时-Z=-30, Z=30
第一次基迭代可行解图示
Z=3x1+5x2=30
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
X1=(0,6,8,0,12) T
4、寻找下一基可行解
Cj
比
值
CB
X