數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化（PPT64頁)

1、第5章:網(wǎng)絡(luò)優(yōu)化 所謂網(wǎng)絡(luò)優(yōu)化，簡單地說，即對網(wǎng)絡(luò)進行定性和定量分析，以便為實現(xiàn)某種優(yōu)化目標而尋求最優(yōu)方案這方面的典型問題有：最小支撐樹問題，最小費用流問題、最大流問題、最短路問題，中心問題，重心問題、運輸問題、指派問題等等樹圖結(jié)構(gòu)：最小支撐樹問題光纜通信連接問題 某公園決定鋪設(shè)最先進的光纖網(wǎng)絡(luò)，為它的主要景點之間提供高速通信(數(shù)據(jù)，聲音和錄像)。 為了利用光纖技術(shù)在景點之間高速通信的優(yōu)勢，不需要在每兩個景點之間都用一條光纜把他們直接聯(lián)系起來。問題：確定需要鋪設(shè)那些光纜使得提供給每個景點之間的高速通信的成本最低。2公園光纜通信問題的路徑系統(tǒng)圖中虛線表示可供選擇的邊3最佳的解決辦法 由于任意兩個

2、節(jié)點之間均可以通信，這個圖必須是連通圖。并且，這個圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然滿足條件,并且成本更小。4樹、圖的專有名詞 圖G定義為點和邊的集合,記為G=V，E,其中，是點的集合，是邊的集合。有向圖區(qū)別于無向圖的關(guān)鍵，在于它的邊（此時也稱弧）是有方向的。一個圖連同定義在其邊集上的實函數(shù)一起稱為一個網(wǎng)絡(luò)，我們把定義在邊集上的實函數(shù)稱為邊的權(quán)數(shù)。該網(wǎng)絡(luò)記為V，E，W。 對于圖G=V，E,如果任意兩個節(jié)點間都可以由一條或幾條邊連起來，則稱該圖為連通圖。連通并且不含圈的無向圖稱為樹。若樹中點的集合等于圖的點的集合，樹中邊的集合是圖的邊的集合的子集，稱樹為圖的支撐樹。在所有的

3、支撐樹中總成本最小的樹稱為最小支撐樹。5最小支撐樹問題的算法 選擇第一條邊：選擇成本最低的備選邊（圖中虛線）。 選擇下一條邊：在一個已經(jīng)有一條邊連接的節(jié)點和另一個還沒有邊連接的節(jié)點之間選擇成本最低的備選邊。 重復(fù)第2個步驟，直到所有的節(jié)點都有一條邊（可能會有多于一條邊）與其相連 . 此時，就得到了最優(yōu)解(最小支撐樹)其中第2步的目的是為了保證每次生成的樹都是連接當(dāng)前子圖的所有頂點的成本最小的樹。6算法的應(yīng)用： 首次連接 V=C，D W=A，B，E，F(xiàn)，G從V中的節(jié)點連向W中節(jié)點的備選邊中選擇成本最小的一條邊7算法的應(yīng)用： 第二次連接 V=B，C，D W=A，E，F(xiàn)，G8算法的應(yīng)用： 第三次連接

4、 V=A，B，C，D W=E，F(xiàn)，G9算法的應(yīng)用： 第四次連接 V=A，B，C，D，F(xiàn) W=E，G10算法的應(yīng)用： 第五次連接 V=A，B，C，D，E，F(xiàn) W=G11算法的應(yīng)用： 最后的連接 V=A，B，C，D，E，F(xiàn)，G12最小費用流問題 這里的流是一個廣泛的概念，例如在交通運輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流，等等。 問題的提出：在一個關(guān)于流的網(wǎng)絡(luò)中，每一個流量都有一定的費用，流所走的路線不一樣，單位費用不一樣。同樣數(shù)量的流量，因為走的路線不一樣，總的費用也不一樣。從而我們希望確定在給定網(wǎng)絡(luò)流量的基礎(chǔ)上，讓流沿著怎樣的路線走，能使總的費用

5、最小。13無限配送公司問題 無限配送公司有兩家工廠生產(chǎn)產(chǎn)品,這些產(chǎn)品需要運到兩個倉庫。工廠1生產(chǎn)80個單位；工廠2生產(chǎn)70個單位。 倉庫1需要60個單位；倉庫2需要90個單位 。工廠1和倉庫1之間以及工廠2和倉庫2之間各有一條鐵路運輸軌道?？ㄜ囁緳C總共可以從每家工廠運輸50個單位到配送中心，然后可以從配送中心運輸50個單位到每個倉庫 （任何運輸?shù)脚渌椭行牡漠a(chǎn)品必須隨后運送到倉庫）。問題：確定一個運輸方案（即每條路線運送多少單位的產(chǎn)品），使得運輸成本達到最小。14網(wǎng)絡(luò)模型 凈流量=流出-流入15最小費用流的專有名詞 網(wǎng)絡(luò)中的圓圈被稱為節(jié)點。 如果節(jié)點要求的凈流量(流出減去流入) 是一個確定的正數(shù)

6、的話，這個點就是一個供應(yīng)點。 如果節(jié)點要求的凈流量(流出減去流入) 是一個確定的負數(shù)的話，這個點就是一個需求點。若節(jié)點要求的凈流量恒為0，這個點稱為轉(zhuǎn)運點。我們把流出接點的量等于流入節(jié)點的量稱為流量守恒。在網(wǎng)絡(luò)里的箭頭被稱為弧。 允許通過某一條弧的最大流量被稱為該弧的容量。 16最小費用流問題的假定 至少有一個節(jié)點是供應(yīng)點；至少有一個節(jié)點是需求點；所有剩下的節(jié)點都是轉(zhuǎn)運點。 通過弧的流只允許沿著箭頭的方向流動，通過弧的最大流量取決于該弧的容量。網(wǎng)絡(luò)中有足夠的弧提供足夠的容量，使得所有在供應(yīng)點產(chǎn)生的流都能夠到達需求點。 在流的單位成本已知的前提下，通過每一條弧的流的成本與流量成正比（費用系數(shù)是確

7、定的）。 最小費用流問題的目標是在給定需求的條件下，使通過網(wǎng)絡(luò)供應(yīng)的總成本最小。17一個網(wǎng)絡(luò)模型 凈流量=流出-流入18數(shù)學(xué)模型19最佳的解決辦法 20最小費用流問題的數(shù)學(xué)建模 設(shè)一個有n個節(jié)點，m條弧的網(wǎng)絡(luò)圖, ，每一個節(jié)點i都對應(yīng)于一個數(shù)bi，表示該節(jié)點要求的凈流量。 如果bi0，節(jié)點i為供應(yīng)節(jié)點，供應(yīng)量為bi；如果bi0，則為需求節(jié)點，需求量為-bi； 如果bi=0，該節(jié)點為轉(zhuǎn)運點。 對于一個網(wǎng)絡(luò)，如果有 ，稱為供求平衡的網(wǎng)絡(luò)。 網(wǎng)絡(luò)所有弧（i,j）G上的流量xij（一共n個分量）組成的向量X=xij稱為網(wǎng)絡(luò)的一個流。（）網(wǎng)絡(luò)中求流量分配使總流量達到一定要求，而總費用最低如果網(wǎng)絡(luò)的一個流

8、滿足以下條件，則這樣的流稱為可行流。a、平衡條件：對網(wǎng)絡(luò)中的任一節(jié)點i，在網(wǎng)絡(luò)中從節(jié)點i通過弧(i,j)流向關(guān)聯(lián)的他節(jié)點j的流量xij之和減去與節(jié)點i關(guān)聯(lián)的其他節(jié)點j通過弧(j,i)流入i的流量xji之和 與該節(jié)點要求的凈流量平衡。即：b、容量限制條件：22數(shù)學(xué)模型：網(wǎng)絡(luò)的每一弧(i,j),都有一個單位流量的費用系數(shù)cij與它對應(yīng)，如果弧(i,j)上的流量為xij，則該弧上這些流量引起的費用為cijxij。網(wǎng)絡(luò)最小費用流問題就是找到使總費用最小的可行流。模型有可行解的必要條件是：該網(wǎng)絡(luò)是供求平衡的網(wǎng)絡(luò)。即： 。為什么？23最小費用流問題的數(shù)學(xué)建模（2）另一類最小費用流問題是在預(yù)算費用C給定的情

9、況下，求流量分配，使得從 能夠輸送的總流量達到最大。 仍用決策變量 表示通過弧(i,j)的流量， 表示弧(i,j)的費用系數(shù)， 表示弧(i,j)上的容量，則數(shù)學(xué)模型為：最大流問題一、 有關(guān)概念：例：下圖是輸油管道網(wǎng)， 為起點， 為終點， ， ， ， 為中轉(zhuǎn)站，弧上的數(shù)字表示該管道的最大輸油能 力（也稱容量），記為 ，問應(yīng)如何安排各管道輸油量，才能使從 到 的總輸油量最大？25 分別稱 為發(fā)點、收點。其余的點稱為轉(zhuǎn)運點。 每一個弧上都給定一個容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記 的每一個弧上都給定一個實際流量 的網(wǎng)絡(luò)稱為給定了網(wǎng)絡(luò)一個流。26b.容量限制條件： 對每一弧上都有 a.平衡條件： 轉(zhuǎn)運點：流出

10、量-流入量=0。 發(fā)收點：發(fā)點流出量=收點流入量=網(wǎng)絡(luò)總流量。 若 ，稱弧 是飽和弧。使網(wǎng)絡(luò)總流量達到最大的可行流稱為最大流 。如果網(wǎng)絡(luò)的一個流滿足以下條件，則這樣的流稱為可行流:27最大流問題的數(shù)學(xué)建模 用決策變量 表示通過弧(i,j)的流量， 表示弧(i,j)的容量，則數(shù)學(xué)模型為：BMZ公司的最大流問題 BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商。雖然它生產(chǎn)的汽車在所有發(fā)達國家銷量都不錯，對它來講，出口到美國尤其重要。BMZ汽車正在加利福尼亞變得特別受歡迎，因此保證洛杉磯中心良好的供應(yīng)顯得特別的重要。 大部分汽車配件以及新車是在該公司位于德國的斯圖加特的總廠生產(chǎn)的，BMZ公司需要制定一個計劃

11、，使得下個月從總廠運送到洛杉磯配送中心的配件流盡可能大。 可以運送多少配件的限制條件就是該公司配送網(wǎng)絡(luò)的容量。 問題：通過每條運輸路線可以運送多少貨物，使得從總廠運送到洛杉磯配送中心的配件流最大。 29BMZ 銷售網(wǎng) 30BMZ的一個網(wǎng)絡(luò)模型 ACBFEG708070604050305040D31數(shù)學(xué)模型32最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題都可以使用這個模型，如設(shè)備更新、管道的鋪設(shè)、線路的安排、廠區(qū)的布局等。最短路問題的一般提法是：設(shè) 為連通圖，圖中各邊或弧 有權(quán) ( 表示 ， 間沒有邊或?。? 為圖中任意兩點，求一條道路 ，使它是從 到 的所有路中總權(quán)最小的

12、路。即： 最小。33最短路問題的假定 在網(wǎng)絡(luò)中選擇一條路，這條路始于某一節(jié)點，叫做始點，并且終于另一個節(jié)點，叫終點。 連結(jié)兩個節(jié)點的連線通常叫做邊(允許任一方向的行進）,也允許存在弧(只允許朝一個方向行進)。 與每條邊相關(guān)的一個非負數(shù)稱為該邊的長度。(注意，邊和弧也可能代表其他類型的活動) 目標是為了選擇從始點到終點的最短路(總長度最小的路) 。 34一個最短路問題的應(yīng)用：為了實現(xiàn)更加人性化的服務(wù),公園管理層需要面向游客出一本旅游線路指南的小冊子。 在該小冊子中要告訴旅客從公園入口,各個景點之間以及入口之間的最短線路。問題:首先考慮從公園入口到公園出口的最短線路.3536由于 最小，所以醫(yī)院應(yīng)

13、建在F ，此時離醫(yī)院最遠的景點A 距離為7。 中心問題：中心醫(yī)務(wù)室應(yīng)建在哪個景點，可使離醫(yī)務(wù)室最遠的景點游客就診時所走的路程最近？37 重心問題：已知各景點的員工人數(shù)分別為40,25,45,30,20,35,50.則會議中心應(yīng)建在哪個景點，可使所有員工在參加會議時間所走的總路程最短？38由于 最小，所以會議中心應(yīng)建在C公園的重心(各個景點員工人數(shù)40,25,45,30,20,35,50.)39有向網(wǎng)絡(luò)最短路問題的數(shù)學(xué)建模 設(shè)始點為1，終點為n，引入01決策變量 ，如果弧(i,j)在從始點到終點的某條路徑上，則 ，否則 。則數(shù)學(xué)模型為：使總成本最小的最短路問題薩拉剛剛高中畢業(yè)。在畢業(yè)典禮上，她父

14、母給了她21000美圓的汽車基金幫助她購買并保養(yǎng)一輛使用了3年的二手車，以供她上大學(xué)。 由于開車費用，維修費用隨著汽車的老化而飛速上漲，薩拉可以一次或者幾次折價將她的汽車置換為其他使用了3年的二手車，在四年大學(xué)畢業(yè)后，她父母將送給她一輛新車，到那時她肯定計劃把舊車折價買出。問題：在接下來的3個暑期，薩拉什么時候應(yīng)該折價買掉她的汽車(如果必要的話)可以使得她在大學(xué)四年的開車，買車，保養(yǎng)汽車的總費用最??？ 41薩拉花費數(shù)據(jù) 問題：在接下來的3個暑期，薩拉什么時候應(yīng)該折價買掉她的汽車(如果必要的話)可以使得她在大學(xué)四年的開車，買車，保養(yǎng)汽車的總費用最??？ 最短路網(wǎng)絡(luò) 解：把這個問題化為最短路問題。節(jié)

15、點表示現(xiàn)在(入學(xué))，節(jié)點，分別表示第一年年末，第二年年末，第三年年末，第四年年末。從一個節(jié)點到另外一個節(jié)點的弧表示在第一個節(jié)點這個時間買車，然后在第二個節(jié)點的那個時間把車折價賣掉的活動43最短路網(wǎng)絡(luò) 弧長買車的價格使用和保養(yǎng)的費用折價買出的價值。這樣該問題就變?yōu)椋呵髲墓?jié)點到節(jié)點的最短路問題.44數(shù)學(xué)模型45最短路問題也可看成最小費用流問題的特例當(dāng)確定從任一節(jié)點i至另一節(jié)點j的最短路時，只要作以下假定：(1)當(dāng)網(wǎng)絡(luò)中任意兩個節(jié)點之間存在連接的弧時，弧上的費用系數(shù)等于該弧的長度；(2)作為起點的節(jié)點i為供應(yīng)節(jié)點且其凈流出量為1，作為終點的節(jié)點j為需求節(jié)點且其凈流出量為-1，所有其他節(jié)點的凈流出量為

16、零；(3) 總費用等于從節(jié)點i（起點）到節(jié)點j（終點）所經(jīng)過的各條弧的長度之和，目標函數(shù)是總費用最小，也就是從節(jié)點i到節(jié)點j的路徑最短。46運輸問題運輸問題的一般提法是：設(shè)某種物資有 個產(chǎn)地各產(chǎn)地的產(chǎn)量是有 個銷地各銷地的銷量是假定從產(chǎn)地 到銷地運輸單位物品的運價是 ，問怎樣調(diào)運這些物品才能使總運費最??？47運輸問題例：某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量及各產(chǎn)地運往各銷地的單位運費如表所示。如何調(diào)運，使總運費最少？銷地產(chǎn)地B1B2B3產(chǎn)量A1646200A2655300銷量150150200500500單位運費 x11 x12 x13 x2

17、1 x22 x23 48運輸問題的假設(shè)需求假設(shè)： 每一個出發(fā)地（產(chǎn)地）都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地（銷地）。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足。 成本假設(shè)： 從任何一個出發(fā)地到任何一個目的地的貨物配送成本 和所配送的數(shù)量成線性比例關(guān)系，因此這個成本就等于配 送的單位成本乘以所配送的數(shù)量。49上例運輸問題的線性模型 min z=6 x11+4 x12+6 x13+6 x21+5 x22+5 x23 s.t. x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x21=150 x12+ x22=150 x

18、13+ x23=200 xij050推廣為一般：51(平衡)運輸問題的線性規(guī)劃模型Min z=S.t.52定理：如果(平衡)運輸問題有可行解,則證 :設(shè)運輸問題有可行解則應(yīng)滿足約束從而有運輸問題的變形總供應(yīng)量總需求量的情形供求，LP模型中把約束xijai改為xijai即可供求，LP模型中把約束xijbj改為xijbj即可目標函數(shù)最大化的情形，如目標是追求利潤或收入時，只需將目標函數(shù)改為max即可某些路線的運輸能力有一定限制的情形如從A2到B3受到運輸能力限制，最多只能運送150時，只需在原LP模型上添加x23150即可54運輸問題的計算機求解用線性規(guī)劃程序求解，輸出部分信息多，且變量和約束輸入

19、較麻煩。用運輸問題程序求解，只需輸入產(chǎn)地個數(shù)、銷地個數(shù)、各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價。前例輸入后，得到的最優(yōu)運輸方案為：55指派問題有4個工人,要指派他們分別完成4項工作,每人做各項工作所消耗的時間如下表。要求1人只做1件事，如何指派使總成本最少?人 工作B1B2B3B4工資24745325112A33956364313A4325125461556模型用0-1變量表示“是非”決策：min z=14*35x11+14*41 x12 +14*27 x13+14*40 x14 +12* 47x21+ 12*45 x22+ 12*32x23 +12*51x24 +13*39x31 +13*56x32 + 13*36x33 + 13*43 x34 +15*32x41 +15*51x42 +15*25x43 +15*46x44 s.t. x11+x12+x13+x14 =1 (A1只能干一件事) x21+x22+x23+x24 =1 (A2只能干一件事) x31+x32+x33+x34 =1 (A3只能干一件事) x41