實用運籌學

－運用Excel建模和求解第5章網(wǎng)絡最優(yōu)化問題實用運籌學

－運用Excel建模和求解第5章本章內(nèi)容要點網(wǎng)絡最優(yōu)化問題的基本概念網(wǎng)絡最優(yōu)化問題的四種主要類型：最小費用流、最大流、最短路、最小支撐樹各種網(wǎng)絡最優(yōu)化問題的建模與應用本章內(nèi)容要點網(wǎng)絡最優(yōu)化問題的基本概念本章節(jié)內(nèi)容5.1網(wǎng)絡最優(yōu)化問題基本概念5.2最小費用流問題5.3最大流問題5.4最短路問題5.5最小支撐樹問題5.6貨郎擔問題和中國郵路問題本章節(jié)內(nèi)容5.1網(wǎng)絡最優(yōu)化問題基本概念本章主要內(nèi)容框架圖本章主要內(nèi)容框架圖圖論的起源和發(fā)展1736年，歐拉的哥尼斯堡七橋問題BACD圖論的起源和發(fā)展1736年，歐拉的哥尼斯堡七橋問題BACD圖論的起源和發(fā)展1847年，基爾霍夫，電網(wǎng)絡，樹”；1852年，《四色猜想》；1964年，華羅庚，《統(tǒng)籌方法平話》。1857年，凱萊，同分異構，“樹”；1956年，杜邦公司，CPM，關鍵路線法；1958年，美國海軍部，PERT，計劃評審技術；1962年，管梅谷，《中國郵路問題》；1859年，哈密頓，哈密頓回路；圖論的起源和發(fā)展1847年，基爾霍夫，電網(wǎng)絡，樹”；1第5章-網(wǎng)絡最優(yōu)化問題課件幾個例子例1

是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。北京天津濟南青島武漢南京上海鄭州連云港徐州幾個例子例1北京天津濟南青島武漢南京上海鄭州連云港徐例2旅行商問題/貨郎（擔）問題

(TSP-TravelingSalesmanProblem)

一名推銷員準備前往若干城市推銷產(chǎn)品.如何為他(她)設計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.例2旅行商問題/貨郎（擔）問題

(TSP-Traveling例3穩(wěn)定婚配

假設有n個男人和n個女人,每人都希望從n個異性中選擇一位自己的配偶.假設每人都對n個異性根據(jù)自己的偏好進行了排序,以此作為選擇配偶的基礎.當給定一種婚配方案(即給每人指定一個配偶)后,如果存在一個男人和一個女人不是互為配偶,但該男人喜歡該女人勝過其配偶,且該女人喜歡該男人也勝過其配偶,則該婚配方案稱為不穩(wěn)定的.安排穩(wěn)定的婚配方案的問題稱為穩(wěn)定婚配問題。例3穩(wěn)定婚配假設有n個男人和n個女人,每人都5.1網(wǎng)絡最優(yōu)化問題基本概念網(wǎng)絡在各種實際背景問題中以各種各樣的形式存在。交通、電子和通訊網(wǎng)絡遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡規(guī)劃也廣泛用于解決不同領域中的各種問題，如生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務策劃等等。網(wǎng)絡規(guī)劃為描述系統(tǒng)各組成部分之間的關系提供了非常有效的直觀和概念上的幫助，廣泛應用于科學、社會和經(jīng)濟活動的各個領域中。近些年來，運籌學（管理科學）中一個振奮人心的發(fā)展是它的網(wǎng)絡最優(yōu)化問題的方法論和應用方面都取得了不同尋常的飛速發(fā)展。5.1網(wǎng)絡最優(yōu)化問題基本概念網(wǎng)絡在各種實際背景問題中以各種5.1網(wǎng)絡最優(yōu)化問題基本概念許多研究的對象往往可以用一個圖表示，研究的目的歸結為圖的極值問題。運籌學中研究的圖具有下列特征：

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

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

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

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

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

①所有供應點：凈流量（總流出－總流入）為正；

②所有轉運點：凈流量為零；

③所有需求點：凈流量為負；

④所有弧的流量fij受到弧的容量限制；

⑤所有弧的流量fij非負。5.2最小費用流問題最小費用流問題的數(shù)學模型為：5.2最小費用流問題例5.1最小費用流問題的數(shù)學模型為：（1）決策變量：設fij為通過弧(節(jié)點i->節(jié)點j)的流量。（2）目標函數(shù)本問題的目標是總運輸成本最小5.2最小費用流問題例5.1最小費用流問題的數(shù)學模型為：5.2最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限制、非負）①供應點F1:

供應點F2: ②轉運點DC: ③需求點W1:

需求點W2: ④弧的容量限制：⑤非負：5.2最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限5.2最小費用流問題

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

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

在例5.2的基礎上，增加了一個發(fā)點ps、一個收點pt、兩個轉運點p1和p2、以及與之相連的7條弧，如圖5-6（下一張幻燈片）所示。目標是從vs和ps兩個發(fā)點運出的總流量最大。這是一個有2個發(fā)點（供應點）和2個收點（需求點）的最大流問題。5.3最大流問題最大流問題的變形主要在于：有多個發(fā)點（供應5.3最大流問題70804010203050406030404070502060v1v2v3v5v4vtp1psptp2vs5.3最大流問題7080401020305040603045.3最大流問題例5.3的數(shù)學模型5.3最大流問題例5.3的數(shù)學模型5.3最大流問題例5.3的電子表格模型5.3最大流問題例5.3的電子表格模型5.3最大流問題最大流問題的一些實際應用：（1）通過配送網(wǎng)絡的流量最大，如例5.2和例5.3；（2）通過管道運輸系統(tǒng)的油的流量最大；（3）通過輸水系統(tǒng)的水的流量最大；（4）通過交通網(wǎng)絡的車輛的流量最大；等等。5.3最大流問題最大流問題的一些實際應用：5.3最大流問題例5.4計劃編制問題。某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表5-1。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應如何分配勞動力完成所有工程，是否能按期完成？5.3最大流問題例5.4計劃編制問題。某市政工程公司在未5.3最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來求解（可設xij為工程i在j月投入的勞動力）外，還可以用最大流的方法來求解。將工程計劃用網(wǎng)絡圖5-8（下一張幻燈片）表示。圖中的節(jié)點5、6、7、8分別表示5～8月份，Ai、Bi、Ci、Di表示工程在第i個月內(nèi)完成的部分。用弧表示某月完成某項工程的狀態(tài)，弧的流量為所投入的勞動力，受到勞動力限制（弧旁邊的數(shù)字表示弧的容量，從S開始的弧，其容量為該公司共有勞動力120人；從節(jié)點5、6、7、8開始的弧以及到節(jié)點A、B、C、D的弧，其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人；到收點T的弧，其容量為每個工程所需勞動力）。合理安排每個月各工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求圖5-8從發(fā)點到收點的最大流問題。5.3最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來5.3最大流問題S675B6A58C5A6C6A7D8C8B7C7BCADT12080801008020080注意：增加一個起點S和一個終點T，其容量是供應量和需求量5.3最大流問題S675B6A58C5A6C6A7D8C85.3最大流問題例5.4市政工程公司勞動力分配電子表格模型P162求解結果（每個月的勞動力分配）如表5-2所示。5月份有剩余勞動力20人，4項工程恰好按期完成。5.3最大流問題例5.4市政工程公司勞動力分配電子表格模型5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力分配簡化版。在P161的工程計劃網(wǎng)絡圖中，可以去掉中間的節(jié)點A5～D8（共10個節(jié)點），直接將代表月份的節(jié)點（5、6、7、8）指向相應的工程節(jié)點（A、B、C、D），其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人。S6758BCADT120100802008080注意：增加一個起點S和一個終點T，其容量是供應量和需求量5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力分配簡化版。此時對應的電子表格模型也做相應的簡化。求得另外一個結果（每個月的勞動力分配）如下表所示。6月份有剩余勞動力20人，4項工程恰好按期完成。5.3最大流問題（補充）例5.4（補充）市政工程公司勞動5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（1）某公司有3個倉庫和4個零售店，各倉庫可提供的貨量及零售店的最大零售量如下表所示，打圈的表示公司指定該店可向相應的倉庫取貨。現(xiàn)在要求作一個調(diào)運方案，使得各店從各倉庫得到的總貨量最多。（答案：最大總貨量為41,4個零售店都能滿足）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（2）某產(chǎn)品從倉庫運往市場銷售，已知各倉庫的可供量、各市場的需求量及從倉庫到市場的運輸能力如下表所示（－表示無路）。試求從倉庫可運往市場的最大流量，各市場需求能否滿足？（答案：最大流量為110，市場B3只滿足50，其他市場都滿足）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（3）某單位招收懂俄、英、日、德、法文的翻譯各1人，現(xiàn)有5人應聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，問這5個人是否都能得到聘書？最多幾個得到招聘，招聘后每人從事哪一方面的翻譯任務？（4人）（4）已知有6臺機床Ai，6種零件Bi。機床A1可加工零件B1；A2可加工零件B1、B2；A3可加工零件B1、B2、B3；A4可加工零件B2；A5可加工零件B2、B3、B4；A6可加工零件B2、B5、B6。現(xiàn)在要求制定一個加工方案，使一臺機床只加工一種零件，一種零件只在一臺機床上加工，要求盡可能多地安排零件的加工。請把這個問題轉化為求網(wǎng)絡最大流的問題，求出能滿足上述條件的加工方案。（答案：最大流為5）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題最小費用最大流問題在實際的網(wǎng)絡應用當中，當涉及到流的問題時，有時考慮的不只是流量，還要考慮費用多少的問題。比如一個鐵路運輸系統(tǒng)的網(wǎng)絡流，不但要考慮網(wǎng)絡系統(tǒng)的貨運量最大，還要考慮總費用最小。最小費用最大流就是要解決這一類的問題。所謂最小費用最大流問題就是：給定一個帶收點和發(fā)點的網(wǎng)絡，對每一條弧（節(jié)點i->節(jié)點j）,除了給出容量cij外，還給出了這條弧的單位流量的費用bij

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

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

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

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

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

某電動汽車公司和學校合作，擬定在校園內(nèi)開通無污染無噪音的“綠色交通”路線。圖5-23是教學樓和學生宿舍樓的分布圖，邊上的數(shù)字為汽車通過兩點間的正常時間（分鐘）。電動汽車公司應如何設計一條行駛路線，使汽車通過每一處教學樓和宿舍樓一次后總時間最少。ABCDEF42.231.51.61.82.62.82.84.25.6貨郎擔問題和中國郵路問題例5.10某電動汽車公司和5.6貨郎擔問題和中國郵路問題對于貨郎擔問題，也是將邊看成長度相等方向相反的兩條弧，其線性規(guī)劃模型P184。用Excel求解貨郎擔問題的想法來源于用Excel求解最短路問題，但要修改。由于在最短路問題中，有些節(jié)點可以不經(jīng)過，但在貨郎擔問題中要求每個節(jié)點都要恰好經(jīng)過一次，所以約束條件改為將每個節(jié)點的總流入和總流出分開。也就是說，每個節(jié)點有兩個約束（總流入=1和總流出=1），而非最短路問題的一個凈流量約束。改進后的Excel方法，有時可以得到只有一個大回路的最優(yōu)解（此時求解結束），但經(jīng)常會得到有幾個小回路的解，此時就應該再增加去掉小回路的約束。5.6貨郎擔問題和中國郵路問題對于貨郎擔問題，也是將邊看成5.6貨郎擔問題和中國郵路問題解：對于例子5.10，第一步：將每個節(jié)點的總流入和總流出分開，電子表格模型如圖5-24所示。Excel求解結果為：A<->D、B<->C、E<->F，也就是說，分成3個小的回路。此時的總時間為13.2分鐘。5.6貨郎擔問題和中國郵路問題解：對于例子5.10，第一步5.6貨郎擔問題和中國郵路問題第二步：去掉第一步的3個小回路。在圖5-24的基礎上，增加這3對節(jié)點（教學樓和學生宿舍樓）不能有回路的約束，電子表格模型如圖5-25所示。Excel求解結果為：A->C->B->E->F->D->A，也就是說，求得一個大回路，此時求解結束。如果還存在有3個節(jié)點或3個節(jié)點以上的小回路，還需增加新的約束，去掉小回路5.6貨郎擔問題和中國郵路問題第二步：去掉第一步的3個小回5.6貨郎擔問題和中國郵路問題一個郵遞員從郵局出發(fā)，將郵件投遞到他管轄的所有街道，最后回到郵局，如何安排他的行駛路線，使總路長最短。這個問題由我國數(shù)學家管梅谷教授于1962年首先提出來的，因此稱為“中國郵路問題”。貨郎擔問題與中國郵路問題的不同之處是前者要遍歷圖的所有節(jié)點，后者要遍歷圖的所有邊。5.6貨郎擔問題和中國郵路問題一個郵遞員從郵局出發(fā)，將郵件5.6貨郎擔問題和中國郵路問題管梅谷教授還給出了求解“中國郵路問題”的“奇偶點圖上作業(yè)法”。這種解法通過添加重復邊（重復邊就是郵遞員重復經(jīng)過的街道），將所有奇點變?yōu)榕键c。但所添加的重復邊要滿足下列兩個條件：（1）每條邊最多重復一次；（2）所有回路中重復邊長之和不超過回路邊長之和的一半。在用“奇偶點圖上作業(yè)法”求解“中國郵路問題”時，需檢查圖中的每一條回路。當圖中回路較多時，檢查不便且容易出錯。對此，受求解最短路問題的Excel解法的啟發(fā)，作者（葉向）給出了求解“中國郵路問題”的Excel解法。5.6貨郎擔問題和中國郵路問題管梅谷教授還給出了求解“中國5.6貨郎擔問題和中國郵路問題例5.11

在圖5-26中，v1是郵局所在地。請幫郵遞員設計一條投遞線路（從郵局出發(fā)，將郵件投遞到他管轄的所有街道，最后回到郵局），使總路長最短。v1v2v3v4v9v6v5v8v7552444434396在圖中有4個奇點v2、v4、v6、v8，采用“奇偶點圖上作業(yè)法”求解，要添加4條重復邊：v1－v2,v1－v8,v4－v5,v5-v6。5.6貨郎擔問題和中國郵路問題例5.11在圖5-26中，5.6貨郎擔問題和中國郵路問題解：例5.10屬于求無向圖上的中國郵路問題。在無向圖中，把每一條邊看成是長度相等、方向互反的兩條弧。例5.11的Excel電子表格模型（隱藏了一些行）：5.6貨郎擔問題和中國郵路問題解：例5.10屬于求無向圖上5.6貨郎擔問題和中國郵路問題Excel的求解結果為：添加所需的4條重復?。翰⑶蠼獬鲆粭l最優(yōu)郵遞路線：

此時的最短總距離為685.6貨郎擔問題和中國郵路問題Excel的求解結果為：添加5.6貨郎擔問題和中國郵路問題（補充）補充：例5.10中國郵路問題的Excel電子表格模型（簡化版）。方法：去掉“虛擬邊”，將“虛擬邊”與“實際邊”合并，這樣決策變量“是否走”變成“走的次數(shù)”，約束條件是每條邊至少走1次、最多走2次，且節(jié)點的凈流量為0。求解結果相同（具體見電子表格模型）。中國郵路問題的應用：如校園灑水車路線問題（道路窄，邊，只要邊都走到即可）、環(huán)衛(wèi)清掃車路線問題（道路寬，雙向車道，兩條弧，需要兩條弧都走到）5.6貨郎擔問題和中國郵路問題（補充）補充：例5.10中國補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9：設xij為x項目第i年年初投資第j年初收回本利，根據(jù)實際情況，有：本利為115％的A13，A24，A35，A46；本利為125％的B36；本利為140％的C26；本利為106％的D12，D23，D34，D45，D56。該連續(xù)投資問題的網(wǎng)絡模型為A,115%A,115%D,106%A,115%A,115%D,106%D,106%D,106%D,106%12345B,125%,<=40C,140%,<=30106網(wǎng)絡上弧的流量是增加的，但節(jié)點的凈流量為0補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9：設xij為補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9：設xij為x項目第i年年初投資第j年初收回本利，根據(jù)實際情況，有：本利為115％的A13，A24，A35，A46；本利為125％的B36；本利為140％的C26；本利為106％的D12，D23，D34，D45，D56。該連續(xù)投資問題的數(shù)學模型為補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9：設xij為補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9電子表格模型補充：用網(wǎng)絡圖方法求解連續(xù)投資問題P80例3.9電子表格模上機實驗五網(wǎng)絡最優(yōu)化問題（－）實驗目的：熟悉運用Excel軟件求解各種網(wǎng)絡最優(yōu)化問題，掌握其求解方法。（二）內(nèi)容和要求：用Excel軟件求解最小費用流問題、最大流問題、最短路問題、中國郵路問題等，題目習題5.1、5.6、5.8、5.12、5.14、5.19（或案例6）（選作題：習題5.9、5.18）

。（三）操作步驟： （1）建立電子表格模型； （2）使用Excel規(guī)劃求解工具求解網(wǎng)絡最優(yōu)化問題； （3）結果分析； （4）在Excel或Word文檔中寫實驗報告，包括數(shù)學模型（習題5.1、5.6、5.12手寫）、電子表格模型和結果分析等。上機實驗五網(wǎng)絡最優(yōu)化問題（－）實驗目的：熟悉運用Exce實用運籌學

－運用Excel建模和求解第5章網(wǎng)絡最優(yōu)化問題實用運籌學

－運用Excel建模和求解第5章本章內(nèi)容要點網(wǎng)絡最優(yōu)化問題的基本概念網(wǎng)絡最優(yōu)化問題的四種主要類型：最小費用流、最大流、最短路、最小支撐樹各種網(wǎng)絡最優(yōu)化問題的建模與應用本章內(nèi)容要點網(wǎng)絡最優(yōu)化問題的基本概念本章節(jié)內(nèi)容5.1網(wǎng)絡最優(yōu)化問題基本概念5.2最小費用流問題5.3最大流問題5.4最短路問題5.5最小支撐樹問題5.6貨郎擔問題和中國郵路問題本章節(jié)內(nèi)容5.1網(wǎng)絡最優(yōu)化問題基本概念本章主要內(nèi)容框架圖本章主要內(nèi)容框架圖圖論的起源和發(fā)展1736年，歐拉的哥尼斯堡七橋問題BACD圖論的起源和發(fā)展1736年，歐拉的哥尼斯堡七橋問題BACD圖論的起源和發(fā)展1847年，基爾霍夫，電網(wǎng)絡，樹”；1852年，《四色猜想》；1964年，華羅庚，《統(tǒng)籌方法平話》。1857年，凱萊，同分異構，“樹”；1956年，杜邦公司，CPM，關鍵路線法；1958年，美國海軍部，PERT，計劃評審技術；1962年，管梅谷，《中國郵路問題》；1859年，哈密頓，哈密頓回路；圖論的起源和發(fā)展1847年，基爾霍夫，電網(wǎng)絡，樹”；1第5章-網(wǎng)絡最優(yōu)化問題課件幾個例子例1

是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。北京天津濟南青島武漢南京上海鄭州連云港徐州幾個例子例1北京天津濟南青島武漢南京上海鄭州連云港徐例2旅行商問題/貨郎（擔）問題

(TSP-TravelingSalesmanProblem)

一名推銷員準備前往若干城市推銷產(chǎn)品.如何為他(她)設計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.例2旅行商問題/貨郎（擔）問題

(TSP-Traveling例3穩(wěn)定婚配

假設有n個男人和n個女人,每人都希望從n個異性中選擇一位自己的配偶.假設每人都對n個異性根據(jù)自己的偏好進行了排序,以此作為選擇配偶的基礎.當給定一種婚配方案(即給每人指定一個配偶)后,如果存在一個男人和一個女人不是互為配偶,但該男人喜歡該女人勝過其配偶,且該女人喜歡該男人也勝過其配偶,則該婚配方案稱為不穩(wěn)定的.安排穩(wěn)定的婚配方案的問題稱為穩(wěn)定婚配問題。例3穩(wěn)定婚配假設有n個男人和n個女人,每人都5.1網(wǎng)絡最優(yōu)化問題基本概念網(wǎng)絡在各種實際背景問題中以各種各樣的形式存在。交通、電子和通訊網(wǎng)絡遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡規(guī)劃也廣泛用于解決不同領域中的各種問題，如生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務策劃等等。網(wǎng)絡規(guī)劃為描述系統(tǒng)各組成部分之間的關系提供了非常有效的直觀和概念上的幫助，廣泛應用于科學、社會和經(jīng)濟活動的各個領域中。近些年來，運籌學（管理科學）中一個振奮人心的發(fā)展是它的網(wǎng)絡最優(yōu)化問題的方法論和應用方面都取得了不同尋常的飛速發(fā)展。5.1網(wǎng)絡最優(yōu)化問題基本概念網(wǎng)絡在各種實際背景問題中以各種5.1網(wǎng)絡最優(yōu)化問題基本概念許多研究的對象往往可以用一個圖表示，研究的目的歸結為圖的極值問題。運籌學中研究的圖具有下列特征：

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

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

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

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

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

①所有供應點：凈流量（總流出－總流入）為正；

②所有轉運點：凈流量為零；

③所有需求點：凈流量為負；

④所有弧的流量fij受到弧的容量限制；

⑤所有弧的流量fij非負。5.2最小費用流問題最小費用流問題的數(shù)學模型為：5.2最小費用流問題例5.1最小費用流問題的數(shù)學模型為：（1）決策變量：設fij為通過弧(節(jié)點i->節(jié)點j)的流量。（2）目標函數(shù)本問題的目標是總運輸成本最小5.2最小費用流問題例5.1最小費用流問題的數(shù)學模型為：5.2最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限制、非負）①供應點F1:

供應點F2: ②轉運點DC: ③需求點W1:

需求點W2: ④弧的容量限制：⑤非負：5.2最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限5.2最小費用流問題

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

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

在例5.2的基礎上，增加了一個發(fā)點ps、一個收點pt、兩個轉運點p1和p2、以及與之相連的7條弧，如圖5-6（下一張幻燈片）所示。目標是從vs和ps兩個發(fā)點運出的總流量最大。這是一個有2個發(fā)點（供應點）和2個收點（需求點）的最大流問題。5.3最大流問題最大流問題的變形主要在于：有多個發(fā)點（供應5.3最大流問題70804010203050406030404070502060v1v2v3v5v4vtp1psptp2vs5.3最大流問題7080401020305040603045.3最大流問題例5.3的數(shù)學模型5.3最大流問題例5.3的數(shù)學模型5.3最大流問題例5.3的電子表格模型5.3最大流問題例5.3的電子表格模型5.3最大流問題最大流問題的一些實際應用：（1）通過配送網(wǎng)絡的流量最大，如例5.2和例5.3；（2）通過管道運輸系統(tǒng)的油的流量最大；（3）通過輸水系統(tǒng)的水的流量最大；（4）通過交通網(wǎng)絡的車輛的流量最大；等等。5.3最大流問題最大流問題的一些實際應用：5.3最大流問題例5.4計劃編制問題。某市政工程公司在未來5～8月份內(nèi)需完成4項工程：修建一條地下通道、修建一座人行天橋、新建一條道路及道路維修。工期和所需勞動力見表5-1。該公司共有勞動力120人，任一工程在一個月內(nèi)的勞動力投入不能超過80人，問公司應如何分配勞動力完成所有工程，是否能按期完成？5.3最大流問題例5.4計劃編制問題。某市政工程公司在未5.3最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來求解（可設xij為工程i在j月投入的勞動力）外，還可以用最大流的方法來求解。將工程計劃用網(wǎng)絡圖5-8（下一張幻燈片）表示。圖中的節(jié)點5、6、7、8分別表示5～8月份，Ai、Bi、Ci、Di表示工程在第i個月內(nèi)完成的部分。用弧表示某月完成某項工程的狀態(tài)，弧的流量為所投入的勞動力，受到勞動力限制（弧旁邊的數(shù)字表示弧的容量，從S開始的弧，其容量為該公司共有勞動力120人；從節(jié)點5、6、7、8開始的弧以及到節(jié)點A、B、C、D的弧，其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人；到收點T的弧，其容量為每個工程所需勞動力）。合理安排每個月各工程的勞動力，在不超過現(xiàn)有人力的條件下，盡可能保證工程按期完成，就是求圖5-8從發(fā)點到收點的最大流問題。5.3最大流問題本問題除了可以用第3章介紹的線性規(guī)劃方法來5.3最大流問題S675B6A58C5A6C6A7D8C8B7C7BCADT12080801008020080注意：增加一個起點S和一個終點T，其容量是供應量和需求量5.3最大流問題S675B6A58C5A6C6A7D8C85.3最大流問題例5.4市政工程公司勞動力分配電子表格模型P162求解結果（每個月的勞動力分配）如表5-2所示。5月份有剩余勞動力20人，4項工程恰好按期完成。5.3最大流問題例5.4市政工程公司勞動力分配電子表格模型5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力分配簡化版。在P161的工程計劃網(wǎng)絡圖中，可以去掉中間的節(jié)點A5～D8（共10個節(jié)點），直接將代表月份的節(jié)點（5、6、7、8）指向相應的工程節(jié)點（A、B、C、D），其容量為任一工程在一個月內(nèi)的勞動力投入不能超過80人。S6758BCADT120100802008080注意：增加一個起點S和一個終點T，其容量是供應量和需求量5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力5.3最大流問題（補充）例5.4（補充）市政工程公司勞動力分配簡化版。此時對應的電子表格模型也做相應的簡化。求得另外一個結果（每個月的勞動力分配）如下表所示。6月份有剩余勞動力20人，4項工程恰好按期完成。5.3最大流問題（補充）例5.4（補充）市政工程公司勞動5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（1）某公司有3個倉庫和4個零售店，各倉庫可提供的貨量及零售店的最大零售量如下表所示，打圈的表示公司指定該店可向相應的倉庫取貨。現(xiàn)在要求作一個調(diào)運方案，使得各店從各倉庫得到的總貨量最多。（答案：最大總貨量為41,4個零售店都能滿足）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（2）某產(chǎn)品從倉庫運往市場銷售，已知各倉庫的可供量、各市場的需求量及從倉庫到市場的運輸能力如下表所示（－表示無路）。試求從倉庫可運往市場的最大流量，各市場需求能否滿足？（答案：最大流量為110，市場B3只滿足50，其他市場都滿足）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題（補充）補充：用最大流的方法來求解4個實際問題：（3）某單位招收懂俄、英、日、德、法文的翻譯各1人，現(xiàn)有5人應聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，問這5個人是否都能得到聘書？最多幾個得到招聘，招聘后每人從事哪一方面的翻譯任務？（4人）（4）已知有6臺機床Ai，6種零件Bi。機床A1可加工零件B1；A2可加工零件B1、B2；A3可加工零件B1、B2、B3；A4可加工零件B2；A5可加工零件B2、B3、B4；A6可加工零件B2、B5、B6。現(xiàn)在要求制定一個加工方案，使一臺機床只加工一種零件，一種零件只在一臺機床上加工，要求盡可能多地安排零件的加工。請把這個問題轉化為求網(wǎng)絡最大流的問題，求出能滿足上述條件的加工方案。（答案：最大流為5）5.3最大流問題（補充）補充：用最大流的方法來求解4個實際5.3最大流問題最小費用最大流問題在實際的網(wǎng)絡應用當中，當涉及到流的問題時，有時考慮的不只是流量，還要考慮費用多少的問題。比如一個鐵路運輸系統(tǒng)的網(wǎng)絡流，不但要考慮網(wǎng)絡系統(tǒng)的貨運量最大，還要考慮總費用最小。最小費用最大流就是要解決這一類的問題。所謂最小費用最大流問題就是：給定一個帶收點和發(fā)點的網(wǎng)絡，對每一條?。ü?jié)點i->節(jié)點j）,除了給出容量cij外，還給出了這條弧的單位流量的費用bij

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

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

某人每天從住處v1開車到工作地v7上班，圖中各弧旁的數(shù)字表示道路的長度（公里），試問該人應選擇哪條路線，從家出發(fā)到工作地，路上行駛的總距離最短。v1v2v3v4v5v6v729683.51452.535.4最短路問題例5.6某人每天從住處v1開車到工作地v5.4最短路問題解：這是一個最短路問題。其數(shù)學模型為：（1）決策變量：設xij為弧(節(jié)點i->節(jié)點j)是否走（1表示走，0表示不走）。（2）目標函數(shù)本問題的目標是總距離最短（3）約束條件(節(jié)點凈流量、非負）P1695.4最短路問題解：這是一個最短路問題。其數(shù)學模型為：5.4最短路問題例5.6