公交转车问题PPT学习教案

1、会计学1公交转车问题公交转车问题第1页/共66页第2页/共66页第3页/共66页第4页/共66页第5页/共66页第6页/共66页第7页/共66页第8页/共66页第9页/共66页第10页/共66页,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia第11页/共66页),(|minmjiam第12页/共66页),(35),(min0mjiammjitSm第13页/共66页,|),(),(),(min21211互不相等nnmmnnnnkkkjikkfjkfkif该模型是形式上的，对于求解没有实质性的该模型是形式上的，对于求解没有实质性的作用。作用。第14页/共66页),(|m

2、inmjiam,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia在实际求解时，先根据公汽线路的数据将在实际求解时，先根据公汽线路的数据将a(i,j,0)的数据存储在矩阵的数据存储在矩阵A0中。中。第15页/共66页a(i,k1,0)+, a(k1,k2,0)+, a(k2,j,0) +,则转车次数为2.,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia),(|minmjiam第16页/共66页第17页/共66页,算机中,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia第18页/共66页第19页/共66页.,1 | )

3、 1,()0 ,(min),(jkikNkmjkakiamjia第20页/共66页,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia第21页/共66页第22页/共66页第23页/共66页第24页/共66页转车次数转车次数站点对数站点对数03965351587599328274263310866064203855110根据题目中的数据根据题目中的数据,北京北京市的公汽站点转市的公汽站点转5次车可次车可以全部到达以全部到达.根据表中的数据根据表中的数据,假设转最多假设转最多2次车是不合理的次车是不合理的,假设转最多假设转最多3次车有一定的合理性次车有一定的合理性.第25页

4、/共66页的乘车费用.点对换乘次数费用（元）S3359S182813S1557S048123S0971S048513S0008S007312S0148S048523S0087S367612关于最小乘车费用关于最小乘车费用,其模型一般只有形式上的其模型一般只有形式上的,对求解没有直接的作用对求解没有直接的作用.我们对具体的六对站点给出讨论的结果我们对具体的六对站点给出讨论的结果.第26页/共66页点对换乘次数费用（元）S3359S182813S1557S048123S0971S048513S0008S007312S0148S048523S0087S367612第27页/共66页点对换乘次数费用（

5、元）S3359S182813S0971S048513第28页/共66页),(35),(min0mjiammjitSm第29页/共66页,到12内求最优.),(35),(min0mjiammjitSm第30页/共66页第31页/共66页第32页/共66页第33页/共66页第34页/共66页第35页/共66页第36页/共66页第37页/共66页第38页/共66页m01234ts(i,j,m)83676359Ts(i,j,m)836763595(m+1)+3ns(i,j) 4449545964最小乘车时间为最小乘车时间为59,需转需转4次车次车.其它答案参见评阅要点其它答案参见评阅要点(该要点给出的

6、答案中该要点给出的答案中包含了起始的包含了起始的3分钟分钟)第39页/共66页n第6组2个站点都在地铁线上,最小转乘次数为0.第40页/共66页第41页/共66页第42页/共66页第43页/共66页n如果有公汽转车,等号要换成大于等于号第44页/共66页第45页/共66页n右端的值第46页/共66页第47页/共66页第48页/共66页第49页/共66页SiDkSjDl(1)p次(3)q次(3)站数站数:N2(l,j,q-1),乘车时间乘车时间: 3N2(l,j,q-1),转车时间转车时间5(q-1)(2)(2)乘车时间乘车时间: tD(k,l)(4)公汽转地铁公汽转地铁,地铁转公汽时间地铁转公

7、汽时间:13总时间总时间:tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13第50页/共66页第51页/共66页第52页/共66页第53页/共66页第54页/共66页5.5(p+q)+3n根据这一下界, 搜索不多的p,q就得到最小时间.第55页/共66页第56页/共66页第57页/共66页第58页/共66页nSDS, , =p,r r nStep4 若TSDS(i,j,h) A(h+1,i,j)停止;否则令h:=h+1，转Step3.第59页/共66页第60页/共66页点对ts(i,j,m)m*ns(

8、i,j)5(m*+1)+3ns(i,j)T*1234563359182810164697141364641557048110699101 1034251009909710485128103105104 106427106103000800738367635964413645901480485106102104 1069552510510200873676654651563105046第61页/共66页点对3359-1828 1557-04810073 0148-0485tSDS(p+q)1+184.5116.59653.587.51+2711109558.586.

9、52+175.5118.51015492.51+37610710063.591.52+2621121005991.53+180.5117.5105.55697.51+47711210568.596.52+3671091056496.53+267114104.56196.54+185.5122.5110.559.5102.5TSDS(i,j,5)621079553.586.5A(6,i,j)6698.59663.591第62页/共66页32448516731413359174617841828LLLSSSS 下行环行下行站站站84189912541231031557191931860902048

10、1LLLLSSSSS 下行下行上行上行站站站站13290469161320971251721590485LLLSSSS 下行环行上行站站站19847601732810325222000816912085048305250073LLLLLSSSSSS 上行下行环行上行上行站站站站站308811564171529301483604236122100485LLLLSSSSS 上行下行上行下行站站站站212319711010087008804273676LLLSSSS 下行环行上行站站站 第63页/共66页3242012428041236213359S20270609( 12)1961( 37)16711828LLTLLSSDSDSS 下行上行上站站站站站841899125412310315571919318609020481LLLLSSSSS 下行下行上行上行站站站站09411564176145309710567( 01)2534( 15)22100485LTLLSSDSDSS 上行上行下行站站站站2001210363200082534( 15)120525(25)0073LTTLSSDDSDS 上行上行站站站2站02411564174135301481487( 02)2534( 15)22100485LTLLS