t1≧5*（n+1）+3*p
而由已知：
5*（n+1）+3*p＞t
说明t≤t1,与假设矛盾．
定理得证．
5．模型的建立和求解
5．1问题一的建立和求解
我们从换乘次数出发，首先建立一个公交车次和公交车次之间的邻接矩阵P，来反映两辆公交车j，k是否能至少经过同一个站点，即两车之间是否可以进行换乘，分别用P（j,k）=1或P（j,k）=0表示．
先考虑不需要换乘的情况．算出可以经过起始站A的所有公交车次，即集合L（A），以及可以经过终到站B的所有公交车次，即集合L（B）．若有公交车m∈L（A）且m∈L（B）则说明从A到B可以通过公交车m直达，判断是否达到时间的最优解，并综合时间，费用两方面，找出能够直达的情况中相对最好的．
再考虑需要转乘一次的情况．设L（A）中有m个元素，分别是j1，j2，……jm；L（B）其中有n个元素，分别是k1，k2……kn．若存在jp∈L（A）（1≦p≦m），和kq∈L（B）（1≦q≦n）使得P（jp，kq）=1，则说明A，B两点可通过jp，kq两辆公交车转乘一次到达．另外，记L（A）中j1这辆车能够经过的站点集合记为Sj1，L（B）中k1这辆车能够经过的站点集合记为Sk1，以次类推．将Sjp（1≦p≦m）和Skq（1≦q≦n）两两作交，若有s同时属于Sjp和Skq，则s就是中转站．也就是说从A点可以乘坐jp到s然后转乘坐kq达到B．判断是否达到时间的最优解，同时从所有这种转乘一次的情况中找出所需时间最短或所需费用最少的方案，并可以与直达情况进行比较．
进一步考虑需要转乘两次的情况．首先搜索这样的公交车d，d满足P（m，jp）=1且P（m，kq）=1，这就说明从A点乘坐jp出发，通过换乘d再换乘kq到达B．判断是否达到时间的最优解，同时从乘坐两次的情况中找出所需时间最短或所需费用最少的方案，并与上面两个方案进行比较．
同理可以处理转乘三次及三次以上的情况．对于三次以上的情况，虽然可以通过计算确定它们会缩短一些时间，但缩短的程度不会很大，尤其进一步考虑费用和方便性，结合实际情况，这种线路的利用性不会很强．事实上，转乘三次之内的方案，虽然不能说它一定就是时间的最优，但综合时间，费用以及方便性，我们可以说它就是最优的．
第二步，我们可以利用Floyd算法给出从A到B的最小站点数，用来估计出运行时间的下界，参看下面的表1．
始末站
最小
站点数
S0087→S3676
S1557→S0481
S0971→S0485
S0008→S0073
S0148→S0485
S0087→S3676
13
25
27
13
25
10
（表1）
第三步，因为考虑到转乘次数的增多会使费用升高，同时时间也不会降低太大的幅度，我们仅在下面的表2中给出6条路线分别转乘一，二，三次的的情况，它们都实现了局部（对于转乘次数）费用的最优，另外给出了全局时间最优解，作以比较．需要注意的是所有的线路都没有直达车，S1557→S0481和S0148→S0485两条线没有转乘一次到达的车．
换乘次数
始末站
换乘一次时间
最优
换乘两次时间
最优
换乘三次
时间最优
全局时间最优
S3359→S1828
用时/分钟
101
73
72
67（换乘五次）
费用/元
3
3
4
6
车站个数
32
21
19
14
路线
下行L436至S1784转下行L167
下行L352至S2903转上行L201至S1790转上行L041
上行L015至S3917转环行L296至S0992转上行L475至S1671转上行L041
上行L015至S1327转上行L328至S0525转上行L103至S0073转下行L480至S2704转上行L027至S1784转下行L167
S1557→S0481
用时/分钟
106
99
99（换乘三次）
费用/元
3
4
4
车站个数
32
28
28
路线
下行L363至S1919转下行L189至S3186转下行L460
下行L084至S1919转下行L189至S3186转下行L091至S0902转上行L254
下行L084至S1919转下行L189至S3186转下行L091至S0902转上行L254
S0971→S0485
用时/分钟
128
106
105
105（换乘三次）
费用/元
3
3
4
4
车站个数
41
32
30
30
路线
下行L013至S2184转下行L417
下行L263至S1609转下行L140至S2654转上行L469
下行L263至S1609转上行L448至S2113转下行L002至2654转上行L469
下行L263至S1609转上行L448至S2113转下行L002至2654转上行L469
S0008→S0073
用时/分钟
83
70
63
59（换乘四次）
费用/元
2
3
4
5
车站个数
29
20
16
13
路线
下行L463至S2083转上行L057
上行L198至S1691转下行L476至S2083转上行L057
上行L043至S1383转下行L282至S1327转上行L328至S0525转上行L103
上行L198至S1691转下行L476至S2085转上行L017至S0483转上行L328至S0525转上行L073
S0148→S0485
用时/分钟
106
102
102（换乘三次）
费用/元
3
4
4
车站个数
32
29
29
路线
上行L308至S0036转上行L156至S2210转下行L417
上行L308至S3604转下行L081至S2361转上行L156至S2210转下行L417
上行L308至S3604转下行L081至S2361转上行L156至S2210转下行L417
S0087→S3676
用时/分钟
65
46
51
46（换乘两次）
费用/元
2
3
4
3
车站个数
20
12
12
12
路线
上行L454至S3496转下行L209
下行L021至S0088转环行L231至S0427转下行L462
上行L206至S0088转环行L231至S1659转下行L406至S0427转下行S462
下行L021至S0088转环行L231至S0427转下行L462
（表2）
最后一步，我们用层次分析法对消费者的各种需求进行决策，从而挑选出最合适的路线推荐给消费者．关于层次分析法的操作，我们做如下说明：
1）对于指定的一条线路，将决策问题分解为3个层次，最上层为目标层，即选择线路方案；最下层是方案层，有m个选择方案；中间层为准则层，有费用和时间两个准则，个层间的联系用相连的直线表示，如图2
（图1）
2）通过消费者的不同侧重来确定个准则对于目标的权重，以及各方案对于每一个准则的权重，这些权重在人的思维过程中通常是定性的．
3）将方案层对准则层的权重及准则层的权重进行综合，最终确定方案曾对目标层的权重，得到最终的决策结果，也就是线路选择结果．
现在，我们以图表的形式给出满足消费者各种需求的最佳路线.
权系数
始末站
时间相对于费用的权重
w=2
w=5
w=0.25
w=0.5
S3359→S1828
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
S1557→S0481
下行L363至S1919转下行L189至S3186转下行L460（106分钟3元）
下行L084至S1919转下行L189至S3186转下行L091至S0902转上行L254（99分钟4元）
下行L363至S1919转下行L189至S3186转下行L460（106分钟3元）
下行L363至S1919转下行L189至S3186转下行L460（106分钟3元）
S0971→S0485
下行L263至S1609转下行L140至S2654转上行L469（105分钟4元）
下行L263至S1609转下行L140至S2654转上行L469（105分钟4元）
下行L263至S1609转下行L140至S2654转上行L469（105分钟4元）
下行L263至S1609转下行L140至S2654转上行L469（105分钟4元）
S0008→S0073
下行L463至S2083转上行L057（83分钟2元）
上行L198至S1691转下行L476至S2085转上行L017至S0483转上行L328至S0525转上行L073（59分钟5元）
下行L463至S2083转上行L057（83分钟2元）
下行L463至S2083转上行L057（83分钟2元）
S0148→S0485
上行L308至S0036转上行L156至S2210转下行L417（106分钟3元）
上行L308至S0036转上行L156至S2210转下行L417（106分钟3元）
上行L308至S0036转上行L156至S2210转下行L417（106分钟3元）
上行L308至S0036转上行L156至S2210转下行L417（106分钟3元）
S0087→S3676
下行L021至S0088转环行L231至S0427转下行L462（46分钟3元）
下行L021至S0088转环行L231至S0427转下行L462（46分钟3元）
上行L454至S3496转下行L209（65分钟2元）
上行L454至S3496转下行L209（65分钟2元）
（表3）
5．2问题二的建立和求解
第一步，首先我们将地铁系统考虑成一个独立的系统，所有出入口组成的集合记为T（D），这里需要对出入口的个数进行一个处理．从附件中可以看出，D012和D018地铁口是环行地铁和直行地铁的换乘点，而这两条地铁不可能是在同一层的，因此事实上地铁系统中是有两个D012和两个D018，我们需要对它们进行区别，具体的做法是用D040和D041来替换T2中的D012和D018．
做41*41的邻接矩阵Q，对于任意Di∈T（D）和Dj∈T（D），若Di和Dj在一条地铁线上相邻，则权为2.5，也就是地铁经过Di和Dj行驶的时间（单位：
分钟），另外特别的，D12和D40之间以及D18和D41之间的权是4，也就是转乘地铁需要的时间，若Di和Dj不相邻，权为∞．由于地铁是双向行驶的，因此Q是对角线为0的对称矩阵．
图2
这样，利用Floyd算法，可以求出地铁系统中任意Di和Dj之间所需要的最短时间．
第二步，将地铁系统放入大环境中，记T（D）中出入口对应的公交车站组成的集合为S（D）．首先分析A，B与S（D）的关系，具体分为以下3种：
1）A∈S（D）且B∈S（D），说明要从起始站A到终到站B不用坐公交车，可以通过地铁直接到达．
2）A
S（D），B∈S（D），说明在进入地铁系统之前需要乘坐公交车．
3）A
S（D），B∈S（D），说明在离开地铁系统之后需要乘坐公交车．
4）A∈S（D）且B
（D），这种情况相对复杂，它说明要想通过地铁实现从A到B的路线，在进入地铁系统之前并且离开地铁系统之后都需要坐公交车．
对于第二种情况，我们采取这样一种方法来寻找需要选择的公交线路，将其称为一维搜索法：
对于任意p∈S（D），p代表进入地铁系统的入口，我们将它想象成一个新的终到站，利用解决问题一的算法，建立起始站A到终到站p的新模型，根据假设，我们只需要考虑有直达的公交车或者转乘一次到达的公交车．第三种情况同理可以解决，将任意q∈S（D），q代表离开地铁系统的出口，想象成一个新的始发站，建立起始站q到中终到站B的新模型，也只考虑有直达的公交车或者转乘一次到达的公交车．之所以称为一维搜索法，主要是想突出只需要从S（D）中选择一个变量遍历．
这两种情况事实上是将起始站A到终到站B分成了两段，这两段加起来所需要的时间和费用都是很容易算出来的．
第四种情况要更复杂一些，我们采用二维搜索法来解决：
对于任意p,q∈S（D），p，q分别代表进入地铁系统的入口和离开地铁系统的出口．同样将p想象成一个新的终到站来建立起始站A到终到站p的公交模型，同时要将q想象成一个新的始发站，建立起始站q到中终到站B的公交模型．之所以称为二维搜索法，主要也是想突出需要从S（D）中选择两个变量遍历．
这一种情况事实上是将起始站A到终到站B分成了三段，这三段加起来所需要的时间和费用也都是很容易算出来的．
第三步，我们分别从时间和费用方面来分析一下得到的数据．在乘坐地铁这一段，费用是常数3元，而时间我们已经求出来是最短的，因此在这一段时间和费用都达到了最优．在乘坐公交车的路段上，因为是沿用了问题一的算法，因此可以说我们可以找到一种时间相当不错而费用达到最优的线路．
下面的表3给出了一些非常好的路线的详细情况，需要注意的是，“直达”表示起点A和终点B都有直接到达地铁系统的车次；“经转一次”的意思是在进入地铁系统前或离开地铁系统后乘坐公交车会有一次转乘的情况．另外，我们是从最优时间进行考虑的，没有填写的项目都是直接被排除了
起止站
直达
经转一次
1
起点站
S3359
时间
（分钟）
71
62
费用
（元）
5
7
线路
上行L15至S3068（D8）转地铁由地铁至S1961（D38）转上行L41至S1828
下行L352至S2903转上行201至S0609（D12）转地铁，由地铁至S1961（D37）转上行L428至S1671转上行L41至S1828
终点站
S1828
3
起
点
站
S0971
时间
（分钟）
96
费用
（元）
5
终点站
S0485
线路
下行L119至S0567（D1）转地铁由地铁至S0464（D21）转下行L395
4
起点站
S0008
时间
（分钟）
53．5
费用
（元）
5
终点站
S0073
线路
上行L200至S2534（D15）转地铁
由地铁至S0525（D25）转上行L103至S0073
5
起点站
S0148
时间
（分钟）
88
86．5
费用
（元）
5
6
终点站
S0485
线路
下行L24至S1487（D2）转地铁
由地铁至S1920（D20）转下行L417至S0485
下行L24至S1487（D2）转地铁
由地铁至S2534（D15）转上行L156至S2210转下行L417至S0485
6
起点站
S0087
时间
（分钟）
30=20+10
对于“20+10”的解释是：
地铁的运行时间是20分钟，进入地铁站4分钟，等待地铁2分钟，离开地铁站4分钟．
终点站
S3676
费用
（元）
3
线路
由地铁D27直达D36
（表4）
最后，综合问题一，重新用层次分析法对消费者的各种需求进行决策，从而挑选出最合适的路线推荐给消费者．见表5
权系数
始末站
时间相对于费用的权重
w=2
w=5
w=0.25
w=0.5
S3359→S1828
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
下行L352至S2903转上行201至S0609（D12）转地铁，由地铁至S1961（D37）转上行L428至S1671转上行L41至S1828（62分钟7元）
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
下行L352至S2903转上行L201至S1790转上行L041（73分钟3元）
S1557→S0481
因为乘坐地铁的最短时间大于乘坐公交车时间且费用高因此我们不考虑这条线路的地铁情况
S0971→S0485
下行L263至S1609转下行L140至S2654转上行L469（106分钟3元）
下行L119到S0567（D1）转地铁到S0464（D21）转下行L395（96分钟5元）
下行L263至S1609转下行L140至S2654转上行L469（106分钟3元）
下行L263至S1609转下行L140至S2654转上行L469（106分钟3元）
S0008→S0073
上行L198至S1691转下行L476至S2083转上行L057（70分钟3元）
上行L200至S2534（D15）转地铁
由地铁至S0525（D25）转上行L103至S0073（53.5分
升级会员 