城區(qū)公路選址問題

1、城區(qū)公路選址問題 摘 要 本文采用了兩種方法，一種是運用幾何解析法，建立模型，確定最優(yōu)點的軌跡，近而求得符合各要求的最優(yōu)方案，另一種是通過計算機編程，采用逐點遍歷的方法，求得滿足要求的各個最優(yōu)點。方法一：幾何解析法。 根據(jù)橢圓上各點與焦點的連線，路線長度相等和三角形性質(zhì)問題，建立了模型(一)、模型（二）、和模型（三）。根據(jù)模型（一）、模型（二）和模型（三）得到的結(jié)論可分別解決問題一，二，三，四，五的選址問題。問題一：在本問題中，我們首先利用模型（一）得到的結(jié)論一，可確定可能的最優(yōu)點分別為C1,C2(或C2)問題二：我們可以運用模型三以及問題一中所求出的各節(jié)點數(shù)據(jù)，可以將優(yōu)化的兩點坐標范圍進一步

2、縮小在圖形A-C1-B-C3之間，經(jīng)過對比，可得到可能為最優(yōu)的五個方案，再對這五個進行逐一求解，最終比較得出這五個方案中的最優(yōu)解。問題三：由模型一和問題一，可以判斷最優(yōu)點應該在線段C1-C2或C2-C3之間，分別設(shè)出兩段上點的坐標，找關(guān)系，列方程，運用編程分別求出兩段的最小值，再比較得出最優(yōu)方案的拐點的坐標。問題四：根據(jù)模型一的結(jié)論二和問題一、問題二和問題三的解答可以確定最優(yōu)坐標點應該為線段C1-C3之間的某點，于是可以得到最優(yōu)彎點橫縱坐標之間的關(guān)系，即X=Y，設(shè)出該點坐標，找關(guān)系，列方程，運用編程求出此段的最優(yōu)彎點。問題五：根據(jù)模型三可知最優(yōu)點坐標應處于直線A-B的右上側(cè)，且處于A-B的垂直

3、平分線上，即位于0-C上，設(shè)為Z（X。，X。)，因此可以算出各微小段對應的單位造價，再對線段A-Z-B進行積分，即可求得直線O-C上任意彎點所對應的路線總造價，再逐一比較，便可得到最優(yōu)方案的最優(yōu)點坐標。一 問題重述城區(qū)公路選址問題某區(qū)政府計劃在下列區(qū)域（見圖1）修建一條從A（0,9）到B（9,0）的直線型公路，由于涉及路面拆遷等因素，各地段建設(shè)費用有所不同，圖1中的數(shù)字代表該區(qū)域公路單位建設(shè)費用（單位：百萬元）。未標數(shù)字的任何地方單位建設(shè)費用均為1。圖1的每個網(wǎng)格長與寬都是1個單位。每個網(wǎng)格的邊界上建設(shè)費用按該地區(qū)最小單位費用計算。 請你按建設(shè)部門的如下具體要求，從建設(shè)費用最省的角度，給出最優(yōu)

4、的方案。（1）公路至多只能有1個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1所示的網(wǎng)格點上。（2）公路至多可以有2個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1所示的網(wǎng)格點上。（3）公路至多只能有1個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1所示的網(wǎng)格線上。（4）公路至多只能有1個轉(zhuǎn)彎點，轉(zhuǎn)彎點可以建在圖1所示區(qū)域的任何位置。（5）如果各區(qū)域的單位建設(shè)費用為（百萬元），公路至多只能有1個轉(zhuǎn)彎點，轉(zhuǎn)彎點可以建在圖1所示區(qū)域的任何位置。 二、符號說明1、該圖上的數(shù)字代表該地域上的單位造價2、模型一圖三中的各數(shù)字的意義：代表：橢圓 代表：橢圓 代表：橢圓代表：橢圓 代表：橢圓 代表：橢圓代表：橢圓3、模型一中的C1、C2、C2、C3、C4、C4

5、、C5、C6、C6、C7分別代表橢圓 橢圓 橢圓 橢圓 橢圓 橢圓 橢圓4、符號M表示，各路線的總造價。三、問題分析1、處理不同路段，單位造價不同的最優(yōu)選址問時，我們想到要分兩步走，第一步分析“路線總長相等的不同路徑方案”選出相等路線總長中的最優(yōu)方案，第二步分析“不同路線總長中的最優(yōu)方案”，選出不同路線總長中的最優(yōu)方案。當?shù)谝徊脚c第二步都分析完全，便得出“不同路徑方案，不同路線總長”中的最優(yōu)方案。處理步驟一時，我們可以采用橢圓來解決問題，因為橢圓上各點與焦點連線的路線總長相等，正好滿足路線總長相等的條件。利用橢圓分析出每個橢圓上的最優(yōu)點后，再進行逐個比較，便可得出最優(yōu)彎點坐標。（如模型一和模型

6、三）2、若已確定某最優(yōu)點位于等腰三角形的頂點上（此點為給定圖形中對角線O-C上網(wǎng)格點中的某點），可采用削頂?shù)姆绞?，減短路線總長，降低路線總造價。四、模型建立與求解模型建立模型一：圖一由于OAB區(qū)域內(nèi)關(guān)于AB對稱的路段造價均大于或等于CAB中相應路段的造價，故可排除在OAB區(qū)域中修路，只考慮在ABC區(qū)域中的情況。如圖M7-C7-C7-N7是以A,B為角點，AC7+BC7為路線總長所畫的橢圓，C7為C7在橢圓軌跡上向左移動微小距離時所在的位置，很容易發(fā)現(xiàn)，AC7+C7B=AC7+C7B,但是A-C7-B只經(jīng)過單位造價為1的區(qū)域，而A-C7-B既經(jīng)過單位造價為1的區(qū)域，又經(jīng)過單位區(qū)域造價為1.1的區(qū)

7、域，故比較這兩個路線，A-C7-B為此橢圓上的最優(yōu)路線。數(shù)學表達式比較： M(A-C7-B）=LAC7*1+LBC7*1=(LAC7+LBC7)*1 M(A-C7-B)=(lAC7+lC7E+lFB)*1+lEF*1.1>(LAC7+lC7E+lFB)*1+lEF*1=lEF*1=M(A-C7-B)設(shè)A-C7-B經(jīng)過單位造價為1,1.1,1.2,1.3,1.4各區(qū)域的線長分別為l1，l1.1，l1.2，l1.3，l1.4，則M(A-C7-B)=1*l1+1.1*l1.1+1.2*l1.2+1.3*l1.3+1.4*l1.4>(l1+l1.1+l1.2+l1.3+l1.4)*1=M（

8、A-C7-B）所以A-C7-B為橢圓M7-C7-N7上的最優(yōu)路線。圖二A-C6-C6-B是以A,B為兩個焦點，AC6+C6B為路線總長所畫的橢圓，設(shè)A-C6-B經(jīng)過單位造價為1和1.1區(qū)域的路長分別為l1，l1.1，則A-C6-B路線總造價為M（A-C6-B）=l1*1+l1.1*1.1；C6是C6沿橢圓逆時針轉(zhuǎn)過微小弧長時的位置，設(shè)A-C6-B路線經(jīng)過單位造價為1和1.1區(qū)域的路長分別為L1，L1.1，則A-C6-B路線總造價：M(A-C6-B)=L1*1+L1.1*1.1由圖易知l1.1<L1.1令L1.1=l1.1+a,則M(A-C6-B)=(l1-a)*1+（l1.1+a）*1.

9、1=l1*1+l1.1*1.1+0.1a>M(A-C6-B)根據(jù)對稱性，故C6，C6為橢圓A-C6-C6-B上網(wǎng)格點中最優(yōu)點圖三.綜合對比分析圖三可得：結(jié)論一：C1為橢圓A-C1-B上最優(yōu)的網(wǎng)格點 C2，C2為橢圓A-C2-C2-B上最優(yōu)網(wǎng)格點 C3為橢圓A-C3-B上最優(yōu)網(wǎng)格點 C4，C4為橢圓A-C4-C4-B上最優(yōu)網(wǎng)格點 C5為橢圓A-C5-B上最優(yōu)網(wǎng)格點 C6，C6為橢圓A-C6-C6-B上最優(yōu)網(wǎng)格點 C7為橢圓A-C7-B上最優(yōu)網(wǎng)格點結(jié)論二：以AB為焦點的所有橢圓，它們與AB的中垂線OC相交的點分別為該橢圓上的最優(yōu)點。 模型二：其中m1,m2,m3分別代表所在區(qū)域的單位造價，且

10、m3>m2>m1；當直線EF較C點下降一個微小距離，則可以減小一定的路線總長，因為CE+CF>EF，故路線A-E-F-B比路線A-C-B總長要短，雖然下降一點高度所經(jīng)過的部分區(qū)域單位造價會有所增高，但路程卻可以減少很多，因此總造價會有所降低，當達到下降到一定高度時，繼續(xù)往下降會則會出現(xiàn)總造價升高，則此時的點為最優(yōu)點。由于題目中涉及到的所有點都是處于一定范圍內(nèi)的網(wǎng)格點，為有限點，故不需要在此證明何時為最優(yōu)點。模型三：圓、之間的半徑差為dr,當dr足夠小時，我們就可以將區(qū)域中的單位造價視為均勻的，假設(shè)區(qū)域、及圓以外的區(qū)域所對應的單位造價分別為m1,m2,m3，且m1>m2&

11、gt;m3，J為J沿橢圓逆時針轉(zhuǎn)過某一微小弧度所對應位置，C,D分別是J-B與圓相交的兩個點，分別計算路線A-J-B與路線A-J-B所對應的總造價：M（A-J-B）= (AJ+JB)* m3M（A-J-B）=(AJ+JC+DB)*m3+CD*m2>( AJ+JC+DB+CD)* m3=(AJ+JB)* m3= M（A-J-B）經(jīng)比較可知路線A-J-B比路線A-J-B更經(jīng)濟，暫且得出A-J-B為當前最優(yōu)路線。 J為J沿橢圓逆時針轉(zhuǎn)過某一微小弧度所對應位置，同理可證路線A-J-B比路線A-J-B更經(jīng)濟以此類推，可以比較出該橢圓上最優(yōu)點的坐標應該是J求解：問題一：根據(jù)模型一中的結(jié)論一，分別計算

12、各橢圓最優(yōu)彎點處的路徑總造價：M的單位為百萬元：A-B:M(A-B)=(1+1.1+1.2+1.3+1.4+1.3+1.2+1.1+1)*sqrt 2=14.99066A-C1-B:M(A-C1-B):2*sqrt(5*5+4*4)*(1+1.1+1.2+1.3)/4=14.73719A-C2-B:M(A-C2-B)= sqrt (5*5+3*3)*(1+1.1+1.2)/3+ sqrt (4*4+6*6)*（1+1.1+1.2+1.3）/4=14.70682A-C3-B:M(A-C3-B)=2*sqrt（6*6+3*3）*(1+1.1+1.2)/3=14.75805A-C4-B:M(A-C4

13、-B)= sqrt （6*6+2*2）*（1+1.1）/2+ sqrt （3*3+7*7）*（1.2+1.1+1）/3=15.01813A-C5-B:M(A-C5-B)=2* sqrt （7*7+2*2）*(1+1.1)/2=15.28823A-C6-B：M(A-C6-B)= sqrt （7*7+1*1）*1+ sqrt （8*8+2*2）*(1+1.1)/2=15.72959A-C7-B:2* sqrt （8*8+1）*1=16.12452經(jīng)過上面數(shù)字的比較可知，A-C2-B為最優(yōu)路線即該問中最優(yōu)網(wǎng)格為C2(5,6)或C2(6,5)問題二：根據(jù)問題（1）中所求出的各路線價格趨勢可確定最優(yōu)單個

14、最優(yōu)拐點應該在線段C1-C3上某點，根據(jù)模型三可對A-C3-B進行優(yōu)化，在C1-C3之間作一條平行于AB的直線EF,可得分別于AC3和C3B的交點EF，由于三角形具有任意兩邊之和大于第三邊的性質(zhì)，所以對于EFC3來說，EC3+C3F>EF,即LA-E-F-B<LA-C3-B,所以我們適當?shù)?減短路線總長來降低總造價。第一步找出A-C3-B-C1區(qū)域中滿足題目要求的所有可能為最優(yōu)路徑的兩彎點坐標，分別為：C3-C3:(5,6)-（6,5）D-D:（4,7）-（7,4）I-I:(4,6)-（6,4）H-H:(3,7)-(7,3)G-G: (2,8)-(8,2)第二步，計算各路線對應的費

15、用：M(A-C2-C2-B)=2* sqrt （3*3+5*5）*(1+1.1+1.2)/3+ sqrt 2*1.3=14.66657M(A-D-D-B)=2* sqrt （2*2+4*4）*(1+1.1)/2+1.2*2 sqrt 2+1.3* sqrt 2=14.62408M(A-I-I-B)=2* sqrt （3*3+4*4）*（1+1.1+1.2）/3+2* sqrt 2*1.3=14.67696M(A-H-H-B)=2* sqrt （2*2+3*3）*(1+1.1)/2+2* sqrt 2*1.3+2* sqrt 2*1.2=14.64273M(A-G-G-B)=2* sqrt （1

16、*1+2*2）*1+2* sqrt 2*1.3+2* sqrt 2*1.2+2* sqrt 2*1.1=14.65447經(jīng)比較M(A-D-D-B)為最小值故A-D-D-B為最優(yōu)路徑即本小問最優(yōu)的兩個轉(zhuǎn)彎點為D(4,7)和D（7,4）問題三：由模型一和第（1）題中的解答結(jié)果，可以判斷出最優(yōu)單個轉(zhuǎn)彎點應該在線段C1-C3上，由模型一中的圖形三可判斷網(wǎng)格線上最優(yōu)點坐標應該處于C1-C2或C2-C3上。 若在線段C1-C2上，可設(shè)所求點坐標為（5,6-y）,y0,1,則：M（y）=sqrt (3+y)*(3+y)+5*5*y*1.3/(3+y)+3*(1+1.1+1.2)/3/(3+y)+ sqrt

17、4*4+(6-y)*(6-y)*(1.3+1.2+1.1+1)/4M(y)= sqrt (3+y)*（3+y）+5*5*(1.3y+3.3)/(3+y)+ sqrt 4*4+(6-y)*(6-y)*1.15,y0,1編程：y:01,step:0.001 輸出Min（My）及對應的坐標（5,6-y） 若在線段C2-C3上，可設(shè)所求點坐標為（6-x，6），x0,1,則：M(X)= sqrt 3*3+(6-x)*（6-x）*(1+1.1+1.2)/3+ sqrt （3+x）*（3+x+6*6x*1.3/(3+x)+3*(1.2+1.1+1)/3/(3+x)M(X)=sqrt3*3+(6-x)*（6-

18、x）*1.1+sqrt(x+3)*（x+3）+6*6(1.3x+3.3)/(3+x)編程：x：01，step：0.001，輸出Min（Mx）及對應的坐標（6-x，6） 比較Min(My)和Min（Mx）最優(yōu)彎點(a,b)根據(jù)對稱性,(b,a)同為最優(yōu)彎點。程序截圖結(jié)果：故最優(yōu)點坐標為（5，5.829）或（5.829，5）問題四根據(jù)模型一中結(jié)論二和題（1）中各彎點時所需的費用，可判斷，最優(yōu)點位于線段C1-C3上，故可設(shè)所求點為：（6-x。，6-x。），則x。0,1M(x。)=2*sqrt(3+x。)*（3+x。）+（6-x。）*（6-x。）*（x。*1.3）/(3+x。)+3*（1+1.1+1.

19、2）/(3+x。)/3=2*sqrt（2x。2-6x。+45）*（1.3x。+3.3）/(3+x。),x。0,1編程序：x。：01，step：0.001輸出最小值Min（Mx。）及對應的坐標（6-x。，6-x。）即最優(yōu)彎點為(6-x。，6-x。)程序截圖結(jié)果：即本問最優(yōu)點為：（5.3099，5.3099）問題五：根據(jù)模型可知：最優(yōu)方案的轉(zhuǎn)彎點在線段AB的中垂線上，即在直線y=x上于是可以設(shè)轉(zhuǎn)彎點坐標為：(a，a）因為路徑的總費用=（權(quán)值*對應路段長）可列出轉(zhuǎn)彎點為（a，a）時路徑的總費用方程為：M（a）=2*0ª(1.5-(0.1*sqrt(x-4)*(x-4)+(a-9)*x/a+

20、5)*(a-9)*x/a+5)*sqrt(1+(a-9)/a)*(a-9)/a)dx而在編程中的思想是x取0.001為單位x從0到9劃分成一個個的距型區(qū)域即用積分的定義性質(zhì)從而達到積分的目的。完成對函數(shù)的積分求得題目結(jié)果。而在求最優(yōu)方案時由于要取任意點，所以程序中用窮舉的方法從a從0到9以0.01為單位逐個取點，并將計算結(jié)果記錄下來比較，從而求得最優(yōu)路徑即最優(yōu)方案。程序截圖結(jié)果：即本問的最優(yōu)點坐標為(5.3089,5.3089)五、方案一的改進與驗證上述建立的三個模型，是通過對路線上一些特殊點進行分析比較得出一般性結(jié)論，選用圖形中已有的交點坐標來驗證結(jié)論的正確性。在建模的同時存在一定的粗糙性，

21、在處理模型一的時候，我們可以采用關(guān)于k的表達式來表示某一橢圓上的任意一點Z分別與焦點A,B連線的斜率，用關(guān)于k的表達式分別表示直線AZ,直線ZB的方程，再求出這兩條直線與網(wǎng)格線的諸多交點，即可求出不同價格區(qū)域上對應的長度，也是關(guān)于k的一個表達式，將每段結(jié)果進行疊加，即得路線A-Z-B的費用M（k），其結(jié)果仍可表示為一個關(guān)于k的表達式，如果k表示的是直線AZ的斜率，則k的變化范圍為-10，因為根據(jù)對稱性可知Z點始終處于直線AB右上部分。故可運用計算機編程，將取得最小費用，即取得min(Mk)時對應的k值求出來。具體編程略方案二：C+程序的實現(xiàn)：1.程序中定義的部分函數(shù)有：void showX(d

22、ouble x1);/顯示直線L1與L2與x=1,x=2,x=3.的交點坐標(用于函數(shù)的檢驗)void showY(double y1);/顯示直線L1與L2與y=1,y=2,y=3.的交點坐標(用于函數(shù)的檢驗)double returnValue(double x1,double y1,double x2,double y2);/返回權(quán)值double returnDistance(double x1,double y1,double x2,double y2);/返回兩點距離double sum(double a,double b);/一個轉(zhuǎn)彎點時的計算路徑總費用double sum(double a,double b,double c,double d);/兩個轉(zhuǎn)彎點時的計算路徑總費用void sequence(double x2,double y2,int count);/對數(shù)組x2和數(shù)組y2進行排序即對坐標（x2,y2）排序double storage(double arrayX,double arrayY);/一個轉(zhuǎn)彎點時的對arrayX與arrayY數(shù)組進行存儲分別對應實現(xiàn)后面的功能。2.本程序的實現(xiàn)思想：總體思路：根據(jù)題目求解過程中對坐標點上各個符合要求的點進行逐個檢索，