2.3.2　单纯形表

2.3.2　单纯形表

上面的求解过程，可以采用更直观的单纯形表来计算，步骤如下：

（1）模型标准化。

（2）确定初始可行解，建立初始单纯形表。

（3）判断目标函数值是否能继续改善，如能改善，转（4）。如不能改善，转（6）。

（4）计算非基变量的检验数δ，决定入基变量。计算检验比θ，决定出基变量，变换形成新的单纯形表。

（5）重复（3）、（4）。

（6）给出最优解。

【例2.9】对[例2.8]采用单纯形表求解。

单纯形计算表2.1中，表中Ⅰ先由检验数δj=zj-cj确定入基变量x2，再由检验比θ 确定出基变量x5，然后以对应列与行交叉点为轴点进行等式变换。表中Ⅱ入基变量x1和出基变量x4确定方法类似。然后以对应列与行交叉点为轴点进行等式变换。

表2.1　单纯形计算表（陈爱光等，1991，有更正）

表2.1中计算公式：

检验数：δj=zj-cj，δk=max[|δj|δj＜0，取负值中绝对值最大的k 列对应的变量为入基变量（引入目标增值快的变量为入基变量）]。

检验比：，取检验比值最小的r 行对应的变量为出基变量（保证所有约束条件成立）。

行等式变换，以ar，k为轴变换：

[对入基变量行处理，该r，k 位置变为1，j=1，…，n，n+1（常数项）]。

其他行变换处理，使k 列ai，j其他行元素变为0[i=1，…，m，i≠r；j=1，…，n，n+1（常数项）]。

表中计算过程：

Ⅰ中第3行的z00=0×12+0×20

z10=0×1+0×1

z20=0×1+0×2…

Ⅰ中第4行的zj-cj：-5=0-5，-8=0-8…(https://www.daowen.com)

Ⅰ中入基变量：δ=max{|-5|，|-8|，|-6|}=8，对应入基变量为x2。

Ⅰ中出基变量：θ=min{12/1=12，20/2=10}，对应出基变量为x5。

Ⅱ中第3行：z0：80=0×2+8×10

z1:0=0×(1/2)+8×(1/2)…

Ⅱ中第4行：zj-cj：-1=4-5，0=8-8…

Ⅱ中入基变量：δ=max{|-1|}，对应入基变量为x1。

Ⅱ中出基变量：θ=min{2/（1/2）=4，10/（1/2）=20}=4，对应出基变量为x4。

所有检验数zj-cj均不小于0时，得到最优解。

单纯形法计算框图如图2.4所示。

图2.4　线性规划求解框图（目标最大化，约束≤情况）

上述采用检验比θ 确定出基变量时，有时会出现两个或两个以上最小值情况，这可能会出现退化解（基变量为0）情况，实际中这种情况较少出现，遇到时可采用“摄动法”“字典序法”“波兰特法”等解决，大家可参阅相关文献（马建华，2014），本书不多介绍。

【例2.10】图解法中的[例2.2]采用单纯形表2.2求解。

标准化：

表2.2　单纯形计算表

最优解：x1=16，x2=0，Z=160

【例2.11】

标准化后采用单纯形表求解见表2.3。

表2.3　单纯形计算表

最优解：x1=20，x2=20，Z=200。