【文章內(nèi)容簡介】 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[利用可增廣鏈調(diào)整流量 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可驗(yàn)證松弛條件 利用上圖構(gòu)造長度網(wǎng)絡(luò) ]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利用可增廣鏈調(diào)整流量 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可驗(yàn)證松弛條件 ]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已經(jīng)滿足約束，所以是最優(yōu)解 運(yùn)輸問題 運(yùn)輸表描述 產(chǎn)地 銷地 產(chǎn)量 銷量 1AmA?2AnB1B?2B2ama?1anb?2b1b21c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx運(yùn)輸問題的圖描述 1B2BnB1A2AmA產(chǎn)地 銷地 1a2ama產(chǎn)量 1b2bnb銷量 1mc2mcmnc11c12c1nc11mnij ijijcx????在流量平衡和非負(fù)約束下極小化總的運(yùn)輸費(fèi)用 產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)規(guī)劃模型（線性規(guī)劃問題） 1111m in . , 1,10 , 1 , 1mnij ijijnij ijmij jiijcxx a i mx b j nx i m j n????? ? ? ?? ? ? ?? ? ? ? ? ?????產(chǎ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例 產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B10221648148221x1022x411x831x1212x532x1114x924x634x3B12413x323x1133x14圖表示 1B2B4B1A2A3A16102214812143B412114210938 561111x12x14x13x21x22x24x23x31x32x34x33x產(chǎn)生基本可行解 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?????上述第一種情況的運(yùn)輸表 產(chǎn)地 銷地 產(chǎn)量 銷量 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? ? ? ?上述第二種情況的運(yùn)輸表 產(chǎn)地 銷地 產(chǎn)量 銷量 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? ? ?結(jié)論：運(yùn)輸問題一組變量的系數(shù)線性無關(guān)的充要條件是 在圖或表中不含有回路 1B2B4B1A2A3A00000003B11x21x24x基本可行解的個數(shù) 1?? nm?用 最小元素法 產(chǎn)生基本可行解 基本思想：優(yōu)先安排單位運(yùn)輸成本最小的運(yùn)輸方式 產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B210 ?22164814828104812511963B12431114產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B222164814828104812511963B1012 ?4311142產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B222616 ?4814828104812511963B10431114210產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B2822 ?64814828104812511963B1043111421014產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B2864814828104812511963B104311614 ?21014 8產(chǎn)地 銷地 產(chǎn)量 銷量 1A3A2A4B1B 2B2864814828104812511963B104311621014 86最后刪除兩個約束 1?? nm不會形成回路 每次刪除一個約束（節(jié)點(diǎn)） ?? 變量 產(chǎn)生基本可行解等價于在運(yùn)輸圖中生成一