運籌學chap6網(wǎng)絡優(yōu)化模型(已修改)
2025-05-28 15:06 本頁面
【正文】 本章主要討論圖論基本概念、理論和方法以及最短路問題、最大流問題和最小費用流問題等網(wǎng)絡優(yōu)化模型及其基本算法。 第六章 圖與網(wǎng)絡優(yōu)化模型 第一節(jié) 圖與網(wǎng)絡 ? 運籌學的重要分支 ? 主要應用領(lǐng)域：物理學、化學、控制論、信息論、科學管理、電子計算機等 ? 圖論理論和方法應用實例： ?在組織生產(chǎn)中，為完成某項生產(chǎn)任務，各工序之間怎樣銜接，才能使生產(chǎn)任務完成得既快又好。 ?一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應該按照怎樣的路線走，所走的路程最短。 ?各種通信網(wǎng)絡的合理架設，交通網(wǎng)絡的合理分布等問題，應用圖論的方法求解都很簡便。 ? 圖論的起源與發(fā)展 ? 七橋問題： 哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個島，河上有七座橋。當時那里的居民熱衷于這樣的問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。圖 81(a) 圖 61 ? 歐拉在 1736年發(fā)表了圖論方面的第一篇論文，解決了著名的哥尼斯堡 七橋問題 。 ? 歐拉將此問題歸結(jié)為如圖 61(b)所示圖形的一筆畫問題。即能否從某一點開始，不重復地一筆畫出這個圖形，最后回到出發(fā)點。歐拉證明了這是不可能的，因為圖 61(b)中的每個點都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個圖不重復地一筆畫成。 一、 圖的基本概念 ? 人們?yōu)榉从骋恍ο笾g關(guān)系時，常會用示意圖。 ? 例 1 右圖是我國北京、上海等十個城市間的鐵路交通圖，反映了這十個城市間的鐵路分布情況。這里用點代表城市，用點和點之間的連線代表這兩個城市之間的鐵路線。 ? 其他示意圖的例子 ?電話線分布圖、煤氣管道圖、航空線圖等。 鐵路交通示意圖 圖 62 圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 ? 例 2 有甲、乙、丙、丁、戊五個球隊，它們之間比賽的情況用圖表示出來。 ? 已知甲隊和其他各隊都比賽過一次，乙隊和甲、丙隊比賽過，丙隊和甲、乙、丁隊比賽過，丁隊和甲、丙、戊隊比賽過，戊隊和甲、丁隊比賽過。為了反映這個情況，可以用點分別代表這五個隊，某兩個隊之間比賽過，就在這兩個隊所相應的點之間聯(lián)一條線，這條線不過其他的點，如圖 63所示。 比賽情況圖 圖 63 ? 關(guān)系的對稱性和非對稱性： ? 幾個例子中涉及到的對象之間的“關(guān)系”具有“對稱性”，就是說，如果甲與乙有這種關(guān)系，那么同時乙與甲也有這種關(guān)系。 ? 實際生活中，有許多關(guān)系不具有這種對稱性。 ? 如例 2，如果人們關(guān)心的是五個球隊比賽的勝負情況，那么從圖 53中就看不出來了。為了反映這一類關(guān)系，可以用一條帶箭頭的連線表示。 ? 例如，如果球隊 v1勝了球隊 v2，可以從 v1引一條帶箭頭的連線到 v2 ? 類似勝負這種非對稱性的關(guān)系，在生產(chǎn)和生活中是常見的，如交通運輸中的“單行線”，部門之間的領(lǐng)導與被領(lǐng)導的關(guān)系，一項工程中各工序之間的先后關(guān)系等。 比賽勝負圖 64 術(shù)語 頂點（結(jié)點）、弧、邊（取消弧的方向）、有向圖、無向圖、鏈、道路、環(huán)、連通圖、連通子圖、次 1 2 3 4 1 2 3 4 1 2 3 4 5 2 1 3 次 道路 頂點 無向圖 鏈 有向圖 弧 環(huán) 連通圖 弧是由一對有序的頂點組成，表示了兩個頂點之間可能運動的方向 連通子圖 由頂點集和弧 組成的圖稱為有向圖 由頂點集和邊組成的圖稱為 無向圖 鏈有一序列弧，如果每一個弧與前一個弧恰有一個公共頂點，則稱這一序列弧為一個鏈。 道路 如果鏈中每一個弧的終點是下面一個弧的起點，則這個鏈稱為一個道路。 環(huán) 連接 a點與 b點的一條鏈，如果 a與 b是同一個點時，稱此鏈為環(huán)。 連通圖 一個圖中任意兩點間至少有一個鏈相連，則稱此圖為連通圖。 任何一個不連通圖都可以分為若干個連通子圖，每一個子圖稱為原圖的一個分圖。 次 : 以 a點為頂點的邊的條數(shù)稱為頂點的次 圖 65 例： 設 V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}, 畫出 G = (V, E ) 的圖 。 或 二、網(wǎng)絡 ? 點或邊帶有某種數(shù)量指標的圖叫 網(wǎng)絡圖 ，簡稱 網(wǎng)絡 。 ? 與點或邊有關(guān)的某些數(shù)量指標，我們經(jīng)常稱之為 權(quán) ，權(quán)可以代表如距離、費用、容量等。 左圖可以看作： ? 從發(fā)電廠（節(jié)點 1）向某城市（節(jié)點 6）輸送電力，必須通過中轉(zhuǎn)站（節(jié)點 2， 3， 4， 5）轉(zhuǎn)送，邊上數(shù)字代表兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。 ? 一個輸油管道網(wǎng)。節(jié)點 1表示管道的起點，節(jié)點 6表示管道的終點，節(jié)點 2到 5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過的最大輸送量。應怎樣安排輸油線路，使從節(jié)點 1到節(jié)點 6的總輸送量最大？ ? 一張城市分布圖。現(xiàn)在要在各城市之間架設電話線，應如何架設，使各城市之間既能通話，又使總的架設路線最短？ 1325464332322第二節(jié) 樹 ? 定義 1（樹的定義） ? 連通且不含環(huán)的無向圖稱為 樹 。 ? 例 1 某工廠的組織機構(gòu)如下所示 工廠組織機構(gòu)圖 樹的性質(zhì) ： ? 任意兩頂點之間必有一條且僅有一條鏈。 ? 去掉任一條邊，則樹成為不連通圖。 ? 不相鄰的兩個頂點間添上一條邊，恰好得到一個環(huán)。 部分圖、生成子圖、部分樹 部分圖 如果 V1? V， E1 ? E則稱 G1為 (全部頂點和部分邊 )G的部分圖； 設 G=(V， E)和 G1=(V1， E1) 部分圖、生成子圖、部分樹 部分圖 生成子圖 設 G=(V， E)和 G1=(V1， E1) 如果 G1=(V1， E1)，
教學課件相關(guān)推薦
鄂ICP備17016276號-1