45 x2 3 3 45
24 x3 1 2 24
0 x4 1 0 0
0 x5 θ i 0 100/3 1 120/3 0
现用例1的标准型来说明上述计算步骤。
max z 2x1 3x2 0x3 0x4 0x5
x1 2x 2 x 3 4x 2 xj 0 8 4x1 x4 16 x 5 12 j 1,2, ,5

i 1
θ列的数字是在确定换入变量后， 0 0 xi xl min a ij 0 按θ规则计算后填入， i a ij a lj 用以确定换出变量； 表1-2 称为初始单纯形表，每迭代一步构造一个新单纯形表。

例 ： 试列出下面线性规划问题的初始单纯型表
z c1 x 1 c m x m c m 1 x m 1 c n x n 0
线 性 规 划 的 方 程 组
为了便于迭代运算，将上述方程组写成增广矩阵形式
z
x1
x2

xm
x m 1

xn
b
0 1 0 0 a 1 ,m 1 0 1 0 a 2 ,m 1 0 0 0 0 1 a m ,m 1 cm 1 1 c1 c 2 c m -z+c1x1+c2x2+…+cmxm+cm+1xm+1+ …
0
X4 1/4 1/2 -1/8 -1/8
θ 4 12
c j→
CB 2 0 3 -z XB x1 x5 x2
0
x5 0 1 0 0 θ
表 1-5
1/2 -3/2
-14
(4) 表1-6最后一行的所有检验数都已为负或零。 表示目标函数值已不可能再增大，于是得到最优解
max f ( x) 40x1 45x 2 24x 3 +0x4+0x5 2x 1 3x 2 x 3 s.t . 3x1 3x 2 2x 3 x1 , x 2 , x 3
+x =100 100 4
120 +x5=120 0
CB 0 0
40 XB b x1 x4 100 2 x5 120 3 cj-zj 40
(3) x1应为换入变量，得表1-5。
c j→
2
3
0
0
0
CB 2 0 3 -z
XB x1 x4 x2
b 2 8 3 -13
x1 1 0 0 0
2
b 4 4 2 x1 1 0 0 0
x2 0 0 1 0
3
x2 0 0 1 0
x3 1 -4 0 -2
0
x3 1 -2
x4 0 1 0 0
x5 -1/2 2 1/4 1/4
i 1 m

cn i xn a 1n a 2n a mn c n c i a in
i 1 m
1 2 m

单纯形表1-2 的说明：
XB (基）列中填入基变量，这里是x 1，x 2 ,…，x m； CB 列中填入基变量的价值系数，这里是 c1 ,c 2 , … , c m ，它们是与基变量相对应的； b 列中填入约束方程组右端的常数； cj 行中填入基变量的价值系数c1 ,c2 , … , c n； 最后一行称为检验数行，对应各非基变量xj 的检验数， m 用以确定换入变量； j c j ci aij , j 1,2, , n
c n c i a in
可根据上述增广矩阵设计计算表---单纯形表
cj CB c1 c2 cm XB x1 x2 xm cj z j b b1 b2 bm
c1 x1 1 0 0 0

cm xm 0 0 1 0
cm 1 x m 1 a 1 ,m 1 a 2 ,m 1 a m ,m 1 c m 1 c i a i ,m 1

(1) 取松弛变量x3,x4,x5为基变量， 得到初始基可行解X(0)=(0,0,8,16,12)T 得到初始单纯形表如下：
，
表 1-3
CB 0 0
目标函数中各变量的价值系数。
cj→ XB x3 x4 x5 b 8 16 12 0 2 3 0 0 0 θ 8/2=4 12/4=3
x1 x2 1 4 0 2 2 0 4 3
4.1单纯形表


为了计算上的方便和规格化，对单纯形法计算 设计了一种专门表格，称为单纯形表。 其功能与增广矩阵相似，下面来建立这种计算表。 将书P23 (1-22) 标准型中的约束方程组与目标函数组 成 n+1 个变量，m+1 个方程的方程组。
x1 x2
a 1m 1 x m 1 a 1 n x n b 1 a 2m 1x m 1 a 2n x n b 2 x m a mm 1x m 1 a mn x n b m
a 1n b 1 a 2n b 2 a mn b m cn 0 +cnxn =0
xn a 1n a 2n a mn
m i 1
线 性 规 划 的 方 程 组

b b2 bm m cibi i 1 b1
z 0 0 0 1 x1 x 2 1 0 0 0 0 0 1 xm 0 0 0 1 0 x m 1 a 1 ,m 1 a 2 ,m 1 a m ,m 1 c m 1 c i a i ,m 1
i 1 m
x3 x4 x5 1 0 0 0 0 1 0 0 0 0 1 0
基变量 0
-z
3.确定主元素
1.计算检验数，由它 确定为换入变量
2. 计算θ，由它确定为算或迭代运算，
c j→ CB 0 0 3 -z XB x3 x4 x2 b 2 16 3 -9 2 x1 1 4 0 2 3 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 -1/2 0 1/4 -3/4 θ 2 4 -