運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)分析實(shí)用教案

1、會(huì)計(jì)學(xué)1運(yùn)籌學(xué)運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析第一頁(yè)，共41頁(yè)。OR3 2北京濟(jì)南徐州青島南京上海連云港鄭州武漢天津第1頁(yè)/共41頁(yè)第二頁(yè)，共41頁(yè)。OR3 3v5v4v3v2v1第2頁(yè)/共41頁(yè)第三頁(yè)，共41頁(yè)。OR3 4第3頁(yè)/共41頁(yè)第四頁(yè)，共41頁(yè)。OR3 5v7v1v2v3v4e1e2e3e4e5e6e7a9v1v2v3v4v5v6a1a2a8a4a3a5a6a7a10e7第4頁(yè)/共41頁(yè)第五頁(yè)，共41頁(yè)。OR3 6qvdVv2)(第5頁(yè)/共41頁(yè)第六頁(yè)，共41頁(yè)。OR3 7第6頁(yè)/共41頁(yè)第七頁(yè)，共41頁(yè)。OR3 8第7頁(yè)/共41頁(yè)第八頁(yè)，共41頁(yè)。OR3 9第8頁(yè)/共41頁(yè)第九頁(yè)，

2、共41頁(yè)。OR3 10第9頁(yè)/共41頁(yè)第十頁(yè)，共41頁(yè)。OR3 11nii12步。第10頁(yè)/共41頁(yè)第十一頁(yè)，共41頁(yè)。OR3 12V2(v1,6）)()(min0PwPwP路P0的權(quán)稱(chēng)為(chn wi)從vs到vt的距離，記為：d（ vs，vt ）第11頁(yè)/共41頁(yè)第十二頁(yè)，共41頁(yè)。OR3 13n最短路算法最短路算法nDijkstra算法算法 ：有向圖：有向圖 ，wij0n一般結(jié)論：一般結(jié)論：nDijkstra算法基本算法基本(jbn)思想思想:n采用標(biāo)號(hào)法采用標(biāo)號(hào)法: P標(biāo)號(hào)和標(biāo)號(hào)和T標(biāo)號(hào)標(biāo)號(hào)nP標(biāo)號(hào)：已確定出最短路的節(jié)點(diǎn)標(biāo)號(hào)：已確定出最短路的節(jié)點(diǎn)(永久性標(biāo)號(hào)永久性標(biāo)號(hào))。nT標(biāo)號(hào)：未確

3、定出最短路的節(jié)點(diǎn)，但表示其距離的上限標(biāo)號(hào)：未確定出最短路的節(jié)點(diǎn)，但表示其距離的上限(試探試探性標(biāo)號(hào)性標(biāo)號(hào))。n算法的每一步都把某一點(diǎn)的算法的每一步都把某一點(diǎn)的T標(biāo)號(hào)改為標(biāo)號(hào)改為P標(biāo)號(hào)直至改完為止標(biāo)號(hào)直至改完為止.nSi：P標(biāo)號(hào)節(jié)點(diǎn)的集合。標(biāo)號(hào)節(jié)點(diǎn)的集合。n 的最短路到的最短路到isjsvvisvvjisvvvvv,.,.,.,第12頁(yè)/共41頁(yè)第十三頁(yè)，共41頁(yè)。OR3 14ijijjwvPvTvT)(),(min)()(min)(iivTvP第13頁(yè)/共41頁(yè)第十四頁(yè)，共41頁(yè)。OR3 15第14頁(yè)/共41頁(yè)第十五頁(yè)，共41頁(yè)。OR3 16wvvvvijisijsjiisvvjisddvvv

4、vvvvjs),(),(,.,.,.,.,min最短路最短路的最短路到第15頁(yè)/共41頁(yè)第十六頁(yè)，共41頁(yè)。OR3 17dsj)1(dsj)2(第16頁(yè)/共41頁(yè)第十七頁(yè)，共41頁(yè)。OR3 18到各點(diǎn)的最短路。即為則該有：，步，對(duì)所有的若進(jìn)行到某一步，如第對(duì)（vvvdvvdvvdwvvdvvdwvvdsjskjskjskijistijstsjjspjkpjktpj),(),(),(.,21),.,2 , 1(),(),(,.,2),.,2 , 1(),()1()1()()1(min第17頁(yè)/共41頁(yè)第十八頁(yè)，共41頁(yè)。OR3 19wdjj1)1(1)()1(1)(1minwddijtiitjd

5、dkjkj)1(1)(1dkj)(1第18頁(yè)/共41頁(yè)第十九頁(yè)，共41頁(yè)。OR3 20第19頁(yè)/共41頁(yè)第二十頁(yè)，共41頁(yè)。OR3 21025-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910wdjj1) 1 (1)() 1 (1)2(1minwddijiij)min()2(1)3(1wddijiijddjj)6(1)5(1第20頁(yè)/共41頁(yè)第二十一頁(yè)，共41頁(yè)。OR3 22第21頁(yè)/共41頁(yè)第二十二頁(yè)，共41頁(yè)。OR3 23第22頁(yè)/共41頁(yè)第二十三頁(yè)，共41頁(yè)。OR3 24第23頁(yè)/共41頁(yè)

6、第二十四頁(yè)，共41頁(yè)。OR3 25vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)第24頁(yè)/共41頁(yè)第二十五頁(yè)，共41頁(yè)。OR3 26第25頁(yè)/共41頁(yè)第二十六頁(yè)，共41頁(yè)。OR3 27第26頁(yè)/共41頁(yè)第二十七頁(yè)，共41頁(yè)。OR3 280),(),(vvvvijjiffjiij)(),(),(fvvvvvjssjffjssj)(),(),(fvvvvvtjjtffjttj)( fv第27頁(yè)/共41頁(yè)第二十八頁(yè)，共41頁(yè)。OR3 29)( fv)()(),(0)()(),(0tifvtsisifvAffvvcfjiijjiiji

7、j第28頁(yè)/共41頁(yè)第二十九頁(yè)，共41頁(yè)。OR3 30.,),(1111111111）的截集，記為（的弧的全體稱(chēng)為分離指向，則把從且使得，和分成兩部分的點(diǎn)集截集：如果將VVvvVVVVVvVvVVtstsVCAVDV1V1V1V1VV*1*1,第29頁(yè)/共41頁(yè)第三十頁(yè)，共41頁(yè)。OR3 31第30頁(yè)/共41頁(yè)第三十一頁(yè)，共41頁(yè)。OR3 32n則稱(chēng) 為從vs到vt的（關(guān)于f的）增廣鏈。 fijf cfcfijijijij00),(),(vvvvjiji第31頁(yè)/共41頁(yè)第三十二頁(yè)，共41頁(yè)。OR3 33的可行流要大，重復(fù)這個(gè)過(guò)程，直到不存在關(guān)于該流的增廣鏈時(shí)就的得到了最大流。第32頁(yè)/共41

8、頁(yè)第三十三頁(yè)，共41頁(yè)。OR3 34可行流f 是最大流的充分必要條件(b yo tio jin)是不存在從 到 可行(kxng)流f 是最大流的充分必要條件是不存在從 到 可行流f 是最大流的充分必要條件是不存在從 f*f*第33頁(yè)/共41頁(yè)第三十四頁(yè)，共41頁(yè)。OR3 35f* ffcijijij*minmin),(min 0 ),(),(),(*vvfvvfvvffjiijjiijjiijij f*f*f*f*f*f*第34頁(yè)/共41頁(yè)第三十五頁(yè)，共41頁(yè)。OR3 36f*必必是是最最大大流流。于于是是）（所所以以，）（）（顯顯然然有有：）于于是是得得截截集集（記記的的增增廣廣鏈鏈，故故因因?yàn)闉椴徊淮娲嬖谠陉P(guān)關(guān)于于則則令令且且若若則則令令且且若若令令fVVfVVvvVVvvcfVVVVVvfVvfVvVvcfVVvcvVjijiijijtjjiijijijs*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1i*1,)(,),(0,),(.,.,0,v 第35頁(yè)/共41頁(yè)第三十六頁(yè)，共41頁(yè)。OR3 37第36頁(yè)/共41頁(yè)第三十七頁(yè)，共41頁(yè)。OR3 38第37頁(yè)/共41頁(yè)第三十八頁(yè)，共