大学论文：线性规划问题(4)

线性规划 毕业论文

考虑约束条件中的非齐次线性方程组，设A为系数矩阵，B为增广矩阵。

线性方程组的解（即可行解）一般有三种情况：无解、唯一解、无穷解。对于上面的非其次线性方程组，当 m<n时，若有解，一定有无穷解；下面考虑无解的情况，如何判断呢，线性代数中的方法是将原方程组经过初等变换后得到阶梯形方程组，通过判断阶梯形方程组中是否出现“0=d（d 0）”，若出现，则原方程组无解；否则，有解。当m≥n时，若有解，如果rank(B)=n，则有唯一解；如果rank(B)<n，则有无穷解；无解时的判断与m<n时相同。

同时，对于LP问题可能有几种结局：有唯一的最优解、有无穷多个最优解、无界解、无解。其中无解的情况即LP问题的约束条件对应的线性方程组无解。

特别的对于二元LP问题，也可以应用图解法，在二维直角坐标平面上作图表示线性规划问题的有关概念，判断有无解，并求解。 3.单纯性法

单纯形法的理论基础：

定理一 若LP问题可行域存在，则可行域是个凸集。 定理二 LP问题的基可行解与可行域的顶点一一对应。

定理三 若LP问题存在最优解，则一定存在一个基可行解是最优解。

若LP问题的最优解存在，则它一定可在其可行域R的一个极点处达到，所以单纯形法的基本思想就是从一个初始极点出发，按照一种简单的规则，自动实现从一个极点转移到另一个极点，同时使目标函