03.4修正单纯形法（课堂PPT）

第四节修正单纯形法,1,单纯形法的解题思路（一）,在单纯形法计算过程中，我们的目的是求出问题的最优解，判断是否得到最优解的原则是检验数的符号，当求最大值时，要求Zj-Cj0；当求最小值时，要求Zj-Cj0。如果不满足条件，可根据Zj-Cj的大小找出主元列（Zj-Cj最大者），找出主元列Pj*后，再计算Qi，而后，根据Qi大小找出主元行（Qi最小者），主元列所对应变量为调入变量，主元行所对应的变量为调出变量，调换基变量后，再重新计算检验数进行判断。,2,单纯形法的解题思路（二）,由此可见，在用单纯形法解题时，每段真正起作用的只是某些数据，Zj-Cj、bi、Pj*，如果我们用计算机解单纯形法，那些作用不大的数据就会占用大量内存，影响解题速度，费用大，所以我们有必要对单纯形法进行修正，以方便计算机的计算。,3,修正单纯形法的思路,修正的单纯形法的基本思路是：只计算与最优解关系最为密切的几个数据，而每一段的计算都以前一段的计算为基础进行推算，这样，单纯形法也就需要记住一些推导公式。,4,如,5,解：,引入松弛变量及人工变量，化为标准形式,6,写出相关的矩阵和向量,7,用单纯形法的表格形式解题,8,9,用修正单纯形法解题,10,初始数据（1）,基变量为x5，x6，x7，基变量对应的目标函数系数向量CB=（c5c6c7)=(0MM),11,初始数据（2）,基矩阵基矩阵的逆阵,12,初始数据（3）,初始基本可行解,13,初始数据（4）,求检验数,14,初始数据（5）,基变量的检验数均为零此时只需计算非基变量对应的检验数：,15,初始数据（6）,以上检验数中，Z2-C20，Z3-C30，比较大小，则选取Z3-C3对应的变量x3为调入变量，接下去寻找调出变量。,16,初始数据（7）,应选取x7为调出变量,17,迭代1（1）,基变量为x5，x6，x3，基变量对应的目标函数系数向量CB=(c5c6c3)=(0M1),18,迭代1（2）,基矩阵基矩阵的逆阵,19,迭代1（3）,可行解,20,迭代1（4）,求检验数,21,迭代1（5）,比较检验数大小，选取x2为调入变量，接下去寻找调出变量。,22,迭代1（6）,应选取x6为调出变量。,23,迭代2（1）,基变量为x5，x2，x3，基变量对应的目标函数系数向量CB=(c5c2c3)=(011),24,迭代2（2）,基矩阵,25,迭代2（3）,可行解,26,迭代2（4）,求检验数,27,迭代2（5）,比较检验数大小，选取x1对应的变量为调入变量，接下去寻找调出变量。,28,迭代2（6）,应选取x5为调出变量。,29,迭代3（1）,基变量为x1，x2，x3，基变量对应的目标函数系数向量CB=(c1c2c3)=(-311),30,迭代3（2）,基矩阵,31,迭代3（3）,可行解,32,迭代3（4）,求检验数,33,迭代3（5）,Zj-Cj均为非正，已得到最优解。x1=4,x2=1,x3=9,x4=x5=x6=x7=0,34,迭代3（6）,最优值,35,修正单纯形法的一般步骤（1）,1、将问题化为标准形式，并写出系数矩阵：A，b，P1，Pn，C2、写出当前基变量及基变量对应的目标函数系数向量CB。,36,修正单纯形法的一般步骤（2）,3、列出基矩阵B，并求出B-1。初始B-1=B=I以后各段可用以下公式来推算或用其他方法计算。,37,修正单纯形法的一般步骤（3）,4、求可行解。5、求检验数Zj-Cj。（1）计算（2）计算非基变量对应的检验数基变量的检验数一定为零，只需计算非基变量对应的检验数：,38,修正单纯形法的一般步骤（4）,（3）若目标函数求最大值，要求Zj-Cj0；若目标函数求最小值，要求Zj-Cj0。若检验数满足符号条件，则得到最优解。最优解为，最优值为。否则继续下一步,39,修正单纯形法的一般步骤（5）,6、比较Zj-Cj大小，找出不满足符号条件的检验数中绝对值最大者，所对应的变量