【正文】 Row Slack or Surplus Dual Price 1 2 3 4 結(jié)果： 1 ( 62 .3 33 73 , 77 .8 64 94 ) , 2( 17 3. 09 80 , 43 .6 43 28 )； , 1 ?S ?S (2)MATLAB 求解結(jié)果：（ 附錄五 .Fun2） 結(jié)果： 1 ( , ) , 2( , )； , 1 ?S ?S 、 運用費馬點 ： 根據(jù) 1 ( , ) , 2( , )做為交叉點設(shè)計路線， 如下圖 所示。 、 引用費馬點 ： 為引用費馬點將圖 中 P P5 用虛線連接，如圖 所示 .（附錄四 .Fun3） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1P2 P3P4P5P6P7P8 （圖 ） 可知：△ P2P6P5 和△ P3P4P5 的 3 個內(nèi)角均小于 120176。那么 費馬點即為 三角形 三個內(nèi)角角平分線交點。 兩點間的直線距離 ≤ ■ 結(jié)果： 新修路的總路程 S: S=D18+D2b+Dba+Da6+Da5+D5d+Ddc+Dc3+D34 =++++++++ =(米 ) 、模型二的建立與求解 、 引入費馬點 ： 費馬點性質(zhì)： 在一個三角形中，到 3 個頂點距離之和最小的點叫做這個三角形的費馬點。 調(diào)整后的最終方案如下圖 所示。（附錄三） MATLAB 運行后的結(jié)果如下表 所示： 表 通過交叉點最短路徑表 點 最短路徑 最短路徑長度 最短路徑 /兩點間的直線距離 P1P5 1 2 10 9 12 5? ? ? ? ? P1P6 1 2 10 9 6? ? ? ? P1P8 18? 1 P2P5 2 1 0 9 1 2 5? ? ? ? P2P6 2 10 9 6? ? ? P2P7 2 1 0 9 6 7? ? ? ? P3P4 34? 1 P3P5 3 11 12 5? ? ? P3P6 3 1 1 1 2 9 6? ? ? ? P3P7 3 1 1 1 2 9 6 7? ? ? ? ? 由表 可知：“ P1P5”、“ P2P5”的“最短路徑 /兩點間的直線距離 ”。（附錄二） MATLAB 運行后的結(jié)果如下表 所示： 表 Kruskal 算法的程序運行結(jié)果表 25 29 30 30 30 32 36 41 57 64 65 6 6 1 5 11 1 9 2 3 3 9 7 9 2 12 12 8 10 10 11 4 12 由表 的結(jié)果可畫出最小生成樹如下圖 所示。 L 新修路的總路程 五、模型的建立與求解 、模型一的建立與求解 針對 P P …… 、 P8 及公園 4 個固定道路交叉點 a、 b、 c、 d，求 出這 12 個點兩兩之間的直線距離，如下表 所示： 表 （ ）入口點及道路交叉點兩兩之間的直線距離表（小數(shù)部分已做處理） P1 P2 P3 P4 P5 P6 P7 P8 a b c d P1 0 30 140 187 141 101 100 32 81 45 108 118 P2 30 0 110 158 122 101 108 56 75 41 81 96 P3 140 110 0 64 108 160 180 162 133 126 57 83 P4 187 158 64 0 94 172 196 202 152 160 81 87 P5 141 122 108 94 0 85 110 142 74 100 60 30 P6 101 101 160 172 85 0 25 83 29 60 104 85 P7 100 108 180 196 110 25 0 76 47 67 125 109 P8 32 56 162 202 142 83 76 0 71 43 121 123 a 81 75 133 152 74 29 47 71 0 36 78 65 b 45 41 126 160 100 60 67 43 36 0 80 81 c 108 81 57 81 60 104 125 121 78 80 0 30 d 118 96 83 87 30 85 109 123 65 81 30 0 以表 所示的矩陣為公園道路設(shè)計連通圖的鄰接矩陣。 四、 符號說明 P1 P2 P3 P4 P5 P6 P7 P8 入口點 a b c d 交叉點 R1 R2 R3 R4 人工湖頂點 Qi(xi,yi) 三角形費馬點 Si 費馬點到三角形 3 個頂點的距離和 Dij i 到 j 的路程 S S39。 公園內(nèi)新修的道路與四周的連接只能與 8 個路口相通，而不能連接到四周的其他點。 根據(jù)距離模型可知距離與入口大小無關(guān)，故可將各入口均視為點 。 方案分析 ：我們可以發(fā)現(xiàn)方案三、四將需要人工湖中有路段通過，這與題目不符。 方案三：連接 P5R1，求 △ R1P4P3 的費馬點，設(shè)計最 短路徑。 修改 P5Q1 路線，對 Q2 區(qū)域局部優(yōu)化方案： 方案一：連接 P5R4，求 △ R4P4P3 的費馬點，設(shè)計最短路徑。 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100R1R2 R3R4P1 P2 P3P4P5P6P7P8Q1Q2 （圖 ） 可知：由于加入了人工湖，原方案中的 P5Q1 路線將不再可行。 入口點兩兩之間的直線距離≤ 通過逐步檢驗分析可知“ P1P P2P P2P P3P P3P5”滿足要求，故簡化為下圖 .（附錄四 .Fun2） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2 P3P4P5P6P7P8 （圖 ） 再通過交叉點設(shè)計“ P1P P2P P2P P3P P3P5”的最短路徑。（附錄四 .Fun1） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2 P3P4P5P6P7P8 （圖 ） 圖 中線段長度，如下表 所示： 兩點間直線段 長度 P1P5 P1P6 P1P8 P2P5 P2P6 P2P7 P3P4 P3P5 P3P6 P3P7 在圖 中尋找“ P1— P P1— P P1— P P2— P P2— P P2— P P3— PP3— P P3— P P3— P7”的最短路徑（可利用邊界）。 在第一個問題中，已經(jīng)知道“ P1— P P1— P P1— P P2— P P2— P P2— PP3— P P3— P P3— P P3— P7”需要通過交叉點設(shè)計路線。 表 入口點兩兩之間的直線 距離表 P1 P2 P3 P4 P5 P6 P7 P8 P1 0 30 140 32 P2 0 110 P3 0 64 P4 0 P5 0 85 110 P6 0 25 P7 0 P8 0 表 入口點兩兩之間的邊界路徑距離表 P1 P2 P3 P4 P5 P6 P7 P8 P1 0 P2 30 0 P3 140 110 0 P4 230 200 90 0 P5 360 330 220 130 0 P6 155 185 295 215 85 0 P7 130 160 270 240 110 25 0 P8 45 75 185 275 195 105 85 0 通過計算：“ P1— P P1— P P1— P P2— P P2— P P2— P P3— P P3— PP3— P P3— P7”需要通過交叉點設(shè)計路線。 “ 8 個入口點兩兩之間的邊界路徑距離 247。 “ 8 個入口點兩兩之間的邊界路徑距離 247。 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100R1R2 R3R4P1 P2 P3P4P5P6P7P8 （圖 3） 注：以上問題中都要求公園內(nèi)新修的道路與四周的連接只能與 8 個路口相通，而不能連接到四周的其它點。 問題三：若公園內(nèi)有一條矩形的湖，新修的路不能通過，但可以到達湖四周的邊，已知矩形的湖為 R1(140,70) , R2(140， 45) , R3(165， 45) , R4(165， 70)，見圖 3（附錄六 .Fun1）。 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2 P3P4P5P6P7P8abcd （圖 2） 問題二：現(xiàn)在公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。問如何設(shè)計道路可使公園內(nèi)道路的總路程最短。（附錄一 .Fun1）。 要求：公園計劃有若干個入口，需建立一個模型去設(shè)計道路讓任意兩個入口相連（可以利用公園的邊，即默認矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長），使總的道路長度和最小，且任意兩個入口之間的最短道 路長不大于兩點連線的 倍。使得公園新修路的總路程最小為 米。最后：運用費馬點優(yōu)化可行方案，分別得到 2 個方案的最優(yōu)道路設(shè)計方案。針對人工湖對路線的破壞段進行局部優(yōu)化。使得公園新修路的總路程最小為 米。 然后：引入費馬點，確定費馬點個數(shù)，運用 LINGO 和 MATLAB 分別求解費馬點坐標(biāo)。使得公園新修路的總路程最小為 米。然后：依據(jù) Kruskal 算法，構(gòu)造最小生成樹。又因公園邊界已經(jīng)存在修建好的道路，且不計入修建總總長度，所以應(yīng)盡量利用邊界道路。 我們參賽選擇的題號是（從 A/B/C/D 中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜? 西安培華學(xué)院 參賽隊員 (打印并簽名 ) ： 1. 胡斌斌 2. 羅丹 3. 白桂興 指導(dǎo)教師 或 指導(dǎo)教師組負責(zé)人 (打印并簽名 )： 李艷 日期： 2022 年 8 月 11 日 賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）： 2022 高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 編 號 專 用 頁 賽區(qū) 評閱編號（由賽區(qū)組委會評閱前進行編號）： 賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）： 評 閱 人 評 分 備 注 全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）： 全國評閱編號（由全國組委會評閱前進行編號）： 公園內(nèi)道路設(shè)計問題 摘要 最短路問題是現(xiàn)實生活中常見的問題，在商業(yè)利潤估算、生產(chǎn)生活、運輸路線選擇等方面都有重要意義。 我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。 承 諾 書 我們仔細閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則 . 我們完全明白，在競賽開始后參賽隊員不能以