2010第三届优秀第一阶段与一等

第三届“ScienceWord杯”数学中编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好竞赛统一编号（由竞赛送至评委团前编号竞赛评阅编号（由竞赛评委团评阅前进行编号22010年第三届“ScienceWord杯”数学中国 目基于博弈论的平行有向路中的Braess无效率检关键 Nash均衡、有向路子博弈、集体理性、最优化方 要Braess悖论是有时交通网络中通路或更高局部运力情况下的Nash均衡的总体效用低于更少通路和更低局部运力情况下的Nash均衡的总体效用的结果，其原因是Wardrop均衡就是Nash均衡而根据Wardrop的均衡解得出的所有博弈方的时间消耗的总和，有时针对二环路交通网络，我们建立起了以从每个博弈固有的交通起始点和终止点为分类属性的30个网络静态子博弈GameSE，并使用这些子博弈来构成主体模型同时通过直接求解无GPS导航系统时的网络博弈的Nash均衡，分别计算出路段W(3,4)即W(车公庙，东四十桥)存在与不存在时的所有车辆达到其目的地一次所需时间总和为：C (小时/300万辆*次)和C' 在完全利己和无GPS的前提下存在Braess悖论。在有GPS导航系统时，我们主要探讨由于GPS降低了博弈方合作的成本，增加了合作的，在所有人都追求集体利益最大化的集体理性的趋势下，均衡会出现什么样的变化。我们分别计算出路段W(3,4)即W(车公庙，东四十桥)存在与不存在时的所有车辆达到其目的地一次所需时间总和为：C''= (小时/300万辆*次)和C'''=CC''C''<C'''<C'<C，因此可得出结论使用GPS导航系统能够明显改善交通状况，并（填写（填写所选题目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提出在一个交通网络上增加一条路段，或提高某首先，建立在没有GPS然后，建立有GPS实时导航系统下的二环路交通模型，并判断此时是否存在ij：用i,jDse：以从SE模型一的假设

模型的假6、车辆通过一路段所需时间tij是选择走这条路段的车辆数决定，不考虑实1模型二的假设模型一的分析、建立及求模型一的分内的五条主干道如下图所示：13134 段，如果在有这条路段的情况下的NashEquilibrium比没有这条路段的情况下NashEquilibriumBraess效率，并且这条路段的存在增加了二环路的Braess无效率。由于这是一个考虑所有点都是起点同时又都是终点的平行有向路的NashEquilibrium问题，因此必须先定义这个复杂博弈的一些概念。平行有向路静态子博弈：有相同的起点S和终点E的车辆我们都将其归入合为WaySE。设笛卡尔积GameSE yerSEWaySE。称GameSE为图的一个静态子博弈。该图中显然有A230个 模型一的建任意GameSENashEquilibriumwi,wjWaySE，TSE(wi)TSE2需注意WaySE只包括从起点SE选择wiWaySE的时间消耗函数TSE(wi)我们先给出所有的静态子博弈GameSEGame12，Game13，Game14，Game15，Game16Game23，Game24，Game25，Game26Game34，Game35，Game36Game45，Game46这里只有15个，另外15个静态子博弈的始终点是与这15个的对称的，并文献研究表明，通过一个相邻两点i,jW(i,jtijijijnij，各个符号的定义见符号说明这样可以表示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有到达终点的完整通路的车辆的数量的总和等于GameSE中所有的车辆数，这是但是仅凭图中所有这些GameSE的局部Nash的Nashnij不仅受此子博弈GameSE的影响，更要受到nij显然有每个GameESW(i,j)的路径W(i1i2i,jin车辆数

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 为了具体描述这个方程，立即给出WaySEWay12，Way13，Way14，Way15，Way16Way23，Way24，Way25，Way26Way34，Way35，Way36Way45，Way464然后我们把每一个集合WaySE这是十五个互异的子博弈（其余的总与这15个对称）的包含各自全部的策略的集合们。显然不同的子博弈GameSE其策略集中没有任何相同的元素，这是因为，策略W(i1i2in都不会有回路出现，因为对于一个子博弈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根据以上的分析，现在总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,这是至关重要的，为了不使表达过于繁复，我们就没有将根据我们的假设延迟参数ijij9tLij n

这里我们认为其等于二环的限制速度，k是唯一的待估计参数。,AAt ij

（*）总是有且仅有唯一解。模型中仅有的参数是ij和j，其他的量都是ijij和W(i1i2i,jin4.3第一部分是求方程组（*）即A 的未知量为W(i,i...,i,j,...,i)t ij

1 受方程（*）tij，进而GameSET(GameSE)CDSET(GameSE)即这个模型中所有车辆消耗的时间。这一部分计算的就第二部是求方程

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

1

t ijC'DSET'(GameSE)就是没有路W（3,4）的交通系统的指标，是用来3,4复杂。为了求解该问题的近似NashC即有通路W(3,4)情况下的我们估算出的市总的车辆运行时间为； C’=<C,所以在问题一中存在Braess悖论，但是并不是很显著。这模型二的分析、建立及求模型二的分的车辆通行时间最小的话，Braess悖论就有可能不复存在。但是这样一来我们模型二的建CS,Ei2,i3,i4

tpath(S,i2,i3,i4,i5,E)numpath(S,i2,i3,i4,i5,tijijijnijlindo合的概括和描述，在模型二中仍然使用静态子博弈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)程，问题一中表示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

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

tij12345表示路径tpath(i,i,i,i,i12345错误而造成性的。GameSE,path(i1,i2,i3,i4,i5,i6),DSE

要从S点行车到E点的车辆的总数。

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不存在中间路径时的总交通时间消耗 根据我们的检验标准，因为C'''C''即有路的时候会比没路的时候花的总时间更少，而且效果极其明显，所以Braess悖论此时显然是不成立的。并且即使是的一种情况C'''也要比问题一条件下最好的一种情况C'即完全理GPSBraess模型的综合评模型的优BraessGPSBraess该模型的特点在于考虑了由30个方向的交通需求所构成的平行有向的所有博弈方的Braess均衡，并求解除了这个均衡。我们的计算方法是单向有向码，但是关于问题一中求解Nash均衡的部分的代码，并未附入文中，只将解第模型的缺模型的推该模型还可以对的二环及三环、四环路中其它路径是否存在Braess无Braess悖论问题。模型中还可以使用嵌套式的计量方法，用以高效的估计参数，【1】谢金星，薛毅.优化建模与LINDO/LINGO软件.： 【3】薛薇.统计分析与SPSS的应用 【7Braess’SParadox[J]．长沙交通学院学报，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