运筹学课件 解的最优性检验

1、 二、解的最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。?11、闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。m+n-1个变量构成基变量的充要条件是它们不构成闭回路。2 X11 X13 X21 X24 X33 B1 B

2、2 B3 B4 A1 X12 X14 A2 X22 X23 A3X31 X32 X34例设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。 3 请给出闭回路 在表中的表示法。 X11 X13 X21 X24 X33 B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3X31 X32 X344下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？（a） （b） （c） （d） （e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；表中的每一行和每一列由折线相连的闭回路的顶点只有两个；5

3、约定作为起始顶点的非基变量为偶数次顶点，其它顶点从1开始顺次排列，那么，该非基变量xij的检验数：现在，在用最小元素法确定上例初始调运方案的基础上，计算非基变量X12的检验数 ：=（闭回路上偶数次顶点运价之和）-（闭回路上奇数次顶点运价之和） 6B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119682101486x11x22x12x31x24x337非基变量的检验数： =c12-c32 +c34 c14=12-5+6-11=2 =c22-c32 +c34 c14 +c13 c23=10-5+6-11+4-3=1 =c11-c21 +c

4、23 -c13=4-2+3-4=18B1B2B3B4 产量A11216A21-110A3101222 销量814121448检验数表92、位势法 （对偶变量法）原问题对偶问题10对偶变量向量YUi,Vj对偶变量，也称为位势变量。第i个第m+j11 以上例初始调运方案为例，设置位势变量 和 ，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：12方程组的特点：方程个数是m+n-1=3+4-1=6个，位势变量共有m+n=3+4=7个，通常称ui为第i行的位势，称vj为第j列的位势；初始方案的每一个基变量xij对应一个方程-所在行和列对应的位势变量之和等于该基变量对应的运价

5、：ui+vj=cij； 13 给定任一变量一个较少的整数或零，解方程组式，即可求得位势变量的一组值。计算非基变量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）=1033=c33-（u3+v3）=11-（-4+3）=12与前面用闭回路法求得的

6、结果相同。 14B1B2B3B4 产量uiA1 16U1(1)A210U2(0)A322U3(-4) 销量814121448vjV1(2)V2(9)V3(3)V4(10)产地销地41210285113411968210148615B1B2B3B4 产量A11216A21-110A3101222 销量814121448检验数表16位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）=（闭回路上偶数次顶点运价之和）-（闭回路上奇数次顶点运价之和） 闭回路法计算非基变量xij检验数的公式：比较检验数计算的两种方法17 三、解的改进 当至少有一个非基变量的检验数是负值时，说明作业表上当前

7、的调运方案不是最优的，应进行调整。 即检验数ij小于零，则应对解进行改进：1、首先在作业表上以xij为起始变量作出闭回路。2、以检验数ij小于零所对应的空格为第一个奇数点，沿闭回路顺或逆时针依次对顶点进行编号。3、在闭回路的所有偶数顶点，求出调整量：4、在闭回路的所有奇数顶点，增加调整量，所有偶数顶点，减去调整量，ij=min该闭回路中偶数次顶点调运量xij18B1B2B3B4 产量A1 16A210A322 销量814121448产地销地41210285113411968210148624=c24-（u2+v4）=9-（0+10）=-1，x24 换入变量,对应的闭回路。x24+-+-19 计

8、算调整量，闭回路偶数顶点，找运输量最小的顶点：=Min（x14，x23）= Min（6，2）= 2。按照下面的方法调整调运量： 闭回路上，奇数次顶点的调运量增加，偶数次顶点（包括起始顶点）的调运量减去；闭回路之外的变量调运量不变。得到新的调运方案： 20B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119682101486+2-2+2-2计算检验数（位势法或闭回路法）21B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119681214842练习:分别使用闭回路法和位势法计算检验数

9、22B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119681214842检验数为非负，得到最优解。11 =031 =912 =222 =223 =133 =1223B1B2B3B4 产量uiA1 16U1(2)A210U2(0)A322U3(-3) 销量814121448vjV1(2)V2(8)V3(2)V4(9)产地销地412102851134119681214842ij=cij-（ui+vj）24B1B2B3B4 产量uiA1 16U1(2)A210U2(0)A322U3(-3) 销量814121448vjV1(2)V2(8)V3(2)V4(9)产地销地4121028511341196812148420922112检验数为非负，得到最优解。ij=cij-（ui+vj）25 结 果 最优调运方案是： x21=8，x32=14，x13=12，x14=4，x24=2， x34=8 相应的最小总运输量为： Zmin=82+145+124+411+29 +86=244 26四、几点说明1、如果运输问题的某一个基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取检