MBA數(shù)據(jù)模型與決策-09圖與網(wǎng)絡(luò)規(guī)劃

第九章圖與網(wǎng)絡(luò)規(guī)劃本章內(nèi)容大綱9.1圖論的基本概述9.2網(wǎng)絡(luò)最大流問題9.3最小費(fèi)用流問題9.4最短路問題9.5最小支撐樹問題9.6網(wǎng)絡(luò)設(shè)施選址問題9.7車輛路徑問題9.8選址路線問題9.1圖的基本概念

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

一個(gè)圖就是點(diǎn)與邊的集合，記作

點(diǎn)與邊的關(guān)聯(lián)

有向圖與無向圖度、奇頂點(diǎn)、偶頂點(diǎn)鏈、閉鏈、開鏈歐拉圖

一個(gè)非空連通圖圖G是E圖的充分必要條件是圖G只含有偶頂點(diǎn)

賦權(quán)圖與網(wǎng)絡(luò)

9.1圖的基本概念

中國郵遞員問題(CPP)

：一個(gè)郵遞員負(fù)責(zé)某些街道的郵件投遞工作，每次都要從郵局出發(fā)走遍他負(fù)責(zé)的所有街道，再回到郵局。那么他應(yīng)如何安排投遞路線，使得所走過的總路程最短?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網(wǎng)絡(luò)最大流問題案例：某企業(yè)的產(chǎn)品需要經(jīng)過多道加工工序，有多個(gè)設(shè)備可以完成這些工序的工作，而企業(yè)現(xiàn)有設(shè)備加工每道工序的能力也不同，即每道工序在一個(gè)工作日內(nèi)加工產(chǎn)品的最大數(shù)量是有限制的，圖中，邊上的數(shù)字即為該工序的最大加工能力。9.2網(wǎng)絡(luò)最大流問題概念：給定有向賦權(quán)圖其中有兩個(gè)特殊的節(jié)點(diǎn)s和t。s稱為發(fā)點(diǎn)，t稱為收點(diǎn)。而剩下的結(jié)點(diǎn)稱之為轉(zhuǎn)運(yùn)點(diǎn)。圖中各邊的方向和權(quán)數(shù)表示允許的流向和最大可能的流量（容量），并假設(shè)容量均為整數(shù)。問在這個(gè)網(wǎng)絡(luò)圖中從發(fā)點(diǎn)流出到收點(diǎn)匯集，最大可通過的實(shí)際流量為多少？流向分布情況怎樣？9.2網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題模型及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網(wǎng)絡(luò)最大流問題__程序計(jì)算結(jié)果9.3最小費(fèi)用流問題案例：某配送公司擁有一個(gè)固定的配送網(wǎng)絡(luò)，網(wǎng)絡(luò)中某些地方需要送貨，某些地方需要發(fā)貨，公司現(xiàn)為每條路線配備固定的運(yùn)輸車輛，每輛車都有固定的裝載容量限制。9.3最小費(fèi)用流問題_概念9.3最小費(fèi)用流問題最小費(fèi)用流問題模型及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最小費(fèi)用流問題_程序計(jì)算結(jié)果9.4最短路問題案例：某服務(wù)公司幾乎時(shí)刻都往返于一個(gè)城市的不同社區(qū)，需要事先確定城市各個(gè)社區(qū)之間的最短線路。要求總旅程最短的旅行路線：實(shí)際上就是在一個(gè)賦權(quán)連通圖上，求一條從起點(diǎn)到另一節(jié)點(diǎn)的路P，使得通路P上的總權(quán)和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最小支撐樹問題案例：企業(yè)有五個(gè)數(shù)據(jù)中心，中心之間用光纜連接，己知這五個(gè)車間的位置、可供鋪設(shè)光纜的地方及數(shù)據(jù)中心之間的距離，問光纜怎樣鋪設(shè)才能使管線總長最省?9.5最小支撐樹問題__概念設(shè)圖G=(V、E)是一個(gè)賦權(quán)連通圖，T是G的一棵支撐子樹，稱T中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即w(T)=，如果支撐樹T*的權(quán)w(T*)是G所有支撐樹的權(quán)中最小的，則稱T*為G的最小支撐樹(簡稱為最小樹)9.5最小支撐樹問題__破圈法求一個(gè)賦權(quán)連通圖G的最小支撐樹的方法還有“破圈法”，此方法簡單易行?！捌迫Ψā保涸趫DG中任取一個(gè)圈，去掉圈上權(quán)最大的一條邊，反復(fù)進(jìn)行，直到?jīng)]有圈為止。對例9-6依此去掉的邊為：(v5、v6)，(v2、v5)，(v3、v1)，(v6、v4)。也得到圖9-12所示的最小樹，總權(quán)和為14。9.6網(wǎng)絡(luò)設(shè)施選址問題P-中位問題：不考慮建站成本，而選P個(gè)服務(wù)站最小化總路線成本。P-中心問題：是探討如何在網(wǎng)絡(luò)中選擇P個(gè)服務(wù)站，使得任意一需求點(diǎn)到距離該需求點(diǎn)最近的服務(wù)站的最大距離最小。最大覆蓋問題：在服務(wù)站的數(shù)目和服務(wù)半徑已知的條件下，如何設(shè)立P個(gè)服務(wù)站使得可接受服務(wù)的需求量最大。集覆蓋問題：覆蓋所有需求點(diǎn)顧客的前提下，服務(wù)站總的建站個(gè)數(shù)或建設(shè)費(fèi)用最小。9.6網(wǎng)絡(luò)設(shè)施選址問題__中位問題案例：商業(yè)公司希望從它的10個(gè)零售店中選擇3個(gè)進(jìn)行擴(kuò)建，成立物流中心為它的10個(gè)零售店進(jìn)行配送服務(wù)，已知每個(gè)零售店每天的配送量，零售店之間的距離，問：如何選擇最合適的物流中心使得總配送成本最低。9.6網(wǎng)絡(luò)設(shè)施選址問題__中位問題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網(wǎng)絡(luò)設(shè)施選址問題__中位問題9.6網(wǎng)絡(luò)設(shè)施選址問題__集覆蓋問題9.6網(wǎng)絡(luò)設(shè)施選址問題__最大覆蓋問題9.6網(wǎng)絡(luò)設(shè)施選址問題__中心問題9.7車輛路徑問題案例：車輛路徑問題(VehicleRoutingProblem，VRP)是指對一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。9.7車輛路徑問題9.7車輛路徑問題為何需要約束式(6)？為了避免一輛車子產(chǎn)出多個(gè)回路的現(xiàn)象。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車輛路徑問題__程序計(jì)算結(jié)果9.8選址路線問題案例：某企業(yè)有6個(gè)穩(wěn)定的經(jīng)銷商，現(xiàn)決定為其建立配送中心，已知該企業(yè)候選的2輛5噸及其估算的車輛成本，2個(gè)候選的建站場地及其估算的建站費(fèi)用，6個(gè)客戶每天的大致配送量，建站場地及客戶的位置及距離，7、8為候選的建站場地；1至6為經(jīng)銷商位置。9.8選址路線問題__概念選址路線問題是一個(gè)結(jié)合選址問題與車輛路徑問題的決策。該問題研究如何選址配送中心，并且安排最優(yōu)的配送車輛與配送路線，以使總建站成本、車輛成本、行駛成本最小。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)