圖與網(wǎng)絡(luò)模型及方法

圖與網(wǎng)絡(luò)模型及方法 圖與子圖圖的連通與割集樹與支撐樹最小樹最短有向路最大流最小費(fèi)用流最大對集 圖與網(wǎng)絡(luò)無向圖的基本概念網(wǎng)絡(luò)的基本概念關(guān)聯(lián)矩陣和鄰接矩陣關(guān)聯(lián)矩陣鄰接矩陣主要結(jié)論子圖 緒論 圖論起源于18世紀(jì) 第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的 哥尼斯堡的七座橋 1847年 克?；舴?yàn)榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了 樹 的概念 1857年 凱萊在計(jì)數(shù)烷n2n 2CH的同分異構(gòu)物時 也發(fā)現(xiàn)了 樹 哈密爾頓于1859年提出 周游世界 游戲 用圖論的術(shù)語 就是如何找出一個連通圖中的生成圈 緒論 近幾十年來 由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展 大大地促進(jìn)了圖論研究和應(yīng)用 圖論的理論和方法已經(jīng)滲透到物理 化學(xué) 通訊科學(xué) 建筑學(xué) 運(yùn)籌學(xué) 生物遺傳學(xué) 心理學(xué) 經(jīng)濟(jì)學(xué) 社會學(xué)等學(xué)科中 緒論 圖論中所謂的 圖 是指某類具體事物和這些事物之間的聯(lián)系 如果我們用點(diǎn)表示這些具體事物 用連接兩點(diǎn)的線段 直的或曲的 表示兩個事物的特定的聯(lián)系 就得到了描述這個 圖 的幾何形象 圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型 借助于圖論的概念 理論和方法 可以對該模型求解 哥尼斯堡七橋問題 這個圖是連通的 且每個點(diǎn)都與偶數(shù)線相關(guān)聯(lián) 緒論 圖與網(wǎng)絡(luò)是運(yùn)籌學(xué) OperationsResearch 中的一個經(jīng)典和重要的分支 所研究的問題涉及經(jīng)濟(jì)管理 工業(yè)工程 交通運(yùn)輸 計(jì)算機(jī)科學(xué)與信息技術(shù) 通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域的最短路問題 最大流問題 最小費(fèi)用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題 圖 由若干個點(diǎn)和連接這些點(diǎn)的連線所組成的圖形 vi 圖中的點(diǎn) 稱為頂點(diǎn) 代表具體事物 研究對象 ei 圖中的連線 稱為邊 對象之間的聯(lián)系 m G E G的邊數(shù) 簡記為m n G V G的頂點(diǎn)數(shù) 簡記為n 一 圖的概念 記V vi 點(diǎn)的集合 E ei 邊的集合 G V E G 一個圖 m 6 n 5 圖的基本概念 有向圖 無向圖 邊e vi vj 有方向vi為始點(diǎn) vj為終點(diǎn) 邊e vi vj 無方向 此時 vi vj vj vi e4 v3 v4 v4 v3 e4 v3 v4 v4 v3 e5 v3 v4 v4 v3 此時 vi vj vj vi e5 v4 v3 v3 v4 圖 有向圖 無向圖 二 常用名詞 1 端點(diǎn)和關(guān)聯(lián)邊 2 相鄰點(diǎn)和相鄰邊 3 多重邊與環(huán) 4 多重圖和簡單圖 無環(huán)也無多重邊的圖稱為簡單圖 含有多重邊的圖稱為多重圖 5 次 6 懸掛點(diǎn)和懸掛邊 次為1的點(diǎn)稱為懸掛點(diǎn) 與懸掛點(diǎn)相聯(lián)的邊稱為懸掛邊 7 孤立點(diǎn) 8 奇點(diǎn)與偶點(diǎn) G的邊數(shù)m 6 性質(zhì)1 在圖G V E 中 所有點(diǎn)的次之和是邊數(shù)m的兩倍 證明 由于每條邊均與兩個頂點(diǎn)關(guān)聯(lián) 因此在計(jì)算頂點(diǎn)的次時每條邊都計(jì)算了兩遍 所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的二倍 三 次 度 的性質(zhì) 性質(zhì)2 在任何圖G V E 中 奇點(diǎn)的個數(shù)為偶數(shù) 證明 設(shè)V1 V2分別是圖G中奇點(diǎn)和偶點(diǎn)的集合 則V1 V2 V V1 V2 有性質(zhì)1 因?yàn)閂2是偶點(diǎn)的集合 d vi i V2 均為偶數(shù) 所以 只有偶數(shù)個奇數(shù)相加才能得到偶數(shù) 所以V1中的點(diǎn) 即奇點(diǎn)的個數(shù)為偶數(shù) 四 鏈 路 連通圖 1 鏈 對于無向圖G V E 若圖G中有一個點(diǎn)與邊的交替序列 vi0 ei1 vi1 ei2 vik 1 eik vik 且eit vit 1 vit t 1 2 k 則稱該交替序列 為連結(jié)vi0和vik的一條鏈 簡單鏈 中只有重復(fù)的點(diǎn)而無重復(fù)邊者為簡單鏈 初等鏈 中沒有重復(fù)的點(diǎn)和重復(fù)邊者為初等鏈 圈 無向圖G中 連結(jié)vi0與vik的一條鏈 當(dāng)vi0與vik是同一個點(diǎn)時 稱此鏈為圈 圈中只有重復(fù)點(diǎn)而無重復(fù)邊者為簡單圈 既 除起點(diǎn) 終點(diǎn)重復(fù)外 無重復(fù)點(diǎn)也無重復(fù)邊者為初等圈 不是鏈 初等鏈 簡單鏈 簡單圈 初等圈 2路 在有向圖D V A 中 若有從vi0到vik不考慮方向的鏈 且各邊方向一致 則稱之為從vi0到vik的一條路 對于有向圖可以類似于無向圖定義鏈和圈 初等鏈 圈 簡單鏈 圈 此時不考慮邊的方向 而當(dāng)鏈 圈 上的邊方向相同時 稱為道路 回路 對于無向圖來說 道路與鏈 回路與圈意義相同 3連通圖 一個圖中任意兩點(diǎn)間至少有一條鏈 或路 相連的圖 連通圖 非連通圖 五 網(wǎng)絡(luò)在實(shí)際問題中 往往只用圖來描述所研究對象之間的關(guān)系還不夠 與圖聯(lián)系在 起的 通常還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo) 通常稱之為 權(quán) 權(quán)可以代表如距離 費(fèi)用 通過能力 容量 等等 這種帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò) 賦權(quán)圖 如公路交通圖 vi表示城市 ei表示公路w ei 表示公路ei的長度 如w e2 50表示城市v2與城市v3之間的距離是50千米 六 完全圖 偶圖 1 完全圖 一個簡單圖 若任意兩個頂點(diǎn)之間均有一條邊相連 則稱這樣的圖為完全圖 對于完全圖 由于每個頂點(diǎn)與所有其余頂點(diǎn)都有一條邊相連 所以在有n個頂點(diǎn)的完全圖中 各個頂點(diǎn)的次均為 n 1 2 偶圖 若圖G的頂點(diǎn)能分成兩個互不相交的非空集合V1和V2 使在同一集合中的任意兩個頂點(diǎn)均不相鄰 稱這樣的圖為偶圖 也稱為二部圖 若偶圖的頂點(diǎn)集合V1 V2之間的每一對不同頂點(diǎn)都有一條邊相連 稱這樣的圖為完全偶圖 v2 v3 v4 v5 v2 v3 v4 v5 v1 v1 完全圖 完全 偶圖 定理一個圖為偶圖的充分必要條件該圖無奇圈 七 子圖 部分圖對于圖G1 V1 E1 和圖G2 V2 E2 若有 稱G1是G2的一個子圖 若有 稱G1是G2的一個部分圖 生成子圖 部分圖也是子圖 但子圖不一定是部分圖 生成子圖 七 子圖 部分圖 部分圖也是子圖 但子圖不一定是部分圖 生成子圖 對于圖G1 V1 E1 和圖G2 V2 E2 若有 稱G1是G2的一個子圖 若有 稱G1是G2的一個部分圖 生成子圖 八 前向弧與后向弧設(shè) 是一條從vs到vt的鏈 則鏈 上與鏈的方向一致的弧稱為前向弧 記這些弧為 鏈 上與鏈的方向相反的弧稱為后向弧 記這些弧為 vs v1 v2 v3 v4 v5 vt 前向弧與后向弧 子圖設(shè)G1 V1 E1 G2 V2 E2 子圖定義 如果V2 V1 E2 E1稱G2是G1的子圖 真子圖 如果V2 V1 E2 E1稱G2是G1的真子圖 部分圖 如果V2 V1 E2 E1稱G2是G1的部分圖 導(dǎo)出子圖 如果V2 V1 E2 vi vj vi vj V2 稱G2是G1中由V2導(dǎo)出的導(dǎo)出子圖 九 圖的矩陣表示用矩陣表示圖對研究圖的性質(zhì)及應(yīng)用常常是比較方便的 定義 網(wǎng)絡(luò) 賦權(quán)圖 G V E 其邊 vi vj 有權(quán) ij 構(gòu)造矩陣A aij n n 其中 稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣 例 寫出下圖的權(quán)矩陣 v1 v2 v3 v4 v5 7 6 5 4 2 4 9 3 8 定義 對于圖G V E V n 構(gòu)造一個矩陣A aij n n 其中 稱矩陣A為圖G的鄰接矩陣 例 寫出下圖的鄰接矩陣 v1 v3 v5 v2 v4 v6 當(dāng)G為無向圖時 鄰接矩陣為對稱矩陣 最短軌道問題 給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò) 在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間 找一條最短鐵路線 以各城鎮(zhèn)為圖G的頂點(diǎn) 兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點(diǎn)間的邊 得圖G 對G的每一邊e 賦以一個實(shí)數(shù)w e 直通鐵路的長度 稱為e的權(quán) 得到賦權(quán)圖G G的子圖的權(quán)是指子圖的各邊的權(quán)和 問題就是求賦權(quán)圖G中指定的兩個頂點(diǎn)u0 v0間的具最小權(quán)的軌 這條軌叫做u0 v0間的最短路 它的權(quán)叫做u0 v0間的距離 亦記作d u0 v0 最短軌道問題求法 Dijkstra算法 基本思想是按距u0從近到遠(yuǎn)為順序 依次求得u0到G的各頂點(diǎn)的最短路和距離 直至v0 或直至G的所有頂點(diǎn) 算法結(jié)束 為避免重復(fù)并保留每一步的計(jì)算信息 采用了標(biāo)號算法 最短軌道問題求法 Dijkstra算法 定義 連通且不含圈的無向圖稱為樹 記作T V E 二 樹 樹可以有很多等價的定義 以下定理中的各命題都體現(xiàn)樹的特征 定理設(shè)G V E 是一無向圖 V n E m 則以下命題是等價的 1 G是樹 2 G的每對頂點(diǎn)之間有唯一的一條路 3 G連通且m n 1 4 G無圈且m n 1 5 G無圈 在G的任一對頂點(diǎn)上加一新邊后產(chǎn)生圈 6 G連通 但刪去任何一邊后不再連通 定理 無向圖G有生成樹當(dāng)且僅當(dāng)G連通 證明 必要性顯然 只證充分性 若G無圈 則G本身就是G的生成樹 若G有圈C 則在G中刪去C的一條邊 所得的圖是連通的 繼續(xù)這個過程 直到所得的圖T無圈為止 則T就是G的一棵生成樹 定義 若圖G的生成子圖是一棵樹 則稱該樹為G的生成樹 支撐樹 或簡稱為圖G的樹 b 為 a 圖的生成樹 最小生成樹的求法 避圈法與破圈法 定義 樹的各條邊稱為樹枝 一般圖G的生成樹有多個 稱其中樹枝總長度最小的生成樹為最小樹 避圈法 在圖G中 每步選出一條邊e 使它與已選邊不構(gòu)成圈 且e是未選邊中長度最小的邊 直到選夠n 1邊為止 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 1 1 2 1 1 2 3 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 v1 v2 v3 v8 v7 v6 v5 v4 v0 1 1 2 1 1 2 3 2 破圈法 從網(wǎng)絡(luò)圖N中任取一回路 去掉該回路中權(quán)數(shù)最大的一條邊 得一子網(wǎng)絡(luò)圖N1 在N1中再任取一回路 去掉該回路中權(quán)數(shù)最大的一條邊 得一子網(wǎng)絡(luò)圖N2 如此繼續(xù)下去 直到剩下的子圖中不再含回路為止 該子圖就是N的最小生成樹 v1 v2 v3 v8 v7 v6 v5 v4 v0 4 1 1 2 1 3 1 4 4 4 5 2 3 5 5 2 筑路選線問題 欲修筑連接n個城市的鐵路 已知i城與j城之間的鐵路造價為wij 設(shè)計(jì)一個線路圖使總造價最低連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹 賦權(quán)圖的具最小權(quán)的生成樹叫做最小生成樹造最小生成樹的兩種常用算法 prim算法與Kruskal算法 prim算法構(gòu)造最小生成樹 設(shè)置兩個集合P和Q 其中P用于存放G的最小生成樹中的頂點(diǎn) 集合Q存放G的最小生成樹中的邊 令集合P的初值為 1P v 假設(shè)構(gòu)造最小生成樹時 從頂點(diǎn)v1出發(fā) 集合Q的初值為Q prim算法的思想是 從所有p P v V P的邊中 選取具有最小權(quán)值的邊pv 將頂點(diǎn)v加入集合P中 將邊pv加入集合Q中 如此不斷重復(fù) 直到P V時 最小生成樹構(gòu)造完畢 這時集合Q中包含了最小生成樹的所有邊 Kruskal算法構(gòu)造最小生成樹 可行遍問題 定義1 經(jīng)過G的每條邊的跡叫做G的Euler跡 閉的Euler跡叫做Euler回路或E回路 含Euler回路的圖叫做Euler圖 直觀地講 Euler圖就是從一頂點(diǎn)出發(fā)每邊恰通過一次能回到出發(fā)點(diǎn)的那種圖 即不重復(fù)地行遍所有的邊再回到出發(fā)點(diǎn) 定理6 i G是Euler圖的充分必要條件是G連通且每頂點(diǎn)皆偶次 ii G是Euler圖的充分必要條件是G連通且 iii G中有Euler跡的充要條件是G連通且至多有兩個奇次點(diǎn) 定義包含G的每個頂點(diǎn)的軌叫做Hamilton 哈密頓 軌 閉的Hamilton軌叫做Hamilton圈或H圈 含Hamilton圈的圖叫做Hamilton圖 直觀地講 Hamilton圖就是從一頂點(diǎn)出發(fā)每頂點(diǎn)恰通過一次能回到出發(fā)點(diǎn)的那種圖 即不重復(fù)地行遍所有的頂點(diǎn)再回到出發(fā)點(diǎn) Euler回路的Fleury算法 可行遍問題的應(yīng)用 中國郵遞員問題一位郵遞員從郵局選好郵件去投遞 然后返回郵局 當(dāng)然他必須經(jīng)過他負(fù)責(zé)投遞的每條街道至少一次 為他設(shè)計(jì)一條投遞路線 使得他行程最短 中國郵遞員問題的數(shù)學(xué)模型 在一個賦權(quán)連通圖上求一個含所有邊的回路 且使此回路的權(quán)最小 若此連通賦權(quán)圖是Euler圖 則可用Fleury算法求Euler回路 此回路即為所求 對于非Euler圖 1973年 Edmonds和Johnson給出下面的解法 多郵遞員問題 郵局有k k 2 位投遞員 同時投遞信件 全城街道都要投遞 完成任務(wù)返回郵局 如何分配投遞路線 使得完成投遞任務(wù)的時間最早 我們把這一問題記成kPP kPP的數(shù)學(xué)模型如下 旅行商 TSP 問題 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品 然后回到他的出發(fā)地 如何為他設(shè)計(jì)一條最短的旅行路線 從駐地出發(fā) 經(jīng)過每個城市恰好一次 最后返回駐地 是在一個賦權(quán)完全圖中 找出一個有最小權(quán)的Hamilton圈 稱這種圈為最優(yōu)圈與最短路問題及連線問題相反 目前還沒有求解旅行商問題的有效算法 所以希望有一個方法以獲得相當(dāng)好 但不一定最優(yōu) 的解 改良圈算法 旅行商問題的數(shù)學(xué)表達(dá)式 對集 1957年 貝爾熱 Berge 得到最大對集的充要條件 定理2M是圖G中的最大對集當(dāng)且僅當(dāng)G中無M可增廣軌 1935年 霍爾 Hall 得到下面的許配定理 定理3G為二分圖 X與Y是頂點(diǎn)集的劃分 G中存在把X中頂點(diǎn)皆許配的對集的充要條件是 S X 則 N S S 其中N S 是S中頂點(diǎn)的鄰集 推論1 若G是k次 k 0 正則2分圖 則G有完美對集 所謂k次正則圖 即每頂點(diǎn)皆k度的圖 由此推論得出下面的婚配定理 定理4每個姑娘都結(jié)識k k 1 位小伙子 每個小伙子都結(jié)識k位姑娘 則每位姑娘都能和她認(rèn)識的一個小伙子結(jié)婚 并且每位小伙子也能和他認(rèn)識的一個姑娘結(jié)婚 人員分派問題 工作人員x1 x2 xn去做n件工作y1 y2 yn 每人適合做其中一件或幾件 問能否每人都有一份適合的工作 如果不能 最多幾人可以有適合的工作 這個問題的數(shù)學(xué)模型是 G是二分圖 頂點(diǎn)集劃分為V G XUY X x1 xn Y y1 yn 當(dāng)且僅當(dāng)xi適合做工作yj時 xiyj E G 求G中的最大對集 人員分派問題匈牙利算法 1965年埃德門茲 Edmonds 提出匈牙利算法 匈牙利算法 i 從G中任意取定一個初始對集M ii 若M把X中的頂點(diǎn)皆許配 停止 M即完美對集 否則取X中未被M許配的一頂點(diǎn)u 記S u T iii 若N S T 停止 無完美對集 否則取y N S T iv 若y是被M許配的 設(shè)yz M S SU z T TU y 轉(zhuǎn) iii 否則 取可增廣軌P u y 令M M E P U E P M 轉(zhuǎn) ii 最優(yōu)分派問題 在人員分派問題中 工作人員適合做的各項(xiàng)工作當(dāng)中 效益未必一致 我們需要制定一個分派方案 使公司總效益最大 這個問題的數(shù)學(xué)模型是 在人員分派問題的模型中 圖G的每邊加了權(quán)w xi yj 0表示xi干yj工作的效益 求加權(quán)圖G上的權(quán)最大的完美對集 解決這個問題可以用庫恩 曼克萊斯 Kuhn Munkres 算法 定義若映射l V G R 滿足 x X y Y l x l y w x y 則稱l是二分圖G的可行頂點(diǎn)標(biāo)號 令El xy xy E G l x l y w xy 稱以lE為邊集的G的生成子圖為相等子圖 記作Gl 可行頂點(diǎn)標(biāo)號是存在的 例如 定理5Gl的完美對集即為G的權(quán)最大的完美對集 Kuhn Munkres算法 最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一 許多優(yōu)化問題可以便用這個模型 如設(shè)備更新 管道鋪設(shè) 線路安排 廠區(qū)布局等 最短路問題的一般提法 設(shè)G V E 為連通圖 圖中各邊 vi vj 有權(quán)l(xiāng)ij lij 表示vi vj間無邊 vs vt為圖中任意兩點(diǎn) 求一條路 使它是從vs到vt的所有路中總權(quán)最小的路 即 最小 有些最短路問題是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有點(diǎn)的最短路 或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路 下面介紹三種算法 可分別用于求解這幾種最短路問題 2 使用條件 網(wǎng)絡(luò)中所有的弧 邊 權(quán)均非負(fù) 即 1 基本思路基于以下原理 若序列 vs v1 vn 1 vn 是從vs到vn的最短路 則序列 vs v1 vn 1 必為從vs到vn 1的最短路 1 Dijkstra算法本算法由Dijkstra于1959年提出 可用于求解指定兩點(diǎn)vs vt間的最短路 或從指定點(diǎn)vs到其余各點(diǎn)的最短路 下面給出Dijkstra算法基本步驟 采用標(biāo)號法 可用兩種標(biāo)號 T標(biāo)號與P標(biāo)號 T標(biāo)號為試探性標(biāo)號 P為永久性標(biāo)號 給vi點(diǎn)一個P標(biāo)號時 表示從vs到點(diǎn)vi的最短路權(quán) vi點(diǎn)的標(biāo)號不再改變 給vi點(diǎn)一個T標(biāo)號時 表示從vs到點(diǎn)vi的估計(jì)最短路權(quán)的上界 是一種臨時標(biāo)號 凡沒有得到P標(biāo)號的點(diǎn)都有T標(biāo)號 算法每一步都把某一點(diǎn)的T標(biāo)號改為P標(biāo)號 當(dāng)終點(diǎn)vt得到P標(biāo)號時 全部計(jì)算結(jié)束 對于有n個頂點(diǎn)的圖 最多經(jīng)n一1步就可以得到從始點(diǎn)到終點(diǎn)的最短路 標(biāo)號的意義 標(biāo)號P 永久性標(biāo)號 從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán) 標(biāo)號T 臨時性標(biāo)號 從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)上界 計(jì)算步驟 第二步 若vi為剛得到P標(biāo)號的點(diǎn) 考慮這樣的點(diǎn)vj vi vj 屬于E 且vj為T標(biāo)號 對vj的T標(biāo)號進(jìn)行如下的更改 T vj min T vj P vi lij 第三步 比較所有具有T標(biāo)號的點(diǎn) 把最小者改為P標(biāo)號 即 第一步 給始點(diǎn)vs標(biāo)上永久性標(biāo)號P vs 0 其余各點(diǎn)標(biāo)臨時性標(biāo)號T vj 當(dāng)存在兩個以上最小者時 可同時改為P標(biāo)號 若全部點(diǎn)均為P標(biāo)號則停止 否則用代vi轉(zhuǎn)回第二步 例 用Dijkstar算法求下圖中v1到v7點(diǎn)的最短路 v1 v3 v2 v7 v5 v4 v6 1 7 1 3 4 4 4 5 2 5 7 2 1 首先給v1以P標(biāo)號 P v1 0 其余所有點(diǎn)給T標(biāo)號 T vi 圖中 內(nèi)的數(shù)表示P標(biāo)號 內(nèi)的數(shù)表示T標(biāo)號 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 v6 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 5 2 由于邊 v1 v2 v1 v3 v1 v4 屬于E 且v2 v3 v4為T標(biāo)號 所以修改這三個點(diǎn)的標(biāo)號 T v2 min T v2 P v1 l12 min 0 4 4T v3 min T v3 P v1 l13 min 0 2 2T v4 min T v4 P v1 l14 min 0 5 5 7 3 比較所有T標(biāo)號 T v3 最小 所以令P v3 2 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 5 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 4 9 7 4 v3為剛得到P標(biāo)號的點(diǎn) 考察邊 v3 v4 v3 v6 的端點(diǎn)v4 v6 T v4 min T v4 P v3 l34 min 5 2 2 4T v6 min T v6 P v3 l36 min 2 7 9 5 比較所有T標(biāo)號 T v2 T v4 最小 所以令P v2 P v4 4 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 v3 2 v6 4 4 9 7 6 v2 v4為剛得到P標(biāo)號的點(diǎn) 考察邊 v2 v5 v4 v5 v4 v6 的端點(diǎn)v5 v6 T v5 min T v5 P v4 l45 P v2 l25 min 4 3 4 4 7T v6 min T v6 P v4 l46 min 9 4 4 8 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 8 7 7 v3 2 v6 7 比較所有T標(biāo)號 T v5 所以令P v5 7 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 8 v3 2 v6 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 14 8 v3 2 v6 8 v5為剛得到P標(biāo)號的點(diǎn) 考察邊 v5 v6 v5 v7 的端點(diǎn)v6 v7 T v6 min T v6 P v5 l56 min 8 7 1 8T v7 min T v7 P v5 l57 min 7 7 14 7 7 9 比較所有T標(biāo)號 T v6 最小 所以令P v6 8 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 14 8 v3 2 v6 10 v6為剛得到P標(biāo)號的點(diǎn) 考察邊 v6 v7 的端點(diǎn)v7 T v7 min T v7 P v6 l67 min 14 8 5 13 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 13 8 v3 2 v6 7 7 11 只有一個T標(biāo)號T v7 令P v7 13 停止 v1 0 v2 v7 v5 v4 1 1 3 4 4 4 5 2 5 7 2 4 4 7 13 8 v3 2 v6 7 計(jì)算結(jié)果見上圖 v1到v7的最短路為 同時得到v1到其余各點(diǎn)的最短路 這個算法只適用于全部權(quán)為非負(fù)情況 如果某邊的權(quán)為負(fù) 算法失效 上面的例題是針對無向圖求最短路的問題 對有向圖最短路的求法類似 下面以設(shè)備更新問題為例說明有向圖最短路的計(jì)算方法 例 設(shè)備更新問題 某企業(yè)在四年內(nèi)都要使用某種設(shè)備 在每年年初作出是購買新設(shè)備還是繼續(xù)使用舊設(shè)備的決策 若購買新設(shè)備就要支付購置費(fèi) 若繼續(xù)使用舊設(shè)備 則需支付維修費(fèi)用 這種設(shè)備在四年之內(nèi)每年年初的價格以及使用不同時間 年 的設(shè)備的維修費(fèi)用估計(jì)為 問題 制定一個四年之內(nèi)的設(shè)備更新計(jì)劃 使得四年之內(nèi)的設(shè)備購置費(fèi)和維修費(fèi)用之和最小 可以用求最短路問題的方法來解決總費(fèi)用最少的設(shè)備更新計(jì)劃問題 符號的含義 vi 第i年年初購進(jìn)一臺新設(shè)備 v5表示第四年年底 弧 vi vj 表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初 即第j 1年年底 弧 vi vj 的權(quán)數(shù)表示從第i年年初購進(jìn)的設(shè)備一直使用到第j年年初所花費(fèi)的購置費(fèi)和維修費(fèi)用的總和 如何制定使得總費(fèi)用最少的設(shè)備更新計(jì)劃問題可以轉(zhuǎn)化最短路問題 此最短路問題如圖所示 圖中權(quán)數(shù) ij的確定 12 10 2 12 13 10 2 4 16 14 10 2 4 7 23 15 10 2 4 7 14 37 23 11 2 13 24 11 2 4 17 25 11 2 4 7 24 34 12 2 14 35 12 2 4 18 45 13 2 15 下面用Dijkstra算法求v1到v5的最短路 給v1以P標(biāo)號 P v1 0 其余各點(diǎn)給以T標(biāo)號 T vi i 2 3 4 5 圖中 內(nèi)的數(shù)表示P標(biāo)號 內(nèi)的數(shù)表示T標(biāo)號 2 由于 v1 v2 v1 v3 v1 v4 v1 v5 A 且v2 v3 v4 v5為T標(biāo)號 所以修改這四個點(diǎn)的標(biāo)號 T v2 min T v2 P v1 12 min 0 12 12T v3 min T v3 P v1 13 min 0 16 16T v4 min T v4 P v1 14 min 0 23 23T v5 min T v5 P v1 15 min 0 37 37 3 比較所有具有T標(biāo)號的點(diǎn) 把最小者改為P標(biāo)號 T v2 最小 令P v2 12 4 v2為剛得到P標(biāo)號的點(diǎn) 考察弧 v2 v3 v2 v4 v2 v5 的端點(diǎn)v3 v4 v5 T v3 min T v3 P v2 23 min 16 12 13 16T v4 min T v4 P v2 24 min 23 12 17 23T v5 min T v5 P v2 25 min 37 12 24 36 5 比較所有具有T標(biāo)號的點(diǎn) 把最小者改為P標(biāo)號 T v3 最小 令P v3 16 6 考察點(diǎn)v3T v4 min T v4 P v3 34 min 23 16 14 23T v5 min T v5 P v3 35 min 36 16 18 34 7 所有T標(biāo)號中 T v4 最小 令P v4 23 8 考察點(diǎn)v4T v5 min T v5 P v4 45 min 34 23 15 34 9 只有一個T標(biāo)號T v5 令P v5 34 計(jì)算結(jié)束 由上可知 v1到v5的最短路為v1 v3 v5 長度為34 其含義為 最佳更新計(jì)劃為第一年年初購買新設(shè)備使用到第二年年底 第三年年初 第三年年初再購買新設(shè)備使用到第四年年底 這個計(jì)劃使得總的支付最小 其值為34 v1 v3 v2 v7 v5 v4 v6 1 7 1 3 4 4 5 2 5 7 2 練習(xí) 求下圖中任意兩點(diǎn)間的最短路 4 例 某地7個村莊之間的現(xiàn)有交通道路如下圖所示 邊旁數(shù)字為各村莊之間道路的長度 現(xiàn)要在某一村莊修建一所小學(xué) 該小學(xué)應(yīng)建在哪個村莊 可使離該村最遠(yuǎn)的村莊的學(xué)生所走的路程最少 該問題可分作兩步來考慮 1 求出任意兩個村莊之間的最短路長 2 找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn) 大中取小即可 首先寫出權(quán)矩陣 用Floyd算法求出任意兩點(diǎn)之間的最短路的長度 找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn)取這些最遠(yuǎn)距離中的最小者 小學(xué)應(yīng)建在v4村 max 作業(yè) P227習(xí)題4 4 覆蓋與點(diǎn)獨(dú)立集 最大流問題 最大流問題是在一個給定網(wǎng)絡(luò)上求流量最大的可行流 即給一個網(wǎng)絡(luò)的每條弧規(guī)定一個流量的上界 求從點(diǎn)vs到vt的最大流 下圖是一個輸油管道網(wǎng) vs為起點(diǎn) vt為終點(diǎn) v1 v6為中轉(zhuǎn)站 弧旁的數(shù)表示該管道的最大輸油量 問題 如何安排 才能使從vs到vt的輸油量最大 最大流問題1最大流問題的數(shù)學(xué)描述1 1網(wǎng)絡(luò)中的流定義在以V為節(jié)點(diǎn)集 A為弧集的有向圖G V A 上定義如下的權(quán)函數(shù) i L A R為孤上的權(quán)函數(shù) 弧 i j A對應(yīng)的權(quán)L i j 記為lij 稱為孤 i j 的容量下界 lowerbound ii U A R為弧上的權(quán)函數(shù) 弧 i j A對應(yīng)的權(quán)U i j 記為uij 稱為孤 i j 的容量上界 或直接稱為容量 capacity iii D V R為頂點(diǎn)上的權(quán)函數(shù) 節(jié)點(diǎn)i V對應(yīng)的權(quán)D i 記為di 稱為頂點(diǎn)i的供需量 supply demand 此時所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò) 可以記為N V A L U D 由于我們只討論V A為有限集合的情況 所以對于弧上的權(quán)函數(shù)L U和頂點(diǎn)上的權(quán)函數(shù)D 可以直接用所有孤上對應(yīng)的權(quán)和頂點(diǎn)上的權(quán)組成的有限維向量表示 因此L U D有時直接稱為權(quán)向量 或簡稱權(quán) 由于給定有向圖G V A 后 我們總是可以在它的弧集合和頂點(diǎn)集合上定義各種權(quán)函數(shù) 所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò) 定義對于流網(wǎng)絡(luò)N V A L U D 其上的一個流 flow f是指從N的弧集A到R的一個函數(shù) 即對每條弧 i j 賦予一個實(shí)數(shù)fij 稱為弧 i j 的流量 如果流f滿足則稱f為可行流 feasibleflow 至少存在一個可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò) feasiblenetwork 約束 1 稱為流量守恒條件 也稱流量平衡條件 約束 2 稱為容量約束 定義 設(shè)有向連通圖G V E G的每條邊 vi vj 上有非負(fù)數(shù)cij稱為邊的容量 僅有一個入次為0的點(diǎn)vs稱為發(fā)點(diǎn) 源 一個出次為0的點(diǎn)vt稱為收點(diǎn) 匯 其余點(diǎn)為中間點(diǎn) 這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò) 常記做G V E C 對任一G中的邊 vi vj 有流量fij 稱集合f fij 網(wǎng)絡(luò)G上的一個流 稱滿足下列條件的流f為可行流 1 容量限制條件 對G中每條邊 vi vj 有0 fij cij 2 平衡條件 對中間點(diǎn)vi 即中間點(diǎn)vi的物資的輸入量與輸出量相等 對收 發(fā)點(diǎn)vs vt 有 即從vs點(diǎn)發(fā)出的物資總量等于vt點(diǎn)輸入的量 W為網(wǎng)絡(luò)流的總流量 可行流總是存在的 例如f 0 就是一個流量為0的可行流 最大流問題就是在容量網(wǎng)絡(luò)中 尋找流量最大的可行流 一個流f fij 當(dāng)fij cij 則稱流f對邊 vi vj 是飽和的 否則稱f對 vi vj 不飽和 根據(jù)弧的流量是否為0 可把弧分為零流弧和非零流弧兩類 最大流問題實(shí)際是個線性規(guī)劃問題 但是利用它與圖的緊密關(guān)系 能更為直觀簡便地求解 把網(wǎng)絡(luò)D V E C 的點(diǎn)集V剖分為兩個非空集合Vs和Vt 即Vs Vt Vs Vt V 使vs Vs vt Vt 把從Vs指向Vt的弧的全體稱為 分離vs和vt的 截集 稱截集中所有弧的容量之和為這個截集的容量 簡稱為截量 分離vs和vt的截集往往不只一個 稱其中截量最小的為最小截集 由截集的定義可知 截集是從vs到vt的必經(jīng)之路 無論去掉哪個截集 從vs到vt就不存在路了 因此任何一個可行流的流量不會超過任何一個截集的容量 因而若能找到一個可行流和一個截集 使得可行流的流量等于這個截集的容量 則該可行流一定是最大流 該截集一定是最小截集 在上圖中 若令Vs vs v1 v6 Vt v2 v3 v4 v5 vt 則 截集為 vs v5 v1 v2 v1 v5 v6 v5 v6 v4 截量為3 2 4 2 3 14 設(shè) 是網(wǎng)絡(luò)中從vs到vt的一條鏈 給 定向?yàn)閺膙s到vt 沿此方向 上的弧可分為兩類 一類是與鏈的方向一致的弧稱為正向弧 用 表示正向弧的全體 另一類是與鏈的方向相反的弧稱為反向弧 用 表示反向弧的全體 在上圖中 在鏈 vs v5 v6 v4 v3 vt 中 vs v5 v6 v4 v3 vt v5 v6 v4 v3 增廣鏈 對于可行流f 是一條從vs到vt的一條鏈 如果 中的弧均為非飽和弧 中的弧均為非零流弧 則稱 為從vs到vt的關(guān)于f的增廣鏈 定理 最大流量 最小截量定理 在網(wǎng)絡(luò)N中 從vs到vt的最大流的流量等于分離vs到vt的最小截集的截量 計(jì)算網(wǎng)絡(luò)最大流的方法增廣鏈的實(shí)際意義在于沿著這條鏈存在增大輸送能力的潛力 如沿著增廣鏈 1 vs v2 v5 v4 v6 vt 凡是正向弧的流量都增加1 反向弧的流量都減少1 見上圖 結(jié)果整個網(wǎng)絡(luò)的流增加了1 即由6增加到7 用這種方法調(diào)整后的流仍為可行流 這樣就得到了一個尋找最大流的方法 從一個可行流開始 尋找關(guān)于這個可行流的增廣鏈 若增廣鏈存在 則可以經(jīng)過調(diào)整 得到一個新的可行流 其流量比調(diào)整前的可行流大 重復(fù)這個過程 直到不存在增廣鏈時就得到了最大流 下面介紹計(jì)算網(wǎng)絡(luò)最大流的標(biāo)號算法標(biāo)號法是由Ford和Fulkerson在1957年提出的設(shè)已有一個可行流f 若網(wǎng)絡(luò)中沒有給出可行流 則可設(shè)f為零流 標(biāo)號法可分為兩步 一 標(biāo)號過程在這個過程中 網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號點(diǎn) 或者是未標(biāo)號點(diǎn) 每個標(biāo)號點(diǎn)的標(biāo)號包含兩個部分 第一個標(biāo)號表明它的標(biāo)號是從哪一點(diǎn)得到的 以便找出增廣鏈 第二個標(biāo)號是為確定增廣鏈的調(diào)整量 用的 1 給發(fā)點(diǎn)vs以標(biāo)號 0 第二個數(shù)值表示從上一標(biāo)號點(diǎn)到這個標(biāo)號點(diǎn)的最大允許調(diào)整量 vs為發(fā)點(diǎn) 不限允許調(diào)整量 故為 最大流的一種算法 標(biāo)號法 2 選擇一個已標(biāo)號的點(diǎn)vi 對于vi的所有未標(biāo)號的鄰點(diǎn)vj 按下列規(guī)則處理 若邊 vi vj E 且fij0 則令 vj min fji vi 并給vj以標(biāo)號 vi vj 3 重復(fù) 2 直到收點(diǎn)vt被標(biāo)號或不再有點(diǎn)可標(biāo)號時為止 若vt得到標(biāo)號 說明存在一條增廣鏈 轉(zhuǎn) 二 調(diào)整過程 若vt未得到標(biāo)號 標(biāo)號過程已無法進(jìn)行時 說明f已是最大流 二 調(diào)整過程 1 確定調(diào)整量 vt 2 若vt的標(biāo)號為 vj vt 則以fit 代替fit 若vt的標(biāo)號為 vj vt 則以fit 代替fit 3 令vj代替vt 返回 2 若vj vs 則去掉所有標(biāo)號轉(zhuǎn) 一 標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基本思想 用標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可增廣軌 使網(wǎng)絡(luò)的流量得到增加 直到最大為止 即首先給出一個初始流 這樣的流是存在的 例如零流 如果存在關(guān)于它的可增廣軌 那么調(diào)整該軌上每條弧上的流量 就可以得到新的流 對于新的流 如果仍存在可增廣軌 則用同樣的方法使流的值增大 繼續(xù)這個過程 直到網(wǎng)絡(luò)中不存在關(guān)于新得到流的可增廣軌為止 則該流就是所求的最大流 標(biāo)號法過程 A 標(biāo)號過程 通過標(biāo)號過程尋找一條可增廣軌 B 增流過程 沿著可增廣軌增加網(wǎng)絡(luò)的流量 這兩個過程的步驟分述如下 例 用標(biāo)號法求下圖所示的網(wǎng)絡(luò)中從vs到vt的最大流量 圖中弧旁數(shù)值為容量cij 1 圖中沒有給出初始可行流 可設(shè)零流為出初始可行流 如圖1 先給vs標(biāo)以標(biāo)號 0 2 檢查vs的鄰點(diǎn)v1 v2可知 vs v1 E 且fs1 0 cs1 10 令 v1 min 10 0 10 給v1以標(biāo)號 vs 10 用同樣的方法給v2以標(biāo)號 vs 14 見圖2 3 檢查v1的尚未標(biāo)號的鄰點(diǎn)v3 v4可知 v1 v3 E 且f13 0 c13 10 令 v3 min v1 10 0 min 10 10 10 給v3以標(biāo)號 v1 10 用同樣的方法給v4以標(biāo)號 v1 10 4 檢查v3的尚未標(biāo)號的鄰點(diǎn)v5 v6可知 v3 v5 E 且f35 0 c35 4 令 v5 min v3 4 0 min 10 4 4 給v5以標(biāo)號 v3 4 對于v6 由于 v6 v3 E 且f63 0 不滿足標(biāo)號條件 檢查v4的尚未標(biāo)號的鄰點(diǎn)vt可知 v4 vt E 且f4t 0 c4t 13 令 vt min v4 13 0 min 10 13 10 給vt以標(biāo)號 v4 10 5 由于vt已得到標(biāo)號 則存在增廣鏈 標(biāo)號過程結(jié)束 轉(zhuǎn)入調(diào)整過程 令 vt 10為調(diào)整量 從vt開始 按標(biāo)號 v4 10 找到v4并用f4t 10代替f4t 由標(biāo)號 v1 10 找到v1并用f14 10代替f14 再由標(biāo)號 vs 10 找到vs并用fs1 10代替fs1 調(diào)整過程結(jié)束 調(diào)整后的可行流見圖5 去掉所有標(biāo)號 重新開始標(biāo)號過程 圖5 先給vs標(biāo)以標(biāo)號 0 檢查vs的鄰點(diǎn)v1 v2可知 vs v1 E但fs1 10 cs1 10 不滿足標(biāo)號條件 vs v2 E且fs2 0 cs2 14 令 v2 min 14 0 14 給v2以標(biāo)號 vs 14 圖6 v6 5 用同樣的方法可得v6的標(biāo)號 v2 5 vt的標(biāo)號 v6 5 令 5為調(diào)整量 從vt開始進(jìn)行調(diào)整 調(diào)整后的可行流見下圖 去掉所有標(biāo)號 重新開始標(biāo)號過程 0 vs 9 v2 5 不滿足標(biāo)號條件 反向零流弧 v4 3 去掉所有標(biāo)號 重新開始標(biāo)號過程 令 3為調(diào)整量 從vt開始進(jìn)行調(diào)整 調(diào)整后的可行流見下圖 0 v2 2 v3 2 v3 2 v5 2 vs 6 v6 2 令 2為調(diào)整量 從vt開始進(jìn)行調(diào)整 調(diào)整后的可行流見下圖 0 v2 2 v3 2 v3 2 v5 2 vs 6 v6 2 用標(biāo)號法在得到最大流的同時也得到最小截集 如圖中虛線所示 標(biāo)號點(diǎn)集合為VS 即VS vs v2 未標(biāo)號點(diǎn)集合為Vt 即Vt v1 v3 v4 v5 v6 vt 最小截集 vs v1 v2 v3 v2 v6 最小截集的意義 最小截集中各弧的容量總和決定了網(wǎng)絡(luò)的通過能力 為了提高網(wǎng)絡(luò)的通過能力 就必須增大最小截集中弧的容量 去掉所有標(biāo)號 重新開始標(biāo)號過程 0 vs 4 vt未得到標(biāo)號 但標(biāo)號過程已無法進(jìn)行 說明已得到最大流 其值為20 3 5 2 最小費(fèi)用流問題 上面我們介紹了一個網(wǎng)絡(luò)上最短路以及最大流的算法 但是還沒有考慮到網(wǎng)絡(luò)上流的費(fèi)用問題 在許多實(shí)際問題中 費(fèi)用的因素很重要 例如 在運(yùn)輸問題中 人們總是希望在完成運(yùn)輸任務(wù)的同時 尋求一個使總的運(yùn)輸費(fèi)用最小的運(yùn)輸方案 這就是下面要介紹的最小費(fèi)用流問題 4 6最小費(fèi)用流問題 最小費(fèi)用最大流問題 給了一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò) 對每一條弧 vi vj 除了給出容量cij外 還給出了這條弧的單位流量的費(fèi)用bij 要求一個最大流F 并使得總運(yùn)送費(fèi)用最小 最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法較麻煩 因此下面介紹用線性規(guī)劃模型結(jié)合運(yùn)籌學(xué)軟件求解最小費(fèi)用最大流問題例 某石油公司擁有一個管道網(wǎng)絡(luò) 使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn) 這個網(wǎng)絡(luò)的一部分如下圖所示 由于管道的直徑的變化 它的各段管道 vi vj 的容量cij 單位 萬加侖 小時 各段管道單位流量的費(fèi)用為bij 單位 百元 萬加侖 如圖 從采地v1向銷地v7運(yùn)送石油 怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小 求出最大流量和最小費(fèi)用 弧旁括號中第一個數(shù)表示容量cij 第二個數(shù)表示單位流量的費(fèi)用bij 用線性規(guī)劃模型求解該問題 可分為兩個步驟 第一步先求出此網(wǎng)絡(luò)圖中的最大流量F 通過運(yùn)籌學(xué)軟件獲得以下結(jié)果 f12 5 f14 5 f23 2 f25 3 f43 2 f46 1 f47 2 f35 2 f36 2 f57 5 f67 3 最大流量 10 第二步在最大流量F的所有解中 找出一個最小費(fèi)用的解 下面建立第二步中的線性規(guī)劃模型如下 仍然設(shè)弧 vi vj 上的流量為fij 這時已知網(wǎng)絡(luò)中最大流量為F 線性規(guī)劃模型如下 s t 用管理運(yùn)籌學(xué)軟件 可求得如下結(jié)果 f12 4 f14 6 f25 3 f23 1 f43 3 f57 5 f36 2 f46 1 f47 2 f67 3 f35 2 其最優(yōu)值 最小費(fèi)用 145 與前面求最大流的結(jié)果對比 f12 5 f14 5 f23 2 f25 3 f43 2 f46 1 f47 2 f35 2 f36 2 f57 5 f67 3最大流量 10 如果把上例的問題改為 每小時運(yùn)送6萬加侖的石油從采地v1到銷地v7最小費(fèi)用是多少 應(yīng)怎樣運(yùn)送 這就變成了一個最小費(fèi)用流的問題 一般來說 所謂最小費(fèi)用流的問題就是 在給定了收點(diǎn)和發(fā)點(diǎn)并對每條弧 vi vj 賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中 求一個給定值f的流量的最小費(fèi)用 這個給定值f的流量應(yīng)小于等于最大流量F 否則無解 求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可 在上例中只要把f12 f14 F改為f12 f14 f 6得到了最小費(fèi)用流的線性規(guī)劃的模型 4 7分配問題 一 最大匹配例 考慮有n個工人 m件工作的工作分配問題 每個工人能力不同 各能勝任某幾項(xiàng)工作 假設(shè)每件工作只需一人做 每人只做一件工作 問怎樣分配才能使盡可能多的工人有工作 定義 匹配與最大匹配 在二部圖G X Y E M是邊集E的子集 若M中的任意兩條邊都沒有公共端點(diǎn) 則稱M為圖G的一個匹配 若不存在另一匹配M1 使得 M1 M M 表示集合M中邊的條數(shù) 則稱M為最大匹配 上例中的問題用圖的語言描述如下 用x1 x2 xn表示n個工人 y1 y2 ym表示m項(xiàng)工作 xi yj 表示工人xi能勝任工作yj X x1 x2 xn Y y1 y2 ym 得到一個二部圖G X Y E 問題 在圖G中找一個邊集E的子集M 使得M中的任意兩條邊沒有公共端點(diǎn) 并且邊數(shù)盡可能的多 即最大匹配 令 則最大匹配問題的線性規(guī)劃模型為 這里 ij 1 二 最優(yōu)匹配例4 15 現(xiàn)有4個工人 4臺不同的機(jī)床 由于工人對各臺機(jī)床的操作技術(shù)水平不同 每個工人在各臺機(jī)床上完成給定任務(wù)所需工時不同 其效率矩陣為 問題 哪個工人操作哪臺機(jī)床可使總工時最少 工人 機(jī)床 1 數(shù)學(xué)模型對于有n個工人和n項(xiàng)工作的分配問題 社xij 1或0分別表示工人i做 不做工作j 數(shù)學(xué)模型為 minz s t 2 匈牙利方法 定理4 9 若矩陣W的元素可分成0與非0兩部分 則覆蓋0元素的直線數(shù)等于位于不同行不同列的0元素的最大個數(shù) 定理4 8 如果從分配問題效率矩陣W ij 的每一行元素中分別減去 或加上 一個常數(shù)ui 從每一列分別減去 或加上 一個常數(shù)vj 得到一個新效率矩陣B bij 其中bij ij ui vj 則二者的最優(yōu)解等價 匈牙利方法 根據(jù)定理4 8的方法不斷變換效率矩陣W 使其產(chǎn)生盡可能多的0元素 并且始終保持所有元素非負(fù) 直到能從變換后的矩陣中找出位于不同行不同列的0元素為止 這些0元對應(yīng)的xij 1 其余元素對應(yīng)xij 0的方案為最優(yōu)解 下面以例4 15說明最優(yōu)匹配的匈牙利方法的應(yīng)用 1 變換效率矩陣 2 在B1中尋找位于不同行 不同列的0元 1 檢查B1的每行 列 從中找出未加標(biāo)記的0元最少的行 列 在該行 列 用 標(biāo)出一個0元 若該行 列 有多個0元 則任意標(biāo)一個 2 把剛得到的0 所在的行 列中的其余0元劃去 用0表示 3 0 0就是有標(biāo)記的0元 返1 反復(fù)進(jìn)行 直到所有0元都有標(biāo)記為止 這樣得到的0 元一定位于不同行 不同列 如果個數(shù)等于n 已符合最優(yōu)性條件 否則轉(zhuǎn)3 3 找出能覆蓋矩陣中所有0元的最少直線集合1 對沒有0 的行打 2 對已打 的行中所有0元所在的列打 3 再對打有 的列中所有0 元所在的行打 4 重復(fù)2 3 直到得不出新的打 的行 列為止 5 沒有打 的行和打 的列就是覆蓋所有0元的最少直線集合 4 修改矩陣B1 1 在未被直線覆蓋的所有元素中找出最小元素 2 所有打 的行都減去此最小元素 所有打 的列都加上此最小元素 令這個新矩陣為B2 返回2 符合最優(yōu)條件 總工時29 工人 機(jī)床 一般的指派問題在實(shí)際應(yīng)用中 會遇到各種非標(biāo)準(zhǔn)形式的指派問題 通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式 然后再用匈牙利法求解 1 最大化指派問題設(shè)最大化指派問題系數(shù)矩陣C cij n n 其中最大元素為m 令矩陣B bij n n m cij n n 則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解 例矩陣 的最大元素為c33 16 取m 16 令 2 人數(shù)和事數(shù)不等的指派問題若人少事多 則添上一些虛擬的 人 這些虛擬的 人 做各事的費(fèi)用系數(shù)可取0 理解為這些費(fèi)用實(shí)際上不會發(fā)生 若人多事少 則添上一些虛擬的 事 這些虛擬的 事 被各人做的費(fèi)用系數(shù)同樣也取0 3 一個人可做幾件事的指派問題若某個人可做幾件事 則可將該人化作相同的幾個 人 來接受指派 這幾個 人 做同一件事的費(fèi)用系數(shù)當(dāng)然都一樣 4 某事一定不能由某人做的指派問題若某事一定不能由某個人做 則可將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M 例 某商業(yè)公司計(jì)劃開辦五家新商店 為了盡早建成營業(yè) 商業(yè)公司決定由5家建筑公司分別承建 已知建筑公司Ai i 1 2 5 對新商店Bj j 1 2 5 的建造費(fèi)用的報價 萬元 為cij i j 1 2 5 見下表 商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分配建造任務(wù) 才能使總的建造費(fèi)用最少 cij 這是標(biāo)準(zhǔn)形式的指派問題 為了保證工程質(zhì)量 經(jīng)研究決定舍棄建筑公司A1和A5 而讓技術(shù)力量較強(qiáng)的建筑公司A1 A2和A3來承建 根據(jù)實(shí)際情況 可以允許每家建筑公司承建一家或二家商店 求使總費(fèi)用最少的指派方案 反映投標(biāo)費(fèi)用的系數(shù)矩陣為 cij 由于每家建筑公司最多可承建兩家新商店 因此 把每家建筑公司化作相同的兩家建筑公司 Ai和 i 1 2 3 這樣 系數(shù)矩陣變?yōu)?上面的系數(shù)矩陣有6行5列 為了使 人 和 事 的數(shù)目相同 引入一件虛工作B6 使之成為標(biāo)準(zhǔn)指派問題的系數(shù)矩陣 用匈牙利解法解以C為系數(shù)矩陣的最小化指派問題 得最優(yōu)指派方案為由A1承建B1和B3 A2承建B2 A3承建B4和B5 這樣 總的建造費(fèi)用最省 為4十7十9十8十7 35 萬元 工作數(shù)量 工人數(shù)量 工作的數(shù)量的工人的數(shù)量相等 工作數(shù)量 工人數(shù)量 工作的數(shù)量的工人的數(shù)量不相等 虛工作 4 8網(wǎng)絡(luò)計(jì)劃 網(wǎng)絡(luò)計(jì)劃技術(shù)廣泛應(yīng)用于建筑施工和新產(chǎn)品的研制計(jì)劃 計(jì)算機(jī)系統(tǒng)的安裝調(diào)試及各種大型復(fù)雜工程的控制管理 其基本原理 首先是把所要做的工作 哪項(xiàng)工作先做 哪項(xiàng)工作后做 各占用多少時間 以及各項(xiàng)工作之間的相互關(guān)系等運(yùn)用網(wǎng)絡(luò)圖的形式表達(dá)出來 其次是通過簡單的計(jì)算 找出哪些工作是關(guān)鍵的 哪些工作不是關(guān)鍵的 并在原來計(jì)劃方案的基礎(chǔ)上 進(jìn)行計(jì)劃的優(yōu)化 一 PRET網(wǎng)絡(luò)圖 programevaluationandreviewtechnique PERT 網(wǎng)絡(luò)圖又稱箭線圖 是由帶箭頭的線和節(jié)點(diǎn)組成的 用來表示工作流程的有向 有序的網(wǎng)狀圖形 繪圖符號1 工作 活動 工序