文档介绍：运筹学—线性规划(三)
§3单纯形法的计算步骤及相关的特殊情况
前面我们讨论了单纯形法的理论基础及其可行性。本节将讨论单纯形法的实施计算步骤。
一﹑单纯形法的计算步骤
1﹒单纯形表
将约束方程组与目标函数组成n+1个变量,m+1个方程的方程组(设x1 , x2,…, xm是基变量) 。
x1 +a1m+1xm+1+…+a1nxn= b1
x2 +a2m+1xm+1+…+a2nxn= b2
· · · · · · · · · · · · · · · · · · · · ·
xm+amm+1xm+1+…+amnxn= bm
-z+ c1x1+c2x2+…+ cmxm + cm+1xm+1 +…+ cnxn= 0
0 1 0 … 0 a1m+1… a1n b1
0 0 1… 0 a2m+1… a2n b2
· · · · · · · · · · · · · · · · ·
0 0 0 …1 amm+1… amn bm
-z x1 x2… xm xm+1 … xn b
1 c1 c2 …cm cm+1 … cn 0
系数增广矩阵:
采用初等变换将c1 c2 …cm 变换为零,可得:
0 1 0 … 0 a1m+1 … a1n b1
0 0 1… 0 a2m+1 … a2n b2
· · · · · · · · · · · · · · · · ·
0 0 0 …1 amm+1 … amn bm
-z x1 x2… xm xm+1 … xn b
1 0 0 …0 cm+1 -∑ciaim+1 … cn -∑ciain -∑cibi
m
i=1
m
i=1
m
i=1
非基变量检验数δj 。
cj
c1
..
cm
cm+1
..
cn
θ i
CB
XB
b
x1
..
xm
xm+1
..
xn
c1
c2
·
cm
x1
x2
·
xm
b1
b2
·
bm
1
0
·
0
..
..
..
..
0
0
·
1
a1m+1
a2m+1
·
amm+1
..
..
..
..
a1n
a2n
·
amn
θ 1
θ 2
·
θ m
-z
m
-∑cibi
i=1
0
..
0
cm+1 -
m
∑ciaim+1
i=1
cn -
m
∑ciain
i=1
计算表1—1:
非基变量检验数δj
基变量及价值系数
换出变量确定参数
系数矩阵
价值系数
方程组右端系数
2﹒计算步骤
(1)找出初始可行基,确定初始基可行解,建立初始单纯形表。
(2)检验各非基变量xj的检验数δj=cj-
i=1
m
∑ ciaij ,
如果δj≤0 ,j=m+1, …,n; …,n;则已得到最优解,可停止计算。否则转入下一步。
(3)在δj﹥0 ,j=m+1,…,n 中,若存在某个δk对应xk的系数向量pk≤0,则问题是无界,停止计算。否则,转入下一步。
(5)以alk为主元素进行迭代,把xk所对应的列向量
pk=
a1k
a2k
alk
amk
·
·
0
0
1
0
·
·
变换为
第 l 行
将XB列中的xl换为xk,得到新的单纯形表。
在得到最优解或确定无界解之前,重复(2)—(5)。
(4)根据max( δj﹥0 )= δk ,确定xk 为换入变量,按θ规则计算
θ=min (——︱ aik﹥0 )
bi
aik
=——
bl
alk
可确定xl为换出变量。转下一步。
3﹒举例
例 1 求下列线性规划问题的解
max z=2x1+3x2
x1+ 2x2≤8
4x1 ≤16
4x2≤12
x1﹐x2 ≥0
max z=2x1+3x2+0x3+0x4+0x5
x1+ 2x2 + x3 =8
4x1 + x4 =16
4x2 + x5=12
x1﹐x2 ﹐x3 ﹐x4 ﹐x5 ≥0
B=
1 0 0
0 1 0
0 0 1
系数矩阵A=
1 2 1 0 0
4 0 0 1 0
0 4 0 0 1
是一个基。
x3 , x4 , x5是基变量, x1 , x2 是非基变量
X(0)=(0,0,8,16,12)T是基可行解。
c=(2,3,0,0,0)
b=(8,16,12)T
CB=(0,0,0) , XB=(x3 , x4 , x5)
cj
2
3
0
0
0
θ i
CB
XB
b
x1
x2
x3
x4
x5
0
0
0
x3
x4
x5
8
16
12
1
4<br