運(yùn)籌學(xué)網(wǎng)絡(luò)最優(yōu)化問題

實(shí)用運(yùn)籌學(xué)

－運(yùn)用Excel建模和求解第5章網(wǎng)絡(luò)最優(yōu)化問題本章內(nèi)容要點(diǎn)網(wǎng)絡(luò)最優(yōu)化問題的基本概念網(wǎng)絡(luò)最優(yōu)化問題的四種主要類型：最小費(fèi)用流、最大流、最短路、最小支撐樹各種網(wǎng)絡(luò)最優(yōu)化問題的建模與應(yīng)用本章節(jié)內(nèi)容5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念5.2最小費(fèi)用流問題5.3最大流問題5.4最短路問題5.5最小支撐樹問題5.6貨郎擔(dān)問題和中國郵路問題本章主要內(nèi)容框架圖5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念網(wǎng)絡(luò)在各種實(shí)際背景問題中以各種各樣的形式存在。交通、電子和通訊網(wǎng)絡(luò)遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡(luò)規(guī)劃也廣泛用于解決不同領(lǐng)域中的各種問題，如生產(chǎn)、分配、項(xiàng)目計劃、廠址選擇、資源管理和財務(wù)策劃等等。網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效的直觀和概念上的幫助，廣泛應(yīng)用于科學(xué)、社會和經(jīng)濟(jì)活動的各個領(lǐng)域中。近些年來，運(yùn)籌學(xué)（管理科學(xué)）中一個振奮人心的發(fā)展是它的網(wǎng)絡(luò)最優(yōu)化問題的方法論和應(yīng)用方面都取得了不同尋常的飛速發(fā)展。5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念許多研究的對象往往可以用一個圖表示，研究的目的歸結(jié)為圖的極值問題。運(yùn)籌學(xué)中研究的圖具有下列特征：

(1)用點(diǎn)表示研究對象，用連線（不帶箭頭的邊或帶箭頭的弧）表示對象之間某種關(guān)系；

(2)強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀；

(3)每條邊上都賦有一個權(quán)，其圖稱為賦權(quán)圖。實(shí)際中權(quán)可以代表兩點(diǎn)之間的距離、費(fèi)用、利潤、時間、容量等不同的含義；

(4)建立一個網(wǎng)絡(luò)模型，求最大值或最小值。5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念v1v3v5v2v4v68736548521對于該網(wǎng)絡(luò)圖，可以提出許多極值問題5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念（1）將某個點(diǎn)vi的物資或信息送到另一個點(diǎn)vj，使得運(yùn)送成本最小。這屬于最小費(fèi)用流問題。（2）將某個點(diǎn)vi的物資或信息送到另一個點(diǎn)vj，使得流量最大。這屬于最大流問題。（3）從某個點(diǎn)vi出發(fā)到達(dá)另一個點(diǎn)vj，怎樣安排路線使得總距離最短或總費(fèi)用最小。這屬于最短路問題。5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念（4）點(diǎn)vi表示自來水廠及用戶，vi與vj之間的邊表示兩點(diǎn)間可以鋪設(shè)管道，權(quán)為vi與vj間鋪設(shè)管道的距離或費(fèi)用，極值問題是如何鋪設(shè)管道，將自來水送到其他5個用戶并且使總的費(fèi)用最小。這屬于最小支撐樹問題。

(5)售貨員從某個點(diǎn)vi出發(fā)走過其他所有點(diǎn)后回到原點(diǎn)vi，如何安排路線使總路程最短。這屬于貨郎擔(dān)問題或旅行售貨員問題。（6）郵遞員從郵局vi出發(fā)要經(jīng)過每一條邊將郵件送到用戶手中，最后回到郵局vi，如何安排路線使總路程最短。這屬于中國郵遞員問題。5.1網(wǎng)絡(luò)最優(yōu)化問題基本概念網(wǎng)絡(luò)最優(yōu)化問題類型主要包括：（1）最小費(fèi)用流問題；（2）最大流問題；（3）最短路問題；（4）最小支撐樹問題；（5）貨郎擔(dān)問題和中國郵路問題，等等5.2最小費(fèi)用流問題最小費(fèi)用流問題的模型在網(wǎng)絡(luò)最優(yōu)化中扮演著重要的角色，因?yàn)樗倪m用性很廣，并且求解方法容易。通常最小費(fèi)用流問題用于最優(yōu)化貨物從供應(yīng)點(diǎn)到需求點(diǎn)的網(wǎng)絡(luò)。目標(biāo)是在通過網(wǎng)絡(luò)配送貨物時，以最小的成本滿足需求，一種典型的應(yīng)用就是使得配送網(wǎng)絡(luò)的運(yùn)營最優(yōu)。最小費(fèi)用流問題的特殊類型包括運(yùn)輸問題和指派問題，以及在下面將要提到的兩種重要類型：最大流問題和最短路問題。5.2最小費(fèi)用流問題例5.1某公司有兩個工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)送到兩個倉庫中。其配送網(wǎng)絡(luò)圖如圖5－2所示。目標(biāo)是確定一個運(yùn)輸方案（即每條路線運(yùn)送多少單位的產(chǎn)品），使通過配送網(wǎng)絡(luò)的運(yùn)輸成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（無限制，700）（無限制，900）5.2最小費(fèi)用流問題最小費(fèi)用流問題的三個基本概念：1、最小費(fèi)用流問題的構(gòu)成（網(wǎng)絡(luò)表示）（1）節(jié)點(diǎn)：包括供應(yīng)點(diǎn)、需求點(diǎn)和轉(zhuǎn)運(yùn)點(diǎn)；（2）?。嚎尚械倪\(yùn)輸線路（節(jié)點(diǎn)i->節(jié)點(diǎn)j），經(jīng)常有最大流量（容量）的限制。5.2最小費(fèi)用流問題2、最小費(fèi)用流問題的假設(shè)（1）至少一個供應(yīng)點(diǎn)；（2）至少一個需求點(diǎn)；（3）剩下都是轉(zhuǎn)運(yùn)點(diǎn)；（4）通過弧的流只允許沿著箭頭方向流動，通過弧的最大流量取決于該弧的容量；（5）網(wǎng)絡(luò)中有足夠的弧提供足夠容量，使得所有在供應(yīng)點(diǎn)中產(chǎn)生的流都能夠到達(dá)需求點(diǎn)；（有解）（6）在流的單位成本已知前提下，通過每一條弧的流的成本和流量成正比；（目標(biāo)是線性的）（7）最小費(fèi)用流問題的目標(biāo)在滿足給定需求條件下，使得通過網(wǎng)絡(luò)供應(yīng)的總成本最?。ɑ蚩偫麧欁畲螅?.2最小費(fèi)用流問題3、最小費(fèi)用流問題的解的特征（1）具有可行解的特征：在以上的假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點(diǎn)所提供的流量總和等于需求點(diǎn)所需要的流量總和時（即平衡條件），最小費(fèi)用流問題有可行解；（2）具有整數(shù)解的特征：只要其所有的供應(yīng)、需求和弧的容量都是整數(shù)值，那么任何最小費(fèi)用流問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解（與運(yùn)輸問題和指派問題的解一樣）。因此，沒有必要加上所有決策變量都是整數(shù)的約束條件。5.2最小費(fèi)用流問題最小費(fèi)用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fij為通過弧（節(jié)點(diǎn)i->節(jié)點(diǎn)j）的流量。（2）目標(biāo)是通過網(wǎng)絡(luò)供應(yīng)的總成本最小。（3）約束條件

①所有供應(yīng)點(diǎn)：凈流量（總流出減總流入）為正； ②所有轉(zhuǎn)運(yùn)點(diǎn)：凈流量為零； ③所有需求點(diǎn)：凈流量為負(fù)； ④所有弧的流量fij受到弧的容量限制； ⑤所有弧的流量fij非負(fù)。5.2最小費(fèi)用流問題例5.1最小費(fèi)用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fij為通過弧(節(jié)點(diǎn)i->節(jié)點(diǎn)j)的流量。（2）目標(biāo)函數(shù)本問題的目標(biāo)是總運(yùn)輸成本最小。5.2最小費(fèi)用流問題（3）約束條件(節(jié)點(diǎn)凈流量、弧的容量限制、非負(fù)）①供應(yīng)點(diǎn)F1:

供應(yīng)點(diǎn)F2: ②轉(zhuǎn)運(yùn)點(diǎn)DC: ③需求點(diǎn)W1:

需求點(diǎn)W2: ④弧的容量限制：⑤非負(fù)：5.2最小費(fèi)用流問題

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

大規(guī)模的最小費(fèi)用流問題的求解一般采用“網(wǎng)絡(luò)單純法（NetworkSimplexMethod）”?，F(xiàn)在，許多公司都使用網(wǎng)絡(luò)單純法來解決他們的最小費(fèi)用流問題。有些問題是非常龐大的，有著數(shù)萬個節(jié)點(diǎn)和弧。有時，弧的數(shù)量甚至可能會多得多，達(dá)到幾百萬條。但Excel的規(guī)劃求解中沒有網(wǎng)絡(luò)單純法，但其他的線性規(guī)劃的商業(yè)軟件包通常都有這種方法。5.2最小費(fèi)用流問題最小費(fèi)用流問題有五種重要的特殊類型：（1）運(yùn)輸問題：有出發(fā)地(供應(yīng)點(diǎn)-供應(yīng)量)和目的地(需求點(diǎn)-需求量)，沒有轉(zhuǎn)運(yùn)點(diǎn)和弧的容量限制，目標(biāo)是總運(yùn)輸成本最小（或總利潤最大）。（2）指派類型：出發(fā)地(供應(yīng)點(diǎn)-供應(yīng)量為1)是人，目的地(需求點(diǎn)-需求量為1)是任務(wù)，沒有轉(zhuǎn)運(yùn)點(diǎn)和弧的容量限制，目標(biāo)是總指派成本最?。ɑ蚩偫麧欁畲螅＃?）轉(zhuǎn)運(yùn)問題：有出發(fā)地(供應(yīng)點(diǎn)-供應(yīng)量)和目的地(需求點(diǎn)-需求量)，有轉(zhuǎn)運(yùn)點(diǎn)，但沒有弧的容量限制(或有容量限制)，目標(biāo)是總流量費(fèi)用最?。ɑ蚩偫麧欁畲螅?。5.2最小費(fèi)用流問題最小費(fèi)用流問題有五種重要的特殊類型(續(xù))：（4）最大流問題：有供應(yīng)點(diǎn)、需求點(diǎn)、轉(zhuǎn)運(yùn)點(diǎn)、弧的容量限制，但沒有供應(yīng)量和需求量的限制，目標(biāo)是通過網(wǎng)絡(luò)到目的地的總流量最大。（5）最短路問題：有供應(yīng)點(diǎn)(供應(yīng)量為1)、需求點(diǎn)(需求量為1)、轉(zhuǎn)運(yùn)點(diǎn)、沒有弧的容量限制，目標(biāo)是通過網(wǎng)絡(luò)到目的地的總距離最短。5.3最大流問題在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等。而網(wǎng)絡(luò)系統(tǒng)最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)中的實(shí)際問題起著十分重要的作用。最大流問題也與網(wǎng)絡(luò)中的流有關(guān)，但目標(biāo)不是使得流的總成本最小，而是尋找一個流的方案，使得通過網(wǎng)絡(luò)的流量最大。除了目標(biāo)（流最大化和成本最小化）不一樣外，最大流問題的特征和最小費(fèi)用流問題的特征非常相似。5.3最大流問題例5.2

某公司要從起始點(diǎn)vs（發(fā)點(diǎn)）運(yùn)送貨物到目的地vt（收點(diǎn)），其網(wǎng)絡(luò)圖如圖5－4（下一張幻燈片）所示。圖中每條弧（節(jié)點(diǎn)i->節(jié)點(diǎn)j）旁邊的權(quán)cij表示這段運(yùn)輸線路的最大通過能力（容量）。要求制定一個運(yùn)輸方案，使得從vs到vt的運(yùn)貨量達(dá)到最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。5.3最大流問題708060403050407050vsv1v2v3v5v4vt5.3最大流問題例5.2最大流問題的線性規(guī)劃數(shù)學(xué)模型：（1）決策變量設(shè)fij為通過?。ü?jié)點(diǎn)i->節(jié)點(diǎn)j）的流量。（2）目標(biāo)函數(shù)本問題的目標(biāo)是從vs流出的總流量最大。（3）約束條件(轉(zhuǎn)運(yùn)點(diǎn)的凈流量為0、弧的容量限制、非負(fù)）5.3最大流問題例5.2最大流問題電子表格模型5.3最大流問題最大流問題的變形主要在于：有多個發(fā)點(diǎn)（供應(yīng)點(diǎn)）和多個收點(diǎn)（需求點(diǎn)）。例5.3

在例5.2的基礎(chǔ)上，增加了一個發(fā)點(diǎn)ps、一個收點(diǎn)pt、兩個轉(zhuǎn)運(yùn)點(diǎn)p1和p2、以及與之相連的7條弧，如圖5－6（下一張幻燈片）所示。目標(biāo)是從vs和ps兩個發(fā)點(diǎn)運(yùn)出的總流量最大。這是一個有2個發(fā)點(diǎn)（供應(yīng)點(diǎn)）和2個收點(diǎn)（需求點(diǎn)）的最大流問題。5.3最大流問題70804010203050406030404070502060v1v2v3v5v4vtp1psptp2vs5.3最大流問題例5.3的數(shù)學(xué)模型5.3最大流問題例5.3的電子表格模型5.3最大流問題最大流問題的一些實(shí)際應(yīng)用：（1）通過配送網(wǎng)絡(luò)的流量最大，如例5.2和例5.3；（2）通過管道運(yùn)輸系統(tǒng)的油的流量最大；（3）通過輸水系統(tǒng)的水的流量最大；（4）通過交通網(wǎng)絡(luò)的車輛的流量最大；等等。5.3最大流問題例5.4計劃編制問題。某市政工程公司在未來5～8月份內(nèi)需完成4項(xiàng)工程：修建一條地下通道、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表5－1。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應(yīng)如何分配勞動力完成所有工程，是否能按期完成？工程工期需要勞動力（人）A.地下通道5～7月100B.人行天橋6～7月80C.新建道路5～8月200D.道路維修8月805.3最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來求解（可設(shè)xij為工程i在j月投入的勞動力）外，還可以用最大流的方法來求解。將工程計劃用網(wǎng)絡(luò)圖5－8（下一張幻燈片）表示。圖中的節(jié)點(diǎn)5、6、7、8分別表示5～8月份，Ai、Bi、Ci、Di表示工程在第i個月內(nèi)完成的部分。用弧表示某月完成某項(xiàng)工程的狀態(tài)，弧的流量為所投入的勞動力，受到勞動力限制（弧旁邊的數(shù)字表示弧的容量，從S開始的弧，其容量為該公司共有勞動力120人；從節(jié)點(diǎn)5、6、7、8開始的弧以及到節(jié)點(diǎn)A、B、C、D的弧，其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人；到收點(diǎn)T的弧，其容量為每個工程所需勞動力）。合理安排每個月各工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求圖5－8從發(fā)點(diǎn)到收點(diǎn)的最大流問題。5.3最大流問題S675B6A58C5A6C6A7D8C8B7C7BCADT12080801008020080注意：增加一個起點(diǎn)和一個終點(diǎn)，其容量是供應(yīng)量和需求量5.3最大流問題例5.4市政工程公司勞動力分配電子表格模型P162求解結(jié)果（每個月的勞動力分配）如表5－2所示。5月份有剩余勞動力20人，4項(xiàng)工程恰好按期完成。月份投入勞動力項(xiàng)目A項(xiàng)目B項(xiàng)目C項(xiàng)目D51002080612040807120804081204080合計46010080200805.3最大流問題最小費(fèi)用最大流問題在實(shí)際的網(wǎng)絡(luò)應(yīng)用當(dāng)中，當(dāng)涉及到流的問題時，有時考慮的不只是流量，還要考慮費(fèi)用多少的問題。比如一個鐵路運(yùn)輸系統(tǒng)的網(wǎng)絡(luò)流，不但要考慮網(wǎng)絡(luò)系統(tǒng)的貨運(yùn)量最大，又要考慮總費(fèi)用最小。最小費(fèi)用最大流就是要解決這一類的問題。所謂最小費(fèi)用最大流問題就是：給定一個帶收點(diǎn)和發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條弧（節(jié)點(diǎn)i->節(jié)點(diǎn)j）,除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij

，要求一個最大流F，并使得總運(yùn)費(fèi)用最小。最小費(fèi)用最大流問題也是一個線性規(guī)劃問題。5.3最大流問題例5.5

某公司有一個管道網(wǎng)絡(luò)（如圖5－10所示，下一張幻燈片），使用這個網(wǎng)絡(luò)可以把石油從采地v1運(yùn)送到銷地v7。由于輸油管道長短不一，每段管道除了有不同的流量cij限制外，還有不同的單位流量的費(fèi)用bij。每段管道旁邊括號內(nèi)的數(shù)值意義為（cij，bij）。如果使用這個網(wǎng)絡(luò)系統(tǒng)，從采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最?。?.3最大流問題(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)v1v7v6v5v4v3v25.3最大流問題解：用線性規(guī)劃來求解此題，分為兩步走。第一步：先求出此網(wǎng)絡(luò)系統(tǒng)的最大流量F。數(shù)學(xué)模型P164電子表格模型P165求得的最大流量F=10第二步：在最大流量F的所有解中，找出一個最小費(fèi)用的解。數(shù)學(xué)模型P166電子表格模型P166求得的最小費(fèi)用為1455.4最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等最短路問題的最普遍的應(yīng)用是在兩個點(diǎn)之間尋找最短路，是最小費(fèi)用流問題的一種特殊類型：源的供應(yīng)量為1、目的地（需求點(diǎn)）的需求量為1、轉(zhuǎn)運(yùn)點(diǎn)的凈流量為0、沒有弧的容量限制，目標(biāo)：通過網(wǎng)絡(luò)到目的地的總距離最短。5.4最短路問題例5.6

某人每天從住處v1開車到工作地v7上班，圖中各弧旁的數(shù)字表示道路的長度（公里），試問該人應(yīng)選擇哪條路線，從家出發(fā)到工作地，路上行駛的總距離最短。v1v2v3v4v5v6v729683.51452.535.4最短路問題解：這是一個最短路問題。其數(shù)學(xué)模型為：（1）決策變量：設(shè)xij為弧(節(jié)點(diǎn)i->節(jié)點(diǎn)j)是否走（1表示走，0表示不走）。（2）目標(biāo)函數(shù)本問題的目標(biāo)是總距離最短。（3）約束條件(節(jié)點(diǎn)凈流量、非負(fù)）P1695.4最短路問題例5.6的最短路問題的電子表格模型5.4最短路問題最短路問題的應(yīng)用很廣，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。下面舉兩個例子：（1）設(shè)備更新問題；（2）新產(chǎn)品開發(fā)時間問題。5.4最短路問題例5.7設(shè)備更新問題。某工廠的某臺機(jī)器可連續(xù)工作4年，決策者每年年初都要決定機(jī)器是否需要更新。若購置新機(jī)器，就要支付購置費(fèi)用；若繼續(xù)使用，則需要支付維修與運(yùn)行費(fèi)用，而且隨著機(jī)器使用的年限費(fèi)用逐年增多。已知計劃期（4年）中每年的購置價格及維修與運(yùn)行費(fèi)用。試制定今后4年的機(jī)器更新計劃，使總的支付費(fèi)用最少。年限1234購置費(fèi)（萬元）2.52.62.83.1維修與運(yùn)行費(fèi)（萬元）11.5245.4最短路問題解：把該問題看作最短路問題。設(shè)節(jié)點(diǎn)1和節(jié)點(diǎn)5表示計劃期的始點(diǎn)和終點(diǎn)（節(jié)點(diǎn)5可以理解為第4年末）。圖5－15中各?。╥，j）表示第i年初購進(jìn)的機(jī)器使用到j(luò)年初（即j-1年底），弧旁的數(shù)字由表5－3中的數(shù)據(jù)計算得到?；￠L＝購置價格＋使用多年的維修與運(yùn)行總費(fèi)用例如，考慮從節(jié)點(diǎn)1到節(jié)點(diǎn)3的弧，這條弧對應(yīng)的是在第1年初購進(jìn)的機(jī)器，使用到3年初（即使用了2年），所以從①到③的弧長＝2.5＋1+1.5=5（萬元）5.4最短路問題例5.7設(shè)備更新問題的網(wǎng)絡(luò)模型因此，把求最優(yōu)的設(shè)備更新問題轉(zhuǎn)化為求節(jié)點(diǎn)1到節(jié)點(diǎn)5的最短路問題135243.53.63.84.111575.35.17.15.4最短路問題例5.7的電子表格模型5.4最短路問題如果已知不同役齡機(jī)器年末的處理價格如表5－4所示，那么在這計劃期（4年）機(jī)器的最優(yōu)更新計劃又會怎樣？表5－4不同役齡機(jī)器年末的處理價格使用年數(shù)1234處理價（萬元）21.61.31.15.4最短路問題這還是一個最短路問題，網(wǎng)絡(luò)模型不變，還如圖5－15所示，只是弧長不同。

弧長＝購置價格＋使用多年的維修與運(yùn)行總費(fèi)用－使用多年后處理價5.4最短路問題有處理價格的設(shè)備更新問題的電子表格模型5.4最短路問題例5.8新產(chǎn)品投放市場決策。已知新產(chǎn)品計劃20個月后投放市場，但還有四個沒有時間重疊的階段沒有完成，而每個階段的實(shí)施水平可以從正常水平提高為優(yōu)先水平或應(yīng)急水平，使之能夠加速完成；而且最后三個階段中都可以考慮提高實(shí)施水平。第一階段可以以正常速度，也可以加速完成。表5－5（P174）列出了在這些水平下所需的時間。管理層給這四個階段的預(yù)算撥款為3000萬元，每個階段的費(fèi)用如表5－6（P174）所示。管理層希望確定這四個階段各自應(yīng)該采取哪一種水平，從而在3000萬元預(yù)算限制內(nèi)，使得這種產(chǎn)品可以盡早地推向市場。5.4最短路問題解：這個問題可以用最短路問題來求解。圖5－18（P175）是該問題的網(wǎng)絡(luò)圖，每個節(jié)點(diǎn)代表了那個時間點(diǎn)的情況。一個虛擬目的地(節(jié)點(diǎn)T)(下一張幻燈片)電子表格模型P176－177由于四個階段，每個階段都要完成且完成一次，所以可以用第6章的0-1整數(shù)規(guī)劃來求解。5.4最短路問題對于有多個實(shí)際目的地或有多個實(shí)際出發(fā)地的最短路問題的處理方法：當(dāng)網(wǎng)絡(luò)中有多個實(shí)際目的地時，在每個實(shí)際目的地和虛擬目的地之間插入一條長度為0的弧，從而使得網(wǎng)絡(luò)中仍然只有一個目的地。同樣地，如果網(wǎng)絡(luò)中有多個實(shí)際出發(fā)地，可以增加一個虛擬出發(fā)地，虛擬出發(fā)地到實(shí)際出發(fā)地的弧長也是0。5.5最小支撐樹問題許多網(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é)點(diǎn)已經(jīng)給出，但必須決定在網(wǎng)絡(luò)中要加入哪些邊。特別地，向網(wǎng)絡(luò)中插入的每一條可能的邊都有成本。為了使得每兩個節(jié)點(diǎn)之間形成路，需要提供足夠的邊。目標(biāo)就是以某種方法完成網(wǎng)絡(luò)設(shè)計，使得邊的總成本最小。這種問題稱為最小支撐樹問題。5.5最小支撐樹問題例5.9某公司鋪設(shè)光導(dǎo)纖維網(wǎng)絡(luò)問題。某公司的管理層已經(jīng)決定鋪設(shè)最先進(jìn)的光導(dǎo)纖維網(wǎng)絡(luò)，為它的主要中心之間提供高速通信（數(shù)據(jù)、聲音和圖像）。圖5－20（下一張幻燈片）中的節(jié)點(diǎn)顯示了該公司主要中心（包括公司的總部、巨型計算機(jī)、研究區(qū)、生產(chǎn)和配送中心等）的分布圖。虛線是鋪設(shè)纖維光纜可能的位置。每條虛線旁邊的數(shù)字表示了如果選擇在這個位置鋪設(shè)光纜需要花費(fèi)的成本。

為了充分利用光纖技術(shù)在中心之間高速通信的優(yōu)勢，不需要在每兩個中心之間都用一條光纜把它們直接連接起來?，F(xiàn)在的問題就是要確定需要鋪設(shè)哪些光纜使得提供給每兩個中心之間的高速通信的總成本最低。實(shí)際上，這就是一個最小支撐樹問題。5.5最小支撐樹問題425414371572ABDCEFG5.5最小支撐樹問題通過“貪婪算法”來求解。求解最小支撐樹問題的貪婪算法有很多。比如，Kruskal算法，其步驟如下：（1）選擇第一條邊：選擇成本最低的備選邊；（2）選擇下一條邊：從剩下的邊中取一條邊滿足：（a）最小邊；（b）不構(gòu)成圈；（3）重復(fù)第（2）步驟，直到選取的邊數(shù)為節(jié)點(diǎn)數(shù)-1。此時就得到了最優(yōu)解（最小支撐樹）。處理成本相同的邊：當(dāng)有幾條邊同時是成本最低的邊時，任意選擇一條邊不會影響最后的最優(yōu)解。利用Kruskal算法求解例5.9的最小支撐樹的步驟P181－1825.6貨郎擔(dān)問題和中國郵路問題一個推銷員從n個城市中的某個城市出發(fā)，到其他n－1個城市推銷貨物，每個城市都必須訪問并且只訪問一次，最后回到出發(fā)地，如何安排他的行走路線使總距離最短，這就是貨郎擔(dān)問題或旅行售貨員問題。5.6貨郎擔(dān)問題和中國郵路問題例5.10

某電動汽車公司和學(xué)校合作，擬定在校園內(nèi)開通無污染無噪音的“綠色交通”路線。圖5－23是教學(xué)樓和學(xué)生宿舍樓的分布圖，邊上的數(shù)字為汽車通過兩點(diǎn)間的正常時間（分鐘）。電動汽車公司應(yīng)如何設(shè)計一條行駛路線，使汽車通過每一處教學(xué)樓和宿舍樓一次后總時間最少。ABCDEF42.231.51.61.82.62.82.84.25.6貨郎擔(dān)問題和中國郵路問題對于貨郎擔(dān)問題，也是將邊看成長度相等方向相反的兩條弧，其線性規(guī)劃模型P184。用Excel求解貨郎擔(dān)問題的想法來源于用Excel求解最短路問題，但要修改。由于在最短路問題中，有些節(jié)點(diǎn)可以不經(jīng)過，但在貨郎擔(dān)問題中要求每個節(jié)點(diǎn)都要恰好經(jīng)過一次，所以約束條件改為將每個節(jié)點(diǎn)的總流入和總流出分開。也就是說，每個節(jié)點(diǎn)有兩個約束（總流入=1和總流出=1），而非最短路問題的一個凈流量約束。改進(jìn)后的Excel方法，有時可以得到只有一個大回路的最優(yōu)解（此時求解結(jié)束），但經(jīng)常會得到有幾個小回路的解，此時就應(yīng)該再增加去掉小回路的約束。5.6貨郎擔(dān)問題和中國郵路問題解：對于例子5.10，第一步：將每個節(jié)點(diǎn)的總流入和總流出分開，電子表格模型如圖5－24所示。Excel求解結(jié)果為：A<->D、B<->C、E<->F，也就是說，分成3個小的回路。此時的總時間為13.2分鐘。5.6貨郎擔(dān)問題和中國郵路問題第二步：去掉第一步的3個小回路。在圖5－24的基礎(chǔ)上，增加這3對節(jié)點(diǎn)（教學(xué)樓和學(xué)生宿舍樓）不能有回路的約束，電子表格模型如圖5－25所示。Excel求解結(jié)果為：A->C->B->E->F->D->A，也就是說，求得一個大回路，此時求解結(jié)束。如果還存在有3個節(jié)點(diǎn)或3個節(jié)點(diǎn)以上的小回路，還需增加新的約束，去掉小回路。5.6貨郎擔(dān)問題和中國郵路問題一個郵遞員從郵局出發(fā)，將郵件投遞到