运筹学4单纯形法迭代原理课件

1、运筹学4单纯形法迭代原理,单纯形法迭代原理,运筹学4单纯形法迭代原理,三. 单纯形法的基本思想1、顶点的逐步转移,即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。,运筹学4单纯形法迭代原理,根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依

2、据？,运筹学4单纯形法迭代原理,转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标函数达到最优值 2需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优 判断标准是什么？,运筹学4单纯形法迭代原理,解LP问题单纯形法的基本思路：,初始可行基：设法在约束矩阵 中 构造出一个m阶单位阵,检验数,进基变量：检验数 离基变量：最小比值准则,运筹学4单纯形法迭代原理,1.确定初始基本可行解,LP:,？,希望在化LP的标准形式时，A中都含有一个m阶单位阵。,运筹学4单纯形法迭代原理,观察法 观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型

3、的约束 将新增的松弛变量(+)作为初始基变量，对应的系数列向量构成单位阵； LP限制条件有“”类型的约束 左端新增剩余变量(-)后，再加上一个非负的新变量人工变量。 LP限制条件有“=”类型的约束 直接在左端加上人工变量。,运筹学4单纯形法迭代原理,在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目标函数上做些“修正”大M法或两阶段法,非基变量取0，算出基变量，搭配在一起构成 初始基本可行解：,运筹学4单纯形法迭代原理,2.建立判别准则,判断：初始基本可行解或经过若干次迭代后得到的新基本可行解当前解是否为最优解？,一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式 为：,

4、典式,若,运筹学4单纯形法迭代原理,用非基变量表示目标函数的表达式：,典式,检验数,运筹学4单纯形法迭代原理,其中,（1）最优性判别定理,（2）有无穷多个“最优解”的判别定理,运筹学4单纯形法迭代原理,3、进行基变换,（1）进基变量的确定原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善。,（2）离基变量的确定在保持解的可行性的前提下，使目标函数较快增大。,运筹学4单纯形法迭代原理,当 时，为使 ，需要,从而， 最大可取到,最小比值原则,运筹学4单纯形法迭代原理,离基变量：,是可行解！,是否还是基本解？,是,运筹学4单纯形法迭代原理,从而，目标函数得到了改善。,运筹学4

5、单纯形法迭代原理,第四节 单纯形表,运筹学4单纯形法迭代原理,（1）建立初始单纯形表，假定B=I，b0 设maxZ=c1x1+c2x2+cnxn,将目标函数改写为：-Z+c1x1+c2x2+cnxn=0,运筹学4单纯形法迭代原理,检验数行,最后一行是检验数行，标出了对应决策变量xj的检验数,第一行是价值系数行，标出了决策变量xj的价值系数cj,第二行是标示行，标出了表中主体各行的含义。,第一列标出了基变量的价值系数。,第二列标出了当前基变量的名称。,第三列是右端项，前m个元素是当前基本可行解的基变量的取值,最 小 比 值 准 则,运筹学4单纯形法迭代原理,将初始数据填入上表，可得到初始单纯形表

6、。,观察检验数行，若所有的 ，则停止计算。否则进行下一步。,1.检验当前基本可行解是否为最优解？,最优性判别定理,运筹学4单纯形法迭代原理,2.检验是否为无界解？,3.选择进基变量,从而xm+t是进基变量， pm+t为进基向量，并称表中pm+t所在的列为主列。,4.选择离基变量,最小比值准则,从而xl是离基变量， 并称表中离基变量所在的行为主行。,5. 基变换,主行和主列的交叉元素称为主元素al,m+t,运筹学4单纯形法迭代原理,-Z0,-Z,XB,cj,x1,x2,xm,xm+1,xn,c1,c2,cm,cm+1,cn,CB,n,m,mn,m,m,n,m,n,m,a,a,a,a,a,a,s,

7、s,.,0,.,0,0,.,1,.,0,0,.,.,.,.,.,.,.,.,0,.,1,0,.,0,.,0,1,1,1,2,1,2,1,1,1,+,+,+,+,m,m,m,b,x,c,b,x,c,b,x,c,:,:,:,2,2,2,1,1,1,cl xl bl 0 0 . . . 0 al,m+1 . . . aln, ,主行同除以al,m+t,即将主元素化为1,将新的主行的(-ai,m+t)倍分别加到第i行，即将主列的其他元素化为0.,将新的主行的 倍分别加到最后一行，即将xm+t的检验数化为0.,运筹学4单纯形法迭代原理,6. 回到1,对新解作最优性检验。,运筹学4单纯形法迭代原理,例：用单纯形法求解线性规划问题,解：,标准化：,运筹学4单纯形法迭代原理,建立初始单纯行表, ,基变换, ,运筹学4单纯形法迭代原理,基变换, ,运筹学4单纯形法迭代原理,基变换,运筹学4单纯形法迭代原理,运筹学4单纯形法迭代原理,说 明 用单纯