《运筹学课件解的最优性检验》由会员分享，可在线阅读，更多相关《运筹学课件解的最优性检验（28页珍藏版）》请在金锄头文库上搜索。
1、运筹学教程 二、解的最优性检验二、解的最优性检验 检查当前调运方案是不是最优方案的过程检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。方案就是最优调运方案，否则就应进行调整。?1运筹学教程1 1、闭回路法、闭回路法、闭回路法、闭回路法 以以以以确确确确定定定定了了了了初初初初始始始始调调调调运运运运方方方方案案案案的的的的作作作作
2、业业业业表表表表为为为为基基基基础础础础，以以以以一一一一个个个个非非非非基变量作为起始顶点，寻求闭回路。基变量作为起始顶点，寻求闭回路。基变量作为起始顶点，寻求闭回路。基变量作为起始顶点，寻求闭回路。 该该该该闭闭闭闭回回回回路路路路的的的的特特特特点点点点是是是是：除除除除了了了了起起起起始始始始顶顶顶顶点点点点是是是是非非非非基基基基变变变变量量量量外外外外，其他顶点均为基变量（对应着填上数值的格）。其他顶点均为基变量（对应着填上数值的格）。其他顶点均为基变量（对应着填上数值的格）。其他顶点均为基变量（对应着填上数值的格）。可可可可以以以以证证证证明明明明，如如如如果果果果对对对对闭闭闭
3、闭回回回回路路路路的的的的方方方方向向向向不不不不加加加加区区区区别别别别，对对对对于于于于每每每每一一一一个非基变量而言，以其为起点的闭回路存在且唯一。个非基变量而言，以其为起点的闭回路存在且唯一。个非基变量而言，以其为起点的闭回路存在且唯一。个非基变量而言，以其为起点的闭回路存在且唯一。m+n-1个变量构成基变量的充要条件是它个变量构成基变量的充要条件是它们不构成闭回路。们不构成闭回路。2运筹学教程 X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X23 A3X31X32X34例设例设例设例设m=3m=3，n=4n=4，决策变量，决策变量，决策变量，决策
4、变量x xij ij表示从产地表示从产地表示从产地表示从产地A Ai i到销地到销地到销地到销地B Bj j的的的的调运量，列表如下，给出闭回路调运量，列表如下，给出闭回路调运量，列表如下，给出闭回路调运量，列表如下，给出闭回路 在表中的表示法在表中的表示法在表中的表示法在表中的表示法用折线用折线用折线用折线连接起来的顶点变量。连接起来的顶点变量。连接起来的顶点变量。连接起来的顶点变量。 3运筹学教程 请给出闭回路请给出闭回路 在表中的表示法。在表中的表示法。 X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X23 A3X31X32X344运筹学教程下面的折
5、线构成的封闭曲线连接的顶点变量下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？哪些不可能是闭回路？（a） （b） （c） （d） （e）表表中中的的折折线线构构成成一一条条封封闭闭曲曲线线，且且所所有有的的边都是边都是水平水平或或垂直垂直的；的；表表中中的的每每一一行行和和每每一一列列由由折折线线相相连连的的闭闭回回路的顶点只有两个路的顶点只有两个；5运筹学教程约约定定作作为为起起始始顶顶点点的的非非基基变变量量为为偶偶数数次次顶顶点点，其其它它顶顶点点从从1开开始始顺顺次次排排列列，那那么么，该该非非基基变变量量xij的检验数：的检验数：现在，在用最小元素法确定上例初始调运方现在，
6、在用最小元素法确定上例初始调运方案的基础上，计算非基变量案的基础上，计算非基变量X12的检验数的检验数 ：=（闭回路上偶数次顶点运价之和）（闭回路上偶数次顶点运价之和）-（闭（闭回路上奇数次顶点运价之和）回路上奇数次顶点运价之和） 6运筹学教程B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119682101486x11x22x12x31x24x337运筹学教程非基变量的检验数：非基变量的检验数： =c12-c32 +c34 c14=12-5+6-11=2 =c c2222-c-c32 32 +c+c34 34 cc14 14 +c+c1
7、3 13 cc2323=10-5+6-11+4-=10-5+6-11+4-3=13=1 =c11-c21 +c23 -c13=4-2+3-4=18运筹学教程B1B2B3B4 产量A11216A21-110A3101222 销量814121448检验数表检验数表9运筹学教程2、位势法、位势法（对偶变量法）（对偶变量法）原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题10运筹学教程对偶变量向量对偶变量向量YUi,Vj对偶变量，也称为位势变量。对偶变量，也称为位势变量。第i个第m+j11运筹学教程 以上例初始调运方案为例，设置位势变量以上例初始调运方案为例，设置位势变量以上例初始调运方案为例
8、，设置位势变量以上例初始调运方案为例，设置位势变量 和和和和 ，在初始调运方案表的基础上增加一行和，在初始调运方案表的基础上增加一行和，在初始调运方案表的基础上增加一行和，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：一列（见下页表格）。然后构造下面的方程组：一列（见下页表格）。然后构造下面的方程组：一列（见下页表格）。然后构造下面的方程组：12运筹学教程方程组的特点：方程组的特点：方方程程个个数数是是m+n-1=3+4-1=6个个，位位势势变变量量共共有有m+n=3+4=7个个，通通常常称称ui为为第第i行行的的位位势势，称称vj为第为第j列的位势；列的位势；初
9、初始始方方案案的的每每一一个个基基变变量量xij对对应应一一个个方方程程-所所在在行行和和列列对对应应的的位位势势变变量量之之和和等等于于该该基基变变量对应的运价：量对应的运价：ui+vj=cij； 13运筹学教程 给给给给定定定定任任任任一一一一变变变变量量量量一一一一个个个个较较较较少少少少的的的的整整整整数数数数或或或或零零零零，解解解解方方方方程程程程组组组组式式式式，即即即即可可可可求求求求得得得得位势变量的一组值。计算非基变量位势变量的一组值。计算非基变量位势变量的一组值。计算非基变量位势变量的一组值。计算非基变量x xij ij检验数的公式检验数的公式检验数的公式检验数的公式 i
10、j ij=c=cij ij- -（u ui i+v+vj j）在在在在式式式式中中中中，令令令令u u2 2=0=0，则则则则可可可可解解解解得得得得v v1 1=2=2，v v3 3=3=3，u u1 1=1=1， u u4 4=10, =10, u u3 3=-4, =-4, v v2 2=9=9，计算检验数，计算检验数，计算检验数，计算检验数 1111= c= c1111- -（u u1 1+v+v1 1） =4- =4-（1+21+2）=1=1 1212=c=c1212- -（u u1 1+v+v2 2）=12-=12-（1+91+9）=2=2 2222=c=c2222- -（u u2
11、 2+v+v2 2）=10-=10-（0+90+9）=1=1 2424=c=c2424- -（u u2 2+v+v4 4）=9-=9-（0+100+10）=-1=-1 3131=c=c3131- -（u u3 3+v+v1 1）=8-=8-（-4+2-4+2）=10=10 3333=c=c3333- -（u u3 3+v+v3 3）=11-=11-（-4+3-4+3）=12=12与与与与 前前前前 面面面面 用用用用 闭闭闭闭 回回回回路路路路 法法法法 求求求求 得得得得 的的的的 结结结结果相同。果相同。果相同。果相同。 14运筹学教程B1B2B3B4 产量uiA1 16U1(1)A210
12、U2(0)A322U3(-4) 销量814121448vjV1(2)V2(9)V3(3)V4(10)产地销地41210285113411968210148615运筹学教程B1B2B3B4 产量A11216A21-110A3101222 销量814121448检验数表检验数表16运筹学教程位势法计算非基变量位势法计算非基变量xij检验数的公式检验数的公式 ij=cij-（ui+vj）=（闭回路上偶数次顶点运价之和）（闭回路上偶数次顶点运价之和）-（闭（闭回路上奇数次顶点运价之和）回路上奇数次顶点运价之和） 闭回路法计算非基变量闭回路法计算非基变量xij检验数的公式：检验数的公式：比较检验数计算的
13、两种方法比较检验数计算的两种方法17运筹学教程 三、解的改进三、解的改进三、解的改进三、解的改进 当当当当至至至至少少少少有有有有一一一一个个个个非非非非基基基基变变变变量量量量的的的的检检检检验验验验数数数数是是是是负负负负值值值值时时时时，说说说说明明明明作作作作业业业业表表表表上上上上当当当当前前前前的的的的调调调调运运运运方方方方案案案案不不不不是是是是最最最最优优优优的的的的，应应应应进进进进行行行行调调调调整整整整。 即即即即检检检检验验验验数数数数 ij ij小小小小于于于于零零零零，则则则则应对解进行改进：应对解进行改进：应对解进行改进：应对解进行改进：1 1、首先在作业表上以
14、、首先在作业表上以、首先在作业表上以、首先在作业表上以x xij ij为起始变量作出闭回路。为起始变量作出闭回路。为起始变量作出闭回路。为起始变量作出闭回路。2 2、以以以以检检检检验验验验数数数数 ij ij小小小小于于于于零零零零所所所所对对对对应应应应的的的的空空空空格格格格为为为为第第第第一一一一个个个个奇奇奇奇数数数数点点点点，沿沿沿沿闭闭闭闭回回回回路路路路顺或逆时针依次对顶点进行编号。顺或逆时针依次对顶点进行编号。顺或逆时针依次对顶点进行编号。顺或逆时针依次对顶点进行编号。3 3、在闭回路的所有偶数顶点，求出调整量、在闭回路的所有偶数顶点，求出调整量、在闭回路的所有偶数顶点，求出
15、调整量、在闭回路的所有偶数顶点，求出调整量 ：4 4、在在在在闭闭闭闭回回回回路路路路的的的的所所所所有有有有奇奇奇奇数数数数顶顶顶顶点点点点，增增增增加加加加调调调调整整整整量量量量 ，所所所所有有有有偶偶偶偶数数数数顶顶顶顶点点点点，减减减减去调整量去调整量去调整量去调整量 ，ij=min该闭回路中该闭回路中偶数次偶数次顶点调运量顶点调运量xij18运筹学教程B1B2B3B4 产量A1 16A210A322 销量814121448产地销地41210285113411968210148624=c24-（u2+v4）=9-（0+10）=-1，x24 换入变量换入变量,对应的闭回路。对应的闭回路
16、。x24+-+-19运筹学教程计计算算调调整整量量，闭闭回回路路偶偶数数顶顶点点，找找运运输输量量最最小小的顶点：的顶点：=Min=Min（x x1414，x x2323）= Min= Min（6 6，2 2）= 2= 2。按照下面的方法调整调运量：按照下面的方法调整调运量： 闭闭回回路路上上，奇奇数数次次顶顶点点的的调调运运量量增增加加，偶偶数数次次顶顶点点（包包括括起起始始顶顶点点）的的调调运运量量减减去去；闭闭回路之外的变量调运量不变。回路之外的变量调运量不变。得到新的得到新的调调运方案运方案： 20运筹学教程B1B2B3B4 产量A1 16A210A322 销量814121448产地销
17、地412102851134119682101486+2-2+2-2计算检验数（位势法或闭回路法）计算检验数（位势法或闭回路法）21运筹学教程B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119681214842练习练习:分别使用闭回路法和位势法计算检验数分别使用闭回路法和位势法计算检验数22运筹学教程B1B2B3B4 产量A1 16A210A322 销量814121448产地销地412102851134119681214842检验数为非负，得到最优解。检验数为非负，得到最优解。 1 11 =0 3 31 =9 12 =2 22 =2 2
18、3 =1 33 =1223运筹学教程B1B2B3B4 产量uiA1 16U1(2)A210U2(0)A322U3(-3) 销量814121448vjV1(2)V2(8)V3(2)V4(9)产地销地412102851134119681214842 ij ij= =c cij ij- -（u ui i+v+vj j）24运筹学教程B1B2B3B4 产量uiA1 16U1(2)A210U2(0)A322U3(-3) 销量814121448vjV1(2)V2(8)V3(2)V4(9)产地销地4121028511341196812148420922112检验数为非负，得到最优解。检验数为非负，得到最优解
19、。 ij ij= =c cij ij- -（u ui i+v+vj j）25运筹学教程 结结 果果 最优调运方案是：最优调运方案是： x x2121=8=8，x x3232=14=14，x x1313=12=12，x x1414=4=4，x x2424=2=2， x x3434=8=8 相应的最小总运输量为：相应的最小总运输量为： Z Zminmin=82+145+124+411+29 +86=244=82+145+124+411+29 +86=244 26运筹学教程四、几点说明四、几点说明四、几点说明四、几点说明1 1、如果运输问题的某一个基可行解有多个非基变量、如果运输问题的某一个基可行解
20、有多个非基变量、如果运输问题的某一个基可行解有多个非基变量、如果运输问题的某一个基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一的检验数为负，在继续进行迭代时，取它们中的任一的检验数为负，在继续进行迭代时，取它们中的任一的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常变量为换入变量均可使目标函数值得到改善，但通常变量为换入变量均可使目标函数值得到改善，但通常变量为换入变量均可使目标函数值得到改善，但通常取检验数中最小者对应的变量为换入变量。取检验数中最小者对应的变量为换入变量。取检验数中最小者对应的变量为换入变量。取检验数中最小者
21、对应的变量为换入变量。2 2、当迭代得到最优解，如果有某非基变量的检验数、当迭代得到最优解，如果有某非基变量的检验数、当迭代得到最优解，如果有某非基变量的检验数、当迭代得到最优解，如果有某非基变量的检验数等于零，则说明问题有无穷多解。等于零，则说明问题有无穷多解。等于零，则说明问题有无穷多解。等于零，则说明问题有无穷多解。3 3、在迭代过程中，如果划去某行的同时，也划去某、在迭代过程中，如果划去某行的同时，也划去某、在迭代过程中，如果划去某行的同时，也划去某、在迭代过程中，如果划去某行的同时，也划去某一列，出现退化解，退化时应保证基变量的个数为一列，出现退化解，退化时应保证基变量的个数为一列，出现退化解，退化时应保证基变量的个数为一列，出现退化解，退化时应保证基变量的个数为m+n-1m+n-1，在划去某列或行中的某个空格填入数字，在划去某列或行中的某个空格填入数字，在划去某列或行中的某个空格填入数字，在划去某列或行中的某个空格填入数字0 0。27运筹学教程小结小结:表上作业法求解运输问题的计算步骤。表上作业法求解运输问题的计算步骤。作业作业:3.728
