修正单纯形法.pptx

《修正单纯形法.pptx》由会员分享，可在线阅读，更多相关《修正单纯形法.pptx（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、单纯形法的解题思路（一）在单纯形法计算过程中，我们的目的是求出问题的最优解，判断是否得到最优解的原则是检验数的符号，当求最大值时，要求Zj-Cj0；当求最小值时，要求Zj-Cj0。如果不满足条件，可根据Zj-Cj的大小找出主元列（Zj-Cj最大者），找出主元列Pj*后，再计算Qi，而后，根据Qi大小找出主元行（Qi最小者），主元列所对应变量为调入变量，主元行所对应的变量为调出变量，调换基变量后，再重新计算检验数进行判断。第1页/共41页单纯形法的解题思路（二）由此可见，在用单纯形法解题时，每段真正起作用的只是某些数据，Zj-Cj、bi、Pj*，如果我们用计算机解单纯形法，那些作用不大的数据就会

2、占用大量内存，影响解题速度，费用大，所以我们有必要对单纯形法进行修正，以方便计算机的计算。第2页/共41页修正单纯形法的思路修正的单纯形法的基本思路是：只计算与最优解关系最为密切的几个数据，而每一段的计算都以前一段的计算为基础进行推算，这样，单纯形法也就需要记住一些推导公式。第3页/共41页如第4页/共41页解：引入松弛变量及人工变量，化为标准形式 第5页/共41页写出相关的矩阵和向量第6页/共41页用单纯形法的表格形式解题第7页/共41页段段Cj0-31100MMQi注注基基bP1P2P3P4P5P6P710 x5111-21010011Mx63-412-10103/2Mx71-20（1）0

3、0011Zj-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第8页/共41页用修正单纯形法解题第9页/共41页初始数据（1）基变量为x5，x6，x7，基变量对应的目标

4、函数系数向量 CB=（c5 c6 c7)=(0 M M)第10页/共41页初始数据（2）基矩阵基矩阵的逆阵 第11页/共41页初始数据（3）初始基本可行解 第12页/共41页初始数据（4）求检验数 第13页/共41页初始数据（5）基变量的检验数均为零此时只需计算非基变量对应的检验数：第14页/共41页初始数据（6）以上检验数中，Z2-C20，Z3-C30，比较大小，则选取Z3-C3对应的变量x3为调入变量，接下去寻找调出变量。第15页/共41页初始数据（7）应选取x7为调出变量 第16页/共41页迭代1（1）基变量为x5，x6，x3，基变量对应的目标函数系数向量 CB=(c5 c6 c3)=(

5、0 M 1)第17页/共41页迭代1（2）基矩阵 基矩阵的逆阵第18页/共41页迭代1（3）可行解 第19页/共41页迭代1（4）求检验数 第20页/共41页迭代1（5）比较检验数大小，选取x2为调入变量，接下去寻找调出变量。第21页/共41页迭代1（6）应选取x6为调出变量。第22页/共41页迭代2（1）基变量为x5，x2，x3，基变量对应的目标函数系数向量 CB=(c5 c2 c3)=(0 1 1)第23页/共41页迭代2（2）基矩阵 第24页/共41页迭代2（3）可行解 第25页/共41页迭代2（4）求检验数 第26页/共41页迭代2（5）比较检验数大小，选取x1对应的变量为调入变量，接

6、下去寻找调出变量。第27页/共41页迭代2（6）应选取x5为调出变量。第28页/共41页迭代3（1）基变量为x1，x2，x3，基变量对应的目标函数系数向量 CB=(c1 c2 c3)=(-3 1 1)第29页/共41页迭代3（2）基矩阵 第30页/共41页迭代3（3）可行解第31页/共41页迭代3（4）求检验数 第32页/共41页迭代3（5）Zj-Cj均为非正，已得到最优解。x1=4,x2=1,x3=9,x4=x5=x6=x7=0 第33页/共41页迭代3（6）最优值第34页/共41页修正单纯形法的一般步骤（1）1、将问题化为标准形式，并写出系数矩阵：A，b，P1，Pn，C2、写出当前基变量及

7、基变量对应的目标函数系数向量CB。第35页/共41页修正单纯形法的一般步骤（2）3、列出基矩阵B，并求出B-1。初始B-1=B=I以后各段可用以下公式来推算或用其他方法计算。第36页/共41页修正单纯形法的一般步骤（3）4、求可行解。5、求检验数Zj-Cj。（1）计算（2）计算非基变量对应的检验数基变量的检验数一定为零，只需计算非基变量对应的检验数：第37页/共41页修正单纯形法的一般步骤（4）（3）若目标函数求最大值，要求Zj-Cj0；若目标函数求最小值，要求Zj-Cj0。若检验数满足符号条件，则得到最优解。最优解为 ，最优值为 。否则继续下一步 第38页/共41页修正单纯形法的一般步骤（5）6、比较Zj-Cj大小，找出不满足符号条件的检验数中绝对值最大者，所对应的变量为调入变量，记为xj*.7、计算 第39页/共41页修正单纯形法的一般步骤（6）8、计算 找出 所对应的变量为调出变量，记为xi*.。9、写出新的基变量及CB。10、转到第3步。第40页/共41页谢谢大家观赏！第41页/共41页