如果出于某种目的,我们就是不能去询问地铁管理内部的人员和它们系统,只能从外界的角度去看,
只能用公共的信息去做这件事情的话,
2号线站点一共有n,每个站点是Si,两站点之间的里程数d(Si,Sj),两站点之间的计价p(Si,Sj),
其中i、j(- {1,2,...,n},这些信息一定能得到。
乘客进入2号线的方式有两种,从2号线的进站口进,从其他线换乘2号线;
同样的,乘客离开2号线,有可能出站,有可能去换乘其它线;
换乘有时候需要闸机验票,有时候不需要;需要闸机验票的我们就不视为换乘了;
我们选择一个特定的日期,在2号线每个进出站口,安装E[ai+bi]个进出站人口计数器,计数进闸机刷卡的人次,
其中i 遍历1 到 n,ai 表示 i 站点进站口的数量 bi 表示 i 站点出站口的数量,计数一天进出站人的数量,E[] 表示加总吧,
就有数据
Mai:该天 i 进站口进站人次 Mbi:该天 i 出站口出站人次
首先能得到的是| E[Mai] - E[Mbi] |
其中E[Mai] 里面包含了从2号线站点进站,同时,从2号线站点出站 或者从其他线 站点出站的人次
其中E[Mbi] 里面包含了从2号线站点进或者 从其他站点进,同时 从2号线站点出站的人次
收费的完成必须包含一次进站,一次出站,
其实我们就看到这个问题是一个图论里面的问题,考虑到,不管是从 i 站到 j站,还是从 j 站 到 i 站的收费都是一样的,我们的目的是估算营收,那么这个 图问题 呢,能归结为一个无向图的问题。
这里就好像必须显示出模型的局限性,问题的关键就在于我们身处于外部,没办法跟踪到换乘的人最终是从2号线之外的哪个
站出的,和,到底有多少人次从2号线出,是从别的线换乘过来的,
这时,我们假设cai 是从2号线之外的线换乘过来,在 i 站进入2号线,而我们没有统计到的人次,因为没有在i处闸机验票,
假设cbi是从Si 站出去换乘其它的线,而我们没有统计到的人次
接下来 我们就能得到一个模型了, 我们就实在不考虑,钻闸机进出站的,能被我们的计数器统计到而不能被地铁系统统计到的人了!他们不贡献营收,却被我们观测了,实际操作时可以忽略这部分数量,也可以剔除。
E[Mai+cai]=E[Mbi+cbi], i 遍历1,2,3, ...,n
其实这成为了帮我们解决问题的一个条件,
那么,我们要求的问题,实际就是:
E[ E[ p(Si,Sj)* L(Si ,Sj )] ] i,j 需要遍历1,2,3...,n,
其中 L(Si ,Sj )就表示从 i 站 到 j 站这一天的人次,包括从 i 站进,从 j 站出的人次,和,从外线转到2号线 i
站,从 j 站 出的人,和 从 i 站进没从 j 站出但从 j 站换乘去其他站的人次,写出来就是
L(Si,Sj)= L0(Si,Sj)+ cai + cbi
接下来,我们就要把我们统计到的信息,转化为我们要求的信息,也就是要发现,进站人次,出站人次,和
从i 站进从 j 站出的人次之间的关系了,(看来为了适应模型的简便性,我们还是要将该问题纳入一个有向图的问题。)
进站人次 Mai=E [ L(Si , Sj)],其中,需要,j 遍历1,2,... , n
出站人次 Maj=E [ L(Si , Sj)],其中,需要,i 遍历1,2,... , n
============================================================================
现在总结一下,我们得到的模型,
求: E[ E[ p(Si,Sj)* L(Si ,Sj )] ] i,j 需要遍历1,2,3...,n,其中i,j是有先后的,
已知条件: E[Mai+cai]=E[Mbi+cbi], i 遍历1,2,3, ...,n
L(Si,Sj)= L0(Si,Sj)+ cai + cbi
Mai=E [ L(Si , Sj)],其中,需要,j 遍历1,2,... , n,即Si
Maj=E [ L(Si , Sj)],其中,需要,i 遍历1,2,... , n
Mbi=E [ L(Si , Sj)],其中,需要,j 遍历1,2,... , n
Mbj=E [ L(Si , Sj)],其中,需要,i 遍历1,2,... , n
已知,Mai、Mbi 是正整数。
============================================================================
分析整个问题,这好像是一个二部图,就是知道了顶点的度,需要求边的个数,所以,接下去的问题的重点,就是把这个问题解出来。
不难发现要解的问题是线性问题,只要我们求出L(Si ,Sj ),就能得到最后的答案,为了得到答案,我们清晰化这个图。
---------------------------------------------------------------------------------------------------------------------------------------------------------
但是我们只知道,这个二部有向图的所有点的出度和入度,也就是,我们把二号线的站点看做了二部图的点,
把从i 到 j 是Si 点 到 Sj 点的有向边,我们把这个图叫做G:
G的点就是2号线的所有站点(注意,包括两个方向),G的边就是某个人一次从2号线站点上并且在2号线站点下乘地铁行为。
我们看到如果我们研究的问题其实是终点 或者 始点是2号线的有向图问题,我们将牵扯到其他地铁线的部分也考虑进来,形成
一个G*图,就是包含Non Line 2 部分的图。
G*的边就是某人一次乘地铁的行为经过了2号线的站点(注意,不一定以2号线的站点作为始点或终点),G*的点就是能允许这种行为发生的所有地铁线路上的站点。
---------------------------------------------------------------------------------------------------------------------------------------------------------
Mai 是Si 站的出度,Mbi是Si 站的入度,也就是,
inDeg(G,Si)=Mbi + cai ,outDeg(G,Si)=Mai + cbi
L(i,j)是整数,而且肯定有界,所以一定可以找到可行解,而且,如果解的组数越少,越好,也就是我们至少
可以得出2号线营收的一个范围区间。