1. 項目概述當(dāng)數(shù)學(xué)建模遇上城市“血管”規(guī)劃自來水管道鋪設(shè)聽起來像是市政工程或給排水專業(yè)的活兒怎么就成了數(shù)學(xué)建模的經(jīng)典賽題這恰恰是數(shù)學(xué)建模的魅力所在——它用抽象的數(shù)學(xué)工具去解決現(xiàn)實世界中那些看似龐雜、充滿約束的實際問題。我參加過不少數(shù)學(xué)建模競賽也帶過學(xué)生團隊發(fā)現(xiàn)“管道鋪設(shè)”這類問題幾乎是各類賽事的“?？汀币驗樗昝廊诤狭藞D論、優(yōu)化算法和成本分析是一個檢驗綜合能力的絕佳場景。簡單來說這個問題就是給定一片區(qū)域比如一個新開發(fā)區(qū)、一個工業(yè)園區(qū)或一個居民小區(qū)里面有若干個需要供水的用戶點居民樓、工廠等以及一個或多個水源點水廠、加壓站。你的任務(wù)就是設(shè)計一套管道網(wǎng)絡(luò)用最經(jīng)濟的方式把水從水源送到每一個用戶點。這里的“經(jīng)濟”通常指管道建設(shè)總成本最低而成本又和管道的長度、材質(zhì)、直徑等因素掛鉤。這可不是隨便畫畫連接線那么簡單它涉及到如何選擇管道路徑、如何確定管道規(guī)格、如何在多個水源和用戶之間分配流量是一個典型的網(wǎng)絡(luò)優(yōu)化問題。無論是參加“高教社杯”全國大學(xué)生數(shù)學(xué)建模競賽還是準(zhǔn)備美賽MCM/ICM這類問題都極具代表性。它考察的不僅僅是數(shù)學(xué)公式的套用更是將實際問題轉(zhuǎn)化為數(shù)學(xué)模型的能力、對多種算法如最小生成樹、最短路徑、線性/非線性規(guī)劃的靈活運用以及利用編程工具如MATLAB、Python進行求解和結(jié)果可視化的綜合技能。接下來我就以一個資深建模者的視角帶你層層拆解這個問題的核心分享從問題分析到論文成稿的全流程實戰(zhàn)經(jīng)驗。2. 問題拆解與模型構(gòu)建思路面對一個具體的管道鋪設(shè)問題第一步不是急著寫代碼或查公式而是靜下心來把題目描述“翻譯”成數(shù)學(xué)語言。這個過程決定了整個模型的走向和最終方案的優(yōu)劣。2.1 核心要素抽象化首先我們需要從工程問題中提取出數(shù)學(xué)模型的基本元素節(jié)點將水源點、用戶需求點抽象為網(wǎng)絡(luò)中的“節(jié)點”。通常水源點被視為供應(yīng)點或“根”節(jié)點用戶點被視為需求點。有時為了路徑更優(yōu)我們還可以在道路交叉口或特定位置引入“虛擬節(jié)點”或“ Steiner點”斯坦納點但這會大大增加問題復(fù)雜度屬于進階玩法。邊連接兩個節(jié)點的管道抽象為網(wǎng)絡(luò)中的“邊”。每條邊有兩個關(guān)鍵屬性長度和成本系數(shù)。成本系數(shù)可能是一個簡單的單位長度造價也可能是一個與管道直徑、材質(zhì)、埋深相關(guān)的復(fù)雜函數(shù)。權(quán)重通常指邊的成本即鋪設(shè)這條管道所需的費用。最基本的情況是成本 單位長度造價 × 管道長度。但實際問題中成本可能還與地形平地、山地、穿越河流、地質(zhì)條件、是否需拆遷等因素有關(guān)這就需要為不同的邊賦予不同的單位成本。約束條件這是模型的血肉。常見的約束包括連通性約束必須保證從水源點到每一個用戶點都存在通路即網(wǎng)絡(luò)是連通的。流量約束如果考慮水力管道直徑需滿足用戶節(jié)點的流量或水壓需求。這會將問題從單純的圖論問題升級為網(wǎng)絡(luò)流優(yōu)化問題。樹狀網(wǎng)絡(luò)約束在很多簡化模型中要求最終的管道網(wǎng)絡(luò)是一棵樹即任意兩點間只有唯一路徑無環(huán)。這是因為環(huán)狀管網(wǎng)雖然可靠性高但初期建設(shè)成本通常更高。競賽題中為簡化問題常默認(rèn)采用樹狀結(jié)構(gòu)。單/多水源是一個水源供應(yīng)所有點還是多個水源協(xié)同供應(yīng)。目標(biāo)函數(shù)我們最終要優(yōu)化的東西。99%的情況下是最小化管道網(wǎng)絡(luò)的總建設(shè)成本。在考慮流量和管徑時目標(biāo)函數(shù)可能是“最小化總投資管道成本泵站成本等”。2.2 模型類型選擇與思路演進根據(jù)問題的具體條件我們可以選擇不同復(fù)雜度的模型基礎(chǔ)版不考慮流量和管徑的靜態(tài)最小成本網(wǎng)絡(luò)這是最經(jīng)典的版本。問題退化為給定節(jié)點坐標(biāo)和邊的造價求一個連接所有節(jié)點的網(wǎng)絡(luò)使得總成本最小。如果網(wǎng)絡(luò)必須是樹那就是經(jīng)典的最小生成樹問題。常用的算法有Prim算法從一個根節(jié)點水源開始逐步生長出一棵樹。非常適合單水源問題能保證生成的樹以水源為根。Kruskal算法對所有邊按權(quán)重排序從小到大選擇不構(gòu)成環(huán)的邊加入。更適合無指定根節(jié)點或需要快速理解的情況。注意如果問題沒有強制要求樹狀結(jié)構(gòu)那么最優(yōu)解可能是“最小生成樹”因為增加任何邊都會增加成本在邊權(quán)為正的前提下。所以即使題目沒說最小生成樹也常常是一個優(yōu)秀的候選解。進階版考慮流量需求的管徑優(yōu)化網(wǎng)絡(luò)一旦引入用戶節(jié)點的用水量需求問題就變得復(fù)雜起來。管道直徑的選擇直接影響成本和輸水能力。大管徑成本高但水頭損失小小管徑成本低但可能無法輸送足夠流量或?qū)е履┒怂畨翰蛔?。這時模型變成一個混合整數(shù)非線性規(guī)劃問題決策變量包括哪些邊被選中0-1變量、被選中邊的管徑離散選擇變量、管道中的流量連續(xù)變量。目標(biāo)函數(shù)是管道成本與管徑、長度有關(guān)的最小化約束包括節(jié)點流量平衡方程、管道壓降方程等。求解這類問題需要用到專業(yè)的優(yōu)化求解器如LINGO、Gurobi或設(shè)計啟發(fā)式算法。高階版多階段規(guī)劃或帶可靠性要求有些題目會考慮城市規(guī)劃是分階段的或者要求管網(wǎng)系統(tǒng)具備一定的可靠性如當(dāng)某段管道損壞時能有備用路徑供水。這就涉及到多階段優(yōu)化和網(wǎng)絡(luò)可靠性設(shè)計可能需要用到更復(fù)雜的隨機規(guī)劃或魯棒優(yōu)化模型。對于大多數(shù)競賽場景能把“基礎(chǔ)版”做扎實并嘗試向“進階版”做一些合理的探索和簡化就已經(jīng)能產(chǎn)出非常出色的論文了。我的建議是先完成再完美。先用最小生成樹給出一個可行解作為論文的基準(zhǔn)方案然后再嘗試加入流量因素進行優(yōu)化對比結(jié)果展示你的思考深度。3. 核心算法實現(xiàn)與編程實戰(zhàn)理論分析之后就要動手實現(xiàn)。這里我以最經(jīng)典的、基于坐標(biāo)和歐氏距離的最小生成樹問題為例展示用Python搭配networkx和matplotlib庫的完整求解和可視化流程。假設(shè)我們有1個水源點和9個用戶點。3.1 數(shù)據(jù)準(zhǔn)備與問題描述首先我們定義節(jié)點。通常水源點編號為0。import numpy as np import matplotlib.pyplot as plt import networkx as nx # 定義節(jié)點坐標(biāo) (水源點 用戶點) # 節(jié)點0為水源其余1-9為用戶點 coordinates { 0: (0, 0), # 水源 1: (2, 3), 2: (4, 1), 3: (5, 4), 4: (7, 2), 5: (8, 5), 6: (3, 6), 7: (6, 7), 8: (1, 8), 9: (9, 9) } # 定義節(jié)點類型和需求為進階模型準(zhǔn)備 node_demand {0: 0} # 水源供應(yīng)需求為負或0 for i in range(1, 10): node_demand[i] np.random.randint(10, 30) # 隨機生成用戶點用水需求單位升/秒3.2 構(gòu)建完全圖并計算邊權(quán)我們的目標(biāo)是連接所有節(jié)點因此先假設(shè)任意兩點間都可以直接鋪設(shè)管道即構(gòu)建一個完全圖邊的權(quán)重就是兩點間的歐氏距離乘以一個單位成本系數(shù)。這里為了簡化設(shè)單位成本系數(shù)為1即權(quán)重等于距離。# 創(chuàng)建完全無向圖 G nx.Graph() G.add_nodes_from(coordinates.keys()) # 計算所有節(jié)點對之間的歐氏距離作為邊權(quán)成本 for i in coordinates: for j in coordinates: if i j: # 避免重復(fù)添加邊 x1, y1 coordinates[i] x2, y2 coordinates[j] distance np.sqrt((x2 - x1)**2 (y2 - y1)**2) # 這里可以乘以一個成本系數(shù)例如不同地形成本不同 cost distance # 假設(shè)單位距離成本為1 G.add_edge(i, j, weightcost) # 為節(jié)點添加坐標(biāo)屬性用于繪圖 for node, (x, y) in coordinates.items(): G.nodes[node][pos] (x, y)3.3 應(yīng)用最小生成樹算法求解我們分別使用Prim算法指定水源為根和Kruskal算法求解并對比結(jié)果。在單位成本一致的情況下它們求出的總成本應(yīng)該相同但樹的結(jié)構(gòu)可能因算法而異不過最小生成樹的總權(quán)重唯一。# 使用Kruskal算法求最小生成樹 (MST) mst_kruskal nx.minimum_spanning_tree(G, algorithmkruskal) total_cost_kruskal sum(G.edges[u, v][weight] for u, v in mst_kruskal.edges()) # 使用Prim算法求最小生成樹指定根節(jié)點為0水源 mst_prim nx.minimum_spanning_tree(G, algorithmprim) total_cost_prim sum(G.edges[u, v][weight] for u, v in mst_prim.edges()) print(fKruskal算法得到的最小生成樹總成本: {total_cost_kruskal:.2f}) print(fPrim算法得到的最小生成樹總成本: {total_cost_prim:.2f})3.4 結(jié)果可視化與方案展示將原始節(jié)點、可能的連接以淺色表示以及最終選中的最小生成樹管道以粗線高亮繪制出來能讓你的論文結(jié)果部分增色不少。# 繪制圖形 plt.figure(figsize(12, 6)) # 子圖1原始完全圖 plt.subplot(1, 2, 1) pos nx.get_node_attributes(G, pos) nx.draw_networkx_nodes(G, pos, node_colorlightblue, node_size300) nx.draw_networkx_nodes(G, pos, nodelist[0], node_colorred, node_size500, label水源) # 高亮水源 nx.draw_networkx_edges(G, pos, alpha0.2, edge_colorgray) # 淺色表示所有可能連接 nx.draw_networkx_labels(G, pos) plt.title(原始節(jié)點與所有可能連接完全圖) plt.axis(equal) plt.legend() # 子圖2最小生成樹方案以Prim結(jié)果為例 plt.subplot(1, 2, 2) nx.draw_networkx_nodes(G, pos, node_colorlightblue, node_size300) nx.draw_networkx_nodes(G, pos, nodelist[0], node_colorred, node_size500, label水源) nx.draw_networkx_edges(G, pos, edgelistmst_prim.edges(), width3, edge_colordarkorange, label鋪設(shè)管道) nx.draw_networkx_labels(G, pos) plt.title(f最小生成樹管道鋪設(shè)方案\n總成本: {total_cost_prim:.2f}) plt.axis(equal) plt.legend() plt.tight_layout() plt.show() # 輸出詳細的邊信息 print(\n 最小生成樹管道鋪設(shè)詳情 ) print(起點-終點 | 長度成本) print(- * 30) for u, v in mst_prim.edges(): length G.edges[u, v][weight] print(f {u:2d} - {v:2d} | {length:.2f})實操心得在競賽中數(shù)據(jù)往往不是直接給坐標(biāo)而是給節(jié)點間的距離矩陣或者給的是街區(qū)距離曼哈頓距離而非直線距離。這時你需要根據(jù)題目描述在構(gòu)建圖的時候正確計算邊權(quán)。例如如果是街區(qū)距離邊權(quán)cost abs(x2-x1) abs(y2-y1)。這個細節(jié)是很多新手容易忽略的失分點。4. 模型進階引入流量與管徑優(yōu)化基礎(chǔ)模型假設(shè)所有管道成本只與長度有關(guān)這顯然不符合工程實際。管徑越大造價越高但輸水能力也越強。接下來我們嘗試在模型中加入流量因素做一個簡化版的管徑優(yōu)化。4.1 問題簡化與假設(shè)為了在競賽有限時間內(nèi)使問題可解我們通常需要做出合理簡化管徑離散化假設(shè)市場上只有幾種標(biāo)準(zhǔn)管徑可供選擇如DN100, DN150, DN200而不是連續(xù)變量。水力模型簡化忽略復(fù)雜的水頭損失計算采用一個簡化的規(guī)則例如“某管徑下最大允許流量”?；蛘呶覀兛梢詫ⅰ皾M足流量需求”轉(zhuǎn)化為對管道“容量”的約束。流向確定在樹狀網(wǎng)絡(luò)中從水源到每個用戶的路徑是唯一的。因此每條管道中的流量等于所有通過該管道供水的下游用戶的需求量之和。這是一個自頂向下的確定過程。4.2 建立混合整數(shù)規(guī)劃模型思路設(shè)x_{ij}^bextvpl為0-1變量表示節(jié)點i到j(luò)的管道是否采用管徑d。f_{ij}為連續(xù)變量表示從i流向j的流量假設(shè)方向從i到j(luò)。c_bextvpl為單位長度、管徑為d的管道成本。L_{ij}為節(jié)點i到j(luò)的距離。D為所有可選管徑的集合。Q_{max}^bextvpl為管徑d的最大允許流量。目標(biāo)函數(shù)最小化總成本Minimize Σ_{i,j} Σ_{d in D} (c_d * L_ij * x_{ij}^bextvpl)約束條件網(wǎng)絡(luò)結(jié)構(gòu)約束選中的邊構(gòu)成一棵以水源為根的樹。這可以用經(jīng)典的“單商品流”約束或“Miller-Tucker-Zemlin”約束來刻畫但較為復(fù)雜。在編程求解時一種實用的啟發(fā)式方法是先確定拓撲結(jié)構(gòu)如用最小生成樹再優(yōu)化管徑。即兩階段法。流量平衡約束對于每個非水源節(jié)點j流入流量 - 流出流量 該節(jié)點需求。管徑容量約束如果從i到j(luò)的管道被選中且管徑為d則流量f_{ij} Q_max^d。這可以表示為f_{ij} Σ_{d in D} (Q_max^d * x_{ij}^bextvpl)。管徑唯一性約束對于每條可能被選中的邊(i,j)只能選擇一種管徑Σ_{d in D} x_{ij}^bextvpl 1。注意這里是1而不是1因為這條邊可能不被選中。4.3 兩階段啟發(fā)式算法實現(xiàn)示例由于完整的MIP模型求解較慢我們可以采用一個高效的兩階段啟發(fā)式方法第一階段用最小生成樹確定管道網(wǎng)絡(luò)的拓撲結(jié)構(gòu)即哪些邊需要鋪設(shè)。第二階段在固定的樹狀結(jié)構(gòu)上從葉子節(jié)點向水源根節(jié)點回溯計算每條邊需要承載的流量然后根據(jù)流量為其選擇能滿足要求的最小標(biāo)準(zhǔn)管徑因為成本隨管徑增大而增加所以選最小可行管徑是最經(jīng)濟的。# 假設(shè)我們已通過第一階段得到最小生成樹 mst_prim (一個networkx的Graph對象) # 定義管徑選項及其屬性 pipe_options { DN100: {max_flow: 15, cost_per_unit_length: 10}, # 最大流量15單位長度成本10 DN150: {max_flow: 30, cost_per_unit_length: 18}, DN200: {max_flow: 50, cost_per_unit_length: 25} } # 將樹轉(zhuǎn)為以水源節(jié)點0為根的有向樹方便計算流量 directed_tree nx.dfs_tree(mst_prim, source0) # 計算每條邊需要承載的流量自底向上后序遍歷 # 首先初始化所有節(jié)點的“子樹總需求”葉子節(jié)點就是自身需求 subtree_demand node_demand.copy() # 開始時每個節(jié)點的子樹需求就是自身需求 # 按從葉子到根的順序處理節(jié)點逆拓撲序 # 獲取一個逆拓撲序從葉子到根 reverse_order list(reversed(list(nx.topological_sort(directed_tree)))) # 有向樹拓撲排序 for node in reverse_order: if node 0: continue # 根節(jié)點水源不需要向上傳遞 # 找到該節(jié)點的父節(jié)點在有向樹中入度為1 predecessors list(directed_tree.predecessors(node)) if predecessors: parent predecessors[0] # 將當(dāng)前節(jié)點的子樹總需求加到父節(jié)點的子樹總需求上 subtree_demand[parent] subtree_demand[node] # 現(xiàn)在對于有向樹中的每條邊 (parent - child)其需要承載的流量就是 child 的 subtree_demand edge_flow {} for u, v in directed_tree.edges(): # u是父v是子 edge_flow[(u, v)] subtree_demand[v] # 根據(jù)流量為每條邊選擇管徑 edge_diameter {} total_cost_advanced 0 print(\n 考慮流量后的管徑優(yōu)化方案 ) print(邊父-子 | 所需流量 | 選定管徑 | 長度 | 該段成本) print(- * 60) for (u, v), flow in edge_flow.items(): length G.edges[u, v][weight] # 獲取邊的長度 # 選擇能滿足流量的最小成本管徑 chosen_diam None min_cost_for_edge float(inf) for diam, props in pipe_options.items(): if flow props[max_flow]: cost props[cost_per_unit_length] * length if cost min_cost_for_edge: min_cost_for_edge cost chosen_diam diam # 理論上管徑選項應(yīng)覆蓋所有流量范圍這里假設(shè)總能找到 edge_diameter[(u, v)] chosen_diam total_cost_advanced min_cost_for_edge print(f {u:2d} - {v:2d} | {flow:7.1f} | {chosen_diam:^8} | {length:4.2f} | {min_cost_for_edge:7.2f}) print(f\n優(yōu)化后管網(wǎng)總成本: {total_cost_advanced:.2f}) print(f相較于僅考慮長度的基礎(chǔ)方案成本 {total_cost_prim:.2f}成本變化: {total_cost_advanced - total_cost_prim:.2f})注意這個兩階段方法是啟發(fā)式的不一定得到全局最優(yōu)解因為拓撲結(jié)構(gòu)是第一階段單獨決定的可能不是考慮管徑成本后的最優(yōu)拓撲。但在時間有限的競賽中這是一個非常有效且合理的策略。你可以在論文中明確指出這是“分解-優(yōu)化”的啟發(fā)式思路并討論其優(yōu)缺點。5. 論文寫作要點與常見陷阱數(shù)學(xué)建模競賽三分靠模型七分靠表達。一個清晰、嚴(yán)謹(jǐn)、美觀的論文是獲勝的關(guān)鍵。5.1 論文核心結(jié)構(gòu)摘要重中之重用300字左右概括問題、你的方法、模型、算法、主要結(jié)果和結(jié)論。要獨立成文讓評委不看正文也能知道你們做了什么。模板“針對XX問題本文建立了……模型。首先……其次……然后運用……算法求解最后……。結(jié)果表明……。本文的特色在于……?！眴栴}重述與分析不要照抄題目要用自己的話梳理問題的背景、條件和目標(biāo)。進行問題分析指出問題的類型優(yōu)化、預(yù)測、評估等、關(guān)鍵難點和解決思路。模型假設(shè)與符號說明列出所有為了簡化問題而做出的合理假設(shè)。符號說明用三線表清晰明了。模型建立與求解這是論文主體。分小節(jié)闡述你的模型5.1 基礎(chǔ)模型如最小生成樹模型5.2 模型改進如引入流量與管徑的優(yōu)化模型5.3 算法設(shè)計詳細說明你用的算法步驟最好配上流程圖5.4 求解過程說明使用的軟件、工具包、求解器參數(shù)等模型結(jié)果與分析用表格和圖表展示結(jié)果總成本、管道明細表、網(wǎng)絡(luò)圖。進行靈敏度分析改變某個參數(shù)如單位成本、某個用戶需求觀察結(jié)果如何變化。這能體現(xiàn)模型的穩(wěn)健性和你的思考深度。例如“將水源點坐標(biāo)微調(diào)至(0.5, 0.5)總成本變化小于2%表明模型對水源位置不敏感。”方案對比如果你的模型有多個版本如基礎(chǔ)版vs進階版一定要對比結(jié)果分析差異原因。模型評價與推廣客觀評價自己模型的優(yōu)點計算快、易于理解、結(jié)果合理和缺點忽略了地形起伏、假設(shè)需求恒定等。提出模型的改進方向和在類似問題如電網(wǎng)鋪設(shè)、通信光纜布局中的應(yīng)用前景。參考文獻與附錄規(guī)范引用參考文獻。將核心代碼、大型數(shù)據(jù)表格放在附錄。5.2 常見陷阱與避坑指南陷阱一模型與算法混淆。在論文中“模型”是指你用數(shù)學(xué)公式、變量、約束描述的問題結(jié)構(gòu)“算法”是求解這個模型的具體計算步驟如Prim算法、遺傳算法。一定要分開寫。陷阱二只有結(jié)果沒有分析。擺出總成本就完了不行要分析這個方案為什么好管道走向有什么特點成本主要花在哪里。靈敏度分析是拉開差距的關(guān)鍵。陷阱三圖表質(zhì)量低下。用MATLAB或Python畫圖時務(wù)必保證清晰度。坐標(biāo)軸標(biāo)簽、圖例、標(biāo)題要齊全。網(wǎng)絡(luò)圖節(jié)點不要重疊可以用nx.spring_layout或nx.kamada_kawai_layout進行布局優(yōu)化。陷阱四忽略單位。長度是米還是公里成本是元還是萬元流量是升/秒還是立方米/天全文必須統(tǒng)一并在符號說明中明確標(biāo)出。陷阱五代碼堆砌。附錄里的代碼要有重點只放核心函數(shù)或算法主流程并加上必要的注釋。不要粘貼全部幾十行代碼。陷阱六假設(shè)不合理。假設(shè)是為了簡化但不能改變問題的本質(zhì)。例如不能假設(shè)“所有用戶需求為零”來簡化問題。你的假設(shè)需要讓人感覺是“在可控范圍內(nèi)對現(xiàn)實情況的合理近似”。個人心得管道鋪設(shè)問題是一個非常好的練手項目它像一把鑰匙能幫你打開運籌學(xué)、圖論和優(yōu)化算法的大門。在實戰(zhàn)中最關(guān)鍵的一步永遠是“問題分析”?；ò胄r仔細讀題、畫示意圖、列舉已知和未知遠比一上來就套公式有效。當(dāng)你拿到題目看到那些散落的“點”能在腦海里自動將它們連成一張“圖”并開始思考“權(quán)重”和“約束”時你就已經(jīng)成功了一半。剩下的就是用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)和清晰的表達將你的思考呈現(xiàn)出來。