運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型

本章主要討論圖論基本概念、理論和方法以及最短路問(wèn)題、最大流問(wèn)題和最小費(fèi)用流問(wèn)題等網(wǎng)絡(luò)優(yōu)化模型及其基本算法。

第六章圖與網(wǎng)絡(luò)優(yōu)化模型

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!節(jié)圖與網(wǎng)絡(luò)運(yùn)籌學(xué)的重要分支主要應(yīng)用領(lǐng)域：物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、電子計(jì)算機(jī)等圖論理論和方法應(yīng)用實(shí)例：在組織生產(chǎn)中，為完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間怎樣銜接，才能使生產(chǎn)任務(wù)完成得既快又好。一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。各種通信網(wǎng)絡(luò)的合理架設(shè)，交通網(wǎng)絡(luò)的合理分布等問(wèn)題，應(yīng)用圖論的方法求解都很簡(jiǎn)便。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!圖論的起源與發(fā)展七橋問(wèn)題：哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個(gè)島，河上有七座橋。當(dāng)時(shí)那里的居民熱衷于這樣的問(wèn)題：一個(gè)散步者能否走過(guò)七座橋，且每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)。圖8-1(a)圖6-1歐拉在1736年發(fā)表了圖論方面的篇論文，解決了著名的哥尼斯堡七橋問(wèn)題。歐拉將此問(wèn)題歸結(jié)為如圖6-1(b)所示圖形的一筆畫(huà)問(wèn)題。即能否從某一點(diǎn)開(kāi)始，不重復(fù)地一筆畫(huà)出這個(gè)圖形，最后回到出發(fā)點(diǎn)。歐拉證明了這是不可能的，因?yàn)閳D6-1(b)中的每個(gè)點(diǎn)都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個(gè)圖不重復(fù)地一筆畫(huà)成。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!例2有甲、乙、丙、丁、戊五個(gè)球隊(duì)，它們之間比賽的情況用圖表示出來(lái)。已知甲隊(duì)和其他各隊(duì)都比賽過(guò)一次，乙隊(duì)和甲、丙隊(duì)比賽過(guò)，丙隊(duì)和甲、乙、丁隊(duì)比賽過(guò)，丁隊(duì)和甲、丙、戊隊(duì)比賽過(guò)，戊隊(duì)和甲、丁隊(duì)比賽過(guò)。為了反映這個(gè)情況，可以用點(diǎn)分別代表這五個(gè)隊(duì)，某兩個(gè)隊(duì)之間比賽過(guò)，就在這兩個(gè)隊(duì)所相應(yīng)的點(diǎn)之間聯(lián)一條線，這條線不過(guò)其他的點(diǎn)，如圖6-3所示。比賽情況圖圖6-3運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!術(shù)語(yǔ)

頂點(diǎn)（結(jié)點(diǎn)）、弧、邊（取消弧的方向）、有向圖、無(wú)向圖、鏈、道路、環(huán)、連通圖、連通子圖、次1234123412345213次道路頂點(diǎn)無(wú)向圖鏈有向圖弧環(huán)連通圖弧是由一對(duì)有序的頂點(diǎn)組成，表示了兩個(gè)頂點(diǎn)之間可能運(yùn)動(dòng)的方向連通子圖

由頂點(diǎn)集和弧組成的圖稱為有向圖

由頂點(diǎn)集和邊組成的圖稱為無(wú)向圖

鏈有一序列弧，如果每一個(gè)弧與前一個(gè)弧恰有一個(gè)公共頂點(diǎn)，則稱這一序列弧為一個(gè)鏈。

道路如果鏈中每一個(gè)弧的終點(diǎn)是下面一個(gè)弧的起點(diǎn)，則這個(gè)鏈稱為一個(gè)道路。

環(huán)連接a點(diǎn)與b點(diǎn)的一條鏈，如果a與b是同一個(gè)點(diǎn)時(shí)，稱此鏈為環(huán)。

連通圖一個(gè)圖中任意兩點(diǎn)間至少有一個(gè)鏈相連，則稱此圖為連通圖。

任何一個(gè)不連通圖都可以分為若干個(gè)連通子圖，每一個(gè)子圖稱為原圖的一個(gè)分圖。

次:以a點(diǎn)為頂點(diǎn)的邊的條數(shù)稱為頂點(diǎn)的次

圖6-5運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!二、網(wǎng)絡(luò)點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡(jiǎn)稱網(wǎng)絡(luò)。與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，我們經(jīng)常稱之為權(quán)，權(quán)可以代表如距離、費(fèi)用、容量等。左圖可以看作：

從發(fā)電廠（節(jié)點(diǎn)1）向某城市（節(jié)點(diǎn)6）輸送電力，必須通過(guò)中轉(zhuǎn)站（節(jié)點(diǎn)2，3，4，5）轉(zhuǎn)送，邊上數(shù)字代表兩節(jié)點(diǎn)間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。一個(gè)輸油管道網(wǎng)。節(jié)點(diǎn)1表示管道的起點(diǎn)，節(jié)點(diǎn)6表示管道的終點(diǎn)，節(jié)點(diǎn)2到5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過(guò)的最大輸送量。應(yīng)怎樣安排輸油線路，使從節(jié)點(diǎn)1到節(jié)點(diǎn)6的總輸送量最大？一張城市分布圖?，F(xiàn)在要在各城市之間架設(shè)電話線，應(yīng)如何架設(shè)，使各城市之間既能通話，又使總的架設(shè)路線最短？運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!

樹(shù)的性質(zhì)：任意兩頂點(diǎn)之間必有一條且僅有一條鏈。去掉任一條邊，則樹(shù)成為不連通圖。不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，恰好得到一個(gè)環(huán)。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!部分圖、生成子圖、部分樹(shù)部分圖生成子圖設(shè)G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,則稱G1為G的生成子圖；運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!1325464332322最小生成樹(shù)不一定唯一最小生成樹(shù)：

設(shè)有一連通圖G=(V,L),對(duì)于每一邊e=(vi,vj)，有一個(gè)權(quán)wij≥0。一棵生成樹(shù)所有樹(shù)枝上權(quán)的總和，稱為這個(gè)生成樹(shù)的權(quán)。具有最小權(quán)的生成樹(shù)稱為最小生成樹(shù)（最小樹(shù)）。

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!方法一：破圈法步驟：1、在給定的賦權(quán)的連通圖上任找一個(gè)圈。2、在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹(shù)，否則返回第1步。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!方法二：(加邊)避圈法（Kruskal）開(kāi)始選一條最小權(quán)的邊，以后每一步中，總從未被選中的邊中選一條最小權(quán)的邊，使之與已選的邊不構(gòu)成圈，直到所有的邊都檢驗(yàn)完，即可得最小樹(shù)。（每步中，若有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條）。

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!練習(xí)：房屋開(kāi)發(fā)商正規(guī)劃設(shè)計(jì)某居住新區(qū)的下水管道，圖中各數(shù)字表示各棟樓房之間鋪設(shè)管道的工程費(fèi)用。房屋開(kāi)發(fā)商應(yīng)怎樣設(shè)計(jì)最佳的管道鋪設(shè)方案，使總工程費(fèi)用最少。

2873965657單位：十萬(wàn)元6V1V2V3V5V4V6運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!算法（Dijkstra(迪杰斯特拉)1959年提出的）1325464332322第0步：P(1)=0,T(i)=+∞；第1步：與1相連的標(biāo)號(hào)為2,3，均是T標(biāo)號(hào)，修改2,3的標(biāo)號(hào)，T(2)=min{T(2),P(1)+w12}=min{+∞,P(1)+w12}=4,T(3)=3；在所有的T標(biāo)號(hào)中，3的標(biāo)號(hào)最小，改3的標(biāo)號(hào)為P(3)=3；第2步：修改與3相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，2的標(biāo)號(hào)最小，改為P(2)=4；第3步：修改與2相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，5的標(biāo)號(hào)最小，改為P(5)=6；第4步：修改與5相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，4的標(biāo)號(hào)最小，改為P(4)=7；第5步：修改與4相連的T標(biāo)號(hào)；只剩下節(jié)點(diǎn)6是T標(biāo)號(hào)，修改6的標(biāo)號(hào)，P(6)=8。從節(jié)點(diǎn)6開(kāi)始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!例：用Dijkstra方法求圖8-4所示的賦權(quán)圖中，從v1到所有點(diǎn)的最短路。圖8-4運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!練習(xí)：設(shè)備更新問(wèn)題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門(mén)就要決定是購(gòu)置新的，還是繼續(xù)使用舊的。若購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用?，F(xiàn)在的問(wèn)題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新計(jì)劃，使得總的支付費(fèi)用最少。我們用一個(gè)五年之內(nèi)要更新某種設(shè)備的計(jì)劃為例，若已知該種設(shè)備在各年年初的價(jià)格為：第1年第2年第3年第4年第5年1111121213還已知使用不同時(shí)間(年)的設(shè)備所需要的維修費(fèi)用為：使用年數(shù)0～11～22～33～44～5維修費(fèi)用5681118運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!解：如何制定使得總的支付費(fèi)用最少的設(shè)備更新計(jì)劃呢?可以把這個(gè)問(wèn)題化為最短路問(wèn)題，見(jiàn)圖8-5。圖8-5運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!

城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了10個(gè)搭乘車站。為了減少運(yùn)行時(shí)間，提高服務(wù)質(zhì)量以及最大化利用公司的車隊(duì)，管理方希望出租車司機(jī)盡可能地選擇最短路線。使用下面公路與街道的網(wǎng)絡(luò)圖，請(qǐng)說(shuō)明司機(jī)從車站1到車站10應(yīng)選擇什么樣的路線。運(yùn)行時(shí)間如圖所示。最優(yōu)路線為：1－５－４－６－７－10，最短距離是25運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!第四節(jié)網(wǎng)絡(luò)最大流問(wèn)題一、基本概念與基本定理二、尋求最大流的標(biāo)號(hào)法運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!可行流與最大流

在運(yùn)輸網(wǎng)絡(luò)的實(shí)際問(wèn)題中可以看出，對(duì)于流有兩個(gè)明顯的要求：1.是每個(gè)弧上的流量不能超過(guò)該弧的最大通過(guò)能力(即弧的容量)；2.是中間點(diǎn)的流量為零。

因?yàn)閷?duì)于每個(gè)點(diǎn)，運(yùn)出這點(diǎn)的產(chǎn)品總量與運(yùn)進(jìn)這點(diǎn)的產(chǎn)品總量之差，是這點(diǎn)的凈輸出量，簡(jiǎn)稱為是這一點(diǎn)的流量；由于中間點(diǎn)只起轉(zhuǎn)運(yùn)作用，所以中間點(diǎn)的流量必為零。易見(jiàn)發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等，也是這個(gè)方案的總輸送量。因此有：運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!可行流總是存在的。比如令所有弧的流量fij=0，就得到一個(gè)可行流(稱為零流)。其流量v(f)=0。最大流問(wèn)題就是求一個(gè)流｛fij｝使其流量v(f)達(dá)到最大，并且滿足：0≤fij≤cij(vi，vj)∈A①

②最大流問(wèn)題是一個(gè)特殊的線性規(guī)劃問(wèn)題。即求一組｛fij｝，在滿足條件①和②下使v(f)達(dá)到極大。將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問(wèn)題的方法較之線性規(guī)劃的一般方法要方便、直觀得多。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!割集21st28811

任給一個(gè)包含收點(diǎn)但不包含發(fā)點(diǎn)的支點(diǎn)集V*，則稱i(弧起點(diǎn))不屬于V*，j(弧終點(diǎn))屬于V*的弧(i,j)的全體為割集。割集的容量是割集中所有弧的容量的總和。如果將割集從網(wǎng)絡(luò)中移去，則就不可能有從起點(diǎn)到終點(diǎn)的路徑。一個(gè)網(wǎng)絡(luò)可能有許多割集。任何從發(fā)點(diǎn)到收點(diǎn)的可行流小于等于任何割集的容量。直觀上說(shuō)，截集是從vs到vt的必經(jīng)之道。V*割集任何割集的容量是從起點(diǎn)到終點(diǎn)的最大流的上界。如果能找到一個(gè)可行流和一個(gè)割集使得割集從起點(diǎn)到終點(diǎn)的容量等于可行流的流量，則該可行流就是一個(gè)最大流。最大流---最小割集定理

V*={1,t}割集是{(s,1)，(2,t)}，容量2+1=3

支點(diǎn)集V*={1,2,t},割集？{(s,1)，(s,2)},容量2+8=10運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!求最大流的標(biāo)號(hào)算法2．調(diào)整過(guò)程由收點(diǎn)標(biāo)號(hào)算出的作為調(diào)整量（即）。對(duì)增廣鏈各弧的調(diào)整如下：

增廣鏈以外各弧流量不變。去掉所有標(biāo)號(hào)，對(duì)新的可行流，重新進(jìn)入標(biāo)號(hào)過(guò)程。直到標(biāo)號(hào)過(guò)程中斷。當(dāng)前流就是最大流。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!標(biāo)號(hào)算法vsv2v1v3vt32223(0,+∞)重復(fù)標(biāo)號(hào)過(guò)程。給網(wǎng)絡(luò)中的各個(gè)點(diǎn)標(biāo)號(hào)：先給發(fā)點(diǎn)vs標(biāo)上(0,+∞)。檢查vs給v2標(biāo)上(vs,1)，檢查v2,在弧(v2,vt)上,f2t=C2t=2,不滿足標(biāo)號(hào)條件，在弧(v1,v2)上，f12=0,也不滿足標(biāo)號(hào)條件，標(biāo)號(hào)無(wú)法繼續(xù)。算法結(jié)束。4(vs,1)222022如下圖所示，弧上數(shù)字表示該弧的容量，求該網(wǎng)絡(luò)的最大流。最大流量為從發(fā)點(diǎn)流出的量這時(shí)的可行流就是所求的最大流

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!解：(1)標(biāo)號(hào)過(guò)程①首先給vs標(biāo)上(0，+∞)②檢查vs，在弧(vs，v2)上，fs2=cs2=3，不滿足標(biāo)號(hào)條件?；?vs，v1)上，fs1=1，cs1=5，fs1＜cs1，則v1的標(biāo)號(hào)為(vs，l(v1))，其中l(wèi)(v1)=min［l(vs)，(cs1-fs1)］=min［+∞，5-1］=4運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!圖8-8(2)調(diào)整過(guò)程按點(diǎn)的個(gè)標(biāo)號(hào)找到一條增廣鏈，如圖8-8中雙箭頭線表示。易見(jiàn)μ+=｛(vs，v1)，(v3，vt)｝μ-=｛(v2，v1)，(v3，v2)｝按θ=1在μ上調(diào)整f。μ+上：fs1+θ=1+1=2f3t+θ=1+1=2μ-上：f21?θ=1?1=0f32?θ=1?1=0其余的fij不變。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!從一個(gè)費(fèi)用最小的可行流出發(fā)（這樣的可行流一定存在，因?yàn)橘M(fèi)用，所以就是一個(gè)流量為0的最小費(fèi)用流），找出這個(gè)可行流的費(fèi)用最小的一條增廣鏈L，沿L調(diào)整，直到找不到費(fèi)用最小的增廣鏈，就得到了最小費(fèi)用最大流。第五節(jié)最小費(fèi)用流問(wèn)題

對(duì)于網(wǎng)絡(luò)圖G中的弧，除標(biāo)明弧的容量外，還要標(biāo)明流過(guò)該弧單位流量的費(fèi)用，G的一個(gè)可行流，使得流的總運(yùn)輸費(fèi)用：達(dá)到最小。特別，如果可行流是最大流時(shí)，此問(wèn)題就是最小費(fèi)用最大流問(wèn)題。

最小費(fèi)用流問(wèn)題最小費(fèi)用最大流的基本思路運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!一、圖的基本概念人們?yōu)榉从骋恍?duì)象之間關(guān)系時(shí)，常會(huì)用示意圖。例1右圖是我國(guó)北京、上海等十個(gè)城市間的鐵路交通圖，反映了這十個(gè)城市間的鐵路分布情況。這里用點(diǎn)代表城市，用點(diǎn)和點(diǎn)之間的連線代表這兩個(gè)城市之間的鐵路線。其他示意圖的例子電話線分布圖、煤氣管道圖、航空線圖等。鐵路交通示意圖圖6-2圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!關(guān)系的對(duì)稱性和非對(duì)稱性：幾個(gè)例子中涉及到的對(duì)象之間的“關(guān)系”具有“對(duì)稱性”，就是說(shuō)，如果甲與乙有這種關(guān)系，那么同時(shí)乙與甲也有這種關(guān)系。實(shí)際生活中，有許多關(guān)系不具有這種對(duì)稱性。如例2，如果人們關(guān)心的是五個(gè)球隊(duì)比賽的勝負(fù)情況，那么從圖5-3中就看不出來(lái)了。為了反映這一類關(guān)系，可以用一條帶箭頭的連線表示。例如，如果球隊(duì)v1勝了球隊(duì)v2，可以從v1引一條帶箭頭的連線到v2類似勝負(fù)這種非對(duì)稱性的關(guān)系，在生產(chǎn)和生活中是常見(jiàn)的，如交通運(yùn)輸中的“單行線”，部門(mén)之間的領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)的關(guān)系，一項(xiàng)工程中各工序之間的先后關(guān)系等。比賽勝負(fù)圖6-4運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!例：

設(shè)V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},畫(huà)出G=(V,E)的圖?；蜻\(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!第二節(jié)樹(shù)定義1（樹(shù)的定義）連通且不含環(huán)的無(wú)向圖稱為樹(shù)。例1某工廠的組織機(jī)構(gòu)如下所示工廠組織機(jī)構(gòu)圖運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!部分圖、生成子圖、部分樹(shù)部分圖如果V1V，E1

E則稱G1為(全部頂點(diǎn)和部分邊)G的部分圖；設(shè)G=(V，E)和G1=(V1，E1)運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!部分圖、生成子圖、部分樹(shù)部分圖生成子圖部分樹(shù)如果V1V，E1

E則稱G1為G的部分圖；設(shè)G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,則稱G1為G的生成子圖；

如果G=(V，E)的部分圖G1=(V，E1)是樹(shù)，則稱G1為G的一個(gè)部分樹(shù)。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!

例：某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中v1,…,v7表示7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。v1331728541034v7v6v5v4v2v3圖6-11運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)解：按照?qǐng)D16-11的(f)設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長(zhǎng)度為最短，為1900米。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!例：右圖,用避圈法求其最小生成樹(shù)。

類似地,可定義連通圖G的最大生成樹(shù).運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!從一特殊的節(jié)點(diǎn)出發(fā)，找出從該節(jié)點(diǎn)到網(wǎng)絡(luò)中任何其它節(jié)點(diǎn)的最短路徑問(wèn)題某人買了一輛價(jià)值12000美元的新車，一輛車每年的維護(hù)費(fèi)用依賴于年初時(shí)的車齡，具體費(fèi)用見(jiàn)下表。為了避免舊車的高維護(hù)費(fèi)用，他決定賣掉舊車買新車。舊車的價(jià)格依賴于交易時(shí)的車齡，見(jiàn)右表。為計(jì)算簡(jiǎn)單起見(jiàn)，假設(shè)任何時(shí)間新車的價(jià)格不變均為12000美元。他希望在今后5年內(nèi)的凈費(fèi)用最小（即：凈費(fèi)用=購(gòu)買價(jià)+維護(hù)價(jià)-售出價(jià)）。

車齡每年的維護(hù)費(fèi)用售出價(jià)格123456200040005000900012000700060002000100001234562177777121212213131441221第三節(jié)最短路問(wèn)題節(jié)點(diǎn)i表示第i年年初，當(dāng)i<j時(shí)，?。╥,j）表示第i年年初買一輛新車并一直用到第j年年初。?。╥,j）的長(zhǎng)度為cij，cij表示如果第i年年初買車并在第j年年初賣掉更換新車，從第i年年初到第j年年初期間總費(fèi)用。Cij=(i,i+1,····,j-1年的維護(hù)費(fèi))+第i年年初買新車的費(fèi)用-第j年年初該車的售出價(jià)格C12=2+12-7=7C13+c35+c56是1到6的最小費(fèi)用，第3年年初與第五年初交易，今后5年的凈費(fèi)用最小。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!Dijkstra方法的基本思想：從vs出發(fā)，逐步向外探尋最短路。執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)(稱為這個(gè)點(diǎn)的標(biāo)號(hào))，它或者表示從vs到該點(diǎn)的最短路的權(quán)(稱為P標(biāo)號(hào))，或者是從vs到該點(diǎn)的最短路的權(quán)的上界(稱為T(mén)標(biāo)號(hào))，方法的每一步是去修改T標(biāo)號(hào)，并且把某一個(gè)具T標(biāo)號(hào)的點(diǎn)改變?yōu)榫逷標(biāo)號(hào)的點(diǎn)，從而使D中具P標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)，這樣，至多經(jīng)過(guò)p?1步，就可以求出從vs到各點(diǎn)的最短路。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!解：計(jì)算的最后結(jié)果為P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。這樣從v1到v8的最短鏈為(v1，v3，v2，v5，v9，v8)，總權(quán)為11。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!可供選擇的設(shè)備更新方案顯然是很多的。例如，每年都購(gòu)置一臺(tái)新設(shè)備，則其購(gòu)置費(fèi)用為11+11+12+12+13=59，而每年支付的維修費(fèi)用為5，五年合計(jì)為25。于是五年總的支付費(fèi)用為59+25=84。又如決定在、三、五年各購(gòu)進(jìn)一臺(tái)，這個(gè)方案的設(shè)備購(gòu)置費(fèi)為11+12+13=36，維修費(fèi)為5+6+5+6+5=27。五年總的支付費(fèi)用為63。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!這樣一來(lái)，制定一個(gè)最優(yōu)的設(shè)備更新計(jì)劃問(wèn)題就等價(jià)于尋求從v1到v6的最短路的問(wèn)題。按求解最短路的計(jì)算方法，｛v1，v3，v6｝及｛v1，v4，v6｝均為最短路，即有兩個(gè)最優(yōu)方案。一個(gè)方案是在第1年、第3年各購(gòu)置一臺(tái)新設(shè)備；另一個(gè)方案是在第1年、第4年各購(gòu)置一臺(tái)新設(shè)備。五年總的支付費(fèi)用均為53。

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!例：六個(gè)村莊每村上學(xué)人數(shù)見(jiàn)下表，村與村的距離見(jiàn)下圖，現(xiàn)只能在某一個(gè)村建一所小學(xué)，問(wèn)在哪個(gè)村建校最為合理？村莊ABCDEF上學(xué)人數(shù)6040503070100ABCEFD633647281運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!容量網(wǎng)絡(luò)、可行流24531142010519152730流量容量

容量網(wǎng)絡(luò)：標(biāo)有弧容量的網(wǎng)絡(luò)。156104610150可行流

網(wǎng)絡(luò)流的兩個(gè)條件：每個(gè)弧的流量不能超過(guò)該弧的最大通過(guò)能力，即容量；中間支點(diǎn)的流量為零。可行流：中間點(diǎn)的流量為零。而發(fā)點(diǎn)和收點(diǎn)的流量必須相等。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!定義：滿足下述條件的流f稱為可行流：(1)容量限制條件：對(duì)每一弧(vi，vj)∈A0≤fij≤cij(2)平衡條件：對(duì)于中間點(diǎn)：流出量等于流入量，即對(duì)每個(gè)i(i≠s,t發(fā)點(diǎn)與收點(diǎn))有對(duì)于發(fā)點(diǎn)vs，記對(duì)于收點(diǎn)vt，記式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量(或收點(diǎn)的凈輸入量)。運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!增廣鏈13425201051419152730156104610150飽和弧非飽和弧零弧增廣鏈增廣鏈:

設(shè)f是一個(gè)可行流，C是從發(fā)點(diǎn)Vs到收點(diǎn)Vt的一條鏈，若C滿足以下條件，則稱C為一條增廣鏈：(1)在弧上，，即C+(弧的方向與鏈的方向一致

)中每一條弧是非飽和弧(2)在弧上，，即C-(弧的方向與鏈的方向相反

)中每一條弧是非零流弧

C＋中每一條弧是非飽和弧;C－中每一條弧是非零流弧。

運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!

從一個(gè)可行流出發(fā)，（若網(wǎng)絡(luò)中沒(méi)有給定f，則可以設(shè)f是零流）需要經(jīng)過(guò)標(biāo)號(hào)過(guò)程與調(diào)整過(guò)程。1．標(biāo)號(hào)過(guò)程在這個(gè)過(guò)程中，網(wǎng)絡(luò)中的點(diǎn)或是標(biāo)號(hào)點(diǎn)或是未標(biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：標(biāo)號(hào)表示它的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量用的。標(biāo)號(hào)過(guò)程開(kāi)始時(shí)，總是先給發(fā)點(diǎn)標(biāo)上。其余各點(diǎn)標(biāo)號(hào)的規(guī)則是：設(shè)是已標(biāo)號(hào)的點(diǎn)，檢查與點(diǎn)關(guān)聯(lián)的另一頂點(diǎn)未標(biāo)號(hào)的?。海?）如果在弧上（即前向?。?，則給標(biāo)號(hào)，其中。如果，則不標(biāo)號(hào)。（2）如果在弧上（即后向?。?，則給標(biāo)號(hào)，其中，負(fù)號(hào)說(shuō)明經(jīng)后向弧到。如果，則不標(biāo)號(hào)。重復(fù)上述步驟，直到被標(biāo)上號(hào)，表明得到一條從到的增廣鏈C，轉(zhuǎn)入調(diào)整過(guò)程。求最大流的標(biāo)號(hào)算法運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型共52頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!標(biāo)號(hào)算法vsv2v1v3vt32223(0,+∞)

找到初始可行流。給網(wǎng)絡(luò)中的各個(gè)點(diǎn)標(biāo)號(hào)：總是先給發(fā)點(diǎn)vs標(biāo)上(0,+∞)。其余各點(diǎn)標(biāo)號(hào)的規(guī)則是：設(shè)vi是已標(biāo)號(hào)的點(diǎn)，檢查與點(diǎn)vi關(guān)聯(lián)的另一頂點(diǎn)未標(biāo)號(hào)的弧：（1）如果在弧(vi,vj)上（即前向弧），fij<cij，則給vj標(biāo)號(hào)(vi,l(vj))，其中l(wèi)(vj)=min{l(vi),cij-fij}。如果fij=cij，則vj不標(biāo)號(hào)。（2）如果在弧(vj,vi)上（即后向?。?，fij>0，則給vj標(biāo)號(hào)(-vi,l(vj))，其中l(wèi)(vj)=min{l(vi),fji}，負(fù)號(hào)說(shuō)明經(jīng)后向弧到vi。如果fji=0，則vj不標(biāo)號(hào)。調(diào)