03.4修正单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四节,修正单纯形法,单纯形法的解题思路一,在单纯形法计算过程中，我们的目的是求出问题的最优解，推断是否得到最优解的原则是检验数的符号，当求最大值时，要求Zj-Cj0；当求最小值时，要求Zj-Cj0。假设不满足条件，可依据Zj-Cj的大小找出主元列Zj-Cj最大者，找出主元列Pj*后，再计算Qi，而后，依据Qi大小找出主元行Qi最小者，主元列所对应变量为调入变量，主元行所对应的变量为调出变量，调换基变量后，再重新计算检验数进展推断。,单纯形法的解题思路二,由此可见，在用单纯形法解题时，每段真正起作用的只是某些数据，Zj-Cj、bi、Pj*，假设我们用计算机解单纯形法，那些作用不大的数据就会占用大量内存，影响解题速度，费用大，所以我们有必要对单纯形法进展修正，以便利计算机的计算。,修正单纯形法的思路,修正的单纯形法的根本思路是：只计算与最优解关系最为亲切的几个数据，而每一段的计算都以前一段的计算为根底进展推算，这样，单纯形法也就需要记住一些推导公式。,如,解：,引入松弛变量及人工变量，化为标准形式,写出相关的矩阵和向量,用单纯形法的表格形式解题,段,Cj,0,-3,1,1,0,0,M,M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,5,11,1,-2,1,0,1,0,0,11,M,x,6,3,-4,1,2,-1,0,1,0,3/2,M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Zj-Cj,4M,-6M+3,M-1,3M-1,-M,0,0,0,2,0,x,5,10,3,-2,0,0,1,0,-1,M,x,6,1,0,（,1,）,0,-1,0,1,-2,1,1,x,3,1,-2,0,1,0,0,0,1,Zj-Cj,M+1,1,M-1,0,-M,0,0,-3M+1,3,0,x,5,12,（,3,）,0,0,-2,1,2,-5,1,x,2,1,0,1,0,-1,0,1,-2,1,x,3,1,-2,0,1,0,0,0,1,Zj-Cj,-2,1,0,0,-1,0,-M+1,-M-1,4,-3,x,1,4,1,0,0,-2/3,1/3,2/3,-5/3,1,x,2,1,0,1,0,-1,0,1,-2,1,x,3,9,0,0,1,-4/3,2/3,4/3,-7/3,Zj-Cj,-2,0,0,0,-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,应选取,x,7,为调出变量,迭代11,基变量为,x,5,，,x,6,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,5,c,6,c,3,)=(0 M 1),迭代12,基矩阵,基矩阵的逆阵,迭代13,可行解,迭代14,求检验数,迭代15,比较检验数大小，选取x2为调入变量，接下去查找调出变量。,迭代16,应选取,x,6,为调出变量。,迭代21,基变量为,x,5,，,x,2,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,5,c,2,c,3,)=(0 1 1),迭代22,基矩阵,迭代23,可行解,迭代24,求检验数,迭代25,比较检验数大小，选取x1对应的变量为调入变量，接下去查找调出变量。,迭代26,应选取,x,5,为调出变量。,迭代31,基变量为,x,1,，,x,2,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,1,c,2,c,3,)=(-3 1 1),迭代32,基矩阵,迭代33,可行解,迭代34,求检验数,迭代35,Z,j,-C,j,均为非正，,已得到最优解。,x,1,=4,x,2,=1,x,3,=9,x,4,=x,5,=x,6,=x,7,=0,迭代36,最优值,修正单纯形法的一般步骤1,1,、将问题化为标准形式，并写出系数矩阵：,A,，,b,，,P,1,，,，,Pn,，,C,2,、,写出当前基变量及基变量对应的目标函数系数向量,C,B,。,修正单纯形法的一般步骤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,、计算,找出 所对应的变量为调出变量，记为,x,i*,.,。,9,、,写出新的基变量及,C,B,。,10,、,转到第,3,步。,