管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)(存儲版)
【正文】 則 D(2)給出網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，經(jīng)過一至三個(gè)中間點(diǎn)時(shí)的最短距離。 求重心 村莊之間的最短距離 dij * 村莊 人數(shù) wi v1 v2 v3 v4 v5 v6 v7 v1 30 0 5 2 7 7 6 10 v2 40 5 0 7 2 5 4 8 v3 25 2 7 0 6 5 4 8 v4 20 7 2 6 0 3 2 6 v5 50 7 5 5 3 0 1 3 v6 60 6 4 4 2 1 0 4 v7 60 10 8 8 6 3 4 0 ∑ wi dij * 1700 1335 1430 1070 835 770* 1330 例：下圖為一大型企業(yè)區(qū)域交通網(wǎng)絡(luò)圖。已知各分廠每月的原材料需求量見下圖。 在容量網(wǎng)絡(luò)上通常規(guī)定一個(gè)發(fā)點(diǎn) vS，一個(gè)收點(diǎn) vT，其余都是中間點(diǎn)。 把流量 fij作為變量，根據(jù)可行流的定義及網(wǎng)絡(luò)最大流問題的提法，可見最大流問題也是一個(gè)線性規(guī)劃問題，其數(shù)學(xué)模型為：求一組流量 fij使 ??????????????????????????? ??)(0)(ni)(1n. ..32i01i)()(m a x對所有的弧對所有的?。ㄊ拯c(diǎn)）當(dāng)（中間點(diǎn)），當(dāng)（發(fā)點(diǎn)）當(dāng)滿足ijijijjiijfCffvfvfffv3．增廣鏈 定義 設(shè)網(wǎng)絡(luò) D=（ V， A， C）中有一個(gè)流 f={fij}，則稱 fij=Cij的?。?vi， vj）為飽和弧。 這里 }vv{V 311 ，? }vvvv{V65421 ，????)VV()vv(ji1111ji)vv(C)VV(C，)VV( 11，)VV( 11，216510)VV(C 11 ????， 若對于一個(gè)可行流 f*，網(wǎng)絡(luò)圖中有一個(gè)截集 ，使 則 f*必是最大流，而 是 D的所有截集中截量最小的一個(gè)，即最小截集。 2．調(diào)整過程 由標(biāo)號過程得到一條增廣鏈 μ ，則調(diào)整量為 然后在增廣鏈 μ 的一切前向弧 μ +上增加 θ ，一切后向弧 μ 上減少 θ ，不在增廣鏈上的弧流量不變。 。 （ 2）如果連接 vi與 vj的弧（ vi， vj）是后向弧，且 ，則給 vj標(biāo)號，即 。 例圖 1818 4．截集與截量 截集是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)與收點(diǎn)分割開，使 vS到 vT的流中斷的一個(gè)弧的集合。 ijij Cf0 ??0?? ???? AvvjiAvvijijjiff），（），（)()()()()()(fvvVfVvffvvVfVvfTTss?????， 零流是最簡單的可行流。定義了容量的圖 D，稱為容量網(wǎng)絡(luò)。 先用公式 計(jì)算 d(vi)，見下表： 再用公式 計(jì)算 d(v*)， 由表可知，應(yīng)將俱樂部建在分廠 v2或 v6。 解：計(jì)算見表。 解 設(shè) dij表示相鄰兩點(diǎn) vi與 vj間的距離，若 vi與 vj不相鄰時(shí)，令 dij=∞ 。 （ 3）從已標(biāo)號的頂點(diǎn)出發(fā)，找出與已標(biāo)號點(diǎn)相鄰的所有未標(biāo)號點(diǎn)。 ? ?? ??? ? Tvv ijji w)T(w ，求最小部分樹的兩種方法 算法 Ⅰ （ Kruskal算法）：其基本思想是，每一步從未選的邊中，選一條具有最小權(quán)的邊，使與已選的邊不構(gòu)成圈，直到每一條邊都選查過為止。反之，若圖 G是連通圖，則 G必有部分樹。 第三節(jié) 樹 一、樹的概念及性質(zhì) 定義 如果圖 G是一個(gè)無圈的連通圖，則稱 G為樹。如果鏈（圈） Q中含的邊與頂點(diǎn)均不相同，則稱 Q為初等鏈（圈）。 同構(gòu)的圖被認(rèn)為是相同的。 （ 7）以頂點(diǎn) v為端點(diǎn)的邊的條數(shù)，稱為點(diǎn) v的 次（或稱度），記為 d（ v）。第十八章 圖與網(wǎng)絡(luò) 德國古城 —
公司管理相關(guān)推薦
鄂ICP備17016276號-1