網(wǎng)絡(luò)最優(yōu)化問題課件

1、實用運籌學(xué)運用Excel建模和求解第5章網(wǎng)絡(luò)最優(yōu)化問題第1頁，共73頁。本章內(nèi)容要點網(wǎng)絡(luò)最優(yōu)化問題的基本概念網(wǎng)絡(luò)最優(yōu)化問題的四種主要類型：最小費用流、最大流、最短路、最小支撐樹各種網(wǎng)絡(luò)最優(yōu)化問題的建模與應(yīng)用第2頁，共73頁。本章節(jié)內(nèi)容5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念5.2 最小費用流問題5.3 最大流問題5.4 最短路問題5.5 最小支撐樹問題5.6 貨郎擔(dān)問題和中國郵路問題第3頁，共73頁。本章主要內(nèi)容框架圖第4頁，共73頁。5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念網(wǎng)絡(luò)在各種實際背景問題中以各種各樣的形式存在。交通、電子和通訊網(wǎng)絡(luò)遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡(luò)規(guī)劃也廣泛用于解決不同領(lǐng)域中的各種問題，如

2、生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務(wù)策劃等等。網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效的直觀和概念上的幫助，廣泛應(yīng)用于科學(xué)、社會和經(jīng)濟活動的各個領(lǐng)域中。近些年來，運籌學(xué)（管理科學(xué)）中一個振奮人心的發(fā)展是它的網(wǎng)絡(luò)最優(yōu)化問題的方法論和應(yīng)用方面都取得了不同尋常的飛速發(fā)展。第5頁，共73頁。5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念許多研究的對象往往可以用一個圖表示，研究的目的歸結(jié)為圖的極值問題。運籌學(xué)中研究的圖具有下列特征：(1) 用點表示研究對象，用連線（不帶箭頭的邊或帶箭頭的弧）表示對象之間某種關(guān)系； (2) 強調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；(3) 每條邊上都賦有一

3、個權(quán)，其圖稱為賦權(quán)圖。實際中權(quán)可以代表兩點之間的距離、費用、利潤、時間、容量等不同的含義；(4) 建立一個網(wǎng)絡(luò)模型，求最大值或最小值。第6頁，共73頁。5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念v1v3v5v2v4v68736548521對于該網(wǎng)絡(luò)圖，可以提出許多極值問題 第7頁，共73頁。5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念（1）將某個點vi的物資或信息送到另一個點vj，使得運送成本最小。這屬于最小費用流問題。（2）將某個點vi的物資或信息送到另一個點vj，使得流量最大。這屬于最大流問題。（3）從某個點vi出發(fā)到達另一個點vj，怎樣安排路線使得總距離最短或總費用最小。這屬于最短路問題。第8頁，共73頁。5.1

4、 網(wǎng)絡(luò)最優(yōu)化問題基本概念（4）點vi表示自來水廠及用戶，vi與vj之間的邊表示兩點間可以鋪設(shè)管道，權(quán)為vi與vj間鋪設(shè)管道的距離或費用，極值問題是如何鋪設(shè)管道，將自來水送到其他5個用戶并且使總的費用最小。這屬于最小支撐樹問題。 (5) 售貨員從某個點vi出發(fā)走過其他所有點后回到原點vi，如何安排路線使總路程最短。這屬于貨郎擔(dān)問題或旅行售貨員問題。（6）郵遞員從郵局vi出發(fā)要經(jīng)過每一條邊將郵件送到用戶手中，最后回到郵局vi，如何安排路線使總路程最短。這屬于中國郵遞員問題。第9頁，共73頁。5.1 網(wǎng)絡(luò)最優(yōu)化問題基本概念網(wǎng)絡(luò)最優(yōu)化問題類型主要包括：（1）最小費用流問題；（2）最大流問題；（3）最短

5、路問題； （4）最小支撐樹問題；（5）貨郎擔(dān)問題和中國郵路問題，等等第10頁，共73頁。5.2 最小費用流問題最小費用流問題的模型在網(wǎng)絡(luò)最優(yōu)化中扮演著重要的角色，因為它的適用性很廣，并且求解方法容易。通常最小費用流問題用于最優(yōu)化貨物從供應(yīng)點到需求點的網(wǎng)絡(luò)。目標(biāo)是在通過網(wǎng)絡(luò)配送貨物時，以最小的成本滿足需求，一種典型的應(yīng)用就是使得配送網(wǎng)絡(luò)的運營最優(yōu)。最小費用流問題的特殊類型包括運輸問題和指派問題，以及在下面將要提到的兩種重要類型：最大流問題和最短路問題。第11頁，共73頁。5.2 最小費用流問題例5.1 某公司有兩個工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運送到兩個倉庫中。其配送網(wǎng)絡(luò)圖如圖52所示。目標(biāo)是確定一

6、個運輸方案（即每條路線運送多少單位的產(chǎn)品），使通過配送網(wǎng)絡(luò)的運輸成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（無限制，700）（無限制，900）第12頁，共73頁。5.2 最小費用流問題最小費用流問題的三個基本概念：1、最小費用流問題的構(gòu)成（網(wǎng)絡(luò)表示）（1）節(jié)點：包括供應(yīng)點、需求點和轉(zhuǎn)運點；（2）?。嚎尚械倪\輸線路（節(jié)點i-節(jié)點j），經(jīng)常有最大流量（容量）的限制。第13頁，共73頁。5.2 最小費用流問題2、最小費用流問題的假設(shè)（1）至少一個供應(yīng)點；（2）至少一個需求點；（3）剩下都是轉(zhuǎn)運點；（4）通過弧的流只允許沿著箭頭方向流

7、動，通過弧的最大流量取決于該弧的容量；（5）網(wǎng)絡(luò)中有足夠的弧提供足夠容量，使得所有在供應(yīng)點中產(chǎn)生的流都能夠到達需求點；（有解）（6）在流的單位成本已知前提下，通過每一條弧的流的成本和流量成正比；（目標(biāo)是線性的）（7）最小費用流問題的目標(biāo)在滿足給定需求條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最?。ɑ蚩偫麧欁畲螅５?4頁，共73頁。5.2 最小費用流問題3、最小費用流問題的解的特征（1）具有可行解的特征：在以上的假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點所提供的流量總和等于需求點所需要的流量總和時（即平衡條件），最小費用流問題有可行解；（2）具有整數(shù)解的特征：只要其所有的供應(yīng)、需求和弧的容量都是整數(shù)值，那么任何最小費用流問

8、題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解（與運輸問題和指派問題的解一樣）。因此，沒有必要加上所有決策變量都是整數(shù)的約束條件。第15頁，共73頁。5.2 最小費用流問題最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fij為通過弧（節(jié)點i-節(jié)點j）的流量。（2）目標(biāo)是通過網(wǎng)絡(luò)供應(yīng)的總成本最小。（3）約束條件 所有供應(yīng)點：凈流量（總流出減總流入）為正； 所有轉(zhuǎn)運點：凈流量為零； 所有需求點：凈流量為負； 所有弧的流量fij受到弧的容量限制； 所有弧的流量fij非負。第16頁，共73頁。5.2 最小費用流問題例5.1最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fij為通過弧(節(jié)點i-節(jié)點j)的流量

9、。（2）目標(biāo)函數(shù) 本問題的目標(biāo)是總運輸成本最小。第17頁，共73頁。5.2 最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限制、非負） 供應(yīng)點 F1: 供應(yīng)點 F2: 轉(zhuǎn)運點 DC: 需求點 W1: 需求點 W2: 弧的容量限制： 非負：第18頁，共73頁。5.2 最小費用流問題 例5.1的電子表格模型：列出了網(wǎng)絡(luò)中的弧和各弧所對應(yīng)的容量、單位成本。決策變量為通過弧的流量。目標(biāo)是計算流量的總成本。每個節(jié)點的凈流量為約束條件。供應(yīng)點的凈流量為正，需求點的凈流量為負，而轉(zhuǎn)運點的凈流量為0。這里用了一個竅門：用兩個SUMIF函數(shù)的差來計算每個節(jié)點的凈流量，這樣快捷且不容易犯錯。第19頁，共73頁

10、。5.2 最小費用流問題 大規(guī)模的最小費用流問題的求解一般采用“網(wǎng)絡(luò)單純法（Network Simplex Method）”?，F(xiàn)在，許多公司都使用網(wǎng)絡(luò)單純法來解決他們的最小費用流問題。有些問題是非常龐大的，有著數(shù)萬個節(jié)點和弧。有時，弧的數(shù)量甚至可能會多得多，達到幾百萬條。但Excel的規(guī)劃求解中沒有網(wǎng)絡(luò)單純法，但其他的線性規(guī)劃的商業(yè)軟件包通常都有這種方法。第20頁，共73頁。5.2 最小費用流問題最小費用流問題有五種重要的特殊類型：（1）運輸問題：有出發(fā)地(供應(yīng)點-供應(yīng)量)和目的地(需求點-需求量)，沒有轉(zhuǎn)運點和弧的容量限制，目標(biāo)是總運輸成本最?。ɑ蚩偫麧欁畲螅?。（2）指派類型：出發(fā)地(供應(yīng)點

11、-供應(yīng)量為1)是人，目的地(需求點-需求量為1)是任務(wù)，沒有轉(zhuǎn)運點和弧的容量限制，目標(biāo)是總指派成本最小（或總利潤最大）。（3）轉(zhuǎn)運問題：有出發(fā)地(供應(yīng)點-供應(yīng)量)和目的地(需求點-需求量)，有轉(zhuǎn)運點，但沒有弧的容量限制(或有容量限制)，目標(biāo)是總流量費用最小（或總利潤最大）。第21頁，共73頁。5.2 最小費用流問題最小費用流問題有五種重要的特殊類型(續(xù))：（4）最大流問題：有供應(yīng)點、需求點、轉(zhuǎn)運點、弧的容量限制，但沒有供應(yīng)量和需求量的限制，目標(biāo)是通過網(wǎng)絡(luò)到目的地的總流量最大。（5）最短路問題：有供應(yīng)點(供應(yīng)量為1) 、需求點(需求量為1) 、轉(zhuǎn)運點、沒有弧的容量限制，目標(biāo)是通過網(wǎng)絡(luò)到目的地的總

12、距離最短。第22頁，共73頁。5.3 最大流問題在許多實際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等。而網(wǎng)絡(luò)系統(tǒng)最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)中的實際問題起著十分重要的作用。最大流問題也與網(wǎng)絡(luò)中的流有關(guān)，但目標(biāo)不是使得流的總成本最小，而是尋找一個流的方案，使得通過網(wǎng)絡(luò)的流量最大。除了目標(biāo)（流最大化和成本最小化）不一樣外，最大流問題的特征和最小費用流問題的特征非常相似。第23頁，共73頁。5.3 最大流問題例5.2 某公司要從起始點vs（發(fā)點）運送貨物到目的地vt（收點），其網(wǎng)絡(luò)圖如圖54（下一張幻燈片）所示。圖

13、中每條弧（節(jié)點i-節(jié)點j）旁邊的權(quán)cij表示這段運輸線路的最大通過能力（容量）。要求制定一個運輸方案，使得從vs到vt的運貨量達到最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。第24頁，共73頁。5.3 最大流問題708060403050407050vsv1v2v3v5v4vt第25頁，共73頁。5.3 最大流問題例5.2最大流問題的線性規(guī)劃數(shù)學(xué)模型：（1）決策變量 設(shè)fij為通過?。ü?jié)點i-節(jié)點j）的流量。（2）目標(biāo)函數(shù) 本問題的目標(biāo)是從vs流出的總流量最大。 （3）約束條件(轉(zhuǎn)運點的凈流量為0、弧的容量限制、非負）第26頁，共73頁。5.3 最大流問題例5.2最大流問題電子表格模型第27頁，

14、共73頁。5.3 最大流問題最大流問題的變形主要在于：有多個發(fā)點（供應(yīng)點）和多個收點（需求點）。例5.3 在例5.2的基礎(chǔ)上，增加了一個發(fā)點ps、一個收點pt、兩個轉(zhuǎn)運點p1和p2、以及與之相連的7條弧，如圖56（下一張幻燈片）所示。目標(biāo)是從vs和ps兩個發(fā)點運出的總流量最大。這是一個有2個發(fā)點（供應(yīng)點）和2個收點（需求點）的最大流問題。第28頁，共73頁。5.3 最大流問題70804010203050406030404070502060v1v2v3v5v4vtp1psptp2vs第29頁，共73頁。5.3 最大流問題例5.3的數(shù)學(xué)模型第30頁，共73頁。5.3 最大流問題例5.3的電子表格模

15、型第31頁，共73頁。5.3 最大流問題最大流問題的一些實際應(yīng)用：（1）通過配送網(wǎng)絡(luò)的流量最大，如例5.2和例5.3；（2）通過管道運輸系統(tǒng)的油的流量最大；（3）通過輸水系統(tǒng)的水的流量最大；（4）通過交通網(wǎng)絡(luò)的車輛的流量最大；等等。第32頁，共73頁。5.3 最大流問題例5.4 計劃編制問題。某市政工程公司在未來58月份內(nèi)需完成4項工程：修建一條地下通道、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表51。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應(yīng)如何分配勞動力完成所有工程，是否能按期完成？工程工期需要勞動力（人）A.地下通道57月100B

16、.人行天橋67月80C.新建道路58月200D.道路維修 8月80第33頁，共73頁。5.3 最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來求解（可設(shè)xij為工程i在j月投入的勞動力）外，還可以用最大流的方法來求解。將工程計劃用網(wǎng)絡(luò)圖58（下一張幻燈片）表示。圖中的節(jié)點5、6、7、8分別表示58月份，Ai、Bi、Ci、Di表示工程在第i個月內(nèi)完成的部分。用弧表示某月完成某項工程的狀態(tài)，弧的流量為所投入的勞動力，受到勞動力限制（弧旁邊的數(shù)字表示弧的容量，從S開始的弧，其容量為該公司共有勞動力120人；從節(jié)點5、6、7、8開始的弧以及到節(jié)點A、B、C、D的弧，其容量為任一工程在一個月內(nèi)的勞動

17、力投入不能超過80人；到收點T的弧，其容量為每個工程所需勞動力）。合理安排每個月各工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求圖58從發(fā)點到收點的最大流問題。第34頁，共73頁。5.3 最大流問題S675B6A58C5A6C6A7D8C8B7C7BCADT12080801008020080注意：增加一個起點和一個終點，其容量是供應(yīng)量和需求量第35頁，共73頁。5.3 最大流問題例5.4市政工程公司勞動力分配電子表格模型P162求解結(jié)果（每個月的勞動力分配）如表52所示。5月份有剩余勞動力20人，4項工程恰好按期完成。月份投入勞動力項目A項目B項目C項目D5100208

18、0612040807120804081204080合計4601008020080第36頁，共73頁。5.3 最大流問題最小費用最大流問題在實際的網(wǎng)絡(luò)應(yīng)用當(dāng)中，當(dāng)涉及到流的問題時，有時考慮的不只是流量，還要考慮費用多少的問題。比如一個鐵路運輸系統(tǒng)的網(wǎng)絡(luò)流，不但要考慮網(wǎng)絡(luò)系統(tǒng)的貨運量最大，又要考慮總費用最小。最小費用最大流就是要解決這一類的問題。所謂最小費用最大流問題就是：給定一個帶收點和發(fā)點的網(wǎng)絡(luò)，對每一條弧（節(jié)點i-節(jié)點j）,除了給出容量cij外，還給出了這條弧的單位流量的費用bij ，要求一個最大流F，并使得總運費用最小。最小費用最大流問題也是一個線性規(guī)劃問題。第37頁，共73頁。5.3 最

19、大流問題例5.5 某公司有一個管道網(wǎng)絡(luò)（如圖510所示，下一張幻燈片），使用這個網(wǎng)絡(luò)可以把石油從采地v1運送到銷地v7。由于輸油管道長短不一，每段管道除了有不同的流量cij限制外，還有不同的單位流量的費用bij。每段管道旁邊括號內(nèi)的數(shù)值意義為（cij，bij）。如果使用這個網(wǎng)絡(luò)系統(tǒng)，從采地v1向銷地v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最小？第38頁，共73頁。5.3 最大流問題(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)v1v7v6v5v4v3v2第39頁，共73頁。5.3 最大流問題解：用線性規(guī)劃來求解此

20、題，分為兩步走。第一步：先求出此網(wǎng)絡(luò)系統(tǒng)的最大流量F。數(shù)學(xué)模型P164電子表格模型P165求得的最大流量F=10第二步：在最大流量F的所有解中，找出一個最小費用的解。數(shù)學(xué)模型P166電子表格模型P166求得的最小費用為145第40頁，共73頁。作業(yè)： 第190頁 第1題（最小費用流、最大流）周三上機：第145頁 第11題（指派問題） 第十二周上機以及作業(yè)第41頁，共73頁。5.4 最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等最短路問題的最普遍的應(yīng)用是在兩個點之間尋找最短路，是最小費用流問題的一種特殊類型：源的供應(yīng)

21、量為1 、目的地（需求點）的需求量為1 、轉(zhuǎn)運點的凈流量為0、沒有弧的容量限制，目標(biāo)：通過網(wǎng)絡(luò)到目的地的總距離最短。第42頁，共73頁。5.4 最短路問題例5.6 某人每天從住處v1開車到工作地v7上班，圖中各弧旁的數(shù)字表示道路的長度（公里），試問該人應(yīng)選擇哪條路線，從家出發(fā)到工作地，路上行駛的總距離最短。v1v2v3v4v5v6v729683.51452.53第43頁，共73頁。5.4 最短路問題解：這是一個最短路問題。其數(shù)學(xué)模型為：（1）決策變量：設(shè)xij為弧(節(jié)點i-節(jié)點j)是否走（1表示走，0表示不走）。（2）目標(biāo)函數(shù)本問題的目標(biāo)是總距離最短。（3）約束條件(節(jié)點凈流量、非負）P169

22、第44頁，共73頁。5.4 最短路問題例5.6的最短路問題的電子表格模型第45頁，共73頁。5.4 最短路問題最短路問題的應(yīng)用很廣，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。下面舉兩個例子：（1）設(shè)備更新問題；（2）新產(chǎn)品開發(fā)時間問題。第46頁，共73頁。5.4 最短路問題例5.7 設(shè)備更新問題。某工廠的某臺機器可連續(xù)工作4年，決策者每年年初都要決定機器是否需要更新。若購置新機器，就要支付購置費用；若繼續(xù)使用，則需要支付維修與運行費用，而且隨著機器使用的年限費用逐年增多。已知計劃期（4年）中每年的購置價格及維修與運行費用。試制定今后4年的機器更新計劃，使總的支付費用最少。年限1234購置費（

23、萬元）2.52.62.83.1維修與運行費（萬元）11.524第47頁，共73頁。5.4 最短路問題解：把該問題看作最短路問題。 設(shè)節(jié)點1和節(jié)點5表示計劃期的始點和終點（節(jié)點5可以理解為第4年末）。圖515中各?。╥，j）表示第i年初購進的機器使用到j(luò)年初（即j-1年底），弧旁的數(shù)字由表53中的數(shù)據(jù)計算得到?；￠L購置價格使用多年的維修與運行總費用 例如，考慮從節(jié)點1到節(jié)點3的弧，這條弧對應(yīng)的是在第1年初購進的機器，使用到3年初（即使用了2年），所以 從到的弧長2.51+1.5=5（萬元）第48頁，共73頁。5.4 最短路問題例5.7 設(shè)備更新問題的網(wǎng)絡(luò)模型 因此，把求最優(yōu)的設(shè)備更新問題轉(zhuǎn)化為求

24、節(jié)點1到節(jié)點5的最短路問題135243.53.63.84.111575.35.17.1第49頁，共73頁。5.4 最短路問題例5.7的電子表格模型第50頁，共73頁。5.4 最短路問題如果已知不同役齡機器年末的處理價格如表54所示，那么在這計劃期（4年）機器的最優(yōu)更新計劃又會怎樣？表54 不同役齡機器年末的處理價格使用年數(shù)1234處理價（萬元）21.61.31.1第51頁，共73頁。5.4 最短路問題這還是一個最短路問題，網(wǎng)絡(luò)模型不變，還如圖515所示，只是弧長不同。 弧長購置價格使用多年的維修與運行總費用使用多年后處理價第52頁，共73頁。5.4 最短路問題有處理價格的設(shè)備更新問題的電子表格

25、模型第53頁，共73頁。5.4 最短路問題例5.8 新產(chǎn)品投放市場決策。 已知新產(chǎn)品計劃20個月后投放市場，但還有四個沒有時間重疊的階段沒有完成，而每個階段的實施水平可以從正常水平提高為優(yōu)先水平或應(yīng)急水平，使之能夠加速完成；而且最后三個階段中都可以考慮提高實施水平。第一階段可以以正常速度，也可以加速完成。表55（P174）列出了在這些水平下所需的時間。 管理層給這四個階段的預(yù)算撥款為3000萬元，每個階段的費用如表56 （P174）所示。 管理層希望確定這四個階段各自應(yīng)該采取哪一種水平，從而在3000萬元預(yù)算限制內(nèi)，使得這種產(chǎn)品可以盡早地推向市場。第54頁，共73頁。5.4 最短路問題解：這個

26、問題可以用最短路問題來求解。圖518（P175）是該問題的網(wǎng)絡(luò)圖，每個節(jié)點代表了那個時間點的情況。一個虛擬目的地(節(jié)點T)(下一張幻燈片)電子表格模型P176177由于四個階段，每個階段都要完成且完成一次，所以可以用第6章的0-1整數(shù)規(guī)劃來求解。第55頁，共73頁。5.4 最短路問題對于有多個實際目的地或有多個實際出發(fā)地的最短路問題的處理方法：當(dāng)網(wǎng)絡(luò)中有多個實際目的地時，在每個實際目的地和虛擬目的地之間插入一條長度為0的弧，從而使得網(wǎng)絡(luò)中仍然只有一個目的地。同樣地，如果網(wǎng)絡(luò)中有多個實際出發(fā)地，可以增加一個虛擬出發(fā)地，虛擬出發(fā)地到實際出發(fā)地的弧長也是0。第56頁，共73頁。5.5 最小支撐樹問題

27、許多網(wǎng)絡(luò)問題可以歸結(jié)為最小支撐樹問題。例如，設(shè)計長度最小的公路網(wǎng)把若干城市（鄉(xiāng)村）聯(lián)系起來；設(shè)計用料最省的電話線網(wǎng)（光纖）把有關(guān)單位聯(lián)系起來，等等。這種問題的目標(biāo)是設(shè)計網(wǎng)絡(luò)。雖然節(jié)點已經(jīng)給出，但必須決定在網(wǎng)絡(luò)中要加入哪些邊。特別地，向網(wǎng)絡(luò)中插入的每一條可能的邊都有成本。為了使得每兩個節(jié)點之間形成路，需要提供足夠的邊。目標(biāo)就是以某種方法完成網(wǎng)絡(luò)設(shè)計，使得邊的總成本最小。這種問題稱為最小支撐樹問題。第57頁，共73頁。5.5 最小支撐樹問題例5.9 某公司鋪設(shè)光導(dǎo)纖維網(wǎng)絡(luò)問題。 某公司的管理層已經(jīng)決定鋪設(shè)最先進的光導(dǎo)纖維網(wǎng)絡(luò)，為它的主要中心之間提供高速通信（數(shù)據(jù)、聲音和圖像）。圖520（下一張幻燈

28、片）中的節(jié)點顯示了該公司主要中心（包括公司的總部、巨型計算機、研究區(qū)、生產(chǎn)和配送中心等）的分布圖。虛線是鋪設(shè)纖維光纜可能的位置。每條虛線旁邊的數(shù)字表示了如果選擇在這個位置鋪設(shè)光纜需要花費的成本。 為了充分利用光纖技術(shù)在中心之間高速通信的優(yōu)勢，不需要在每兩個中心之間都用一條光纜把它們直接連接起來?，F(xiàn)在的問題就是要確定需要鋪設(shè)哪些光纜使得提供給每兩個中心之間的高速通信的總成本最低。實際上，這就是一個最小支撐樹問題。第58頁，共73頁。5.5 最小支撐樹問題425414371572ABDCEFG第59頁，共73頁。5.5 最小支撐樹問題通過“貪婪算法”來求解。求解最小支撐樹問題的貪婪算法有很多。比如

29、，Kruskal算法，其步驟如下：（1）選擇第一條邊：選擇成本最低的備選邊；（2）選擇下一條邊：從剩下的邊中取一條邊滿足：（a）最小邊；（b）不構(gòu)成圈；（3）重復(fù)第（2）步驟，直到選取的邊數(shù)為節(jié)點數(shù)-1。此時就得到了最優(yōu)解（最小支撐樹）。處理成本相同的邊：當(dāng)有幾條邊同時是成本最低的邊時，任意選擇一條邊不會影響最后的最優(yōu)解。利用Kruskal算法求解例5.9的最小支撐樹的步驟P181182第60頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題一個推銷員從n個城市中的某個城市出發(fā)，到其他n1個城市推銷貨物，每個城市都必須訪問并且只訪問一次，最后回到出發(fā)地，如何安排他的行走路線使總距離最短，這就是貨郎

30、擔(dān)問題或旅行售貨員問題。第61頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題例5.10 某電動汽車公司和學(xué)校合作，擬定在校園內(nèi)開通無污染無噪音的“綠色交通”路線。圖523是教學(xué)樓和學(xué)生宿舍樓的分布圖，邊上的數(shù)字為汽車通過兩點間的正常時間（分鐘）。電動汽車公司應(yīng)如何設(shè)計一條行駛路線，使汽車通過每一處教學(xué)樓和宿舍樓一次后總時間最少。ABCDEF42.231.51.61.82.62.82.84.2第62頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題對于貨郎擔(dān)問題，也是將邊看成長度相等方向相反的兩條弧，其線性規(guī)劃模型P184。用Excel求解貨郎擔(dān)問題的想法來源于用Excel求解最短路問題，但要修改。

31、由于在最短路問題中，有些節(jié)點可以不經(jīng)過，但在貨郎擔(dān)問題中要求每個節(jié)點都要恰好經(jīng)過一次，所以約束條件改為將每個節(jié)點的總流入和總流出分開。也就是說，每個節(jié)點有兩個約束（總流入=1和總流出=1），而非最短路問題的一個凈流量約束。改進后的Excel方法，有時可以得到只有一個大回路的最優(yōu)解（此時求解結(jié)束），但經(jīng)常會得到有幾個小回路的解，此時就應(yīng)該再增加去掉小回路的約束。第63頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題解：對于例子5.10，第一步：將每個節(jié)點的總流入和總流出分開，電子表格模型如圖524所示。Excel求解結(jié)果為：AD、BC、EF，也就是說，分成3個小的回路。此時的總時間為13.2分鐘。

32、第64頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題第二步：去掉第一步的3個小回路。在圖524的基礎(chǔ)上，增加這3對節(jié)點（教學(xué)樓和學(xué)生宿舍樓）不能有回路的約束，電子表格模型如圖525所示。Excel求解結(jié)果為：A-C-B-E-F-D-A，也就是說，求得一個大回路，此時求解結(jié)束。如果還存在有3個節(jié)點或3個節(jié)點以上的小回路，還需增加新的約束，去掉小回路。第65頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路問題一個郵遞員從郵局出發(fā)，將郵件投遞到他管轄的所有街道，最后回到郵局，如何安排他的行駛路線，使總路長最短。這個問題由我國數(shù)學(xué)家管梅谷教授于1962年首先提出來的，因此稱為“中國郵路問題”。貨郎擔(dān)問題與中國郵路問題的不同之處是前者要遍歷圖的所有節(jié)點，后者要遍歷圖的所有邊。第66頁，共73頁。5.6 貨郎擔(dān)問題和中國郵路