单纯形法求解—动态演示
在求解LP问题时,有人给出了图解法,但对 多维变量时,却无能为力,于是
美国数学家G·B·Dantgig(丹捷格)发明了 一种“单纯形法”的代数算法，尤其是 方便于计算机运算。这是运筹学史上最 辉煌的阶段。
一、关于标准型解的若干基本概念
线性规划问题标准型的矩阵形式：
Max Z = CX
Z = CX AX=b
设 A=（B , N）（B为一个基，即线性无关向量组R(A)=R(B)）
XT= (XB , XN) T （XB 为基变量，XN为非基变量） C= (CB , CN) （CB 为基变量系数，CN为非基变量系数） 则有： Z= (CB , CN) (XB , XN) T= CB XB+CN XN AX =（ B , N） (XB , XN) T = B XB+ N XN = b 因为B为基, 故有 XB +B-1N XN = B-1b，
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj j cj zj
0 100 0
0 100
Z=25000
初始单纯形表
迭代 基变 次数 量
CB
x1
X2
s1
50 100 0
S1 0 1 0 1
s2 S3
00 0 -1
比值
检验系数区
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
x1
x2
s1
s2
s3
50 100 0 0 0
比值
b bi ai 2
1 Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
基
迭代 次数
变
CB
x1
X2
s1
s2
量
50 100 0 0
1 110
2 101
0
0 100
Zj=CBNj
CB
S1 0
x1 X2 s1 50 100 0 111
s2 S3
比值
b bi
00
ai 2
0 0 300
S2 0 2 1 0 1 0 400
1 S3 0 0 1 0 0 1 250
Zj=CBNj
j cj zj
Z=0
初始单纯形表
迭代 基变 次数 量
CB
S1 0
x1 X2 s1 50 100 0 111
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
1 S3 0
0 ①1
0
0
1 250 250
1
Zj=CBNj 0 0 0 0 0 Z=0
j c j z j 50 100 0 0 0
初始单纯形表 可行解XB=B-1b-B-1NXN>=0
迭代 基变 次数 量
CB
S1 0 S2 0
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2
0 ①1 0 0 1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
s2 S3 00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj j cj zj
Z=25000
初始单纯形表
迭代 基变 次数 量
CB
S1 0
x1 X2 s1 50 100 0 101
s2 S3 00 0 -1
00
ai 2
0 0 300
S2 0 2 1 0 1 0 400
1 S3 0 0 1 0 0 1 250
Zj=CBNj 0 0 0 0 0
j c j z j 50 100 0 0 0
0 Z=
初始单纯形表 可行解XB=B-1b-B-1NXN>=0
迭代 基变 次数 量
CB
S1 0 S2 0
x1 X2 s1
s2 S3
00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj 0 100 0 j c j z j 50 0 0
0 100 0 -100
Z=25000
初始单纯形表
迭代 基变 次数 量
CB
x1 X2 s1 50 100 0
解得可行解XB=B-1b-B-1NXN，代入目标函数Z， Z = CB B-1b + (CN- CB B-1N ) XN
令非基变量XN = 0 ，则有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1b
Z = CB B-1b + (CN- CB B-1N ) XN
b bi ai 2
50
S2 0 2 0 0 1 -1 150
2 x2 100 0 1 0 0 1 250
Zj=CBNj 0 100 0 j c j z j 50 0 0
0 100 0 -100
Z=25000
初始单纯形表
迭代 基变 次数 量
CB
x1
X2
s1
50 100 0
S1 0 1 0 1
（a）
C (c1, c2 ,, cn );
s.t. AX=b X0
（ b） （c）
X (x1, x2 ,, xn )T
a11 a12 …. a1n
b1
A= a21 a22 …. a2n
……………………………
am1 am2 …. amn
b = b2
…………
bm
基矩阵
示例:
目标函数
约 束 条 件
x1 x2 x3 x4
3 0 00 3
0 2 0 0= 2
0 0 11 1
max z 3x1 2x2 x3 x4
3x1
3
s.t.
2x2
2
x3 x4 1
x1 x2 x3
0
行列式≠0 基矩阵
300 020 001
X1,x2,x3为基变量,x4为非基变量
1、单纯形法原理：
迭代 基变 次数 量
CB
x1
X2
s1
s2
S3
比值
b bi aij
1 Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
x1 X2 s1 s2 S3
目标函数系数区
比值
b bi aij
基 变 量 区
1
约束条件
右 端 系
系数区 数
Zj=CBNj j cj zj
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
S1 0 S2 0
x1 X2 s1
CB
xS11 500
xx1 X2 s1
5500 100 0 ①1 0 1
s2 S3 00 0 -1
比值
b bi ai 2
50
S2 0 2 0 0 1 -1 150
3 x2 100 0 1 0 0 1 250
Zj=CBNj
j cj zj
初始单纯形表
迭代 基变 次数 量
CB
x1 50
x1 x2 s1 50 100 0 ①1 0 1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
S1 0
x1 X2 s1 50 100 0 101
CB
S1 0 S2 0
x1 X2 s1
50 100 0 111 210
s2 S3
比值
b bi
00
ai 2
0
0
300
300 1
1
0
400
400 1
2 x2 100 0
①1
0
0
1 250 250
1
Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
S1 0 S2 0
s2 S3 00
比值
b bi ai 2
S1 0 ①1