2.3.1 由算例看单纯形法迭代思路
【例2.8】
（1）模型标准化。
（2）给出一组初始可行解。线性规划中，约束方程个数m＜n 时，基变量个数为m，则非基变量个数为n-m。本例中，约束方程为2个，决策变量为5个，因此至少应有3个变量为0（非基变量），非0的变量称为基变量。不妨设x1=0，x2=0，x3=0，则由约束方程式（2.2）、式（2.3）可知：
代入x1=0，x2=0，x3=0得到初始可行解为X=（0，0，0，12，20）T，这里x1、x2、x3为初始非基变量，x4、x5为初始基变量。此时最优解Z 为0。
式（2.5）、式（2.6）对应后面表2.1单纯形表中Ⅰ栏第1、2行数据：
（3）检验目标函数值是否能继续改善，能改善转（4），不能改善转（6）。
由于max Z=5x1+8x2+6x3中，各变量系数均为正，故调入任何变量都可能使目标函数值改善。
（4）确定调入变量和调出变量，进行等式变换，给出新的基本可行解，改善目标函数值。
1）调入变量。由于max Z=5x1+8x2+6x3中，x2的系数最大，故调入x2对改善目标函数值最有好处，调入x2（进基变量）。
表2.1中单纯形表中取负值最大的检验数对应的变量为入基变量。
2）调出变量。由式（2.5）知，由于x1到x5变量非负的限制，调入x2后，x2变化范围应为0～12。
由式（2.6）知，由于x1到x5变量非负的限制，调入x2后，x2变化范围应为0～10。
这样取式（2.6）则可以满足上面的范围限制，这样可判断调出变量为x5。这种判断实际上是用式（2.5）和式（2.6）相应常数项除以x2前系数后取最小值判断的。即min{12/1，20/2}=10来判断的。
表2.1单纯形表中取检验比最小的行对应的变量为出基变量。
3）等式变换。确定出基和入基变量后，就知道了新的基变量为x2和x4，下面通过变换给出其表达式。
由式（2.6）可给出x2的表达式：
[式（2.7）对应表2.1中Ⅱ栏第2行数据：10 1/2 1 3/2 0 1/2 ]
将式（2.7）代入式（2.5），有
(https://www.daowen.com)
[式（2.8）对应表2.1中对应表中Ⅱ中第1行数据：2 1/2 0 -1/2 1 -1/2]
4）形成新的基本可行解。由于x5为出基变量，取x5=0得到新的可行解为
此时目标函数为
（5）重复（3）、（4）。
1）判断是否最优。由目标函数max Z=80+x1-6x3可知，变量仍有正系数值，引入x1仍然可以改善目标函数值。
2）调入变量。由于目标函数max Z=80+x1-6x3只有x1是正系数，引入x1可以改善目标函数值。
3）调出变量。由式（2.7）知，由于变量非负的限制，调入x1后，x1变化范围应为0～20。
由式（2.8）知，由于变量非负的限制，调入x1后，x1变化范围应为0～4。
这样取式（2.8）则可以满足上面的范围限制，这样可判断调出变量为x4。这种判断实际上是用式（2.7）和式（2.8）相应常数项除以x1前系数后取最小值判断的。即min{10/（1/2），2/（1/2）}=4来判断的。
4）等式变换。确定新的出基和入基变量后，就知道了新的基变量为x1和x2，下面通过变换给出其表达式。
由式（2.8）可给出x1的表达式：
[式（2.9）为表2.1中对应表Ⅲ中第1行数据：4 1 0 -1 2 -1 ]
将式（2.9）代入式（2.7），有
[式（2.10）为表2.1中对应表Ⅲ中第2行数据： 8 0 1 2 -1 1]
5）形成新的基本可行解。由于x4、x5均为出基变量，式（2.9）及式（2.10）中取x4=0、x5=0，有：
新基本可行解为X=（4+x3，8-2x3，0，0，0）T
此时目标函数：
已经没有可以改善的，此时目标函数达到最优。
（6）给出最优解。注意到上面X 中的x3是0，这样有X=（4，8，0，0，0）T，此时目标函数max Z=84。
