1、单纯形法的矩阵描述单纯形法的矩阵描述设线性规划问题可以用如下矩阵形式表示：目标函数 max z=CX 约束条件 AXb 非负条件 X0 将该线性规划问题的约束条件加入松弛变量后，得到标准型：max z=CX+0Xs AX+IXs=b X，X s0 其中，其中，I 是是mm单单位矩位矩阵阵。若以Xs为基变量，并标记成XB，可将系数矩阵(A，I)分为(B，N)两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分：相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作:C=（CB,CN）若经过迭代运算后，可表示为：相应有:线性规划问题
2、可表示为：将（2-2）式移项及整理后得到：令非基变量=0，由上式得到：（1）非基变量的系数表示为：（2）规则表示为：RHS值 表示选用0的分量 换入变量的系数向量（3）单纯形表与矩阵表示的关系:单纯形表中的数据:基变量基变量 非基变量非基变量等式右边等式右边系数矩阵系数矩阵检验数检验数小结小结1）掌握矩阵的运算；）掌握矩阵的运算；2）理解基矩阵的作用；）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。）了解矩阵运算与单纯表的关系。改进单纯形法改进单纯形法求解求解线线性性规规划划问题问题的关的关键键是是计计算算B-1。以下介以下介绍绍一种比一种比较简较简便的便的计计算算B-1的方法。的方法。设
3、设m n系数矩系数矩阵为阵为A，求其逆矩，求其逆矩阵时阵时，可先从第，可先从第1列开始。列开始。以以a11为主元素为主元素,进行变换：进行变换：然后构造含有（然后构造含有（1）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵可得到：可得到：而后以第而后以第2列的列的 为主元素，进行变换为主元素，进行变换:然后构造含有（然后构造含有（2）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵:可得到可得到:重复以上的步骤，直到获得重复以上的步骤，直到获得:可见，可见，EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵用这方法可以求得单纯形法的基矩阵B的逆矩阵的逆矩阵B-1 以例
4、以例1为例进行计算。为例进行计算。第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。(3)确定换出变量表示选择0的元素（4）基变换计算）基变换计算将新的基将新的基 单位矩阵。计算：单位矩阵。计算：（5）计算非基变量的系数矩阵（6）计算RHS第1步计算结束后的结果:计算非基变量的检验数，确定换入变量：计算非基变量的检验数，确定换入变量：确定换出变量：由此得到新的基：由此得到新的基：计算RHS第第2步计算结束后的结果：步计算结束后的结果：第3步：计算非基变量（x3,x5）的检验数:确定换出变量确定换出变量:新的基:计算计算B的逆矩阵：的逆矩阵：计算非基变量的检验数:得到最优解：得到最优解：目标函数的最优值为：目标函数的最优值为：
浙ICP备2021020529号-1 | 浙B2-20240490 
