数据简单明了、恰当地表示出来(制成单纯形表)；
（2）判别X 0是否为最优解。为此，需要给出一个基可行解是否为最优的判别准则；
（3）如果X 0不是最优解，则应另求基可行解X 1，且使得 CT X 1? CT X 0
（至少CT X 1? CT X 0）。同时，由X 0相应的单纯形表给出X 1相应的单纯形表。这里，需要给出X 1迭代X 0的换基迭代(进基、出基)原则
（4）若X 1仍非最优解，则视X 1为X 0重复步骤（3），直至线性规划问题求得最优解，或判定目标函数在D内无下界。
四、用单纯形法求解线性规划模型的具体步骤
1．第1步，找出初始基，建立初始单纯形表。如果在标准型线性规划模型中，约束条件系数矩阵中至少含有一个单位子矩阵B，不妨设B=（P1,P2,,Pm）
（单位子矩阵B称为基，其对应的变量XB称为基变量，对应的价值（费用）系数记为CB，其余变量XN为非基变量），且目标函数中不含基变量,则可简便地确定初始基可行解。
在线性规划模型中，令非基变量xj?0，求出基变量xi的值，即得初始基可行解。注意，在实际问题中，直接确定初始基B是比较困难的。
2．第2步，判断最优，检验各非基变量xj的检验数?j?CBB?1Pj?cj。 （1）若所有的?j?0，则基B为最优基，相应的基可行解即为基最优解，停止计算；
（2）若某个负检验数?j?0，它所对应的列向量的全部分量
B?1Ps?(a1s,a2s,,ams)T?0，则该线性规划问题的目标函数值无上界，即线性规划问
题具有无界解，停止计算；
（3）若某个负检验数?j?0所对应的列向量有正分量，则基B不是最优基。转第3步。
3．第3步，换基迭代。
（1）确定换入变量xs，单纯形表从左至右选择检验数为负的进基。 （2）确定换出变量xr，单纯形表中按最小比值原则从上至下选择变量出基。根据确定?的规则，对Pk列计算?=min{
bib︱aik＞0}=l，确定xl为出基变量，aikalk该规则称为最小比值原则。再返回第2步。
四、改进单纯形法求解线性规划模型的具体步骤 1.设线性规划的标准形式为
5
maxZ?CX?AX?b s.t??X?0其中，A?(aij)m?n?(P1,P2,Pn)，r(A)?m?n，b?0。
在标准形式中，设矩阵B为基，则有
maxz?CBXB?CNXN?0?XS?BXB?NXN?IXS?bs..t??XB,XN,XS?0
其中，XB，XN，XS分别为基变量、非基变量和松弛变量；CB与CN分别为基变量和非基变量的价值系数；N与I分别为非基变量系数矩阵和单位阵。
在目标函数中消除基变量，则有
maxz?CBB?1b?(CBB?1N?CN)XN?CBB?1XS?1?1?1??XB?BNXN?BXS?Bbs..t???XB，XN，XS?0
于是，可建立对应于基B的矩阵形式的单纯形表T（B）：
表3-1 矩阵形式的单纯形表T（B）
C? XB Z b B?1b CB B?1b CB XB I 0 CN XN B?1N CB B?1N? CN CS XS B?1 CB B?1 表中的CBB?1称为单纯形乘子，它是一个m维的行向量。
对于基B，可给出线性规划模型的简洁形式的单纯形表T（B）：
表3-2 矩阵简洁形式的单纯形表T（B）
XB Z 2．检验数的本质
对于标准形式的线性规划模型
b B?1b CB B?1b X B?1A CB B?1A? C maxZ?CX?AX?b s.t??X?0它的变量之间有着确定的数量关系，即由约束方程组AX?b所确定的关系，目标函数中的各个变量间当然也有相同的数量关系。如果把约束方程组确定的变量间的数量关系反映到目标函数中，则目标函数的表达式就等价地变为另一种形
6
式。比如，对于选定的可行基B，把约束方程组AX?b变形，把每一个基变量都用非基变量和常数表达出来，再把这些表达式代入目标函数，则目标函数的新的表达式中将不再含有基变量(或者说在目标函数的新的表达式中．基变量的系数全是0)，这时目标函数新的表达式中各个变量的系数就是此变量的检验数。
显然，对于可行基B，在AX?b（1）两边左乘单纯形乘子CBB?1得：
CBB?1AX?CBB?1b（2）
由（1）+（2）得：
CBB?1AX?Z?CBB?1b?CX
从而有 Z?CBB?1b?(CBB?1A?C)X.
正是这个缘故，每一个单纯形表(对应的可行基记为B)中各变量的检验数都可看成是目标函数的另一种表达式中各个变量的系数，只是新表达式比原表达式还多出一个常数项CBB?1b，它正是此表中的基可行解所对应的目标函数值。
实际上，单纯形法在迭代计算过程中，只对非基变量的检验数、向量和表中基可行解列的数据作计算，对非基变量中不属于换入变量的向量未作计算。基于这一点，改进单纯形法在计算步骤上作了改进，对单纯形法中未作计算的部分不予计算，故称为改进单纯形法。
3．改进单纯形法的计算步骤
1）在确定了下一步迭代的基变量后，求新单纯形表中基矩阵对应的初始单纯形表中矩阵B的逆矩阵B?1，得到新的基可行解XB?B?1b；
2）计算非基变量的检验数C?CBB?1A和CBB?1。若检验数大于零，可进一步判别该线性规划问题是属于无可行解、无穷多最优解还是唯一最优解，计算结束；否则找出最小负检验数对应的变量xk作为换入变量；
3）计算Pk??B?1Pk列的数据。若Pk??0，线性规划问题有无界解，计算结束；否则按最小比值原则来确定第r行基变量xr为换出变量，即
(B?1b)i(B?1b)r?1； ??min{?1|(BPk)i?0}??1i(BPk)i(BPk)r4）用非基变量xk替换基变量xr得出下一步单纯形表中的基变量； 5）重复1）至4）步，直到计算结束为止。 4．解的有关问题 1）退化现象。
如果在基可行解中，有某个基变量(XB)i＝0（i＝1，2，…，m），则称此基可行解为退化解。一般情况下，退化的基可行解（极点）是由若干个不同的基可行解（极点）在特殊情况下合并成一个基可行解（极点）而形成的。
7
退化情形会对单纯形迭代造成不良影响，可能出现以下情况：
①作进基、出基变换后，虽然改变了基，但没有改变基可行解（极点），目标函数当然也不会改进。作若干次基变换后，才脱离退化基可行解（极点），进入其他基可行解（极点）。这种情形会增加迭代次数，使单纯形法收敛的速度减慢。
②在特殊情况下，退化会出现基的循环。一旦这样，单纯形迭代将永远停留在同一极点上，无法求得最优解。换言之，按最小比值θ来确定换出基变量时，有时会出现两个以上相同的最小比值，在下一次迭代时就有一个或几个基变量等于零，从而出现退化解。这时，换出变量xl=0，迭代后目标函数值保持不变。
退化解出现原因是模型中存在多余约束，使多个基可行解对应同一顶点。当存在退化解时，就有可能出现迭代计算的循环。为避免出现计算的循环，1974年伯兰德（Bland）提出了一个简便有效的规则：(1)当存在多个?j? 0时，始终选取下标值为最小的变量作为换入变量；(2)当计算θ值出现两个以上相同的最小比值时，始终选取下标值为最小的变量作为换出变量。
2）无可行解的判别。
当线性规划问题中添加人工变量后，无论用大M法或两阶段法，单纯形表中的解含非零人工变量，实质上是非可行解。当求解结果出现所有?j? 0时，如果基变量中仍含有非零的人工变量（两阶段法求解时第一阶段目标函数值不等于零），表明问题无可行解。
3）最小化目标函数。 对于最小化目标函数问题：
minZ?CX?AX?b
s.t??X?0当然，我们可以转化为求目标函数最大化的问题。事实上，若不转化为求最大化的问题也可以用单纯形法和单纯形表直接求解，只需要将最优性检验条件变为所有变量的检验数组成的向量??C?CBB?1A?0即可。相应的进基变量（换入变量）进基的条件变成?j?0，其他不变。当然用大M法求解初始基可行解时，人工变量在目标函数中的系数变为+M（罚因子）。
4）无穷多个最优解。
8
相关推荐：
loading