《03.4修正单纯形法[专业技术].ppt》由会员分享，可在线阅读，更多相关《03.4修正单纯形法[专业技术].ppt（41页珍藏版）》请在三一文库上搜索。
1、第四节 修正单纯形法,1,高级教学,单纯形法的解题思路（一）,在单纯形法计算过程中，我们的目的是求出问题的最优解，判断是否得到最优解的原则是检验数的符号，当求最大值时，要求Zj-Cj0；当求最小值时，要求Zj-Cj0。如果不满足条件，可根据Zj-Cj的大小找出主元列（Zj-Cj最大者），找出主元列Pj*后，再计算Qi，而后，根据Qi大小找出主元行（Qi最小者），主元列所对应变量为调入变量，主元行所对应的变量为调出变量，调换基变量后，再重新计算检验数进行判断。,2,高级教学,单纯形法的解题思路（二）,由此可见，在用单纯形法解题时，每段真正起作用的只是某些数据，Zj-Cj、bi、Pj*，如果我们用
2、计算机解单纯形法，那些作用不大的数据就会占用大量内存，影响解题速度，费用大，所以我们有必要对单纯形法进行修正，以方便计算机的计算。,3,高级教学,修正单纯形法的思路,修正的单纯形法的基本思路是：只计算与最优解关系最为密切的几个数据，而每一段的计算都以前一段的计算为基础进行推算，这样，单纯形法也就需要记住一些推导公式。,4,高级教学,如,5,高级教学,解：,引入松弛变量及人工变量，化为标准形式,6,高级教学,写出相关的矩阵和向量,7,高级教学,用单纯形法的表格形式解题,8,高级教学,9,高级教学,用修正单纯形法解题,10,高级教学,初始数据（1）,基变量为x5，x6，x7， 基变量对应的目标函数
3、系数向量 CB=（c5 c6 c7)=(0 M M),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=(c5 c6 c
4、3)=(0 M 1),18,高级教学,迭代1（2）,基矩阵 基矩阵的逆阵,19,高级教学,迭代1（3）,可行解,20,高级教学,迭代1（4）,求检验数,21,高级教学,迭代1（5）,比较检验数大小，选取x2为调入变量，接下去寻找调出变量。,22,高级教学,迭代1（6）,应选取x6为调出变量。,23,高级教学,迭代2（1）,基变量为x5，x2，x3， 基变量对应的目标函数系数向量 CB=(c5 c2 c3)=(0 1 1),24,高级教学,迭代2（2）,基矩阵,25,高级教学,迭代2（3）,可行解,26,高级教学,迭代2（4）,求检验数,27,高级教学,迭代2（5）,比较检验数大小，选取x1对应
5、的变量为调入变量，接下去寻找调出变量。,28,高级教学,迭代2（6）,应选取x5为调出变量。,29,高级教学,迭代3（1）,基变量为x1，x2，x3， 基变量对应的目标函数系数向量 CB=(c1 c2 c3)=(-3 1 1),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，
6、P1，Pn，C 2、写出当前基变量及基变量对应的目标函数系数向量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大小，找出不满足符号条件的检验数中绝对值最大者，所对应的变量为调入变量，记为xj*. 7、计算,40,高级教学,修正单纯形法的一般步骤（6）,8、计算 找出 所对应的变量为调出变量，记为xi*.。 9、写出新的基变量及CB。 10、转到第3步。,41,高级教学,