管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)(參考版)
2025-01-12 05:27本頁面
【正文】 。在一次敵對的軍事行動(dòng)中，問至少應(yīng)炸斷幾座及哪幾座橋梁，才能完全切斷兩岸的交通聯(lián)系。 }fm in)fC(m in{m in ijijij ????? ?? ??? ，例 7 求圖 18— 20所示網(wǎng)絡(luò)的最大流，弧旁的數(shù)字是容量 Cij，弧旁括號(hào)內(nèi)的數(shù)字是流量 fij。 2．調(diào)整過程 由標(biāo)號(hào)過程得到一條增廣鏈 μ ，則調(diào)整量為 然后在增廣鏈 μ 的一切前向弧 μ +上增加 θ ，一切后向弧 μ 上減少 θ ，不在增廣鏈上的弧流量不變。 （ 2）如果連接 vi與 vj的?。?vi， vj）是后向弧，且 ，則給 vj標(biāo)號(hào)，即 。 標(biāo)號(hào)法的具體步驟如下： 1．標(biāo)號(hào)過程 標(biāo)號(hào)過程就是尋找增廣鏈的過程。 定理 4（最大流量最小截量定理）：任一個(gè)網(wǎng)絡(luò) D中，從 vS到 vT的最大流的流量等于分離vS， vT的最小截集的容量。 這里 }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è)，即最小截集。 例圖 1818 4．截集與截量 截集是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)與收點(diǎn)分割開，使 vS到 vT的流中斷的一個(gè)弧的集合。 定義 設(shè) μ 是網(wǎng)絡(luò) D中從 vS到 vT的一條鏈，這條鏈上的弧可以分成兩類，把弧的方向與鏈的方向一致的弧，稱為前向弧，鏈中的全體前向弧記為 μ +；把弧的方向與鏈的方向相反的弧，稱為后向弧，鏈中的全體后向弧記為 μ 。 fij=0的?。?vi， vj）為零流弧。 把流量 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）為飽和弧。 ijij Cf0 ??0?? ???? AvvjiAvvijijjiff），（），（)()()()()()(fvvVfVvffvvVfVvfTTss?????， 零流是最簡單的可行流。 例如圖 18— 18 ? ?A)vv()vv(ff jiji ?? ，滿足下列條件的流 f，稱為可行流 （ 1）相容條件：對每一條弧，有 （ 2）平衡條件：對每一個(gè)中間點(diǎn) vij，有 其中等式左端第一項(xiàng)表示從點(diǎn) vi流出貨物的總量，簡記為 f（ vi， V）；第二項(xiàng)表示流進(jìn) vi點(diǎn)的貨物的總量，簡記為 f（ V ， vi）。 最大流問題就是：要把發(fā)點(diǎn)處的一批貨物運(yùn)到終點(diǎn)去，在每一條弧上通過貨物的總量不能超過這條弧的容量，問應(yīng)該怎樣安排運(yùn)輸，才能使發(fā)點(diǎn)到收點(diǎn)的總運(yùn)量達(dá)到最大。 在容量網(wǎng)絡(luò)上通常規(guī)定一個(gè)發(fā)點(diǎn) vS，一個(gè)收點(diǎn) vT，其余都是中間點(diǎn)。定義了容量的圖 D，稱為容量網(wǎng)絡(luò)。 以圖 18— 18所示的運(yùn)輸網(wǎng)絡(luò)為例來說明求解過程。 解：由計(jì)算重心的公式： 既可算得應(yīng)把中心倉庫建在 v6分廠，每月的最小運(yùn)輸量為 122022。已知各分廠每月的原材料需求量見下圖。 先用公式 計(jì)算 d(vi)，見下表： 再用公式 計(jì)算 d(v*)， 由表可知，應(yīng)將俱樂部建在分廠 v2
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1