《运筹学》胡运权清华版-3-02表上作业法.ppt

《《运筹学》胡运权清华版-3-02表上作业法.ppt》由会员分享，可在线阅读，更多相关《《运筹学》胡运权清华版-3-02表上作业法.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三、迭代三、迭代 选进选进基基变量：变量：负负检验数中绝对值最大的一个检验数中绝对值最大的一个 选换出变量：选换出变量：1.设换入变量为设换入变量为y2.从从y出发找一条闭回路。然后将闭出发找一条闭回路。然后将闭回路顶点按顺时针或逆时针编号，回路顶点按顺时针或逆时针编号，y是第是第1号。号。3.偶顶点偶顶点中，运量中，运量最小最小的出基的出基调整调整:记最小运量为记最小运量为 奇顶点：奇顶点：运量运量 偶顶点：偶顶点：运量运量举例 销地产地B1B2B3B4uiA1 u1=1A2u2=0A3u3=-4vjv1=2v2=9v3=3v4=104124112103985611821014861 12

2、21 1-1-1101012121423偶顶点运量最小处偶顶点运量最小处出基出基 销地产地B1B2B3B4产量产量A1 16A210A322销量销量814121448412411210398561182101486101012121423调整2124带圈格总数=m+n1=3+4-1=6总运费244检验 销地产地B1B2B3B4uiA1 u1=0A2u2=A3u3=vjv1=v2=v3=v4=4124112103985611821214844 41111-2-2-5-54 410100 02 22 21 19 91212所有检验数都所有检验数都0，已最优，已最优最优表中，非基变量检验数最优表中，

3、非基变量检验数0，有多个最优解，有多个最优解另一个最优基可行解另一个最优基可行解 销地产地B1B2B3B4uiA1 u1=A2u2=A3u3=vjv1=v2=v3=v4=412411210398561182121484644四、几点说明四、几点说明 1 1 若有多个检验数为负，在继续迭代时，若有多个检验数为负，在继续迭代时，通常选最负的一个作为换入变量；通常选最负的一个作为换入变量；2 2 当迭代到运输问题的最优解时，如果有当迭代到运输问题的最优解时，如果有某个非基变量的检验数某个非基变量的检验数0 0，说明有无穷多最，说明有无穷多最优解；优解；3 3 退化现象退化现象求初始解时退化求初始解时

4、退化 销地产地B1B2B3B4销量销量A1 7A23A39产量产量365531131219287451030例：例：用用最最小小元元素素法法求求初初始始解解当出现当出现行和列行和列同时可同时可以打以打时，时，规规定：只定：只能在一能在一个方向个方向上打上打 销地产地B1B2B3B4销量销量A1 7A23A39产量产量365531131219287451030保证圈保证圈出的基出的基变量个变量个数是数是m+n-1m+n-1个个5632基变量基变量0 0，退化，退化迭代中退化迭代中退化16161322171419M141901320M191523M00u105030202003050V5=15V3

5、=13u4=-15u20u35V1=14 V2=14V4=18+2+20+4+1M-20+2M+1+1M+2-3152610+243偶顶点中偶顶点中两处运量两处运量最小（最小（3030），只），只选一个出选一个出基，另一基，另一个补个补0 0。200304030基变基变量量0 0，退化退化3016161322171419M141901320M191523M005020203020400保证基变量个数保证基变量个数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第二节第二节 表上作业法表上作业法