线性规划单纯形法：什么意思、理论依据
20世纪40年代末，单茨格（Dantzig）提出的单纯形法，完美地解决了线性规划问题。
单纯形法的一些基本概念
在线性规划中，设 A 为约束条件的 m × n 阶系数矩阵（设 n > m ），其秩为 m ， B 是矩阵 A 的一个 m × m 的满秩子矩阵，那么我们称 B 是线性规划问题的一个基。
基变量： B 中每一列所对应的变量叫基变量，其余的叫非基变量。
基本可行解 ：一般地，如果包括松弛变量在内的变量个数为 n ，方程个数为 m ，那么在标准形式中，有 n - m 个变量等于0的可行解叫做基本可行解。
最优解 ：满足目标函数要求的基本可行解为最优解。最优解对应的基为最优基。
矩阵的初等变换 ：将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。
单纯形法的理论依据
单纯形法解决线性规划问题的理论依据：线性规划问题的可行域是 n 维向量空间R n 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。
单纯形法的基本思想：
先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换；按照这个方法重复进行。因基本可行解的个数有限，故经有限次转换后必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法是从某一基本可行解出发，连续地寻找相邻的基本可行解，直到达到最优的迭代过程，其实质是解线性方程组。
