城區(qū)公路選址問(wèn)題.doc

1、城區(qū)公路選址問(wèn)題_學(xué)院 第三屆大學(xué)生數(shù)學(xué)建模競(jìng)賽 （201_年5月17日14時(shí)5月23日14時(shí)） 參賽題目 A B （在所選題目上打勾） 參賽隊(duì)員1 參賽隊(duì)員2 參賽隊(duì)員3 姓名 學(xué)號(hào) 學(xué)院 一卡通號(hào) 手機(jī) Email 教學(xué)部 _第三屆大學(xué)生數(shù)學(xué)建模競(jìng)賽 承 諾 書(shū) 我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話(huà)、電子郵件、網(wǎng)上咨詢(xún)等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。 我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的【參考文獻(xiàn)】：p 的表述方

2、式在正文引用處和【參考文獻(xiàn)】：p 中明確列出。 我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。 我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫(xiě)）： A 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話(huà)）： 參賽隊(duì)員 (打印并簽名_) ：1.2.3.指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名_)： 日期： 201_ 年 05 月 23 日 賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）： _大學(xué)_學(xué)院第三屆大學(xué)生數(shù)學(xué)建模競(jìng)賽 編 號(hào) 專(zhuān) 用 頁(yè) 評(píng)閱編號(hào)（由組委會(huì)評(píng)閱前進(jìn)行編號(hào)）： 評(píng)閱記錄（可供評(píng)閱時(shí)使用）： 評(píng) 閱 人 評(píng) 分 備 注 城區(qū)公

3、路選址問(wèn)題 摘 要 根據(jù)AB之間地的不同區(qū)域不同造價(jià)的特點(diǎn)，本文采用了兩種方法，一種是將連續(xù)問(wèn)題離散化利用窮舉法取最優(yōu)的方法。另一種是在窮舉法的所求結(jié)果的基礎(chǔ)上利用極限定義無(wú)限逼近的思想縮小最優(yōu)轉(zhuǎn)彎點(diǎn)的存在的可能區(qū)域，進(jìn)而再利用非線性規(guī)劃從而得出最優(yōu)解。 問(wèn)題一：用窮舉法建立了一個(gè)模型，所得最優(yōu)轉(zhuǎn)彎點(diǎn)為（5,6）、（6，5）（最小花費(fèi)為14.7068百萬(wàn)元）。 問(wèn)題二：通過(guò)在問(wèn)題一的基礎(chǔ)分析p ，再次利用窮舉法建立了模型逐步計(jì)算關(guān)于CD對(duì)稱(chēng)的兩個(gè)轉(zhuǎn)彎網(wǎng)格點(diǎn)的建設(shè)費(fèi)用，通過(guò)比較得出（4，7），（7，4）兩點(diǎn)，為所最小建設(shè)費(fèi)用的轉(zhuǎn)彎點(diǎn)。最小費(fèi)用為14.624百萬(wàn)元。 問(wèn)題三：本問(wèn)題要求鋪設(shè)線路落在

4、網(wǎng)格線上，利用Matlab求出 f(_) 在各個(gè)網(wǎng)絡(luò)線的最小值，再通過(guò)比較，找出最優(yōu)轉(zhuǎn)彎點(diǎn)（4.5719，6）、（6,4.5719），最小費(fèi)用為14.6989百萬(wàn)元。 問(wèn)題四：同問(wèn)題三模型思想方法，得出關(guān)于建設(shè)總費(fèi)用的目標(biāo)函數(shù)二元方程f(_，y)，再利用Matlab求出 目標(biāo)函數(shù)在可能區(qū)域的最小值，得到最優(yōu)轉(zhuǎn)彎點(diǎn)，最小費(fèi)用為14.6989百萬(wàn)元。 問(wèn)題五：將路線分成無(wú)數(shù)小段，利用積分的思想模型，求出建設(shè)費(fèi)用。 【關(guān)鍵詞】：p ： 窮舉法 無(wú)限逼近 非線性規(guī)劃 一 問(wèn) 題 重 述 城區(qū)公路選址問(wèn)題 某區(qū)政府計(jì)劃在下列區(qū)域（見(jiàn)圖1）修建一條從A（0,9）到B（9,0）的直線型公路，由于涉及路面拆遷

5、等因素，各地段建設(shè)費(fèi)用有所不同，圖1中的數(shù)字代表該區(qū)域公路單位建設(shè)費(fèi)用（單位：百萬(wàn)元）。未標(biāo)數(shù)字的任何地方單位建設(shè)費(fèi)用均為1。圖1的每個(gè)網(wǎng)格長(zhǎng)與寬都是1個(gè)單位。每個(gè)網(wǎng)格的邊界上建設(shè)費(fèi)用按該地區(qū)最小單位費(fèi)用計(jì)算。 請(qǐng)你按建設(shè)部門(mén)的如下具體要求，從建設(shè)費(fèi)用最省的角度，給出最優(yōu)的方案。 （1）公路至多只能有1個(gè)轉(zhuǎn)彎點(diǎn)，且轉(zhuǎn)彎點(diǎn)只能建在圖1所示的網(wǎng)格點(diǎn)上。 （2）公路至多可以有2個(gè)轉(zhuǎn)彎點(diǎn)，且轉(zhuǎn)彎點(diǎn)只能建在圖1所示的網(wǎng)格點(diǎn)上。 （3）公路至多只能有1個(gè)轉(zhuǎn)彎點(diǎn)，且轉(zhuǎn)彎點(diǎn)只能建在圖1所示的網(wǎng)格線上。 （4）公路至多只能有1個(gè)轉(zhuǎn)彎點(diǎn)，轉(zhuǎn)彎點(diǎn)可以建在圖1所示區(qū)域的任何位置。 （5）如果各區(qū)域的單位建設(shè)費(fèi)用為（百

6、萬(wàn)元），公路至多只能有1個(gè)轉(zhuǎn)彎點(diǎn)，轉(zhuǎn)彎點(diǎn)可以建在圖1所示區(qū)域的任何位置。 二 問(wèn)題分析p 本問(wèn)題主圍繞由A點(diǎn)到B點(diǎn)公路選址展開(kāi)，要求建設(shè)費(fèi)用最少。根據(jù)各個(gè)區(qū)域的費(fèi)用不同，確定轉(zhuǎn)彎點(diǎn)的位置。我們采用了兩種方法求得最少的花費(fèi)，分別為非線性規(guī)劃模型和逐點(diǎn)遍歷模型。 問(wèn)題一 我們利用窮舉法建立模型一，用來(lái)確保結(jié)果是最小值，根據(jù)圖像的對(duì)稱(chēng)性以及單位區(qū)域建設(shè)費(fèi)用的分布規(guī)律 ，著重對(duì)AB上方區(qū)域點(diǎn)采用枚舉分析p 計(jì)算，得出結(jié)果。 問(wèn)題二 本問(wèn)題與問(wèn)題一相比,增加一個(gè)轉(zhuǎn)彎點(diǎn)，通過(guò)對(duì)問(wèn)題的分析p 可以得到符合條件的兩個(gè)轉(zhuǎn)彎點(diǎn)，應(yīng)該對(duì)稱(chēng)的分布在直線y=_的兩側(cè)。我們?cè)趩?wèn)題一所建立的兩種模型的基礎(chǔ)上均增加相應(yīng)約束條

7、件，通過(guò)對(duì)比分析p 得出最少花費(fèi)的鋪設(shè)線路（即兩個(gè)轉(zhuǎn)彎點(diǎn)的位置）。 問(wèn)題三 本問(wèn)題要求鋪設(shè)線路落在網(wǎng)格線上，在問(wèn)題1、2的基礎(chǔ)上通過(guò)分析p 歸納縮小符合該條件的網(wǎng)絡(luò)線的分布位置。利用非線性規(guī)劃求解，建立模型二，可以得出一個(gè)關(guān)于建設(shè)總費(fèi)用的目標(biāo)函數(shù)f(_)，而且可知f(_)在整個(gè)區(qū)域連續(xù)且可微，利用Matlab求出 f(_)符合在某一點(diǎn)有局部極小點(diǎn)的條件，再通過(guò)比較符合條件的各個(gè)網(wǎng)絡(luò)線的最小值，找出最優(yōu)解。 問(wèn)題四 類(lèi)似于問(wèn)題三的分析p 方法，找出符合條件的最小區(qū)域。利用非線性規(guī)劃求解，可以得出一個(gè)關(guān)于建設(shè)總費(fèi)用的目標(biāo)函數(shù)f(_,y)，而且可知f(_，y)在整個(gè)區(qū)域連續(xù)且可微，利用Matlab求

8、出 f(_，y)，找出最優(yōu)解。 問(wèn)題五 將路線分成無(wú)數(shù)小段，利用積分的思想模型，求出建設(shè)費(fèi)用 三.符號(hào)說(shuō)明 ， 為建設(shè)總費(fèi)用 _ 為選取轉(zhuǎn)彎點(diǎn)的橫坐標(biāo) y 為選取轉(zhuǎn)彎點(diǎn)的縱坐標(biāo) 為選取轉(zhuǎn)彎點(diǎn)和A點(diǎn)連線與直線y=9的夾角 為選取轉(zhuǎn)彎點(diǎn)和B點(diǎn)連線與直線_=9的夾角 d1 為選取點(diǎn)轉(zhuǎn)彎點(diǎn)與A點(diǎn)之間的距離 d2 為選取點(diǎn)轉(zhuǎn)彎點(diǎn)與B點(diǎn)之間的距離 五.模型建立與求解 D A 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.2 1.2 1.2 1.2 1.2 1.2 1.1 1.1 1.2 C 1.3 1.3 1.3 1.3 1.2 1.1 1.1 1.2 1.3 1.4 1.4

9、 1.3 1.2 1.1 1.1 1.2 1.3 1.4 1.4 1.3 1.2 1.1 1.1 1.2 1.3 1.3 1.3 1.3 1.2 1.1 1.1 1.2 1.2 1.2 1.2 1.2 1.2 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 1.1 B 問(wèn)題一: 通過(guò)觀察圖形分析p 得到圖形關(guān)于直線AB對(duì)稱(chēng)，但由于下側(cè)單位區(qū)域建設(shè)費(fèi)用相對(duì)較大，故而最優(yōu)轉(zhuǎn)彎點(diǎn)必然在AB上側(cè)。AB上側(cè)又關(guān)于直線CD對(duì)稱(chēng)，故而只要分析p CD上方區(qū)域即可。 依次將該區(qū)域各個(gè)點(diǎn)求解建設(shè)費(fèi)用，通過(guò)比較得出（5，6）為網(wǎng)格點(diǎn)上最優(yōu)的轉(zhuǎn)彎點(diǎn)，最小費(fèi)用為14.7068百萬(wàn)元。再有對(duì)稱(chēng)性可得（6

10、，5）也為網(wǎng)格點(diǎn)上最優(yōu)的轉(zhuǎn)彎點(diǎn)，最小費(fèi)用為14.7068百萬(wàn)元。 問(wèn)題二: 通過(guò)在問(wèn)題一的基礎(chǔ)分析p 可知，所選的兩個(gè)最優(yōu)轉(zhuǎn)彎點(diǎn)必然關(guān)于直線CD對(duì)稱(chēng)。逐步計(jì)算對(duì)稱(chēng)的兩個(gè)轉(zhuǎn)彎網(wǎng)格點(diǎn)的建設(shè)費(fèi)用，通過(guò)比較得出 （4，7），（7，4）兩點(diǎn)，為所最小建設(shè)費(fèi)用的轉(zhuǎn)彎點(diǎn)。最小費(fèi)用為14.624百萬(wàn) 元。 問(wèn)題三: 通過(guò)問(wèn)題一二的求解，利用無(wú)限逼近思想可以知道最優(yōu)轉(zhuǎn)彎點(diǎn)網(wǎng)格線必然在問(wèn)題一所求到的轉(zhuǎn)彎點(diǎn)的附近，利用Matlab軟件求解附近的各個(gè)網(wǎng)格線上的建設(shè)費(fèi)用最小的點(diǎn)。 1.左邊網(wǎng)格線 （4> fy=inline(1.1_sqrt(_2+9)+sqrt(9-_)2+36)/(9-_)_(11.1-1.3

11、_); >> _min,fmim=fminbnd(fy,4,5) _min = 4.5719 fmim = 14.6989 右邊的網(wǎng)格線最優(yōu)造價(jià)函數(shù)求解代碼： fy=inline(1.1_sqrt(_2+9)+sqrt(36+(9-_)2)_(11.1-1.3_)/(9-_); >> _min,fmim=fminbnd(fy,5,6) _min = 5.0001 fmim = 14.7068 上邊的網(wǎng)格線最優(yōu)造價(jià)函數(shù)求解代碼： >> fy=inline(10.5-1.2_y)_sqrt(9-y)2+25)/(9-y)+(1.05+0.6/y)_sqrt(y2

12、+16); >> ymin,fmim=fminbnd(fy,6,7) ymin = 6.0001 fmim = 14.7068 下邊的網(wǎng)格線最優(yōu)造價(jià)函數(shù)求解代碼： >> fy=inline(1.15_sqrt(y2+16)+sqrt(25+(9-y)2)_(11.1-1.3_y)/(9-y); >> ymin,fmim=fminbnd(fy,5,6) ymin = 5.8286 fmim = 14.7066 附件二： 問(wèn)題四的Matlab語(yǔ)言代碼： 符合最優(yōu)轉(zhuǎn)彎點(diǎn)區(qū)域最優(yōu)造價(jià)函數(shù)求解代碼： >> syms _ y; z=(11.1-1.3y)_s

13、qrt(_2+y2)/(9-y)+(11.1-1.3_)_sqrt(9-_)2+y2)/(9 -_); >> diff(z,_) ans = (13_(_ - 9)2 + y2)(1/2)/(10_(_ - 9) - (13_)/10 - 111/10)_(_ - 9)2 + y2)(1/2)/(_ - 9)2 + (_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) + (2_ - 18)_(13_)/10 - 111/10)/(2_(_ - 9)2 + y2)(1/2)_(_ - 9) >> diff(z,y) ans = (13

14、_(_2 + y2)(1/2)/(10_(y - 9) - (_2 + y2)(1/2)_(13_y)/10 - 111/10)/(y - 9)2 + (y_(13_)/10 - 111/10)/(_ - 9)2 + y2)(1/2)_(_ - 9) + (y_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) >> _,y=solve(13_(_ - 9)2 + y2)(1/2)/(10_(_ - 9) - (13_)/10 - 111/10)_(_ - 9)2 + y2)(1/2)/(_ - 9)2 + (_(13_y)/10 - 111/10)/(_2 + y2)(1/2)_(y - 9) + (2_ - 18)_(13_)/10 - 111/10)/(2_(_ - 9)2 + y2)(1/2)_(_ - 9)=