我们知道，如果线性规划有有限的最优解，那么该最优解一定可以在可行域的顶点上取到。

单纯形法便是从初始顶点开始，通过最优性判别准则判断，若不是最优，则转移到新顶点迭代，新顶点的目标值必然优于上一个，直到找到最优值停止迭代。

可行域的顶点称作基本可行解，下面开始介绍单纯形法的迭代步骤。

1.化标准型

基变量： x3 , x4 , x5 →只出现在其中一个方程且系数为1
非基变量： x1 , x2
基本可行解： X=(x1,x2,x3,x4,x5)T→非基变量取值全为0的可行解
初始基本可行解： X0=(0,0,6,12,2)T

非退化基本可行解：基变量都大于0的基本可行解
退化基本可行解：至少有一个基变量等于0的基本可行解

2.单纯形表

介绍一下该表的各值：
cj： xj 对应在目标函数中的系数
CB： XB 对应在目标函数中的系数
pj： 为 xjT
b： 为约束方程右边的值

检验数(λj=cj-CBpj) ： 对于某个基本可行解，若它的检验数都≤0，它便是最优解

目标值(Zj=CBb) ： 单纯形表中填的是目标值的相反数，即加上负号

由最优性判别准则（对于某个基本可行解，若它的检验数都≤0，它便是最优解）知道该表不是最优表，于是需要通过变换基本可行解来优化目标值

3.迭代方法

X=(x1,x2,x3,x4,x5)T
X0=(0,0,6,12,2)T→Z0=0
X1=(0,θ,x3‘,x4‘,x5’)T→Z1=4θ↑
maxZ=3x1+4x2=3×0+4×θ=4θ
X1=(θ,0,x3’‘,x4’‘,x5’’)T→Z1=3θ↑
maxZ=3x1+4x2=3×θ+4×0=3θ

选增大倍数大的，即
λk=max{λj|λj>0}→xk为进基变量
λ2=max{λ1,λ2>0}→x2为进基变量

θ=min{6/2,12/2,2/1}=2→x5为离基变量

x3‘=6-2θ=2
x4‘=12-2θ=8
x5‘=2-θ=0
X1=(0,2,2,8,0)T→Z1=8↑

离基变量的确定遵循最小非负比准则

该处p2为(2,2,1)T均>0，若存在≤0的则考虑非负部分即可

X1=(0,2,2,8,0)T→Z1=8↑

由最优性判别准则知该表不是最优表，继续迭代，方法如上，以下列出相应迭代后的表格

X2=(2,2,0,2,0)T→Z2=14↑

X∗=(3,3/2,0,0,1/2)T→Z∗=15↑

迭代结束，找到最优解