下载文档原格式
单纯形法求解过程单纯形法是一种常用于求解线性规划问题的算法，它通过不断地转移基变量来逐步接近最优解。
在本文中，我们将详细介绍单纯形法的求解过程，希望可以帮助读者更好地理解和运用这一算法。
首先，我们需要明确线性规划的基本概念。
线性规划问题通常包括一个目标函数和一组约束条件，目标函数是需要最大化或最小化的线性表达式，约束条件是一组线性不等式或等式。
我们的目标是找到使目标函数达到最优值的变量取值。
接下来，让我们来介绍单纯形法的具体步骤。
首先，我们需要将线性规划问题转化为标准形式，也就是将所有约束条件转化为等式。
然后，我们引入松弛变量，将等式约束转化为不等式约束。
这样，我们就得到了一个初始的可行解。
在开始迭代求解过程之前，我们需要对初始可行解进行检验。
通过计算各个变量的价值系数与目标函数系数的乘积之和，若所有乘积之和均为非负数，则初始可行解即为最优解，我们可以直接结束算法。
如果初始可行解不是最优解，那么我们就需要进行迭代求解。
首先，我们需要选择一个离最优解最近的变量，将其作为基变量。
这个选择需要满足一定的规则，通常是选择目标函数系数与价值系数乘积最小的变量。
确定了基变量后，我们需要通过高斯消元法来更新线性规划问题的限制条件和目标函数。
我们将基变量系数矩阵与目标函数系数矩阵进行运算，得到新的限制条件和目标函数。
然后，我们计算新的可行解，并重新检验可行解的最优性。
在迭代过程中，我们需要不断地选择新的基变量，并更新线性规划问题的限制条件和目标函数，直到达到最优解为止。
每次迭代都会逐步接近最优解，并且每次迭代都会提供一个更好的可行解。
需要注意的是，单纯形法存在一些特殊情况需要考虑，比如无界问题和无可行解问题。
在发现这些问题时，我们需要及时停止迭代，并给出相应的提示。
综上所述，单纯形法是一种常用的求解线性规划问题的有效算法。
通过反复迭代选择基变量，并更新线性规划问题的约束条件和目标函数，我们可以逐步接近最优解。
希望本文的介绍可以帮助读者更好地掌握单纯形法的求解过程，并在实际问题中灵活运用。
•单纯形计算过程特别说明
1. 如何从单纯形表判断最优解
1)唯一最优解判别：最优表中所有非基变量的检验数大于零,则线性规划具有唯一最优解.
2)多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解(或无穷多最优解).
<0且a ik≤０（i=1,…,m）则线性规划具有无界解.
3)无界解判别：某个σ
k
4)无可行解的判别：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解.
5)退化解的判别：
a)存在某个基变量为零的基本可行解;
[此时可能出现循环迭代而永远找不到最优解.该情况是由比值相同造成的.可以证明：当出现比值相同时,按下标最小的基变量作为换出变量可避免出现循环，具体可参阅有关文献];
b)人工变量在最优表的基中,但人工变量的取值为零.
[此种情况是由于存在多余约束(A不行满秩)造成的,可通过消去多余约束加以解决]
3. 计算过程需要特别注意的问题：
在确定了进基变量和出基变量，即确定主元后，单纯形变换的计算方法：
1）主元所在的行所有元素除以主元值，将主元变换成1；
2）用主元行的合适倍数加至其它各行(此时，改变的是其它各行，而主元行不发生变化!)，以将主元列除主元外的其它元素变换成零。
注：采用以上变换方法（而不是任意初等变换）是为了保证：原来在基中并为发生改变的基变量，在变换计算后其对应的基向量不能发生改变。
也就是说：在任何时候，单纯形表中的所有基向量构成的矩阵均为单位矩阵！。
第2章 单纯形法的基本概念2.1 可行解满足约束条件的解X=（12x x x n ，，...,）T ，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。
2.2 基设A 是约束方程组的m × n 维系数矩阵，其秩为m 。
B 是矩阵A 中m × m 阶非奇异子矩阵，则称B 是线性规划问题的一个基。
这就是说矩阵B 是由m 个线性独立的列向量组成。
为不失一般性，可设)(111121,,...,m m m mm a a B p p p a a ⎛⎫ ⎪== ⎪ ⎪⎝⎭称j p 为基向量，与基向量j p 相应的变量j x 为基变量，否则称为非基变量，为了进一步讨论线性规划问题的解，下面研究约束方程组中的求解问题。
假设该方程组系数矩阵A 的秩为m ，且m < n ，故它有无穷多个解。
假设前m 个变量的系数列向量是线性独立的。
这时约束方程组可以写成11211m a a a ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭1x +12222m a a a ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭2x +...+12m m mm a a a ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭m x =12m b b b ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭—1,12,1,1m m m m a a a +++⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭1m x +—...—12n n mn a a a ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭n x 或 11n n i j i j j j m Px b Px ==+=-∑∑上面这个方程组的一个基是)(11121221221212,,...,m m m m m mm a a a a a a B P P P a a a ⎛⎫ ⎪ ⎪== ⎪ ⎪⎝⎭设B X 是对应于这个基的基变量 B X =()12,,...,Tm x x x现若令方程组中的非基变量12...0m m n x x x ++====，这时变量的个数等于线性方程的个数。
用高斯消去法，求出一个解()12,,...,,0, 0m X x x x =该解的非零向量的数目不大于方程个数m ，称X 为基解。
