2010第三屆優(yōu)秀第一階段與一等

第三屆“ScienceWord杯”數(shù)學(xué)中編號(hào)專(zhuān)用頁(yè)參賽隊(duì)伍的參賽號(hào)碼：（請(qǐng)各個(gè)參賽隊(duì)提前填寫(xiě)好競(jìng)賽統(tǒng)一編號(hào)（由競(jìng)賽送至評(píng)委團(tuán)前編號(hào)競(jìng)賽評(píng)閱編號(hào)（由競(jìng)賽評(píng)委團(tuán)評(píng)閱前進(jìn)行編號(hào)22010年第三屆“ScienceWord杯”數(shù)學(xué)中國(guó) 目基于博弈論的平行有向路中的Braess無(wú)效率檢關(guān)鍵 Nash均衡、有向路子博弈、集體理性、最優(yōu)化方 要Braess悖論是有時(shí)交通網(wǎng)絡(luò)中通路或更高局部運(yùn)力情況下的Nash均衡的總體效用低于更少通路和更低局部運(yùn)力情況下的Nash均衡的總體效用的結(jié)果，其原因是Wardrop均衡就是Nash均衡而根據(jù)Wardrop的均衡解得出的所有博弈方的時(shí)間消耗的總和，有時(shí)針對(duì)二環(huán)路交通網(wǎng)絡(luò)，我們建立起了以從每個(gè)博弈固有的交通起始點(diǎn)和終止點(diǎn)為分類(lèi)屬性的30個(gè)網(wǎng)絡(luò)靜態(tài)子博弈GameSE，并使用這些子博弈來(lái)構(gòu)成主體模型同時(shí)通過(guò)直接求解無(wú)GPS導(dǎo)航系統(tǒng)時(shí)的網(wǎng)絡(luò)博弈的Nash均衡，分別計(jì)算出路段W(3,4)即W(車(chē)公廟，東四十橋)存在與不存在時(shí)的所有車(chē)輛達(dá)到其目的地一次所需時(shí)間總和為：C (小時(shí)/300萬(wàn)輛*次)和C' 在完全利己和無(wú)GPS的前提下存在Braess悖論。在有GPS導(dǎo)航系統(tǒng)時(shí)，我們主要探討由于GPS降低了博弈方合作的成本，增加了合作的，在所有人都追求集體利益最大化的集體理性的趨勢(shì)下，均衡會(huì)出現(xiàn)什么樣的變化。我們分別計(jì)算出路段W(3,4)即W(車(chē)公廟，東四十橋)存在與不存在時(shí)的所有車(chē)輛達(dá)到其目的地一次所需時(shí)間總和為：C''= (小時(shí)/300萬(wàn)輛*次)和C'''=CC''C''<C'''<C'<C，因此可得出結(jié)論使用GPS導(dǎo)航系統(tǒng)能夠明顯改善交通狀況，并（填寫(xiě)（填寫(xiě)所選題目3（ 總分 BraessparadoxistherealitythattheglobalutilityofaNashequilibriuminthesystemwhichownsmoreaccessorhigherlocalcapacityislessthantheglobalutilityofaNashequilibriumwhichownslessaccessandlocalcapacity.It’sduetotheequilibriumofWardropistheNashequilibrium,andthesumoftimecostforallyersworkedoutbyWardropequilibriumequationswillbelargerwhiletheaccessorlocalcapacityaremoreattime.ForresearchingonthetrafficnetworkoftheSecondRinginBeijing,wehavefounded30staticnetworksubgamesGameSEwhichdistinguishedbystartingpointsandendpointofallyers,thenusedthissubgamestoformmainthemodelandthecoreofalgorithm.AccordingtothesolutionofnetworkNashequilibriumwhentheGPSdoesnotexist,wehaveworkedoutthesumoftimecostofallyersfromtheirstartingtoaimwhilethewayW(3,4)vizW(ChegongTemple,FortyBridgetheeastern)existsornotis:C (hour/3,000,000*times)andC' (hour3,000,000*times).C'C.ThereforethereexistsBraessparadoxwhilealperfectrationalandnoGPS.IftherewereGPSsystemnavigation,wediscussedwhatwouldhappentoequilibriumofsystemwhileTheGPScutdownthecostofcooperationaddedthedesireofcooperationandeveryyerwascollectivistandoptimizethesumoftimecostofallyers.wehaveworkedoutthesumoftimecostofallyersfromtheirstartingtoaimwhilethewayW(3,4)vizW(ChegongTemple,FortyBridgetheeastern)existsornotisC''= (hour/3,000,000*times)and (hour/3,000,000*times).C'''C'',C''<C'''<C'<CItrepresentthattheGPSsystemnavigationcanimprovestatusoftrafficnetwork.What’smorethecollectivismcouldcouncttheeffectoftheBraessparadoxincreasetheefficiencyofthetrafficthatwouldbemuchworse.WehavealsocalculatedthatGPSnavigationsystemwillsavetheconsumptionofeachvehicleby30.41%.41968年，DietrichBraess提出在一個(gè)交通網(wǎng)絡(luò)上增加一條路段，或提高某首先，建立在沒(méi)有GPS然后，建立有GPS實(shí)時(shí)導(dǎo)航系統(tǒng)下的二環(huán)路交通模型，并判斷此時(shí)是否存在ij：用i,jDse：以從SE模型一的假設(shè)

模型的假6、車(chē)輛通過(guò)一路段所需時(shí)間tij是選擇走這條路段的車(chē)輛數(shù)決定，不考慮實(shí)1模型二的假設(shè)模型一的分析、建立及求模型一的分內(nèi)的五條主干道如下圖所示：13134 段，如果在有這條路段的情況下的NashEquilibrium比沒(méi)有這條路段的情況下NashEquilibriumBraess效率，并且這條路段的存在增加了二環(huán)路的Braess無(wú)效率。由于這是一個(gè)考慮所有點(diǎn)都是起點(diǎn)同時(shí)又都是終點(diǎn)的平行有向路的NashEquilibrium問(wèn)題，因此必須先定義這個(gè)復(fù)雜博弈的一些概念。平行有向路靜態(tài)子博弈：有相同的起點(diǎn)S和終點(diǎn)E的車(chē)輛我們都將其歸入合為WaySE。設(shè)笛卡爾積GameSE yerSEWaySE。稱(chēng)GameSE為圖的一個(gè)靜態(tài)子博弈。該圖中顯然有A230個(gè) 模型一的建任意GameSENashEquilibriumwi,wjWaySE，TSE(wi)TSE2需注意WaySE只包括從起點(diǎn)SE選擇wiWaySE的時(shí)間消耗函數(shù)TSE(wi)我們先給出所有的靜態(tài)子博弈GameSEGame12，Game13，Game14，Game15，Game16Game23，Game24，Game25，Game26Game34，Game35，Game36Game45，Game46這里只有15個(gè)，另外15個(gè)靜態(tài)子博弈的始終點(diǎn)是與這15個(gè)的對(duì)稱(chēng)的，并文獻(xiàn)研究表明，通過(guò)一個(gè)相鄰兩點(diǎn)i,jW(i,jtijijijnij，各個(gè)符號(hào)的定義見(jiàn)符號(hào)說(shuō)明這樣可以表示GameSE nTSE(W(i1,i2,...,in))tij,ij1(ij,ij1ij,ij1nij,ij1j jTSE(W(i1,i2,...,in))TSE(W(k1,k2,...,km))，W(i1,i2,...,in),W(k1,k2,...,km) i i i k k k i i i k k kj j jj j j jjj j3n m(ij,ij ij,ij1nij,ij1)(kj,kj kj,kj1nkj,kj1),W(i1,i2,...,in),W(k1,k2,...,km)WaySEj

,in

N(W(i1,i2...,in))DSE有到達(dá)終點(diǎn)的完整通路的車(chē)輛的數(shù)量的總和等于GameSE中所有的車(chē)輛數(shù)，這是但是僅憑圖中所有這些GameSE的局部Nash的Nashnij不僅受此子博弈GameSE的影響，更要受到nij顯然有每個(gè)GameESW(i,j)的路徑W(i1i2i,jin車(chē)輛數(shù)

N(W(i1,i2...,i,j,...,in

n

))?i, t1 n m(ij,ij1ij,ij1nij,ij1)(kj,kj1kj,kj1nkj,kj1),W(i1,i2,...,in

1

))?i,j

t1 為了具體描述這個(gè)方程，立即給出WaySEWay12，Way13，Way14，Way15，Way16Way23，Way24，Way25，Way26Way34，Way35，Way36Way45，Way464然后我們把每一個(gè)集合WaySE這是十五個(gè)互異的子博弈（其余的總與這15個(gè)對(duì)稱(chēng)）的包含各自全部的策略的集合們。顯然不同的子博弈GameSE其策略集中沒(méi)有任何相同的元素，這是因?yàn)?，策略W(i1i2in都不會(huì)有回路出現(xiàn)，因?yàn)閷?duì)于一個(gè)子博弈GameSE中的任何5t12t13t34t42t13t35t56t64DN(W(1,2))N(W(1,3,4,2)) n N(W(i,i...,i,j,...,i))?i,j t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it13t12t24t43t12t24t46t65 n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it12t24t13t34t13t35t56DN(W(1,2,4))N(W(1,3,4)N(W(1,3,5,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(12,3,4,5,6)W(i,i,i,j,,it12t24t43t35t12t2t46t65t13t35t13t34t46DN(W(1,2,4,3,5))N(W(1,2,4,6,5)N(W(1,3,5))N(W(1,3,4,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it12t24t46t12t24t43t35t56t13t34t46t13t35DN(W(1,2,4,6))N(W(1,2,4,3,5,6)N(W(1,3,4,6))N(W(1,3,5, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it21t13t24t43t24t46t65DN(W(2,1,3)N(W(2,4,3)N(W(2,4,6,5, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it24t21t13t34t21t13t35t56DN(W(2,4)N(W(2,1,3,4)N(W(2,1,3,5,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it21t13t35t21t13t34t46t65t24t43t35t24t46DN(W(2,1,3,5)N(W(2,1,3,4,6,5)N(W(2,4,3,5))N(W(2,4,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it24t46t24t43t35t56t21t13t34t46t21t13t35DN(W(2,4,6)N(W(2,4,3,5,6)N(W(2,1,3,4,6))N(W(2,1,3,5, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,i6t34t31t12t24t35t56DN(W(3,4)N(W(3,1,2,4)N(W(3,5,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it35t31t12t24t46t65t34t46DN(W(3,5)N(W(3,1,2,4,6,5)N(W(3,4,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it31t12t24t46t34t46t35DN(W(3,1,2,4,6)N(W(3,4,6)N(W(3,5, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it42t21t13t35t43t35t46DN(W(4,2,1,3,5)N(W(4,3,5)N(W(4,6, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it46t42t21t13t35t56t43t35DN(W(4,6)N(W(4,2,1,3,5,6)N(W(4,3,5, n N(W(i,i..,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,it56t53t34t46t53t31t12t24DN(W(5,6)N(W(5,3,4,6)N(W(5,3,1,2,4, n N(W(i,i...,i,j,...,i))?i,j(1,2,3,4,5,6)(1,2,3,4,5, t1t SE(1,2,3,4,5,6)(1,2,3,4,5,6)W(i,i,i,j,,i根據(jù)以上的分析，現(xiàn)在總NashEquilibrium的方程組直接給出：7t12t13t34t42t13t35t56t64t42 t t t t12t24t13t34t13t35t56t64 tt t t t t t21t13t24t43t24t46t65t53 t tt t tt tt t t t t t34t31t12t24t35t56t64 t t t tt t ttt t t56t53t34t46t53t31t12t24t46t21t31t43t24t31t53t65t46t24(a t(a t21t42t31t43t31t53t65t46(at21t42t34t53t21t42t64t56t31t53t31t43t64t56(a t tt t ttt(a' t12t31t42t34t42t64t56t35(a tt tt t(a t ttt tt tt tt tttt(a' t43t13t21t42t53t65t46(a tt t t(a tt ttt t(a t65t35t43t64t35t13t21t42t64(a8DN(W(1,3))N(W(1,2,4,3)N(W(1,2,4,6,5,3))(dD14N(W(1,2,4))N(W(1,3,4)N(W(1,3,5,6,4))(dDN(W(1,2,4,3,5))N(W(1,2,4,6,5)N(W(1,3,5))N(W(1,3,4,6,5))(dD23N(W(2,1,3)N(W(2,4,3)N(W(2,4,6,5,3))(d D25N(W(2,1,3,5)N(W(2,1,3,4,6,5)N(W(2,4,3,5))N(W(2,4,6,5))(d08)D D

DN(W(3,1,2,4,6)N(W(3,4,6)N(W(3,5, N(W(4,2,13,5)N(W(4,3,5)N(W(4, N(W(4,6)N(W(4,2,1,3,5,6)N(W(4,D56N(W(5,6)N(W(5,3,4,6)N(W(5,3,1,2,4,D21N(W(2,1))N(W(2,4,3,1))N(W(2,4,6,5,3,1))(dDN(W(3,1))N(W(3,4,2,1)N(W(3,5,6,4,2,1))(dD41N(W(4,2,1))N(W(4,3,1)N(W(4,6,5,3,1))(dDN(W(5,3,4,2,1))N(W(5,6,4,2,1)N(W(5,3,1))N(W(5,6,4,3,1))(d'DN(W(6,4,2,1))N(W(6,5,3,4,2,1)N(W(6,4,3,1))N(W(6,5,3,1))(dD32N(W(3,1,2)N(W(3,4,2)N(W(3,5,6,4,2))(d' N(W(4,2)N(W(4,3,1,2)N(W(4,6,5,3,1,2))(dD52N(W(5,3,1,2)N(W(5,6,4,3,1,2)N(W(5,3,4,2))N(W(5,6,4,2))(d'08)D' D43N(W(4,3)N(W(4,2,1,3)N(W(4,6,5,3))(dDN(W(5,3)N(W(5,6,4,2,1,3)N(W(5,6,4,3))(dD63N(W(6,4,2,1,3)N(W(6,4,3)N(W(6,5,3))(dD54N(W(5,3,1,2,4)N(W(5,3,4)N(W(5,6,4))(d N(W(6,4)N(W(6,5,3,1,2,4)N(W(6,5,3,4))(dnij

其中tijijijnij,這是至關(guān)重要的，為了不使表達(dá)過(guò)于繁復(fù)，我們就沒(méi)有將根據(jù)我們的假設(shè)延遲參數(shù)ijij9tLij n

這里我們認(rèn)為其等于二環(huán)的限制速度，k是唯一的待估計(jì)參數(shù)。,AAt ij

（*）總是有且僅有唯一解。模型中僅有的參數(shù)是ij和j，其他的量都是ijij和W(i1i2i,jin4.3第一部分是求方程組（*）即A 的未知量為W(i,i...,i,j,...,i)t ij

1 受方程（*）tij，進(jìn)而GameSET(GameSE)CDSET(GameSE)即這個(gè)模型中所有車(chē)輛消耗的時(shí)間。這一部分計(jì)算的就第二部是求方程

A） 的未知量滿足W(i,i...,3,4,...,i)A

1

t ijC'DSET'(GameSE)就是沒(méi)有路W（3,4）的交通系統(tǒng)的指標(biāo)，是用來(lái)3,4復(fù)雜。為了求解該問(wèn)題的近似NashC即有通路W(3,4)情況下的我們估算出的市總的車(chē)輛運(yùn)行時(shí)間為； C’=<C,所以在問(wèn)題一中存在Braess悖論，但是并不是很顯著。這模型二的分析、建立及求模型二的分的車(chē)輛通行時(shí)間最小的話，Braess悖論就有可能不復(fù)存在。但是這樣一來(lái)我們模型二的建CS,Ei2,i3,i4

tpath(S,i2,i3,i4,i5,E)numpath(S,i2,i3,i4,i5,tijijijnijlindo合的概括和描述，在模型二中仍然使用靜態(tài)子博弈GameSE和此子博弈的路徑策 SE path(i1,i2,i3,i4,i5,i6),Wayij,tpath(i1,i2,i3,i4,i5,i6) i,j{i1,i2,i3,i4,i5,i6

tij(2)程，問(wèn)題一中表示Nash均衡條件的所有決策條件jjj(i,ij

i

ni

)(kj,k

k

nk

),W(i1,i2,...,in),W(k1,k2,...,km)jjjjjjnjTSE(W(i1,...,in))(ijj

ij,i

ij,ij

)直接寫(xiě)成tpath(i1,i2,i3,i4,i5,i6) i,j{i1,i2,i3,i4,i5,i6

tij12345表示路徑tpath(i,i,i,i,i12345錯(cuò)誤而造成性的。GameSE,path(i1,i2,i3,i4,i5,i6),DSE

要從S點(diǎn)行車(chē)到E點(diǎn)的車(chē)輛的總數(shù)。

DSEWaySE,path(i1,i2,i3,i4,i5,i6),nij iikjik

numpath(i1,i2,i3,i4,i5,i6)(4)模型二的求minCS,Ei2,i3,i4

tpath(S,i2,i3,i4,i5,E)numpath(S,i2,i3,i4,i5,E WaySE,tSESESEnSE ,Way, t (i1,i2,i3,i4,i5,i6

(i1,i2,i3,i4,i5,i6 i,j{i1,i2,i3,i4,i5,i6Game,path(i,i,i,i,i,i), 12345

i1Si6Ei2,i3,i4,i5point

numpath(i1,i2,i3,i4,i5,i6WaySE,path(i1,i2,i3,i4,i5,i6),nij

iikjik

numpath(i1,i2,i3,i4,i5,i6不存在中間路徑時(shí)的總交通時(shí)間消耗 根據(jù)我們的檢驗(yàn)標(biāo)準(zhǔn)，因?yàn)镃'''C''即有路的時(shí)候會(huì)比沒(méi)路的時(shí)候花的總時(shí)間更少，而且效果極其明顯，所以Braess悖論此時(shí)顯然是不成立的。并且即使是的一種情況C'''也要比問(wèn)題一條件下最好的一種情況C'即完全理GPSBraess模型的綜合評(píng)模型的優(yōu)BraessGPSBraess該模型的特點(diǎn)在于考慮了由30個(gè)方向的交通需求所構(gòu)成的平行有向的所有博弈方的Braess均衡，并求解除了這個(gè)均衡。我們的計(jì)算方法是單向有向碼，但是關(guān)于問(wèn)題一中求解Nash均衡的部分的代碼，并未附入文中，只將解第模型的缺模型的推該模型還可以對(duì)的二環(huán)及三環(huán)、四環(huán)路中其它路徑是否存在Braess無(wú)Braess悖論問(wèn)題。模型中還可以使用嵌套式的計(jì)量方法，用以高效的估計(jì)參數(shù)，【1】謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件.： 【3】薛薇.統(tǒng)計(jì)分析與SPSS的應(yīng)用 【7Braess’SParadox[J]．長(zhǎng)沙交通學(xué)院學(xué)報(bào)，2003，19(3)69—72．附錄p/1..7/?!Theseventhpointmeanstheinvisiblepointusedtodescribethereisnointeruptpointbetweetthetowpointwefocusgame(p,p)|&1#NE#&2#AND#(&1#NE#7)#AND#(&2#NE#7):d,At,timecost?!Attheequilibriumtimeofdrivingofthegame(p1,p2).TheNumofthemisway(p,p)/1,2,2,1,1,3,3,1,2,4,4,2,3,4,4,3,3,5,5,3,4,6,6,4,!Beauseallelementsofpathmusthavesamedeg,wedefinepoint7tostanddegofNULL!Thedefiningwayofelementsofpathisbesidethelastpointputtheotherpointintheoriginalorder,andthenput"7"betweenlastpointandthelastpointinorderuntilthenumberofpointsinmeets6.It'svery 0.121, 0.122,0.0151, 0.54, 0.5,4.33, 0.477,!Beacauseofthebetaweestimatedisverysmall,forhusbandcodewritinguselargevalue,thenlessenitin 176.3781124.167758198.46271215.26256200.5458722.084601312.1364 177.93782191.094822.084601 290.0518312.1364191.0948 209.21018271.50061187.12557?!c=@sum(game(s,e):timecost(s,e))/7?!Thefinalaimofquestion1wefocusmin=@sum(game(s,e):timecost(s,e))?!Thefinalaimofquestion2wefocus@for(game(s,e):timecost(s,e)=@sum(path(i1,i2,i3,i4,i5,i6)|i1#eq#s!Calculatethetotaltimecostofeverygame(s,e)whatformtheaimofourtest<1>!?@for(way(i,j):t=a+b*n)?!Theprimaryexpressionofeveryway<2>!?@for(path(i1,i2,i3,i4,i5,i6):tpath(i1,i2,i3,i4,i5,i6)=@sum(way(i,j)|(i#eq#i1#and#j#eq#i2)#or#(i#eq#i2#and#j#eq#i3)#or#(i#eq#i3#and#j#eq#i4)#or#(i#eq#i4#and#j#eq#i5)#or#(i#eq#i5#and#j#eq#i6) :t))?!Ifway(i,j)isonthepath(i1..in),addthetimecostofway(i,j)o