[高等教育]第l六章運籌學(xué)圖與網(wǎng)絡(luò)(編輯修改稿)
2025-02-17 22:47 本頁面
【文章內(nèi)容簡介】 求 到各點的最短路 . 1v1v2v3v4v5v63211111233)0,0()1,1()5,2()3,5(計算過程 : ? ?? ? ? ?),3,5(),3,4(),2,1(),(,)。5,2(),4,5(),(,231,11,30,60m i n,m i n),3,5(),4,5(),4,1(),2,1(),(,)。1,1(v),5,1(),(,1,m i n,110,330,660),5,1(),4,1(),2,1(),(),0,0(451453541412515151514121514121中的弧有已標號點為標號對中的弧有已標號點為標為則中有三條弧分別是標對XXvvvvdckkkkXXvvdckkkkkkkXXv???????????????????? ? ? ?? ? ? ?.5,3,2,1:.,).3,5(),2,3(),(,523,60m i n,m i n)2,3(),2,1(),(,)。4,3(),3,4(),(,331,12,60m i n,m i n23451345145151123232125431343534312vvvvvvvvvvvvvvvvdckkkXXvvvvvdckkkk????????????????????????路如下到各點間的最短計算結(jié)束此時所有點均已標號標號對中的弧有已標號點為標號對SABCDET2 25557734411三 .求網(wǎng)絡(luò)各點間最短距離的矩陣算法 例 6 求下面網(wǎng)絡(luò)中各點間的最短距離 . 定義 : 為圖中相鄰兩點間的距離 ,若 i和 j不相鄰時 ijd.??ijd???????????????????????????????????????????????????????????????0757014351057401435102572024520TTTETDTCTBTATSETEEEDECEBEAESDTDEDDDCDBDADSCTCECDCCCBCACSBTBEBDBCBBBABSATAEADACABAAASSTSESDSCSBSASSddddddddddddddddddddddddddddddddddddddddddddddddd.,0, 該矩陣為對稱矩陣且由于 ?? iijiij ddd從 i到 j的路不一定是從 i直接到 j,它可以是從 i出發(fā)經(jīng)過許多中間點到達 S到 B,如果只考慮經(jīng)過一個中間點時 ,則其最短距離是下列諸距離中的最小值 ,即 ? ?TBSTEBSEDBSDCBSCBBSBABSASBSS dddddddddddddd ??????? ,,m i n一般可寫為 于是構(gòu)造一個新矩陣 ? ? TEDCBASrdd rBSr ,,m i n ?? ? ?rjirij dddDD ?? m i n, )1()1()1( 的每個元素令.)1(離一個中間點時的最短距之間直接到達和經(jīng)過給出了網(wǎng)絡(luò)中任意兩點矩陣 D? ?.,m i n, )1()1()2()2()2(點的最短距離三個中間點直接到達或經(jīng)過一至它給出了網(wǎng)絡(luò)中任意兩中每個元素為構(gòu)造類似地 rjirij dddDD ??? ?.)12(,m i n, )()1()1()(最短距離個中間點時比較得到的到兩個直接到達以及經(jīng)過一個給出了網(wǎng)絡(luò)中任意兩點構(gòu)造的矩陣由更一般地??? ??kkkrjkirkij Dddd?:, )(按下面公式計算值其中時為止則要計算到個點設(shè)網(wǎng)絡(luò)中有 kDp k.2lg )1l g (1,12212 1 kpkp kk ??????????., 6lg2lg )17l g (,7 )3(Dp 故要計算到則本例中 ????? ?? ? ? ?? ?ljiljijiijnmijnljklmijbababaccBACbBaA，???????????,m i n,*,*2211 ?其中定義設(shè)引入如下運算記號在具體計算時為了方便??????????????????????????06511101260143585105479114501341034102412573202894420*)1(DDD????????????????????????0651091114601435751054681045013493410241156320214784420*)1()1()2(DDD????????????????????????0651091113601435751054681045013493410241156320213784420*)2()2()3(DDD例如 : 就是 S到 T的最短距離 ,與前邊計算結(jié)果相同 . 13?STd例 7 如果例 6中的七個點表示七個村鎮(zhèn) ,他們要聯(lián)合辦一所小學(xué) ,各村小學(xué)生人數(shù)分別是 S30,A40,B20,C15,D35,E25,T50. 問小學(xué)建在哪一個村鎮(zhèn) ,使小學(xué)生上 (下 )學(xué)走的總路程為最短 . 解 :將 中第一行各數(shù)字乘 S村小學(xué)生人數(shù) ,這些數(shù)表示小學(xué)建在各村時 ,S村小學(xué)生所走的路程 ,同理可得出下表 )3(DS A B C D E T S A B C D E T 0 80 80 60 280 175 650 60 0 40 45 210 125 550 120 80 0 15 140 75 450 120 120 20 0 175 100 500 240 240 80 75 0 25 250 210 200 60 60 35 0 300 390 440 180 150 175 150 0 1325 1030 880 935 910 865* 1485 小學(xué)應(yīng)建在 E村 . 第四節(jié) 網(wǎng)絡(luò)的最大流 (Maximal flow of work) 流 (Flow)就是將目標由一個地點運送到另一個地點 .如 :公路中的交通流 ,控制系統(tǒng)中的信息流 ,供水系統(tǒng)中的水流 ,金融系統(tǒng)中的現(xiàn)金流 ,郵政系統(tǒng)中的信件流 ,等等 .它們的共同問題是 ,希望經(jīng)過輸送系統(tǒng) ,將目標從一個地點運送到另一個地點的運輸量最大 ,或者將一定數(shù)量的目標在該系統(tǒng)中從一個地點輸送到另
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1