Question

单纯形法计算线性规划的步骤

Answer 1

如果依靠软件，比如MATLAB，MATHEMATICA什么的（甚至EXCEL），都有现成的线性规划的解决方案，照你图里面的条件输入就可以了（不知道具体的软件无法回答）。

以下说明不用软件的手动计算单纯形法的标准方法。
首先添加松弛变量，因为有3个方程，故添加3个松弛变量S1,S2,S3。约束方程组变为：
2X1+X2+X3+S1=2(注意小于等于号变成了等于号，这就是添加松弛变量的作用）。
X1+2X2+3X3+S2=5
2X1+2X2+X3+S3=6
X1,X2,X3,S1,S2,S3>=0
这是一个6个未知数（n），3个方程的方程组（m）。则选择n-m=3个变量作为“基变量”，让其余变量为0（非基变量）。使得方程组退化为：3个未知数，3个方程的方程组。然后根据对目标函数的影响迭代求解。

注意：单纯形法是一个迭代（或者说尝试的过程）。

先列出单纯形表(一个矩阵，里面的数据是目标函数和方程组的系数)。
当我们选择从原点开始（令X1,X2,X3为0，则得到一个基本解：S1=2,S2=3,S3=6 , 目标函数X0=0；），则单纯形矩阵如下：

( {
{1, -3, -1, -3, 0, 0, 0, 0},
{0, 2, 1, 1, 1, 0, 0, 2},
{0, 1, 2, 3, 0, 1, 0, 5},
{0, 2, 2, 1, 0, 0, 1, 6}
} )

呃，不知道怎么在百度里面输入矩阵这种东西。。。反正第一行就是目标函数的方程的系数：
X0-3X1-X2-X3+S1+S2+S3=0
其他行就是下面的方程组。矩阵的最右边一列是方程的右边项。

此时的矩阵是令X1,X2,X3为非基，S1,S2,S3为基的，代表“原点”（起始点）的矩阵，此时的目标：X0=0

然后选择目标函数中系数最大的变量为“进基”（就是选他进入基变量组，设为0），选择解和“进基”变量之比为最小非负数的变量为“离基”（就是让他离开基变量组，不设为0）。

在这里，选择X1作为进基（因为其在目标方程中的系数最小（负得最多，此题选X3也可），S1为离基（因S1行的解与X1系数之比为1，为最小非负数），然后进行矩阵运算（线性代数里面学的那些东西），使得矩阵的第一行中，代表X1,S2,S3的系数为0，S1不为0。

继续矩阵变换，选择进基和离基，直到目标函数的所有系数非负（停止条件），如果是最小化问题则是非正。

懒得算了，告诉你个结果吧。
x0=27/5
x1=1/5
x2=0
x3=8/5

Answer 2

单纯形法计算线性规划的步骤：
（1）把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。
（2）若基本可行解不存在，即约束条件有矛盾，则问题无解。
（3）若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
（4）按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。
（5）若迭代过程中发现问题的目标函数值无界，则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。

Answer 3

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
也可以从任意一本运筹学或者线性规划教材上面查看算法，最好结合例子还看，比较容易懂点。

Answer 4

1、先划LP标准型2、看是否有现成的可行基(之后看检验数，换基迭代)3、没有现成的可行基就用两阶段法先求解辅助问题，判断原问题是否有可行基