全部版块 我的主页
论坛 提问 悬赏 求职 新闻 读书 功能一区 经管百科 爱问频道
4811 4
2014-07-10
昨日去一家美国公司面试,遇到一道题:建模估算上海地铁2号线一天的营收。
虽然面试已结束,但对这题还是毫无头绪,特此请求大神帮忙,不胜感激。

二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2014-7-10 16:40:28

归结为已知图的度求边数问题和求解线性规划问题

如果出于某种目的,我们就是不能去询问地铁管理内部的人员和它们系统,只能从外界的角度去看,
只能用公共的信息去做这件事情的话,

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号线.bmp
  我们看到如果我们研究的问题其实是终点 或者 始点是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号线营收的一个范围区间。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2014-7-10 18:22:23
一个时间段内地铁的班次*该时间段总乘客上车人数*该时间段乘客的平均坐乘站数*每站分摊价格,然后把一整天所有时间段的数据加总不就行了。
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2015-2-4 17:20:45
EchoEstelle 发表于 2014-7-11 10:48
如果出于某种目的,我们就是不能去询问地铁管理内部的人员和它们系统,只能从外界的角度去看,
只能用公共 ...
太专业了, 膜拜!
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2015-2-4 17:20:54
EchoEstelle 发表于 2014-7-11 10:48
如果出于某种目的,我们就是不能去询问地铁管理内部的人员和它们系统,只能从外界的角度去看,
只能用公共 ...
太专业了, 膜拜!
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群