运筹学胡运权清华版302表上作业法3.ppt

三、迭代三、迭代 选进基变量：选进基变量：负负检验数中绝对值最大的一检验数中绝对值最大的一个个 选换出变量：选换出变量：1.设换入变量为设换入变量为y2.从从y出发找一条闭回路。然后将闭出发找一条闭回路。然后将闭回路顶点按顺时针或逆时针编号，回路顶点按顺时针或逆时针编号，y是第是第1号。号。3.偶顶点偶顶点中，运量中，运量最小最小的出基的出基调整调整:记最小运量为记最小运量为 奇顶点：奇顶点：运量运量 偶顶点：偶顶点：运量运量举例 销地产地A1A2A3vjB1 v1=2B2v2=9B3v3=3B4v4=10uiu1=1u2=0u3=-44124112103985611821014861 12 21 1-1-1101012121423偶顶点运量最小处偶顶点运量最小处出基出基 销地产地A1A2A3销量销量B1 8B214B312B414产量产量16102248412411210398561182101486101012121423调整2124带圈格总数=m+n1=3+4-1=6总运费244检验 销地产地A1A2A3vjB1 v1=B2v2=B3v3=B4v4=uiu1=0u2=u3=4124112103985611821214844 41111-2-2-5-54 410100 02 22 21 19 91212所有检验数都所有检验数都0，已最优，已最优最优表中，非基变量检验数最优表中，非基变量检验数0，有多个最优解有多个最优解另一个最优基可行解另一个最优基可行解 销地产地A1A2A3vjB1 v1=B2v2=B3v3=B4v4=uiu1=u2=u3=412411210398561182121484644四、几点说明四、几点说明 1 1 若有多个检验数为负，在继续迭代时，若有多个检验数为负，在继续迭代时，通常选最负的一个作为换入变量；通常选最负的一个作为换入变量；2 2 当迭代到运输问题的最优解时，如果有当迭代到运输问题的最优解时，如果有某个非基变量的检验数某个非基变量的检验数0 0，说明有无穷多最，说明有无穷多最优解；优解；3 3 退化现象退化现象求初始解时退化求初始解时退化 销地产地A1A2A3产量产量B1 3B26B35B45销量销量73931131219287451030例：例：用用最最小小元元素素法法求求初初始始解解当出现当出现行和列行和列同时可同时可以打以打时，时，规规定：只定：只能在一能在一个方向个方向上打上打 销地产地A1A2A3产量产量B1 3B26B35B45销量销量73931131219287451030保证圈保证圈出的基出的基变量个变量个数是数是m+n-1m+n-1个个5632基变量基变量0 0，退化退化迭代中退化迭代中退化DestinationDestination Iteration Iteration 0 0 1 1 2 2 3 3 4 4 5 5 supplysupply u ui i source 1source 1 5050 2 2 6060 3 3 5050 4(D)4(D)5050 DemandDemand 3030 2020 7070 3030 6060 v vj j 16161322171419M141901320M191523M00u105030202003050V5=15V3=13u4=-15u20u35V1=14 V2=14V4=18+2+20+4+1M-20+2M+1+1M+2-3152610+243偶顶点中偶顶点中两处运量两处运量最小（最小（3030），只），只选一个出选一个出基，另一基，另一个补个补0 0。200304030基变基变量量0 0，退化退化30DestinationDestination Iteration Iteration 0 0 1 1 2 2 3 3 4 4 5 5 supplysupply u ui i source 1source 1 5050 2 2 6060 3 3 5050 4(D)4(D)5050 DemandDemand 3030 2020 7070 3030 6060 v vj j 16161322171419M141901320M191523M005020203020400保证基变量个数保证基变量个数m+n-1m+n-1个个基变量基变量0 0，退化退化练习：练习：表上作业法求解运输问题表上作业法求解运输问题产地产地 B1 B2 B3 产量产量 A1 3 5 5 20 A2 1 3 2 40 A3 2 3 4 30 销量销量 60 20 10 参考答案：参考答案：Z*=190