圖論和網(wǎng)絡(luò)分析算法及Matlab實(shí)現(xiàn)(Graph-and-Network-Analysis)課件

圖論與網(wǎng)絡(luò)分析

(GraphTheoryandNetworkAnalysis)一、圖論的基本概念

二、網(wǎng)絡(luò)分析算法三、Matlab實(shí)現(xiàn)2022/10/19圖論與網(wǎng)絡(luò)分析一、圖論的基本概念

二、網(wǎng)絡(luò)分析算法2涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問(wèn)題1、最短路問(wèn)題貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路。

2022/10/19涉及網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)建模問(wèn)題1、最短路問(wèn)題2022/10/152、最小支撐樹(shù)問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？2022/10/192、最小支撐樹(shù)問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公3、指派問(wèn)題

Assignmentproblem

一家公司經(jīng)理安排N名員工去完成N項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)不同。如何分配工作方案可以使總回報(bào)最大？

2022/10/193、指派問(wèn)題

Assignmentproblem一家4、中國(guó)郵遞員問(wèn)題

Chinesepostmanproblem一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？我國(guó)管梅谷教授1960年首先提出，國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。

2022/10/194、中國(guó)郵遞員問(wèn)題

Chinesepostmanprob5、旅行商問(wèn)題

Travelingsalesmanproblem一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他設(shè)計(jì)一條最短的旅行路線？（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）2022/10/195、旅行商問(wèn)題

Travelingsalesmanpr6、運(yùn)輸問(wèn)題

Transportationproblem某種原材料有M個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往N個(gè)使用這些原材料的工廠。假定M個(gè)產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？2022/10/196、運(yùn)輸問(wèn)題

Transportationproblem問(wèn)題的兩個(gè)共同特點(diǎn)（1）目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)問(wèn)題稱為最優(yōu)化或優(yōu)化問(wèn)題。（2）它們都可用圖形形式直觀描述，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)。圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問(wèn)題就是網(wǎng)絡(luò)最優(yōu)化。網(wǎng)絡(luò)優(yōu)化問(wèn)題是以網(wǎng)絡(luò)流為研究的對(duì)象，常常被稱為網(wǎng)絡(luò)流或網(wǎng)絡(luò)流規(guī)劃等。

2022/10/19問(wèn)題的兩個(gè)共同特點(diǎn)（1）目的都是從若干可能的安排或方案中尋求一、圖論的基本概念1.圖與子圖e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如

G：簡(jiǎn)單圖：無(wú)自環(huán)、無(wú)重邊的圖。2022/10/19一、圖論的基本概念1.圖|V|=n表示圖G中節(jié)點(diǎn)個(gè)數(shù)為n，此節(jié)點(diǎn)個(gè)數(shù)n也稱為圖G的階|E|=m表示圖G中邊的個(gè)數(shù)為m任一頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目稱為該頂點(diǎn)的度完全圖：任意兩點(diǎn)有邊相連，用表示完全圖的邊，和每點(diǎn)的度是多少？2022/10/19|V|=n表示圖G中節(jié)點(diǎn)個(gè)數(shù)為n，此節(jié)點(diǎn)個(gè)數(shù)n也稱為圖G的階2.關(guān)聯(lián)與相鄰2022/10/192.關(guān)聯(lián)與相鄰2022/10/152022/10/192022/10/153.鏈與圈2022/10/193.鏈與圈2022/10/154.有向圖與無(wú)向圖，圈，回路比較：2022/10/194.有向圖與無(wú)向圖，圈，回路比較：2022/10/15v1v2v3v5v48342172022/10/19v1v2v3v5v48342172022/10/152022/10/192022/10/155.樹(shù)

例1已知有5個(gè)城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通過(guò)其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4

特點(diǎn)：連通、無(wú)圈。樹(shù)——無(wú)圈的連通圖，記為T。2022/10/195.樹(shù)例1已知有5個(gè)城市，要在它們v1v2v3v5v4樹(shù)的性質(zhì)：（1）樹(shù)的任2點(diǎn)間有且僅有1鏈；（2）在樹(shù)中任去掉1邊，則不連通；（3）在樹(shù)中不相鄰2點(diǎn)間添1邊，恰成1圈；（4）若樹(shù)T有n個(gè)頂點(diǎn)，則T有n-1條邊。2022/10/19v1v2v3v5v4樹(shù)的性質(zhì)：（1）樹(shù)的任2點(diǎn)間有且僅有1鏈6.圖的支撐樹(shù)

若圖G=（V，E）的子圖T=（V，E’）是樹(shù)，則稱T為G的支撐樹(shù)。特點(diǎn)——邊少、點(diǎn)不少。性質(zhì)：G連通，則G必有支撐樹(shù)。證：破圈、保連通。2022/10/196.圖的支撐樹(shù)若圖G=（V，E）的子圖T=（V二、網(wǎng)絡(luò)分析網(wǎng)絡(luò)——賦權(quán)圖，記D=（V，E，C），其中C={c1，…，cn}，

ci為邊ei上的權(quán)（設(shè)ci）。網(wǎng)絡(luò)分析主要內(nèi)容:

最小支撐樹(shù)

最短路

最大流。2022/10/19二、網(wǎng)絡(luò)分析網(wǎng)絡(luò)——賦權(quán)圖，記D=（V，E，C），其中C={一.最小支撐樹(shù)問(wèn)題問(wèn)題：求網(wǎng)絡(luò)D的支撐樹(shù)，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例2求如圖網(wǎng)絡(luò)的最小支撐樹(shù)。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.

2022/10/19一.最小支撐樹(shù)問(wèn)題問(wèn)題：求網(wǎng)絡(luò)D的支撐樹(shù)，使其權(quán)和最小。例避圈法是一種選邊的過(guò)程，其步驟如下：1.從網(wǎng)絡(luò)D中任選一點(diǎn)vi，找出與vi相關(guān)聯(lián)的權(quán)最小的邊[vi，vj]，得第二個(gè)頂點(diǎn)vj；2.把頂點(diǎn)集V分為互補(bǔ)的兩部分V1,1，其中2022/10/19避圈法是一種選邊的過(guò)程，其步驟如下：1.從網(wǎng)絡(luò)D中任選一點(diǎn)對(duì)G中各邊按權(quán)大小順序排列，不妨設(shè)為W1≤W2≤

…

≤Wm填寫Wj對(duì)應(yīng)的各邊aj

S=φ，i=0，j=1{aj}∪S構(gòu)成回路？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN2022/10/19對(duì)G中各邊按權(quán)大小順序排列，不妨設(shè)為W1≤W2≤…≤用避圈法解例2v5v1v3v6v4v2v7255233575711?最小部分樹(shù)如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？——見(jiàn)圈就破，去掉其中權(quán)最大的。2022/10/19用避圈法解例2v5v1v3v6v4v2v7255233575最小支撐樹(shù)問(wèn)題的應(yīng)用例子已知有A、B、C、D、E、F六個(gè)城鎮(zhèn)間的道路網(wǎng)絡(luò)如圖，現(xiàn)要在六個(gè)城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費(fèi)用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費(fèi)用最少的架設(shè)方案。6EACBFD51093539782842022/10/19最小支撐樹(shù)問(wèn)題的應(yīng)用例子已知有A、B、C、D、二.最短路問(wèn)題1.問(wèn)題：求網(wǎng)絡(luò)D中一定點(diǎn)v1到其它點(diǎn)的最短路。例3求如圖網(wǎng)絡(luò)中v1至v7的最短路，圖中數(shù)字為兩點(diǎn)間距離。v5v1v3v6v4v2v72552335757112022/10/19二.最短路問(wèn)題1.問(wèn)題：求網(wǎng)絡(luò)D中一定點(diǎn)v1到其它點(diǎn)的2.方法：Dijkstra算法（Dijkstra，1959）Dijkstra,E.W.(1959).Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik1,269–271.原理：Bellman最優(yōu)化原理若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最短路，Vl是P中除Vs與Vt外的任何一個(gè)中間點(diǎn)，則沿P從Vs到Vl的一條路P1亦必是Vs到Vl的最短路。證明（反證）：若P1不是從Vs到Vl的最短路，則存在另一條Vs到Vl的路P2使W(P2)<W(P1)，若記路P中從Vl到Vt的路為P3。則有W(P2)+W(P3)<W(P1)+W(P3)=W(P)，此說(shuō)明G中存在一條從Vs沿P2到Vl沿P3再到Vt的更短的一條路，這與P使G中從Vs到Vt的一條最短路矛盾。2022/10/192.方法：Dijkstra算法（Dijkstra，195算法思想：設(shè)G中從Vs到Vt的最小路P：Vs…Vj…Vk…Vt，則P不僅是從Vs到Vt的最小路，而且從Vs到P中任意中間點(diǎn)的最短路也在P上，為此可采用如下求解步驟：⑴為求得Vs到Vt的最短路，可先求得Vs到中間點(diǎn)的最短路，然后由中間點(diǎn)再逐步過(guò)渡到終點(diǎn)Vt。

⑵在計(jì)算過(guò)程中，需要把V中“經(jīng)判斷為最短路P途徑之點(diǎn)i”和“尚未判斷是否為最短路P途徑之點(diǎn)j”區(qū)分開(kāi)來(lái)，可設(shè)置集合I和J,前者歸入I，后者歸入J，并令算法初始時(shí)，I中僅包含Vs，其他點(diǎn)全在J中，然后隨著求解過(guò)程的進(jìn)行，I中的點(diǎn)逐漸增加（相應(yīng)J中的點(diǎn)逐漸減少），直到終點(diǎn)Vt歸入I（相應(yīng)J=φ），此時(shí)迭代結(jié)束。I稱為已標(biāo)號(hào)集合,J稱為未標(biāo)號(hào)集合。2022/10/19算法思想：2022/10/15⑶為區(qū)分中間點(diǎn)Vk是否已歸入I中以及逆向求解最短路的方便，可在歸入I中的點(diǎn)Vj上方給予雙標(biāo)號(hào)（lj,Vk），此中l(wèi)j表示從Vs到Vj最短路的距離，而Vk則為從Vs到Vj最短路P中Vj的前一途徑點(diǎn)。⑷為在計(jì)算機(jī)上實(shí)現(xiàn)上述求解思想，還需引入G中各點(diǎn)間一步可達(dá)距離陣D=(dij)n×n，其中|V|=n

2022/10/19⑶為區(qū)分中間點(diǎn)Vk是否已歸入I中以及逆向求解最短路的方便，由圖G建立一步可達(dá)距離陣D=(dij)n×n給V1(Vs)括號(hào)(l1,Vk)=(0,s)給出已標(biāo)號(hào)集合I和未標(biāo)號(hào)集合J的元素對(duì)于給定的I和J，確定集合A={aij|Vi∈I，Vj∈J}

計(jì)算距離給Vk括號(hào)(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ從Vt

逆向搜索雙括號(hào)，可得最小路P途徑各點(diǎn)及最小路距離ENDNYDijkstra算法2022/10/19由圖G建立一步可達(dá)距離陣D=(dij)n×n給V1(Vs)括用標(biāo)號(hào)法解例3v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1][4，v2][7，v3][8，v5][13，v6]最短距為13；最短路為v1-v2-v3-v5-v6-v7。2022/10/19用標(biāo)號(hào)法解例3v5v1v3v6v4v2v72552335752022/10/192022/10/15迭代過(guò)程2022/10/19迭代過(guò)程2022/10/15最短路問(wèn)題應(yīng)用廠址選擇廠址布局設(shè)備更新網(wǎng)絡(luò)線路安裝工程設(shè)計(jì)企業(yè)管理2022/10/19最短路問(wèn)題應(yīng)用廠址選擇2022/10/15最短路問(wèn)題的應(yīng)用例子

某汽車公司正在制訂5年內(nèi)購(gòu)買汽車的計(jì)劃。下面給出一輛新汽車的價(jià)格以及一輛汽車的使用維修費(fèi)用(萬(wàn)元)：

年份 1 2 3 4 5年初價(jià)格 11 11 12 12 13

使用年數(shù)0～11～22～3 3～44～5年維護(hù)費(fèi)用5 6 8 11 18

試用網(wǎng)絡(luò)分析中求最短路的方法確定公司可采用的最優(yōu)策略。2022/10/19最短路問(wèn)題的應(yīng)用例子某汽車公司正在制訂5年內(nèi)購(gòu)解：設(shè)Vi—i年初購(gòu)進(jìn)一臺(tái)新設(shè)備aij—i年初購(gòu)進(jìn)之新設(shè)備使用到第j年初ωij—i年初購(gòu)進(jìn)之新設(shè)備使用到第j年初之總費(fèi)用

方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以費(fèi)用作路長(zhǎng)。2022/10/19解：設(shè)方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期2022/10/192022/10/152022/10/192022/10/15費(fèi)用矩陣2022/10/19費(fèi)用矩陣2022/10/15方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以

費(fèi)用作路長(zhǎng)。2022/10/19方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以

2022/10/192022/10/15可知最短費(fèi)用流（相當(dāng)于最短路）

P：V1V3V6

或者是V1V4V6

|

P|=53萬(wàn)元

結(jié)論：公司五年期設(shè)備更新方案有兩個(gè)：A與B，總費(fèi)用均為53萬(wàn)元。

A方案：第1年初購(gòu)置設(shè)備使用到第3年初,第3年初再購(gòu)置新設(shè)備使用到第5年末（第6年初）

B方案：第1年初購(gòu)置設(shè)備使用到第4年初，第4年初再購(gòu)置新設(shè)備使用到第5年末（第6年初）

2022/10/19可知最短費(fèi)用流（相當(dāng)于最短路）

P：V1V3V6三.最大流問(wèn)題1.問(wèn)題已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點(diǎn)集，A為弧集，C={cij}為容量集，cij為?。╲i，vj）上的容量?，F(xiàn)D上要通過(guò)一個(gè)流f={fij}，其中fij為?。╲i，vj）上的流量。問(wèn)應(yīng)如何安排流量fij可使D上通過(guò)的總流量v最大？例如：v4v2vsv1vtv32131453252022/10/19三.最大流問(wèn)題1.問(wèn)題已知網(wǎng)絡(luò)D=（V，A，C）可采用線性規(guī)劃的單純型法求解（容量約束）（平衡條件）問(wèn)題：最大流問(wèn)題的決策變量、目標(biāo)函數(shù)、約束條件各是什么？2.數(shù)學(xué)模型2022/10/19可采用線性規(guī)劃的單純型法求解（容量約束）問(wèn)題：最大流問(wèn)題的決3.基本概念與定理如：在前面例舉的網(wǎng)絡(luò)流問(wèn)題中，若已給定一個(gè)可行流（如括號(hào)中后一個(gè)數(shù)字所示），請(qǐng)指出相應(yīng)的弧的類型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2022/10/193.基本概念與定理如：在前面例舉的網(wǎng)絡(luò)流問(wèn)題中，若已給定一（2）可增值鏈（增廣鏈）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2022/10/19（2）可增值鏈（增廣鏈）v4v2vsv1vtv3（2，2）（（3）截集與截量截量：截集上的容量和，記為。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）例4對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的截集與截量。2022/10/19（3）截集與截量截量：截集上的容量和，記為例4對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的截集與截量。解：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2022/10/19例4對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的截集與截（4）流量與截量的關(guān)系截集上的流量和相應(yīng)于截集的反向弧上流量和最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2022/10/19（4）流量與截量的關(guān)系截集上的流量和相應(yīng)于截最大流最小割定4.解法（5）最大流的判別條件2022/10/194.解法（5）最大流的判別條件2022/10/15步驟：2022/10/19步驟：2022/10/152022/10/192022/10/151．算法思想給定N＝{V，A，C}，任取一可行流f＝{fij}，若無(wú)可行流，可取零流。l＝1在f中任取一可增路pl利用標(biāo)號(hào)規(guī)則與調(diào)整規(guī)則對(duì)沿著路p的各弧作最大可能調(diào)整是否對(duì)N中所有路均作調(diào)整打印經(jīng)調(diào)整后的最大流f*及最大流量v（f*）取N的一條新可增路pll＝l＋1END雙標(biāo)號(hào)算法2022/10/191．算法思想給定N＝{V，A，C}，任取一可行流f＝{fij尋找一可增路pl，l＝1vs標(biāo)號(hào)（s，∞），沿pl尋找vs的下一相鄰節(jié)點(diǎn)vj按標(biāo)號(hào)規(guī)則對(duì)vj進(jìn)行雙標(biāo)號(hào)（vj，l（vj））

vs＝vt沿pl從收點(diǎn)vt開(kāi)始反向搜索途經(jīng)各弧，按調(diào)整規(guī)則作流量調(diào)整抹去pl上各點(diǎn)之雙標(biāo)號(hào)，從而由原可行流f調(diào)整為新可行流f1，并有v（f）＜v（f1）是否還有新的可增路打印并輸出經(jīng)調(diào)整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*）結(jié)束l＝l＋1取N的新的可增路plj＝k，i＝j(luò)沿pl尋找vj的相鄰的一點(diǎn)vkNYYN2、調(diào)整步驟2022/10/19尋找一可增路pl，l＝1vs標(biāo)號(hào)（s，∞），沿pl尋找vs例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。解：第一次標(biāo)號(hào)及所得可增值鏈如圖，調(diào)量=1，調(diào)后進(jìn)行第二次標(biāo)號(hào)如圖。第二次標(biāo)號(hào)未進(jìn)行到底，得最大流如圖，最大流量v=5，同時(shí)得最小截v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）??????20202022/10/19例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。解：第一次標(biāo)號(hào)及所得可增最大流問(wèn)題的應(yīng)用例子汽車由A城通往B城的可能的路線如下圖所示。環(huán)境保護(hù)部門擬建立足夠數(shù)量的汽車尾氣檢查站，以便使每輛汽車至少必須經(jīng)過(guò)一個(gè)檢查站。建立檢查站的費(fèi)用根據(jù)各路段的條件而有所不同(如圖上數(shù)字所示)。若求這個(gè)問(wèn)題的最小費(fèi)用解，可使用

模型。

a.最短路模型；b.最大流模型；c.最小支撐樹(shù)模型AacbdefgB8244526433673782022/10/19最大流問(wèn)題的應(yīng)用例子汽車由A城通往B城的可能的路延伸問(wèn)題最小費(fèi)用流中國(guó)郵遞員問(wèn)題、歐拉回路（邊）旅行商問(wèn)題、漢密爾頓圈（點(diǎn)）可平面化問(wèn)題指派問(wèn)題統(tǒng)籌網(wǎng)絡(luò)計(jì)劃匹配問(wèn)題2022/10/19延伸問(wèn)題最小費(fèi)用流2022/10/15數(shù)學(xué)建模競(jìng)賽涉及題目1994修路路線設(shè)計(jì)問(wèn)題

1998災(zāi)情巡查路線設(shè)計(jì)

2005DVD在線租賃問(wèn)題

2007乘公交看奧運(yùn)問(wèn)題

2011圍追堵截崗?fù)ぴO(shè)置問(wèn)題2022/10/19數(shù)學(xué)建模競(jìng)賽涉及題目1994修路路線設(shè)計(jì)問(wèn)題

1998災(zāi)情巡1994全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽

要在一山區(qū)修建公路,首先測(cè)得一些地點(diǎn)的高程,數(shù)據(jù)見(jiàn)表1(平面區(qū)域0≤x≤5600,0≤y≤4800,表中數(shù)據(jù)為坐標(biāo)點(diǎn)的高程,單位:米).數(shù)據(jù)顯示:

在y=3200處有一東西走向的山峰;從坐標(biāo)(2400,2400)到(4800,0)有一西北---東南走向的山谷;在(2000,2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流.經(jīng)調(diào)查知,雨量最大時(shí)溪流水面寬度w與(溪流最深處)的x坐標(biāo)的關(guān)系可近似表示為w(x)=((x-24003/4)/2)+5(2400≤x≤4000).公路從山腳(0,800)處開(kāi)始,經(jīng)居民點(diǎn)(4000,2000)至礦區(qū)(2000,4000).已知路段工程成本及對(duì)路段坡度α(上升高程與水平距離之比)的限制如表2.

2022/10/191994全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽要在一山區(qū)修建公路,首先測(cè)題目要求試給出一種線路設(shè)計(jì)方案,包括原理、方法及比較精確的線路位置(含橋梁、隧道),并估算該方案的總成本.

如果居民點(diǎn)改為3600≤x≤4000,2000≤y≤2400的居民區(qū),公路只須經(jīng)過(guò)居民區(qū)即可,那么你的方案需要有什么改變？2022/10/19題目要求試給出一種線路設(shè)計(jì)方案,包括原理、方法及比較精確的表1

2022/10/19表12022/10/15表2

工程種類┃一般路段┃橋梁┃隧道_________┃_______工程成本(元/米)┃300┃2000┃1500(長(zhǎng)度≤300米);3000(長(zhǎng)度>300米)對(duì)坡度α的限制┃α<0.125┃α=0┃α<0.1002022/10/19表2工程種類┃一般路段┃橋梁┃模型計(jì)算方法(1)

對(duì)地圖網(wǎng)格加密，形成圖。(2)

計(jì)算網(wǎng)格的距離，用費(fèi)用作為權(quán)值。(3)求賦權(quán)圖兩點(diǎn)間的最短距離。

2022/10/19模型計(jì)算方法(1)

對(duì)地圖網(wǎng)格加密，形成圖。2022參考答案2022/10/19參考答案2022/10/151998年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽

災(zāi)情巡視路線，下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。2022/10/191998年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽災(zāi)情巡視路線，下圖為某若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。

假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。若巡視組數(shù)已定(如三組)，要求盡快完成巡視，討論T，t和V改變對(duì)最佳巡視路線的影響。上述關(guān)于T,t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。2022/10/19若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路鄉(xiāng)村分布圖2022/10/19鄉(xiāng)村分布圖2022/10/15點(diǎn)的行遍性問(wèn)題1、圖論---哈密爾頓問(wèn)題（是否存在經(jīng)過(guò)所有點(diǎn)一次的圈）2、組合優(yōu)化--旅行商問(wèn)題（賦權(quán)圖經(jīng)過(guò)所有頂點(diǎn)至少一次）

非完全圖的多旅行商問(wèn)題兩點(diǎn)間的最短路長(zhǎng)度作為兩點(diǎn)間的權(quán)，構(gòu)造完全圖。兩邊權(quán)之和不小于第三邊的權(quán)==》完全圖的最優(yōu)哈密爾頓圈《==》原圖的最優(yōu)旅行商問(wèn)題。完全圖---增廣完全圖==求最優(yōu)哈密爾頓圈近似算法或分組后直接搜索注意（1）

兩點(diǎn)間的最短路長(zhǎng)度可用Dijkstra算法（2）

多旅行商問(wèn)題===》最優(yōu)哈密爾頓圈2022/10/19點(diǎn)的行遍性問(wèn)題1、圖論---哈密爾頓問(wèn)題（是否存在經(jīng)過(guò)所有點(diǎn)線性規(guī)劃模型2022/10/19線性規(guī)劃模型2022/10/15問(wèn)題解答：1、分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。

目標(biāo)函數(shù)：

min(C1+C2+C3)限制條件：min(C3-C1)或

者

：min(C1)2、假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線。2022/10/19問(wèn)題解答：2022/10/15

目標(biāo)函數(shù)：

min(H1+H2+H3)

花費(fèi)時(shí)間：Hi=2mi+ni+Ci/V

限制條件：min(max(Hi))總時(shí)間69小時(shí)===》至少4組，4組的路線可以找到。3、在上述關(guān)于T,t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。

單獨(dú)巡視的最短時(shí)間=