增大的可能，因此，要使目标值继续增大，就需要将非基变量和基变量进行对换。
为使目标值尽快达到最优，一般选择正系数大的非基变量作为换入变量，x2为换入变量。由于基变量个数是固定的，所以，在确定了换入变量同时，还需要确定一个基变量作为换出变量，要从基变量
x3,x4,x5中选择一个， x2的值将从零增加到一个正值， 但x2的增加量
必须受约束条件的限制，必须要保证原基变量满足非负条件，即(x1仍是非基变量，为0)
x3?8?2x2?0x4?16?0x5?12?4x2?0?812? 所以，x2只能取：x2?min??,,???3 4??2当x2的值由零增大到3时，基变量x5取值最先变为零，而x3,x4仍保持非负，这就确定用x2换x5，x5作为换出变量，换出为非基变量，所以，新的基变量为x3,x4,x2，非基变量为x1,x5。
再求以x3,x4,x2为基变量的基可行解，同样，将基变量用非基变量表示，
1?x?2?x1?x5?32? 令非基变量x1?x5?0，可得到一个基可行?x4?16?4x1?1?x2?3?x5?4解：X
?1???0,3,2,16,0?，将上式代入目标函数，得，
T21
z?9?2x1?34x5，相应的目标值为Z＝9。
对z?9?2x1?34x5进行分析，非基变量x1的系数还是正的，说
明目标函数值还能增大，由于只有一个非基变量x1系数为正，因此，确定x1为换入变量，换出变量按照下列方法确定：(令x5＝0)
?x3?2?x1?0?216???x4?16?4x1?0 所以，x1?min??,,???2
?14??x?3?0?2对应的x3为换出变量，新的基变量为新的基变量为x1,x4,x2，非基变量为x3,x5。
再求以x1,x4,x2为基变量的基可行解，同样，将基变量用非基变量表示，
?x?2??1???x2?3???x4?8???x3?14x512x5令非基变量x3?x5?0，可得到一个基可行
4x3?2x5解：X?2???2,3,0,8,0?，将上式代入目标函数，得，
Tz?13?x3?
34x5，相应的目标值为Z＝13。
22
还需要继续迭代，最后，得到基可行解为：X?3?T???4,2,0,0,4，
目标函数式子：z?14?1.5x3?0.125x4，目标值为Z＝14。
再分析上面式子，非基变量的系数全为负数，目标函数值不可能再增大。X?3???4,2,0,0,4?为最优解，目标最优值为14。也就是工厂安
T排产品Ⅰ生产4件，产品Ⅱ生产2件，最大可获得利润14元。
1. 初始基可行解的确定
单纯形法是从初始基可行解开始迭代的，要确定初始基可行解，首先需要找出一个初始可行基。
设有以下线性规划问题(化为标准型后)，
maxz?c1x1?c2x2???cnxn?x1?a1,m?1xm?1?a1,m?2xm?2???a1nxn?b1??x2?a2,m?1xm?1?a2,m?2xm?2???a2nxn?b2????????xm?am,m?1xm?1?am,m?2xm?2???amnxn?bm??x1,x2,?,xn?0?
在这个线性规划的系数矩阵(系数列向量)中，可以看出，它有m个线性独立的单位列向量，构成一个单位矩阵，那么，这个单位矩阵就可作为一个初始可行基。
对于一般的线性规划问题化为标准型后，能否找到一个单位阵作为初始可行基，有以下几种情况：
〔1〕 如果线性规划所有的约束条件是“?”形式的不等式，当在每个不等式左边加上一个非负的松弛变量化为标准型后，由这些松弛变量系数列向量构成的矩阵就是一个单位阵，可作为初始可行基。
max?c1x1?c2x2???cnxn?a11x1?a12x2???a1nxn?b1?ax?a22x2???a2nxn?b2?211????????ax?ax???ax?bm22mnnm?m11??x1,x2,?,xn?0
23
max?c1x1?c2x2???cnxn?a11x1?a12x2???a1nxn?xn?1?b1?a21x1?a22x2???a2nxn?xn?2?b2?标准型后: ????????ax?ax???ax?xn?m?bmm11m22mnn???x1,x2,?,xn?m?0
〔2〕 如果线性规划的约束条件是“?”和“＝”形式，在化为标准
型后，一般不存在单位阵，需要添加人工变量，构造一个单位阵作为初始可行基，这部分在后面再讲。
需要注意的是，在线性规划的系数矩阵中，不能任意选择一个基作为初始可行基，因为任选一个基求出的基变量值有可能是负数。所以，一定要以单位阵作为初始可行基。
有了初始可行基后，就可以求出初始基可行解。 将上式移项后(用非基变量表示基变量),得，
x1?b1?a1,m?1xm?1?a1,m?2xm?2???a1nxnx2?b2?a2,m?1xm?1?a2,m?2xm?2???a2nxn?????xm?bm?am,m?1xm?1?am,m?2xm?2???amnxn
令xm?1?xm?2???xn?0，得初始基可行解，
??X??b1,b2,?,bm,0,?,0? ???????n?mT
2. 最优性检验与解的判别
在每一步迭代后,都应检验一下基可行解是否为最优解,从而决定迭代过程是否停止还是继续进行，这就是所谓最优性检验。
在每一步迭代后,迭代结果可能有几种情况，是唯一最优解，无穷多最优解，还是无界解或无可行解，需要建立相应的解的判别准则。 〔1〕最优性检验数
在确定了初始可行基后，基变量用非基变量表示的一般形式为，
24
相关推荐：
loading