【正文】 0,),(,0 ??????? WVvzEvvx iijiijwW ?id??ididsv tvEvvzzdr jiijijij ????? ),(,sv iviv??td例 求總流量為 10的 最小費(fèi)用流 sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(令 ，長度網(wǎng)絡(luò)為 jidrzxijijiij ,0,0 ????sv2v3v4tv11v13226)0(sv)1(2v )4(3v4)4(tv1)3(1v13226求得增廣鏈（紅線）和所有的 （括號內(nèi)的數(shù)） id? ? iddzz itii ???? ,0m a x求出 （ ） izi ?? ,00,3,1,0,4 321 ????? zzzzz ts利用可增廣鏈調(diào)整流量 sv2v3v)4,10(tv)1,7(1v)1,8()3,10()2,5()2,4()6,2(5053132311212????????Wxxxxxxxtsts第一次迭代后的信息均在下圖中，其中頂點(diǎn)后的數(shù) 是對偶變量值，容量和費(fèi)用對下面的數(shù)據(jù)對是流量 簡化成本 ijijijijij cxrxr ?????? 0,00ijijij zzdr ???可驗(yàn)證松弛條件 ]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[利用上圖構(gòu)造長度網(wǎng)絡(luò)圖 ]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[sv2v3v1tv1v00250000求得增廣鏈（紅線）和所有的 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 。,3,12,3。由此形成下面的算法 ????????????????04320405001232037710811030√ √ √ ????????????????04320405001232037710811030√ ????????????????04320405001232037710811030關(guān)于前面描述的迭代算法有以下事實(shí)： 1）每次迭代至少增加一個被圈住的零 2）所有紅圈圈住的一定是獨(dú)立零元素組 3）直線的數(shù)目和紅圈的個數(shù)相同 上述第一個事實(shí)說明迭代算法有限步停止，第二個事實(shí) 說明算法能產(chǎn)生最大的獨(dú)立零元素組，第三個事實(shí)說明 算法產(chǎn)生的是能夠覆蓋所有零元素的數(shù)目最少的直線組 找出未覆蓋處最小的數(shù)，在 沒被行直線覆蓋的行減去最 小數(shù)，然后在有負(fù)數(shù)的列加 上這個最小數(shù) ??????????????????04320405000121126601811030????????????????04321405010121026600811031三、利用第一個性質(zhì)在直線未覆蓋處產(chǎn)生零元素 ? ?????????????????04320405001232037710811030繼續(xù)找最大的獨(dú)立零元素組 ????????????????04321405010121026600811031????????????????04321405010121026600811031????????????????04321405010121026600811031????????????????04321405010121026600811031出現(xiàn)前面討論過的第三種情況， 因此一定可以增加獨(dú)立零元素 最終獲得的獨(dú)立零元素組 獨(dú)立零元素數(shù)等于任務(wù)數(shù)，已得最優(yōu)解 ???????????????????04321405010121026600811031C?????????????????1000001000000010001000100*X非標(biāo)準(zhǔn)形式指派問題如何轉(zhuǎn)換成標(biāo)準(zhǔn)問題 1）目標(biāo)函數(shù)求最大 ? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???????????????????????ninjijijninjijijninjijninjijijninjijijxcAxcxAxAxc1 11 11 11 11 1minminminm a x取 ，令 ，得標(biāo)準(zhǔn)問題 ? ?? ??ninjijcA1 1? ? nnijcAC ????2）人數(shù)和事情不等的問題 補(bǔ)充虛擬的人或事，費(fèi)用系數(shù)取 0 3）一人可做幾件事的問題 將該人轉(zhuǎn)換成相同的幾個人接受指派，這些人 的費(fèi)用系數(shù)完全相同 4）某事一定不能由某人做的問題 將相應(yīng)費(fèi)用取為充分大的正數(shù)