《运筹学课件解的最优性检验.ppt》由会员分享，可在线阅读，更多相关《运筹学课件解的最优性检验.ppt（28页珍藏版）》请在三一办公上搜索。
1、二、解的最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,?,1、闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,m+n-1个变量构成基变量的充要条件是它们不构成闭回路。,例设m=3，n=4，决策变量xij表示从产地Ai到
2、销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,请给出闭回路 在表中的表示法。,下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？,表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；表中的每一行和每一列由折线相连的闭回路的顶点只有两个；,约定作为起始顶点的非基变量为偶数次顶点，其它顶点从1开始顺次排列，那么，该非基变量xij的检验数：,现在，在用最小元素法确定上例初始调运方案的基础上，计算非基变量X12的检验数：,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,x11,x22,x12,x31,x24
3、,x33,非基变量的检验数：,=c12-c32+c34 c14=12-5+6-11=2,=c22-c32+c34 c14+c13 c23=10-5+6-11+4-3=1,=c11-c21+c23-c13=4-2+3-4=1,检验数表,2、位势法（对偶变量法）,原问题,对偶问题,对偶变量向量Y,Ui,Vj对偶变量，也称为位势变量。,第i个,第m+j,以上例初始调运方案为例，设置位势变量 和，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：,方程组的特点：方程个数是m+n-1=3+4-1=6个，位势变量共有m+n=3+4=7个，通常称ui为第i行的位势，称vj为第j列的
4、位势；初始方案的每一个基变量xij对应一个方程-所在行和列对应的位势变量之和等于该基变量对应的运价：ui+vj=cij；,给定任一变量一个较少的整数或零，解方程组式，即可求得位势变量的一组值。计算非基变量xij检验数的公式 ij=cij-（ui+vj）,在式中，令u2=0，则可解得v1=2，v3=3，u1=1，u4=10,u3=-4,v2=9，计算检验数11=c11-（u1+v1）=4-（1+2）=112=c12-（u1+v2）=12-（1+9）=222=c22-（u2+v2）=10-（0+9）=124=c24-（u2+v4）=9-（0+10）=-131=c31-（u3+v1）=8-（-4+2
5、）=1033=c33-（u3+v3）=11-（-4+3）=12,与前面用闭回路法求得的结果相同。,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,检验数表,位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）,比较检验数计算的两种方法,三、解的改进 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。即检验数ij小于零，则应对解进行改进：1、首先在作业表上以xij为起始变量作出闭回路。2、以检验数ij小于零所对应的空格为第一个奇数点，沿闭回路顺或逆时针依次对顶点进行编号。3、在闭回路的所有偶数顶点
6、，求出调整量：4、在闭回路的所有奇数顶点，增加调整量，所有偶数顶点，减去调整量，,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,2,10,14,8,6,24=c24-（u2+v4）=9-（0+10）=-1，x24 换入变量,对应的闭回路。,x24,+,-,+,-,计算调整量，闭回路偶数顶点，找运输量最小的顶点：=Min（x14，x23）=Min（6，2）=2。按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量增加，偶数次顶点（包括起始顶点）的调运量减去；闭回路之外的变量调运量不变。,得到新的调运方案：,产地,销地,4,12,10,2,8,5,11,3,4,11,9
7、,6,8,2,10,14,8,6,+2,-2,+2,-2,计算检验数（位势法或闭回路法）,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,练习:分别使用闭回路法和位势法计算检验数,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,检验数为非负，得到最优解。,11=0,31=9,12=2,22=2,23=1,33=12,产地,销地,4,12,10,2,8,5,11,3,4,11,9,6,8,12,14,8,4,2,ij=cij-（ui+vj）,产地,销地,4,12,10,2,8,5,11,3,4,11,
8、9,6,8,12,14,8,4,2,0,9,2,2,1,12,检验数为非负，得到最优解。,ij=cij-（ui+vj）,结 果 最优调运方案是：x21=8，x32=14，x13=12，x14=4，x24=2，x34=8 相应的最小总运输量为：Zmin=82+145+124+411+29+86=244,四、几点说明1、如果运输问题的某一个基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取检验数中最小者对应的变量为换入变量。2、当迭代得到最优解，如果有某非基变量的检验数等于零，则说明问题有无穷多解。3、在迭代过程中，如果划去某行的同时，也划去某一列，出现退化解，退化时应保证基变量的个数为m+n-1，在划去某列或行中的某个空格填入数字0。,小结:表上作业法求解运输问题的计算步骤。作业:3.7,
