(精品)运筹学课件解的最优性检验

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,二、解的最优性检验,检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,?,1,、闭回路法,以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。,该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。,可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,m+n-1,个变量构成基变量的充要条件是它们不构成闭回路。,X,11,X,13,X,21,X,24,X,33,B,1,B,2,B,3,B,4,A,1,X,12,X,14,A,2,X,22,X,23,A,3,X,31,X,32,X,34,例设,m=3,，,n=4,，,决策变量,x,ij,表示从产地,A,i,到销地,B,j,的调运量，列表如下，给出闭回路,在表中的表示法,用折线连接起来的顶点变量。,请给出闭回路,在表中的表示法。,X,11,X,13,X,21,X,24,X,33,B,1,B,2,B,3,B,4,A,1,X,12,X,14,A,2,X,22,X,23,A,3,X,31,X,32,X,34,下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？,（a）（b）（c）（d）（e）,表中的折线构成一条封闭曲线，且所有的边都是,水平,或,垂直,的；,表中的,每一行,和,每一列由折线相连的闭回路的顶点只有两个,；,约定作为起始顶点的非基变量为偶数次顶点，其它顶点从,1,开始顺次排列，那么，该非基变量,x,ij,的检验数：,现在，在用最小元素法确定上例初始调运方案的基础上，计算非基变量,X,12,的检验数：,=,（闭回路上偶数次顶点运价之和）,-,（闭回路上奇数次顶点运价之和）,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,x11,x22,x12,x31,x24,x33,非基变量的检验数：,=c,12,-c,32,+c,34,c,14,=12-5+6-11=2,=,c,22,-c,32,+c,34,c,14,+c,13,c,23,=10-5+6-11+4-3=1,=c,11,-c,21,+c,23,-c,13,=4-2+3-4=1,B1,B2,B3,B4,产量,A1,1,2,16,A2,1,-1,10,A3,10,12,22,销量,8,14,12,14,48,检验数表,2,、位势法,（对偶变量法）,原问题,对偶问题,对偶变量向量,Y,U,i,V,j,对偶变量，也称为位势变量。,第,i,个,第,m+j,以上例初始调运方案为例，设置位势变量 和 ，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：,方程组的特点：,方程个数是,m+n-1=3+4-1=6,个，位势变量共有,m+n=3+4=7,个，通常称,u,i,为第,i,行的位势，称,v,j,为第,j,列的位势；,初始方案的每一个基变量,x,ij,对应一个方程,-,所在行和列对应的位势变量之和等于该基变量对应的运价：,u,i,+v,j,=,c,ij,；,给定任一变量一个较少的整数或零，解方程组式，即可求得位势变量的一组值。计算非基变量,x,ij,检验数的公式,ij,=,c,ij,-,（,u,i,+v,j,）,在式中，令,u,2,=0,，,则可解得,v,1,=2,，,v,3,=3,，,u,1,=1,，,u,4,=10,u,3,=-4,v,2,=9,，,计算检验数,11,=c,11,-,（,u,1,+v,1,）,=4-,（,1+2,）,=1,12,=c,12,-,（,u,1,+v,2,）,=12-,（,1+9,）,=2,22,=c,22,-,（,u,2,+v,2,）,=10-,（,0+9,）,=1,24,=c,24,-,（,u,2,+v,4,）,=9-,（,0+10,）,=-1,31,=c,31,-,（,u,3,+v,1,）,=8-,（,-4+2,）,=10,33,=c,33,-,（,u,3,+v,3,）,=11-,（,-4+3,）,=12,与前面用闭回路法求得的结果相同。,B1,B2,B3,B4,产量,u,i,A1,16,U,1,(1),A2,10,U,2,(0),A3,22,U,3,(-4),销量,8,14,12,14,48,v,j,V,1,(2),V,2,(9),V,3,(3),V,4,(10),产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,B1,B2,B3,B4,产量,A1,1,2,16,A2,1,-1,10,A3,10,12,22,销量,8,14,12,14,48,检验数表,位势法计算非基变量,x,ij,检验数的公式,ij,=,c,ij,-,（,u,i,+v,j,）,=,（闭回路上偶数次顶点运价之和）,-,（闭回路上奇数次顶点运价之和）,闭回路法计算非基变量,x,ij,检验数的公式：,比较检验数计算的两种方法,三、解的改进,当至少有,一个,非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。即检验数,ij,小于零，则应对解进行改进：,1,、首先在作业表上以,x,ij,为起始变量作出闭回路。,2,、以检验数,ij,小于零所对应的空格为第一个奇数点，沿闭回路顺或逆时针依次对顶点进行编号。,3,、在闭回路的所有偶数顶点，求出调整量,：,4,、,在闭回路的所有奇数顶点，增加调整量,，,所有偶数顶点，减去调整量,，,ij,=min,该闭回路中,偶数次,顶点调运量,x,ij,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,24,=c,24,-,（,u,2,+v,4,）,=9-,（,0+10,）,=-1,，,x,24,换入变量,对应的闭回路。,x24,+,-,+,-,计算调整量，闭回路偶数顶点，找运输量最小的顶点：,=Min,（,x,14,，,x,23,）,=Min,（,6,，,2,）,=2,。,按照下面的方法调整调运量：,闭回路上，奇数次顶点的调运量增加,，,偶数次顶点（包括起始顶点）的调运量减去,；,闭回路之外的变量调运量不变。,得到新的调运方案,：,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,+2,-2,+2,-2,计算检验数（位势法或闭回路法）,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,练习,:,分别使用闭回路法和位势法计算检验数,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,检验数为非负，得到最优解。,1,1,=0,3,1,=9,12,=2,22,=2,23,=1,33,=12,B1,B2,B3,B4,产量,u,i,A1,16,U,1,(2),A2,10,U,2,(0),A3,22,U,3,(-3),销量,8,14,12,14,48,v,j,V,1,(2),V,2,(8),V,3,(2),V,4,(9),产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,ij,=,c,ij,-,（,u,i,+v,j,）,B1,B2,B3,B4,产量,u,i,A1,16,U,1,(2),A2,10,U,2,(0),A3,22,U,3,(-3),销量,8,14,12,14,48,v,j,V,1,(2),V,2,(8),V,3,(2),V,4,(9),产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,0,9,2,2,1,12,检验数为非负，得到最优解。,ij,=,c,ij,-,（,u,i,+v,j,）,结 果,最优调运方案是：,x,21,=8,，,x,32,=14,，,x,13,=12,，,x,14,=4,，,x,24,=2,，,x,34,=8,相应的最小总运输量为：,Z,min,=82+145+124+411+29+86=244,四、几点说明,1,、如果运输问题的某一个基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取检验数中最小者对应的变量为换入变量。,2,、当迭代得到最优解，如果有某非基变量的检验数等于零，则说明问题有无穷多解。,3,、在迭代过程中，如果划去某行的同时，也划去某一列，出现退化解，退化时应保证基变量的个数为,m+n-1,，,在划去某列或行中的某个空格填入数字,0,。,小结,:,表上作业法求解运输问题的计算步骤。,作业,:,3.7,