修正单纯形法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,修正单纯形法,单纯形法的一般解题步骤,最优解不仅是在可行区域的边界上，而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解具有下列三个重要性质：如果存在着一个最优解，那么它必定是角点可行解。如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。只存在有限个数的角点可行解。如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是最优解。,单纯形法的一般解题步骤,单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤,3,进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。,单纯形法的一般解题步骤,改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。,高斯消去法，又称高斯消元法，实际上就是我们俗称的加减消元法。它是线性代数中的一个算法，用于决定线性方程组的解，决定矩阵的秩，以及决定可逆方矩阵的逆。当用于一个矩阵时，高斯消去产生“行消去梯形形式”。,单纯形法的解题思路（一）,在单纯形法计算过程中，我们的目的是求出问题的最优解，判断是否得到最优解的原则是检验数的符号，当求最大值时，要求,Zj-Cj,0,；,当求最小值时，要求,Zj-Cj,0,。,如果不满足条件，可根据,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）,基变量,为,x,5,，,x,6,，,x,7,，,基变量对应的目标函数系数向量,C,B,=,（,c,5,c,6,c,7,)=(0 M M),初始数据（2）,基矩阵,基矩阵的逆阵,初始数据（3）,初始基本可行解,初始数据（4）,求检验数,初始数据（5）,基变量的检验数均为零,此时只需计算非基变量对应的检验数：,初始数据（6）,以上检验数中，,Z,2,-C,2,0，Z,3,-C,3,0,，,比较大小，则选取,Z,3,-C,3,对应的变量,x,3,为调入变量，接下去寻找调出变量,。,初始数据（7）,应选取,x,7,为调出变量,迭代1（1）,基变量为,x,5,，,x,6,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,5,c,6,c,3,)=(0 M 1),迭代1（2）,基矩阵,基矩阵的逆阵,迭代1（3）,可行解,迭代1（4）,求检验数,迭代1（5）,比较检验数大小，选取,x,2,为调入变量，接下去寻找调出变量。,迭代1（6）,应选取,x,6,为调出变量。,迭代2（1）,基变量为,x,5,，,x,2,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,5,c,2,c,3,)=(0 1 1),迭代2（2）,基矩阵,迭代2（3）,可行解,迭代2（4）,求检验数,迭代2（5）,比较检验数大小，选取,x,1,对应的变量为调入变量，接下去寻找调出变量。,迭代2（6）,应选取,x,5,为调出变量。,迭代3（1）,基变量为,x,1,，,x,2,，,x,3,，,基变量对应的目标函数系数向量,C,B,=(c,1,c,2,c,3,)=(-3 1 1),迭代3（2）,基矩阵,迭代3（3）,可行解,迭代3（4）,求检验数,迭代3（5）,Z,j,-C,j,均为非正，,已得到最优解。,x,1,=4,x,2,=1,x,3,=9,x,4,=x,5,=x,6,=x,7,=0,迭代3（6）,最优值,修正单纯形法的一般步骤（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-Cj,0,；,若目标函数求最小值，要求,Zj-Cj,0。,若检验数满足符号条件，则得到最优解。最优解为 ，最优值为 。,否则继续下一步,修正单纯形法的一般步骤（5）,6、比较,Zj-Cj,大小，找出不满足符号条件的检验数中绝对值最大者，所对应的变量为调入变量，记为,x,j*,.,7,、,计算,修正单纯形法的一般步骤（6）,8,、计算,找出 所对应的变量为调出变量，记为,x,i*,.,。,9,、,写出新的基变量及,C,B,。,10,、,转到第,3,步。,