线性规划问题的广义逆矩阵结合初等行变换法

一、最小广逆的定义
　　定义1 设为×矩阵,若存在×矩阵满足=,则称为的g逆。
　　定义2 对任意的×矩阵, ×1矩阵和1×矩阵,若 有g逆满足0, ()0,则称此为的最小广逆,记作 ,其中为阶单位矩阵。
　　设= , >,为满秩的阶方阵,则必是 的一个g逆,记作 ,称之为对应于基的g逆。显然中每有一个基,就有一个对应于基的g逆。一个×()矩阵至多有个对应于基的g逆。将它们的全体组成的集合记作G。
　　二、线性规划最优解的存在性定理
　　设Lp(1) minS=CX
　　其中 相容。
　　定理Lp(1)有最优解的充要条件是有最小广逆且=。
　　证 若Lp(1)有最优解,不妨设它的初始单纯形表为 ,其中为最优基,经旋转变换后的最终单纯形表为 ,()
　　应有00
　　令,显然为的一个g逆。
　　又 ,
　　故为的最小广逆,且。
　　反之,若有最小广逆 ,则取,0,=
　　∴为Lp(1)的可行解
　　又对Lp(1)的任意可行解 ,即 , 0
　　∵0 ∴0
　　即 ==故为Lp(1)的最优解
　　推论:Lp(1)有最优解 的充分必要条件是集合 中至少有一个元素是的最小广逆。
　　三、解Lp(1)问题的广义逆矩阵结合初等行变换法
　　由定理知,若有最小广逆,则Lp(1)一定有最优解。我们至多寻找 次,即可判定Lp(1)是否有最优解。
　　特别地,当有最小广逆且当 时 ,
　　 。
　　因此求解Lp(1)问题的广义逆矩阵结合初等行变换法步骤如下:
　　(一)对增广矩阵[] 进行一系列的初等变换将[]化成一阶梯形矩阵,找出所有的可行基。
　　(二)对每一个可行基,利用初等行变换将可行基所在的列矩阵化为单位矩阵得矩阵[**] 。
　　(3)判断:对每一矩阵[**],考察其对应的*与*是否非负,若成立,则即为Lp(1)的最优解。否则,无最优解。
　　四、实例
　　Lp(1)
　　解
　　对应三个可行基 。
　　对
　　∴ 不是最优解。
　　对 ,
　　∵
　　∴ 为 LP(1)的最优解。
　　对 ,
　　∵
　　不满足条件0 ,∴ 不是最优解。
　　参考文献:
　　[1]吴文达.广义逆矩阵[J].计算机与应用数学,1994,(1):4-23.
　　[2]中国人民大学数学教研室.线性规划[M].中国人民大学出版社,1981,(7):40-47.