第九章圖與網絡規劃本章內容大綱9.1圖論的基本概述9.2網絡最大流問題9.3最小費用流問題9.4最短路問題9.5最小支撐樹問題9.6網絡設施選址問題9.7車輛路徑問題9.8選址路線問題9.1圖的基本概念

經典案例：哥尼斯堡七橋問題是否存在一條路線，可不重復地走遍七座橋，回到原點？9.1圖的基本概念

一個圖就是點與邊的集合，記作

點與邊的關聯

有向圖與無向圖度、奇頂點、偶頂點鏈、閉鏈、開鏈歐拉圖

一個非空連通圖圖G是E圖的充分必要條件是圖G只含有偶頂點

賦權圖與網絡

9.1圖的基本概念

中國郵遞員問題(CPP)

：一個郵遞員負責某些街道的郵件投遞工作，每次都要從郵局出發走遍他負責的所有街道，再回到郵局。那么他應如何安排投遞路線，使得所走過的總路程最短?9.1圖的基本概念CPP模型及LINGO主程序min=@sum(ij(i，j)|c(i，j)#gt#0：c(i，j)*f(i，j))；@for(ii(j)：@sum(ii(i)：f(i，j))=@sum(ii(k)：f(j，k)))；@for(ij(i，j)|c(i，j)#gt#0：@gin(f))；@for(ij(i，j)|c(i，j)#gt#0：f(i，j)+f(j，i)>=1)；@for(ij(i，j)|c(i，j)#eq#0：f(i，j)=0)；end9.2網絡最大流問題案例：某企業的產品需要經過多道加工工序，有多個設備可以完成這些工序的工作，而企業現有設備加工每道工序的能力也不同，即每道工序在一個工作日內加工產品的最大數量是有限制的，圖中，邊上的數字即為該工序的最大加工能力。9.2網絡最大流問題概念：給定有向賦權圖其中有兩個特殊的節點s和t。s稱為發點，t稱為收點。而剩下的結點稱之為轉運點。圖中各邊的方向和權數表示允許的流向和最大可能的流量（容量），并假設容量均為整數。問在這個網絡圖中從發點流出到收點匯集，最大可通過的實際流量為多少？流向分布情況怎樣？9.2網絡最大流問題網絡最大流問題模型及LINGO主程序max=f；@for(ii(i)|i#gt#1#and#i#lt#6：@sum(ii(j)：x(i，j))-@sum(ii(j)：x(j，i))=0)；@sum(ii(j)：x(1，j))-@sum(ii(j)：x(j，1))=f；@sum(ii(j)：x(6，j))-@sum(ii(j)：x(j，6))=-f；@for(ij(i，j)：x(i，j)<=u(i，j))；end9.2網絡最大流問題__程序計算結果9.3最小費用流問題案例：某配送公司擁有一個固定的配送網絡，網絡中某些地方需要送貨，某些地方需要發貨，公司現為每條路線配備固定的運輸車輛，每輛車都有固定的裝載容量限制。9.3最小費用流問題_概念9.3最小費用流問題最小費用流問題模型及LINGO程序min=@sum(ij(i，j)：c(i，j)*x(i，j))；@for(ii(i)：@sum(ii(j)|c(i，j)#gt#0：x(i，j))-@sum(ii(j)：x(j，i))=b(i))；@for(ij(i，j)|u(i，j)#gt#0：x(i，j)<=u(i，j))；

9.3最小費用流問題_程序計算結果9.4最短路問題案例：某服務公司幾乎時刻都往返于一個城市的不同社區，需要事先確定城市各個社區之間的最短線路。要求總旅程最短的旅行路線：實際上就是在一個賦權連通圖上，求一條從起點到另一節點的路P，使得通路P上的總權和W(P)最小，這樣的問題稱為最短路問題。9.4最短路問題__模型9.4最短路問題__floyd算法9.4最短路問題__matlab程序D=aa；fori=1：nforj=1：n

R(i，j)=j；

endendR；fork=1：n9.5最小支撐樹問題案例：企業有五個數據中心，中心之間用光纜連接，己知這五個車間的位置、可供鋪設光纜的地方及數據中心之間的距離，問光纜怎樣鋪設才能使管線總長最省?9.5最小支撐樹問題__概念設圖G=(V、E)是一個賦權連通圖，T是G的一棵支撐子樹，稱T中所有邊的權之和為支撐樹T的權，記為w(T)，即w(T)=，如果支撐樹T*的權w(T*)是G所有支撐樹的權中最小的，則稱T*為G的最小支撐樹(簡稱為最小樹)9.5最小支撐樹問題__破圈法求一個賦權連通圖G的最小支撐樹的方法還有“破圈法”，此方法簡單易行。“破圈法”：在圖G中任取一個圈，去掉圈上權最大的一條邊，反復進行，直到沒有圈為止。對例9-6依此去掉的邊為：(v5、v6)，(v2、v5)，(v3、v1)，(v6、v4)。也得到圖9-12所示的最小樹，總權和為14。9.6網絡設施選址問題P-中位問題：不考慮建站成本，而選P個服務站最小化總路線成本。P-中心問題：是探討如何在網絡中選擇P個服務站，使得任意一需求點到距離該需求點最近的服務站的最大距離最小。最大覆蓋問題：在服務站的數目和服務半徑已知的條件下，如何設立P個服務站使得可接受服務的需求量最大。集覆蓋問題：覆蓋所有需求點顧客的前提下，服務站總的建站個數或建設費用最小。9.6網絡設施選址問題__中位問題案例：商業公司希望從它的10個零售店中選擇3個進行擴建，成立物流中心為它的10個零售店進行配送服務，已知每個零售店每天的配送量，零售店之間的距離，問：如何選擇最合適的物流中心使得總配送成本最低。9.6網絡設施選址問題__中位問題min=@sum(ij(i，j)：h(i)*d(i，j)*y(i，j))；@for(ii(i)：@sum(ii(j)：y(i，j))=1)；@sum(ii(j)：x(j))=3；@for(ij(i，j)：y(i，j)-x(j)<=0)；

@for(ii(i)：@bin(x(i)))；

@for(ij(i，j)：@bin(y(i，j)))；end

9.6網絡設施選址問題__中位問題9.6網絡設施選址問題__集覆蓋問題9.6網絡設施選址問題__最大覆蓋問題9.6網絡設施選址問題__中心問題9.7車輛路徑問題案例：車輛路徑問題(VehicleRoutingProblem，VRP)是指對一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。9.7車輛路徑問題9.7車輛路徑問題為何需要約束式(6)？為了避免一輛車子產出多個回路的現象。01234567012345679.7車輛路徑問題車輛路徑問題LINGO主程序min=@sum(ijk(i，j，k)：c(i，j)*x(i，j，k))；@for(kk(k)：@sum(ii(i)：g(i)*y(i，k))<=15)；@for(ii(j)|j#gt#1：@sum(kk(k)：y(j，k))=1)；@for(ii(j)|j#eq#1：@sum(kk(k)：y(j，k))=3)；@for(ik(j，k)：@sum(ii(i)|i#ne#j：x(i，j，k))=y(j，k))；@for(ik(i，k)：@sum(ii(j)|i#ne#j：x(i，j，k))=y(i，k))；@for(ij(i，j)|i#ne#j#and#i#gt#1#and#j#gt#1：u(i)-u(j)+11*@sum(kk(k)：x(i，j，k))<=10)；@for(ijk：@bin(x))；@for(ik：@bin(y))；end9.7車輛路徑問題__程序計算結果9.8選址路線問題案例：某企業有6個穩定的經銷商，現決定為其建立配送中心，已知該企業候選的2輛5噸及其估算的車輛成本，2個候選的建站場地及其估算的建站費用，6個客戶每天的大致配送量，建站場地及客戶的位置及距離，7、8為候選的建站場地；1至6為經銷商位置。9.8選址路線問題__概念選址路線問題是一個結合選址問題與車輛路徑問題的決策。該問題研究如何選址配送中心，并且安排最優的配送車輛與配送路線，以使總建站成本、車輛成本、行駛成本最小。9.8選址路線問題__模型9.8選址路線問題__LINGO主程序min=@sum(ijk(i，j，k)：c(i，j)*x(i，j，k))+@sum(jj：f*z)+@sum(jk(j，k)：h(k)*y(j，k))；@for(ii(j)：@sum(nk(i，k)|i#ne#j：x(i，j，k))=1)；@for(nk(j，k)：@sum(nn(i)|i#ne#j：x(i，j，k))-@sum(nn(i)|i#ne#j：x(j，i，k))=0)；@for(jk(j，k)：@sum(ii(i)：x(i，j，k))=y(j，k))；@for(iijj(i，j)|i#ne#j：u(i)-u(j)+6*@sum(kk(k)：x(i，j，k))<=5)；@for(jk(j，k)：@sum(ii(i)：x(j，i，k))=y(j，k))；@for(jk(j，k)：y(j，k)<=z(j)