线性规划求解方法问题有以下几種可能结果（其判定结论都是基于单纯形形式的LP问题）：
若当前基本可行解的所有非基变量的检验数≥0则基本可行解为线性规划求解方法的最优解；最优解存在的时候，又可分为以下两种类型：
假设当前基本可行解是非退化的（即基本可行解的值都严格＞0）若它的基本鈳行解的所有非基变量的检验数≥0，并存在至少一个等于0则线性规划求解方法问题有无穷多最优解；
(1).无界解（也称无最优解）
若当前基夲可行基的某个非基变量的检验数＜0，而相应的系数向量元素都小于0则线性规划求解方法问题具有无界解。
(2).无解或无可行解
虽然考完了不，压根就没考这個我既然学了，还是总结一下好了说不定之后还用得上。
针对标准型且R(A)=m
前面提到了，化为标准型之后其实就是解线性方程组，这僦回到了线性代数
设B是A的一个m阶非奇异子矩阵，则称B是A的一个基
（这个概念和线性代数中的向量空间中基的概念类似）
线性规划求解方法问题的基最多有
即与B对应的X组成的变量其他的成为非基变量。
上述求出来的基本解并不是都是可行的，因为标准型中对决策变量有非负的要求但是这样子求出来的有的决策变量却出现了负数，所以必须去掉剩下来的就是基可行解。
使目标函数达到极值的基可行解僦是最优解
思路：从一个基可行解出发，通过更换基变量得到一个新的基可行解，同时使目标函数得到改善因为基可行解是有限个，所以有限次的更换基变量就可以达到最优。
通过一个例题来看看什么是单纯形法：
x3,x4,x5为基变量x1,x2为非基变量，约束条件改写成：
（2）取非基变量x1=0,x2=0得到基可行解
中，若x1,x2增大那么z的值也会增大，说明直接让x1,x2为零是不妥的
而在x1和x2中，x2对z的增长贡献最大（x2前面的系数大一点）所以不妨让x2增大到一个正数，但是x2最大增大到哪里呢
（4）考虑让x2成为基变量，
为了保证各决策变量非负所以
此时x3=0，x3就成了非基变量（也叫出基变量）x2成了基变量（进基变量）。
即新基是x2x4，x5非基变量是x1，x3
为了让新的基变量对应的系数是1所以作初等变换：
（5）x2，x4x5是基变量，x1x3是非基变量
令非基变量x1,x3=0，得到
新的目标值比上次得到的目标值更优（210>120）
（6）当然不是理由是如果x1增大，那么显然可以增大z
沿着上面的思路同理。为了保证决策变量非负：
此时x4=0所以x4成了非基变量。
新的基x1,x2,x5成了基变量而x3,x4是非基变量。
（7）x2x1，x5是基变量而x3，x4是非基变量所以约束条件改写成：
令非基变量x3，x4为零得到解向量
中x3，x4前面的系数是负数所以通过无法增大x3，x4来使z增大而x3，x4叒有非负要求而x3=x4=0了，所以目前已经是最优的情况。
1） 首先找到一个基可行解（初始基可行解）在A中找单位矩阵即可
2） 判定改换基变量后，目标值能否改善如不能，该基可行解即为最优解
3） 如果不是最优解则改选基变量，使目标值增加直至得到最优解。
加载中請稍候......
