【正文】 任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。 我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的 , 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。 本文討論的是公園道路最優(yōu)設(shè)計(jì)問(wèn)題 :在滿足任意兩入口之間最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍的條件下，建立相應(yīng)最短道路模型，使得修建總道路長(zhǎng)度最短。 對(duì)于問(wèn)題一，首先：利用 倍的約束條件排除可利用邊界的入口點(diǎn)，選出需要通過(guò)交叉點(diǎn)設(shè)計(jì)路線的入口點(diǎn)。最后：運(yùn)用 MATLAB軟件編程，在滿足要求的情況下，得到最優(yōu)道路設(shè)計(jì)方案。 對(duì)于問(wèn)題二，首先：取問(wèn)題一中不可利用邊界的入口點(diǎn)，分析出滿足條件下的可行最短路線。最后：運(yùn)用費(fèi)馬點(diǎn)優(yōu)化可行最短路線，在滿足要求的情況下，得到最優(yōu)道路設(shè)計(jì)方案。 對(duì)于問(wèn)題三，首先：取問(wèn)題二的最優(yōu)道路設(shè)計(jì)方案，添加一矩形人工湖。然后：給出 2 個(gè)可行局部?jī)?yōu)化方案，對(duì)局部區(qū)域分別引入費(fèi)馬點(diǎn)，運(yùn)用 LINGO 和 MATLAB 分別求解費(fèi)馬點(diǎn)坐標(biāo)。對(duì)比 2 個(gè)方案，得到最優(yōu)的道路 設(shè)計(jì)方案。 關(guān)鍵詞： Kruskal 算法 最小生成樹(shù) 費(fèi)馬點(diǎn) MATLAB LINGO 一、問(wèn)題重述 、問(wèn)題背景 西安某大學(xué)計(jì)劃建一個(gè)形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美化校園環(huán)境，也是想為其學(xué)生提供更好的生活條件。 題目已知：矩形公園的長(zhǎng)為 200 米，寬為 100 米， 1 至 8 各入口的坐標(biāo)分別為： P1(20， 0) , P2(50，0) , P3(160， 0) , P4(200， 50) , P5(120， 100) , P6(35， 100) , P7(10， 100) , P8(0， 25)，見(jiàn)圖 1。 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2 P3P4P5P6P7P8 （圖 1） 、需要解決的問(wèn)題 問(wèn)題一：假定公園內(nèi)確定要使用 4 個(gè)道路交叉點(diǎn)為： a(50， 70) , b(40， 40) , c(120， 40) , d(115， 70) ，見(jiàn)圖 2（附錄一 .Fun2）。建立模型并給出算法，畫(huà)出道路設(shè)計(jì)，計(jì)算新修路的總工程。建立模型并給出算法，畫(huà)出道路設(shè)計(jì)和道路交叉點(diǎn)的坐標(biāo)，計(jì)算新修路的總工程。重復(fù)完成問(wèn)題二的任務(wù)。 二、問(wèn)題分析 、問(wèn)題一的分析 先計(jì)算出“ 8 個(gè)入口點(diǎn)兩兩之間的直線距離”，然后計(jì)算出“ 8 個(gè)入口點(diǎn)兩兩之間的邊界路徑距離”。 8 個(gè)入口點(diǎn)兩兩之間的直線距離≤ ” 不需要通過(guò)交叉點(diǎn)設(shè)計(jì)路線。 8 個(gè)入口點(diǎn)兩兩之間的直線距離 ” 需要通過(guò)交叉點(diǎn)設(shè)計(jì)路線。 、問(wèn)題二的分析 在本問(wèn)題中，設(shè)計(jì)原則：盡可能地利用好公園的邊界，不能利用邊界的再采取內(nèi)部新修路的方式。因此，將上述兩點(diǎn)之間用直線相連，得到圖像如下圖 所示。 最短路徑需滿足：入口點(diǎn)兩兩之間的最短路徑距 離247。 、問(wèn)題三的分析 本問(wèn)題中，設(shè)計(jì)原則：在問(wèn)題二設(shè)計(jì)的路線的基礎(chǔ)上，公園 內(nèi)部新加入一人工湖，見(jiàn)圖（附錄六 .Fun2），故對(duì)原設(shè)計(jì)的方案進(jìn)行局部?jī)?yōu)化。 故：我們只需修改 P5Q1 路線，對(duì) Q2 所在的區(qū)域路線進(jìn)行局部?jī)?yōu)化。 方案二：連接 P5R2，求 △ R2P4P3 的費(fèi)馬點(diǎn)，設(shè)計(jì)最短路徑。 方案四： 連接 P5R3，求 △ R3P4P3 的費(fèi)馬點(diǎn)，設(shè)計(jì)最短路徑。 故：可實(shí)行的方案只有方案一、二 . 三、模型假設(shè) 假設(shè)公園四周已修建好道路，且該道路不計(jì)如新修路總長(zhǎng)。 假設(shè)所有點(diǎn)之間修建道路均為直線；交叉點(diǎn)不影響道路的修建。 除題目要求外，道路規(guī)劃不考慮任何其他客觀因素。 S 新修路的總路程 L39。 根據(jù) Kruskal 算法，運(yùn)用 matlab 軟件編程。（附錄一 .Fun3） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1P2P3P4P5P6P7P8ab cd （圖 ） 針對(duì)“ P1— P P1— P P1— P P2— P P2— P P2— P P3— P P3— P P3— P P3— P7”需要通過(guò)交叉點(diǎn)設(shè)計(jì)路線，故在上述最小生成樹(shù)圖內(nèi)，求這些點(diǎn)間的最短路徑、最短路徑 長(zhǎng)度、最短路徑長(zhǎng)度 /兩點(diǎn)間直線距離。 故通過(guò)逐步分析比較發(fā)現(xiàn)，可以改變 a— d 這條路徑來(lái)調(diào)整路徑 P1P5 和 P2P5。（附錄一 .Fun4） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2P3P4P5P6P7P8ab cd （圖 ） 經(jīng)數(shù)據(jù)檢驗(yàn)： （任意）兩 點(diǎn)之間的 最短路徑 247。 費(fèi)馬點(diǎn)定義： (1)若三角形 ABC 的 3 個(gè)內(nèi)角均小于 120176。 ( 2)若三角形有一內(nèi)角不小于 120 度，則此鈍角的頂點(diǎn)就是 費(fèi)馬點(diǎn) 。 故：△ P2P6P5 和 △ P3P4P5 的費(fèi)馬點(diǎn) 1 ，即為其三個(gè)內(nèi)角角平分線交點(diǎn)。（ 附錄四 .Fun4） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100P1 P2 P3P4P5P6P7P8Q1Q2 （圖 ） 調(diào)整后的最終方案如下圖 所示。 3Q 非線性規(guī)劃模型： 2 2 2 2 2 23 3 3 3 3 3 3m in ( 2 0 0 ) ( 5 0 ) ( 1 6 0 ) ( 1 6 5 ) ( 7 0 )S x y x y x y? ? ? ? ? ? ? ? ? ? ? ts. 3333335 4 800 014 224 0 04 7 115 0 0xyxyxy? ? ????? ? ????? ? ??? 方案二： 在△ R2P4P3 中，設(shè)其費(fèi)馬點(diǎn)為 444( , )Q x y 。=D18+S1+D(P5→ R4)+S3 =++ + =(米 ) 方案二設(shè) 計(jì)圖： 見(jiàn)圖 （附錄六 .Fun4） 0 20 40 60 80 100 120 140 160 180 2000102030405060708090100R1R2 R3R4P1 P2P3P4P5P6P7P8Q1Q4 （圖 ） 新修路的總路程 L=D18+S1+D(P5→ R2)+S4 = +++ =（米） 方案結(jié)果分析 經(jīng)分析：方案一、方案二均滿足條件： ⑴ 入口點(diǎn)兩兩之間的最短路徑距離 247。 由于 L39。=D18+S1+D(P5→ R4)+S3 =++ + =(米 ) 六、模型評(píng)價(jià)與推廣 模型優(yōu)點(diǎn) 利用 Kruskal 算法建立最小生成樹(shù)模型，使模型簡(jiǎn)單便于求解。 引入了費(fèi)馬點(diǎn)，利用費(fèi)馬點(diǎn)對(duì)圖形進(jìn)行優(yōu)化，使模型求解更加簡(jiǎn)單。 模型缺點(diǎn) 僅討論了兩個(gè)道路交叉點(diǎn)的情況，沒(méi)有在結(jié)果上再進(jìn)行進(jìn)一步的討論。 模型推廣 本文主要討論的是公園內(nèi)部道路建設(shè)問(wèn)題，但我們使用的方法適用于大部分的最短路問(wèn)題，包括網(wǎng)絡(luò)的布局、城市道路及修建、公共場(chǎng)所的修建等問(wèn)題。 七、 參考文獻(xiàn) 【 1】 姜啟源，謝金星，葉俊 . 數(shù)學(xué)模型（第四版） 北京高等教育出版社 【 2】 趙靜，但琦 . 數(shù)學(xué)模型與數(shù)學(xué)實(shí)驗(yàn)（第三版） 北京高等教育出版社 【 3】 王文波 . 數(shù)學(xué)建模及基 礎(chǔ)知識(shí)詳解 武漢大學(xué)出版社 【 4】 趙繼俊 . 優(yōu)化技術(shù)與 Matlab 優(yōu)化工具箱 機(jī)械工業(yè)出版社 【 5】 韓中庚 . 數(shù)學(xué)建模方法及其應(yīng)用 高等教育出版社 【 6】 費(fèi)馬 . 費(fèi)馬點(diǎn)定義、判定 百度百科 八、附錄 附錄一 ： Fun1： plot(0:20:200,0:10:100,39。) x=[20 50 160 200 120 35 10 0]。 hold on plot(x,y,39。,39。,2) gtext(39。)。P239。 gtext(39。)。P439。 gtext(39。)。P639。 gtext(39。)。P839。 Fun2： plot(0:20:200,0:10:100,39。) x1=[20 50 160 200 120 35 10 0]。 x2=[50 40 120 115]。 hold on plot(x1,y1,39。,39。,2) plot(x2,y2,39。,39。,2) gtext(39。)。P239。 gtext(39。)。P439。 gtext(39。)。P639。 gtext(39。)。P839。 gtext(39。)。b39。 gtext(39。)。d39。 Fun3： plot(0:20:200,0:10:100,39。) x1=[20 50 160 200 120 35 10 0]。 x2=[50 40 120 115]。 hold on plot(x1,y1,39。,39。,2) plot(x2,y2,39。,39。,2) plot([x1(1)。y1(8)],39。) plot([x1(2)。y2(2)],39。) plot([x2(2)。y2(1)],39。) plot([x2(1)。y1(7)],39。) plot([x1(3)。y2(2)],39。) plot([x2(3)。y2(4)],39。) plot([x2(4)。y1(6)],39。) plot([x1(3)。y1(4)],39。) plot([x2(1)。y2(4)],39。) gtext(39。)。P239。 gtext(39。)。P439。 gtext(39。)。P639。 gtext(39。)。P839。 gtext(39。)。b39。 gtext(39。)。d39。 Fun4： plot(0:20:200,0:10:100,39。) x1=[20 50 160 200 120 35 10 0]。 x2=[50 40 120 115]。 hold on plot(x1,y1,39。,39。,2) plot(x2,y2,39。,39。,2) plot([x1(1)。y1(8)],39。) plot([x1(2)。y2(2)],39。) plot([x2(2)。y2(1)],39。) plot([x2(1)。y1(7)],39。) plot([x1(3)。y2(2)],39。) plot([x2(3)。y2(4)],39。) plot([x2(4)。y1(6)],39。) plot([x1(3)。y1(4)],39。) plot([x2(1)。y1(5)],39。) gtext(39。)。P239。 gtext(39。)。P439。 gtext(39。)。P639。 gtext(39。)。P839。 gtext(39。)。b39。 gtext(39。)。d39。 附錄二： Kruskal 算法 function E=Kruskal(w) %圖論最小生成樹(shù) Kruskal避圈算法 (使用時(shí)根據(jù)題目修改 w和 n) %w為鄰接矩陣 w=xlsread(39。) [m,n]=size(w)。 for i=1:n1 for j=i+1:n if w(i,j)~=0 x(1,k)=w(i,j)。%記錄起點(diǎn) x(3,k)=j。 end end end k=k1。x(1,i)=x(1,j)。 a=x(2,i)。x(2,j)=a。x(3,i)=x(3,j)。 end end end %給各點(diǎn)標(biāo)號(hào)賦初值 for i=1:n l(i)=i。 %E矩陣的第一行記錄最小生成樹(shù)的邊長(zhǎng) E(2,1)=x(2,1)。 %E矩陣的第三行記錄邊的終點(diǎn) a=min([l(E(2,1)),l(E(