运筹学基础及应用
解：化标准型
max
z 2 x1 x2 0 x3 0 x4 0 x5 5 x2 x3 15 6 x 2 x x4 24 1 2 x5 5 x1 x2 x1 , , x5 0
运筹学基础及应用
表1：列初始单纯形表 （单位矩阵对应的变量为基变量）
运筹学基础及应用
单纯形表
- Z x1基变量 x 2 ... xm XB 0 1 1E 0 单位阵 ....... 0 1 1 c c 0... c 1 2 m xm xNn 非基变量 1 .... X a1m 1 ...a1n a 2 m 1N...a 2 n
非基阵 ......
在上一节单纯形法迭代原理中可 知，每一次迭代计算只要表示出当前的约 束方程组及目标函数即可。
a1m 1 xm 1 ..... a1n xn b1 x1 x a2 m 1 xm 1 ..... a2 n xn b2 2 .......... .......... .......... ..... xm amm 1 xm 1 ..... amn xn bm Z c1 x1 ... cm xm cm 1 xm 1 ... cn xn 0
3
0 1 5/4 -15/2 1*3/2 0 0 1/4 -1/2 +0*15/2 检验数<=0 1 0 -1/4 3/2
cj z j
8.5
0
0
-1/4
-1/2
最优解为X=(7/2,3/2,15/2,0,0) 目标函数值Z=8.5
cj
CB
0 0 0
2
1
0最小的值对应 0 0
的行为主行
4
XB
x4
b
15 24 5
x
x
x1 x2 x3 x
0 6 1
2
x

5
3
5
5 2 1
1 0 0
0 1 0
0 0 1
0
min — 24/6 5/1
cj z j
正检验数中最大者对 应的列为主列
主元化为1 1 0 0 主列单位向量 x4 换出 x1 换入
记 j c j ci aij
i 1
运筹学基础及应用
为书写规范和便于计算，对单纯形法 的计算设计了单纯形表。每一次迭代对应 一张单纯形表，含初始基可行解的单纯形 表称为初始单纯形表，含最优解的单纯形 表称为最终单纯形表。本节介绍用单纯形 表计算线性规划问题的步骤。
运筹学基础及应用
单纯形表
b b1 b2 bm 0
a mm1 ...a mn c m 1
N
cn
运筹学基础及应用
单纯形表
单纯形表结构
cj
CB
c1 cm
c12
c21
0
C
cm cn 0 0
XB
x1 xm
b
b '已知
x2
xm xn

min — 24/6 5/1
b
b '1 ' bm
x1
x2
xm xn

min — 24/6 l 5/1
A
c j zz j
al,mk ,m k am
,m k a1
0
检验数 mk
运筹学基础及应用
用单纯形表求解LP问题
例、用单纯形表求解LP问题
max
z 2 x1 x2 5 x2 15 6 x 2 x 24 1 2 x1 x2 5 x1 , x2 0
0 1 /6 -1/6
-1/3
min 15/5 24/2 6/4
检验数>0 确定主列
最小
确定主列
运筹学基础及应用
表3：换基
（初等行变换，主列化为单位向量，主元为1）
cj
CB
0 2 1
2
1
0
0
4
0
XB
b
15/2 7/2 3/2
x
x3 x x1 x 2 2*7/2
0 1 0
0
x

5
min
x2
x1
A
j a1
a mj
c j zz j
0
检验数 求j
运筹学基础及应用
' bi' bl ' min ' a imk 0 ' 单纯形表结构 i a im k a lm k cj 2 1 0 0 C0
单纯形表
CB
c1 cm
XB
x1 xm
运筹学基础及应用
表2：换基
（初等行变换，主列化为单位向量，主元为1）
cj
CB
0 2 0
2
1
0
0
4
0
XB
x1
b
x
x
x1 x2 x3 x
主元 5 1 2/6 0 4/6 0 1/3 0
x
0 0 1
0

5
3
+0*4/6 c z 1- 2/3= 0
j j
5
15 0*5 0 4 1 2*2/6 1 0
b
b '1 ' bm
x1
x2
xm xn

A
不妨设此 为主列
c j zz j
min ,m k 主行 — a1 24/6 求 l 5/1 ,m k am
0
检验数 mk
运筹学基础及应用
单纯形表
单纯形表结构
主元
cj
CB
c1 cm
2
1
C0
0
0
XB
x1 xm
j
单纯形表 Z Z (c Z )x
j
' Z j ci aij i 1
m
j
2
C X B b Z j x j x1 B Z0 j m 1 ' c1 x1 b 1
cm
xm
' bm
n
检验数 1 0 cj 0 C0
x2
xm xn

min — 24/6 5/1
A
c j zz j
0
检验数
运筹学基础及应用
单纯形表
单纯形表结构
基可行解：
,, bm ,0,,0) X (b1
1
cj
CB
c1 cm
2
C0
0
0
XB
b
c j zz j
x1 b ' 1 ' x m bm
x1
x2
xm xn

min — 24/6 5/1
运筹学基础及应用
§4
单纯形法的计算步骤
单纯形法是一种迭代的算法，它的思 想是在可行域的角点——基本可行解中寻 优。由于角点是有限个，因此，算法经有 限步可终止。
确定一个初始基可行解 检验这个基可行解是否最优 否 寻找一个更好的基可行解
是 停 止
运筹学基础及应用
单纯形法计算步骤
1.将非标准型线性规划化为标准型 2.确定初始基可行解：一般设松弛变量为初时基可 行解 3.判断：若所有的非基变量的检验数σj≤0，则此 解为LP的最优解，若存在某一非基变量的检验数 σj>0，则问题还没有达到最优解，需进行改进 4.迭代：选换入变量max{cj- zj/ cj-zj>0}假设xk为换 入变量；选换出变量θ＝min{bi/aik，aik＞0}，假 设选取xl为换出变量；然后迭代，使得alk＝1，其 m 余aik为0
j m 1
(c
n
j
Z j )x j
0 检验数
min — 24/6 5/1
Z Z0
x1
x2
xm xn
j
j m 1
A
xj
c j zz j 求 0
有时不 写此项
检验数
运筹学基础及应用 m
令：Z 0 ci bi'
i 1 n 0 j
j m 1 单纯形表结构 令： j (c j Z j ) c
A
检验数
0
运筹学基础及应用
' 令： Z c b 单纯形表 0 i i i 1 n m ' Z j ci aij i 1 m
单纯形表结构Z Z 0
cj
CB
c1 cm
XB
x1 xm
b
b1 ' bm
'
2 1 0 0 C 令： j (c j Z j )