其他數(shù)模-與一等

承諾仔細(xì)閱讀了第三屆“ScienceWord杯”數(shù)學(xué)中國數(shù)學(xué)建模網(wǎng)絡(luò)賽的競賽 知道，別人的成果是競賽規(guī)則的,如果別人的成果或其他公開的資料（包括網(wǎng)上查到的資料，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文處和參則的行為，受到嚴(yán)肅處理。允許數(shù)學(xué)中站( 站以非商業(yè)目的的交流不需要提前取得的同意。參賽隊(duì)員(簽名)：1：王光2：隊(duì)員 宋雷參賽隊(duì)員(簽名)： 頁參賽隊(duì)伍的參賽號碼：（請各個(gè)參賽隊(duì)提前填寫好1130競賽（由競賽送至評委團(tuán)前競賽評閱（由競賽評委團(tuán)評閱前進(jìn) 數(shù)學(xué)建模網(wǎng)絡(luò)賽 Braess悖論路段重要度層次分析法博弈論蟻群優(yōu)化蟻群優(yōu)化模型，研究交通擁堵是否源于Braess悖論。分析法算出路徑的組合重要度，得出Braess悖論對城市交通影響非常重要。 使用GPS導(dǎo)航系統(tǒng)并不能緩解交通擁堵，得出Braess悖論在復(fù)雜的道路中存在性。參 （由填寫參 （由填寫所選題目B題重道路交通系統(tǒng)是一個(gè)很復(fù)雜的系統(tǒng)，它不僅表現(xiàn)在有交通線路、工具、客貨流例如交通線機(jī)動(dòng)車流數(shù)量、車速、行人群體數(shù)以及車輛與人群的行駛方向等都是隨交通系統(tǒng)是一個(gè)一有限空間系統(tǒng)，在車輛與人群的增加方面要受到系統(tǒng)空間的影在變，會，系出統(tǒng)的。然而在第二種方法中遇到了一個(gè)違背理論的情況，即在某個(gè)交通區(qū)域增加了一條線1968年意大利數(shù)學(xué)家DietrichBraess發(fā)現(xiàn)交通網(wǎng)絡(luò)中的Braess悖論。本題通過分析實(shí)際城市的道路交通情況，找出引起B(yǎng)raess悖論的因素，在網(wǎng)GPS導(dǎo)航系統(tǒng)，分析是否會緩解交通堵塞，并估計(jì)其效果。題分本題涉及到交通系統(tǒng)和交通網(wǎng)絡(luò)中的Braess悖論，沒有給出固定的數(shù)據(jù)和交通影圖一為分別在于2010年4月24日下午7點(diǎn)42分、8點(diǎn)07分、8點(diǎn)32分、點(diǎn)45分四個(gè)不同時(shí)刻的東四十橋道路交通路況截圖（圖像來源【1其中紅色代表擁擠，①7點(diǎn)42 ②8點(diǎn)07③8點(diǎn)32 ④9點(diǎn)45型假號說符說IE(i,E(x,j)G1、CQk(I Iih節(jié)點(diǎn)i與j節(jié)點(diǎn)i所屬區(qū)域節(jié)點(diǎn)的重要度節(jié)點(diǎn)j所屬區(qū)域節(jié)點(diǎn)的重要度節(jié)點(diǎn)ij之間路段的路程，km節(jié)點(diǎn)i的人口密度，人/平方公里節(jié)點(diǎn)i的總產(chǎn)值，萬元n個(gè)城市的坐標(biāo)n2一次循環(huán)中第k只螞蟻在IP的第ji型準(zhǔn)燈的城市快速環(huán)路。二環(huán)路處于道路路網(wǎng)的位置，圍繞舊城而建，全長32.7京的一題。 公里）數(shù)據(jù)，（數(shù)據(jù)來源：【2】）運(yùn)用做出圖二4x朝陽區(qū)崇文區(qū)朝陽區(qū)崇文區(qū)西城區(qū)東城區(qū)宣武區(qū)21 六模型的建立與模型一的交通性能，然后將某一線路，再檢驗(yàn)新的系統(tǒng)的性能，以此兩個(gè)結(jié)果檢驗(yàn)市二并且根據(jù)路線的選擇計(jì)算S經(jīng)過系統(tǒng)A花費(fèi)的時(shí)間。首先，把交通系統(tǒng)抽象成由若干點(diǎn)組成的網(wǎng)絡(luò)圖，圖的節(jié)點(diǎn)為交通系統(tǒng)中的部分路口，圖的邊為直接或者間接連接所選的路口的路段。根據(jù)節(jié)點(diǎn)所處城市區(qū)域，節(jié)點(diǎn)周圍居民居住密度，居民出行目的地，以及選擇道路的方向，還要節(jié)點(diǎn)附近的旅游場所或者其它活動(dòng)場所，通過了解這些場所的收入來判斷此節(jié)點(diǎn)所在路段I

Pi

1 2

IiIj

有較多的流動(dòng)，連接節(jié)點(diǎn)的路段車流量就會相對的大，對于交通系統(tǒng)，此路段將會是在選擇不同的節(jié)點(diǎn)。所以在做路段的重要度比較時(shí)，將連接同一節(jié)點(diǎn)的路段重要度求和并作平均化，這樣將路段重要度歸結(jié)到路段連接的節(jié)點(diǎn)上。選擇系統(tǒng)邊緣S模型建SS p1n p 1 pij代表同一層的不同因子對上層因子影響程度之比。通常由于成對比較具有性9以及1/2、…1/9，不同數(shù)值代表的意義如表一：比較尺度1PiPj的影響相5PiPj9PiPj的影響絕對PiPj影響之比處在以上之（一）計(jì)算權(quán)向量并做一致性用由成對比較矩陣求權(quán)向量的特征根法對正互反矩陣T求最大特征值（記作λ）和最大特征值λ所對應(yīng)的特征向量（歸一化后）w，即w滿足

CIλn

n12345678900其中n1,2RI01，2對于n3的成對比較矩陣T，將它的一致性指標(biāo)CI與同階（指n相同）的隨機(jī)一致性指標(biāo)RI之比稱為一致性比率CR，當(dāng)CRCI

（二）計(jì)算組合權(quán)向量并做組合一致性 n得到第一層與第二層的目標(biāo)權(quán)向量，記為w(2)w(2),w(2) ,w(2)T。用同樣 n準(zhǔn)則的權(quán)向量，計(jì)算各方案對目標(biāo)的權(quán)向量，這個(gè)稱為組合權(quán)向量，記作w(k。p層的一致性指標(biāo)CI(p),CI(pCI(p（n

w(

RI(p)RI(p),RI(p),...,RI(p)w( CI(pCR(p)

p3,4,..., p層通過一致性檢驗(yàn)的條件為CR(p)0.1定義最下層（第s層）1s數(shù)據(jù)處

CR*CR(

2 C1/ 11/ 1計(jì)算得C層對S層的權(quán)向量(2) 0.1000)T，一致性檢驗(yàn)指CR2

0.00.1 B4、B5，建立成對比較矩陣B11/ 5；對C2、C3依次 1/61/ 1/31/51/ 31/ 1/ 1/B2 ，B3

1/ 15 1/

1130.6871 123 233 3CR30.02510.1CR30.04330.1CR30.00320.1 44 24 244 454 564 674 0.7510)T7響程度的成對比較矩陣不再進(jìn)行一致性檢驗(yàn)。經(jīng)過對關(guān)于B2、B7的影響程度的成對比較矩陣的一致性檢驗(yàn)，得到分別的一致性指標(biāo)CR40.06340.1，CR40.00470.1。 是建立在了解系統(tǒng)的運(yùn)行和了解以往交通信息的基礎(chǔ)上的，要考慮每一段對系統(tǒng)的影因到斷i首先，根據(jù)權(quán)向量3i W3 的組合權(quán)向量，第三層BS層的權(quán)向量為 3W32

組合一致性比率CR3CI

0.0206150.03050.1

RI i0 i0 W400 0 其構(gòu)造方式與W3相同。這樣就可以計(jì)算A層 4W430.0816 CR4CI40.00120.0087RI 面就根據(jù)路段的重要度和彼此路段與節(jié)點(diǎn)的影響度得到選取路線的方法。（平方公里（人/平方公里從業(yè)勞（萬元利用公式可以得到各節(jié)點(diǎn)數(shù)據(jù)（如表四節(jié)點(diǎn)（標(biāo)號pG地圖中測量【3】利用公式計(jì)算路段重要度， ISii在得到節(jié)點(diǎn)的綜合了路段的重要度之后，結(jié)合各層因素對上層因素的影響的權(quán)向5I'' 5I I 6I'' I' I

4

20.2647I8'' I 9 4 II 11

5 I''' 5 I 6 ''' 7 8''' I''' III13 I14

9 I''' 11I''' 11則可以得到S的新的重要度為0.2572置是否存在或者贅余，也就是可能的Braess悖論情形。如圖七把圖中的虛線SSS建立CS層的影響程度的成對比較矩陣 3/ C1/ 1/4 1計(jì)算得C層對S層的權(quán)向量(2) 0.3991)T，一致性檢驗(yàn)指CR2

0.0250.1B5，建立成對比較矩陣B

對C2C3 1/31 11/31/51/ 21/ 1/31/B2 ，B3

1/ 1/ 13 1

123 233 3CR30.02510.1，CR30.02620.1，CR30.0028 44 24 244 454 564 674 7i首先，根據(jù)權(quán)向量3i W3

的組合權(quán)向量，第三層BS層的權(quán)向量為 3W32 組合一致性比率

3CI30.02640.1RIi然后根據(jù)權(quán)向量4i W4 0 其構(gòu)造方式與W3相同。這樣就可以計(jì)算A層

CI 0.0061RI5 I''' 5 I 6 ''' 7 BI'''8''' 9 '''

11''' IBC，CI'''I

13 14 交通系統(tǒng)存在Braess現(xiàn)象。模型在實(shí)際生活中，對于已經(jīng)修建的路且發(fā)生Braess，的而駛使時(shí)最解擁堵。對于劃中要修的路，可進(jìn)行車流的，看是否會產(chǎn)生Braess可能由于其經(jīng)濟(jì)代價(jià)太高或其他原因還不如修建花費(fèi)代價(jià)較小且不會經(jīng)常發(fā)生堵車的模型二的 當(dāng)人們在選擇路徑進(jìn)行考慮時(shí)，最終可以形成每個(gè)選擇路徑的一種Nash均衡， Sisi為是第is(s1,s2s就是一 。若S為全 SS1設(shè)有矩陣對策G{S1S2A}S1 S2 Am S*{xE*|

0,i

n

S*{yE*|y0,i

y

分別稱S*和S*xS*yS*xy E(x,y)aijxiyj 稱G{S*S*E}為對策G E(i,y)aijyjjE(x,j)aijxii,E(x,y)E(i,y)xii和E(x,y)E(x,j)yjj,,

x'

i 則問題（P）的約束條件變?yōu)閍x' j ijiix'

故問題（P）等價(jià)于線性規(guī)劃問題(P')min ax'

j ,n' ij'x i ,

y'y

,j,問題（D）等價(jià)于線性規(guī)劃問題 i ,mjy' j ,假設(shè)現(xiàn)A1B2，A3B3堵塞，分析A1到S選三條較理想路徑：路1:A1、 9 A= 0 90

x'( 1 w y'( 1 v V11 xVx'( 1 yVy'( 1 蟻群算法AAOB建立從巢穴到食物的兩條路徑：OABOBOBOBOB上的信息素。一段時(shí)間后，大部分螞蟻都選擇了道路OB。ASTSP問題的城市數(shù)量、連通情況、路徑長度和信息素的初始值；terminate---condition---notsatisfied：算法的結(jié)束條件未能滿足(結(jié)束條件select-next-city：使用算法定義的路徑選擇規(guī)則(1)選擇螞蟻下一步的走法； [(t)][ ij

如果j pij(t)

allowed

其中，ij

通過手工調(diào)節(jié)；ij(t1)(1)ij(t)ij(t) (t)NumberofAnts arc(i,j)TourofAntL LmQ是一個(gè)固定的正數(shù)；Lm是第m只螞蟻行走的路線長度554321 2345678Sx圖八交通系統(tǒng)二維坐標(biāo)圖點(diǎn)（路口XYS---4828---248----14---112-KLP(1iMj的信息素j(LP)(00且 Pj(L0(1jNPii第二步：啟動(dòng)所有螞蟻，每只螞蟻k(k1, ,K)從集合LPi開始，按照下述 i

P(k(L))

NN

j(LPij第三步：置ttnNCNC1。當(dāng)所有螞蟻在每個(gè)集合中都選擇了1PPi過程經(jīng)歷了n j(I)(tn)j(I)(t)j Pij(I)Pi

k

k(I

(01)為信息素的持久性，1為信息素的消逝程度，k iP環(huán)中第kIjPi

jk(I)Q/ekj(若第kj個(gè)元素，否則為ekmhaxOO (0 1 k(I 為信息素的消逝程度， Pi為本次jk(I)Q/ekjekmhaxOO h為樣本數(shù)量，On,OqFNN的實(shí)際輸出和期望輸出?？梢?，誤差越小，信重復(fù)第二步和第三步，直到所有螞蟻全部收斂到1NCmax，輸出最優(yōu)解算法結(jié)束情況，路線選擇情況，等都考慮到了蟻群優(yōu)化里面。取C為上述坐標(biāo)，設(shè)為選擇路線時(shí)的思想決定系數(shù)，為到路口時(shí)啟發(fā)想哪個(gè)方向走的啟發(fā)權(quán)，需要通過手工調(diào)節(jié)，為經(jīng)常走某條路，下次不K10Q 編程：functionACOTraffic(C,NCmax,K,,,,Q)，得到的圖像

更好的路徑。根據(jù)以上圖像分析出來比較優(yōu)的路徑是：GPS在考慮廣泛使用可以反映當(dāng)前交通擁堵情況的GPS導(dǎo)航系統(tǒng)，經(jīng)研究查變化，其加上系數(shù)后，即可得到模型。則數(shù)據(jù)變化情況為：們設(shè)為選擇路線時(shí)的思想決定系數(shù)，為到路口時(shí)啟發(fā)想哪個(gè)方向走的啟發(fā)權(quán)。取0.2得：K0Q運(yùn) 編程 ACOTraffic(C,NCmax,K,,,,Q)得到的圖（2（3（4（5）圖

圖圖

圖

圖 圖發(fā)現(xiàn)擁有導(dǎo)航系統(tǒng)步不能是的出行變快，是整個(gè)交通系統(tǒng)變好。69.4602，轉(zhuǎn)48.62214

總徑進(jìn)行分析，得出選擇路徑的概率，最終得出其選擇的道路。決方要行駛的時(shí)間使花費(fèi)的時(shí)間增加，最終可以緩解交通擁堵。第四