第二章 第二章 对偶理论与灵敏度分析 §1 单纯形法的矩阵描述
设有线性规划：
LP： MAX Z=CX
ST AX≤b
X≥0
加入松弛变量XS后，可把原方程表示为：
LP： MAX Z=CX+0XS
ST BX+IXS=b
X≥0 XS≥0
式中：X为基变量，B为基变量所对应的基矩阵；XS为非基变
量，I为单位矩阵。
通过计算可得：
AX=（B|BN）（X|XS）T=BX＋BNXS=b
式中：BN为非基变量所对应的非基矩阵；令XS=0，可得LP问题的一个基本可行解：
X=B－1b
对于目标函数，可得：
Z=CBB－1b＋(C－CBB－1A)X
最优目标函数值：
Z=CBB－1b
定义：
单纯形乘子：Y=CBB－1
检验数：σ=C－YA
对应最大检验数所对应的变量进基
检验数的分量为：σj=Cj－YPj
最小θ规则： 所对应的变量为出基变量 |