[所有分类]第5章单纯形法.ppt

第五章 单 纯 形 法 §5.1　单纯形法的基本概念和原理 §5.2　单纯形表格法 §5.3　求目标函数值最小的单纯形表格法 §5.4　几种特殊情况  即本例题中目标函数:Z=50x1+100x2 +0s1 +0s2 +0s3 实际上目标函数中当前基变量X3、X4、X5的系数为0，即所有基变量的检验数为零。由于初始可行解中x1，x2为非基变量，目标函数基变量的系数全部为0，因此就不需要进行用非基变量代换了。 直接把当前目标函数中决策变量的系数视作检验数即可 σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。 §5.2　单纯形表格解法 在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。 求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000. 因此，为了尽量要求人工变量为零，规定人工变量在目标函数中的系数为：M，这里M为任意大的数。这样只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无可行解。 §3　 此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。 第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。 §5.4　几种特殊情况 得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。 但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的 某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远 达不到最优解。 下面一个是由E.Beale给出的循环的例子。 例5 目标函数 ：min f =－（3/4）x4+20x5－（1／2）x6+6x7. 约束条件：x1+（1／4）x4－8x5－x6+9x7=0， x2+（1／2）x4－12x5－（1／2）x6+3x7=0， x3+x6=1， x1，x2，x3，x4，x5，x6，x7≥0. 50 100 0 0 0 50/1 150/2 — 比值 bi/aij 25000 50 150 250 b 0 0 100 cB 0 100 0 0 100 50 0 0 0 -100 1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1 x1 x2 s3 s4 s5 zj s1 s2 x2 基变量 1 迭代次数 进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。得到的第1次迭代的单纯形表如下： 表解过程演示续 X1 50 0 1 0 -1 50 0 0 -2 1 1 50 0 1 0 0 1 250 50 100 50 0 50 27500 0 0 -50 0 -50 50 100 0 0