最小费用流问题

最小费用流问题内容摘要：

tv1v00250000求得增广链（红线）和所有的 id)0(sv)0(2v )0(3v1)1(tv)1(1v00250000  iddzz itii  ,0m a x利用 0,3,1,0,4 321  zzzzz ts1,4,1,0,5 321  zzzzz ts求出 ]4[sv]3[2v ]0[3v]1,0[]0[tv)1,7(]1[1v)1,8()3,10()2,5()2,4()6,2()4,10(]0,5[]0,0[]0,5[]5,0[]0,5[]2,0[利用可增广链调整流量 707,5,5,232312121Wxxxxxxttss]5[sv]4[2v ]1[3v]0,2[]0[tv)1,7(]1[1v)1,8()3,10()2,5()2,4()6,2()4,10(]0,5[]0,0[]1,5[ ]6,0[]0,7[]1,0[第二次迭代后的信息 ijijijijij cxrxr  0,00可验证松弛条件 利用上图构造长度网络 ]5[sv]4[2v ]1[3v]0,2[]0[tv)1,7(]1[1v)1,8()3,10()2,5()2,4()6,2()4,10(]0,5[]0,0[]1,5[ ]6,0[]0,7[]1,0[sv2v3v0tv1v00160100求得增广链（红线）和所有的 id  iddzz itii  ,0m a x利用 2,5,2,0,6 321  zzzzz ts求出 )0(sv)0(2v )0(3v0)1(tv)0(1v001601001,4,1,0,5 321  zzzzz ts利用可增广链调整流量 103,37,5,8,232312121Wxxxxxxttss]6[sv]5[2v ]2[3v]0,2[]0[tv)1,7(]2[1v)1,8()3,10()2,5()2,4()6,2()4,10(]0,5[]0,0[]1,5[ ]6,0[]0,7[]1,0[第三次迭代后的信息 ijijijijij cxrxr  0,00可验证松弛条件 ]6[sv]5[2v ]2[3v]0,2[]0[tv)1,7(]2[1v)1,8()3,10()2,5()2,4()6,2()4,10(]0,8[]0,3[]1,5[ ]6,0[]1,7[ ]0,3[由于总流量等于 10已经满足约束，所以是最优解 运输问题 运输表描述 产地 销地 产量 销量 1AmA2AnB1B2B2ama1anb2b1b21c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx运输问题的图描述 1B2BnB1A2AmA产地 销地 1a2ama产量 1b2bnb销量 1mc2mcmnc11c12c1nc11mnij ijijcx在流量平衡和非负约束下极小化总的运输费用 产销平衡运输问题的数学规划模型（线性规划问题） 1111m in . , 1,10 , 1 , 1mnij ijijnij ijmij jiijcxx a i mx b j nx i m j n           产销平衡假定： Qbanjjmii   11jiQbax jiij ,ˆ 有可行解 1111ˆ ,ˆ ,nniij j ijjmmjij i jiiax b a iQbx a b jQ    11, 1。 , 1 1nmi j i i j jjix a i m x b j n        111 1 1 1 1 1 1 1111 1 1 1 1m m n n m n m ni n i j i j i j i ji i j j i j i jm n m n ni i j j j ni j i j jx x x x xa x b b b                             最后一个约束多余，等式约束可写成 共有 个等式约束 1 nm11, 1。 , 1 1nmi j i i j jjix a i m x b j n        111 11mnmij ijijnaaPxbb 注意： i其中   10 0 1 0 0 1 0 0 T mnijPR jm列向量表示模型 1111m in . , 1, 1 10 , 1 , 1 1mni j i jijni j ijmi j jiijcxx a i mx b j nx i m j n               10 0 1 0 0 T mninPR i例 产地 销地 产量 销量 1A3A2A4B1B 2B10221648148221x1022x411x831x1212x532x1114x924x634x3B12413x323x1133x14图表示 1B2B4B1A2A3A16102214812143B412114210938 561111x12x14x13x21x22x24x23x31x32x34x33x产生基本可行解 1B2B4B1A2A3A00000003B11 1x 14 1x 21 1x 24 1x 如果一组变量（红线表示）形成回路 1 1 1 1 2 1 2 1 1 4 1 4 2 4 2 4 0P x P x P x P x   在 中令其他变量等于 0 110mnij ijijPx1B2B4B1A2A3A00000003B11x21x24x如果一组变量（红线表示）不含回路 2 4 2 1 1 10 0 0x x x    在 中令其他变量等于 0 110mnij ijijPx上述第一种情况的运输表 产地 销地 产量 销量 1A3A2A4B1B 2B000000221 1x 10411 1x 81251114 1x 924 1x 63B0431101 1 1 1 2 1 2 1 1 4 1 4 2 4 2 4 0P x P x P x P x   上述第二种情况的运输表 产地 销地 产量 销量 1A3A2A4B1B 2B000000221x10411x812511924x63B0431102 4 2 1 1 10 0 0x x x    1 1 1 1 2 1 2 1 2 4 2 4 0P x P x P x  结论：运输问题一组变量的系数线性无关的充要条件是 在图或表中不含有回路 1B2B4B1A2A3A00000003B11x21x24x基本可行解的个数 1 nm用 最小元素法 产生基本可行解 基本思想：优先安排单位运输成本最小的运输方式 产地 销地 产量 销量 1A3A2A4B1B 2B210 22164814828104812511963B12431114产地 销地 产量 销量 1A3A2A4B1B 2B222164814828104812511963B1012 4311142产地 销地 产量 销量 1A3A2A4B1B 2B222616 4814828104812511963B10431114210产地 销地 产量 销量 1A3A2A4B1B 2B2822 64814828104812511963B1043111421014产地 销地 产量 销量 1A3A2A4B1B 2B2864814828104812511963B104311614 21014 8产地 销地 产量 销量 1A3A2A4B1B 2B2864814828104812511963B104311621014 86最后删除两个约束 1 nm不会形成回路 每次删除一个约束（节点）  变量 产生基本可行解等价于在运输图中生成一。