03.4修正单纯形法.ppt

第四节第四节 修正单纯形法修正单纯形法 单纯形法的解题思路（一）在单纯形法计算过程中，我们的目的是求出问题的最优解，判断是否得到最优解的原则是检验数的符号，当求最大值时，要求Zj-Cj0；当求最小值时，要求Zj-Cj0。如果不满足条件，可根据Zj-Cj的大小找出主元列（Zj-Cj最大者），找出主元列Pj*后，再计算Qi，而后，根据Qi大小找出主元行（Qi最小者），主元列所对应变量为调入变量，主元行所对应的变量为调出变量，调换基变量后，再重新计算检验数进行判断。单纯形法的解题思路（二）由此可见，在用单纯形法解题时，每段真正起作用的只是某些数据，Zj-Cj、bi、Pj*，如果我们用计算机解单纯形法，那些作用不大的数据就会占用大量内存，影响解题速度，费用大，所以我们有必要对单纯形法进行修正，以方便计算机的计算。修正单纯形法的思路修正的单纯形法的基本思路是：只计算与最优解关系最为密切的几个数据，而每一段的计算都以前一段的计算为基础进行推算，这样，单纯形法也就需要记住一些推导公式。如解：引入松弛变量及人工变量，化为标准形式 写出相关的矩阵和向量用单纯形法的表格形式解题段段Cj0-31100MMQi注注基基bP1P2P3P4P5P6P710 x5111-21010011Mx63-412-10103/2Mx71-20（1）00011Zj-Cj4M-6M+3M-13M-1-M00020 x5103-20010-1Mx610（1）0-101-21 1x31-2010001Zj-CjM+11M-10-M00-3M+130 x512（3）00-212-5 1x21010-101-21x31-2010001Zj-Cj-2100-10-M+1-M-14-3x14100-2/31/32/3-5/31x21010-101-21x39001-4/32/34/3-7/3Zj-Cj-2000-1/3-1/3-M+1/3-M+2/3用修正单纯形法解题初始数据（1）基变量基变量为x5，x6，x7，基变量对应的目标函数系数向量 CB=（c5 c6 c7)=(0 M M)初始数据（2）基矩阵基矩阵基矩阵的逆阵基矩阵的逆阵 初始数据（3）初始基本可行解 初始数据（4）求检验数 初始数据（5）基变量的检验数均为零此时只需计算非基变量对应的检验数：初始数据（6）以上检验数中，Z2-C20，Z3-C30，比较大小，则选取Z3-C3对应的变量x3为调入变量，接下去寻找调出变量。初始数据（7）应选取x7为调出变量 迭代1（1）基变量为x5，x6，x3，基变量对应的目标函数系数向量 CB=(c5 c6 c3)=(0 M 1)迭代1（2）基矩阵 基矩阵的逆阵迭代1（3）可行解 迭代1（4）求检验数 迭代1（5）比较检验数大小，选取x2为调入变量，接下去寻找调出变量。迭代1（6）应选取x6为调出变量。迭代2（1）基变量为x5，x2，x3，基变量对应的目标函数系数向量 CB=(c5 c2 c3)=(0 1 1)迭代2（2）基矩阵 迭代2（3）可行解 迭代2（4）求检验数 迭代2（5）比较检验数大小，选取x1对应的变量为调入变量，接下去寻找调出变量。迭代2（6）应选取x5为调出变量。迭代3（1）基变量为x1，x2，x3，基变量对应的目标函数系数向量 CB=(c1 c2 c3)=(-3 1 1)迭代3（2）基矩阵 迭代3（3）可行解迭代3（4）求检验数 迭代3（5）Zj-Cj均为非正，已得到最优解。x1=4,x2=1,x3=9,x4=x5=x6=x7=0 迭代3（6）最优值修正单纯形法的一般步骤（1）1、将问题化为标准形式，并写出系数矩阵：A，b，P1，Pn，C2、写出当前基变量及基变量对应的目标函数系数向量CB。修正单纯形法的一般步骤（2）3、列出基矩阵B，并求出B-1。初始B-1=B=I以后各段可用以下公式来推算或用其他方法计算。修正单纯形法的一般步骤（3）4、求可行解。5、求检验数Zj-Cj。（1）计算（2）计算非基变量对应的检验数基变量的检验数一定为零，只需计算非基变量对应的检验数：修正单纯形法的一般步骤（4）（3）若目标函数求最大值，要求Zj-Cj0；若目标函数求最小值，要求Zj-Cj0。若检验数满足符号条件，则得到最优解。最优解为 ，最优值为 。否则继续下一步 修正单纯形法的一般步骤（5）6、比较Zj-Cj大小，找出不满足符号条件的检验数中绝对值最大者，所对应的变量为调入变量，记为xj*.7、计算 修正单纯形法的一般步骤（6）8、计算 找出 所对应的变量为调出变量，记为xi*.。9、写出新的基变量及CB。10、转到第3步。