(23)--2.5.4单纯形法的矩阵描述.pdf

单纯形法的

矩阵描述

设线性规划问题的数学模型为:

maxzCX

AXb



s.t.

X0



将其化为标准形式:

maxzCX0X

S

AXIXsb



s.t.

X0,XS0



设迭代到某一步时的基矩阵为B(基变量为XB),令：

T

A(B,N),CCB,CN,X(XB,XN),

则可将标准形式的线性规划模型写成:

maxzCXCX0X

BBNNS

BXNXIXb

BNS



XB,XN,XS0



当XB成为基变量后，其在约束中的系数矩阵变为单位矩阵。

因为整个迭代过程是对约束条件进行的初等变换，当B变

成I相当于在初始约束条件的两边左乘了一个逆矩阵B-1。

即11

B(BXBNXNXS)Bb

所以111

IXBNXBXBb

BNS

由此可得矩阵形式的初始单纯形表和迭代后的单纯形表。

初始单纯形表

非基变量基变量

解θ

基系数基XBXNXS