《物流运输管理计算题复习》由会员分享，可在线阅读，更多相关《物流运输管理计算题复习（31页珍藏版）》请在金锄头文库上搜索。
1、一、泊位通过能力计算二、列车编组计划一、算法原理假定存在一个方向上每支车流在途中每个支点站都改编的编组方案（即一支直达列流也没有的方案）。这样，任何一个编组方案与它比较，只要有某支车流（设车流量为N通）在某支点站无改编通过，相对于这个假想的方案就有车小时节省N通t节。把方案中有无改编通过车流的支点站集合记作W，设 ，在w站无改编通过的车流量为 ，w站的t节为 ，则直达车流无改编通过途中支点站的车小时总节省F通为以F节表示编组方案总的车小时节省，则目标函数为：就算法思想而言，表格计算法并不对全部编组方案计算方案值，而是利用几个判别条件，把肯定有利的列流（如果存在的话）首先确定下来，把不合理的列流
2、排除在外，对可能有利的列流，按不同的车流合并方式计算车小时节省，然后加以比较选择。这些判别条件包括绝对条件、必要条件和充分条件。 1.绝对条件该支车流在沿途任一支点站无改编通过的车小时节省都不小于该车流编开直达列流在列车始发站的集结车小时消耗。其中,K为直达车流（i, j）的途中支点站集合例题 由绝对条件可以得到一个推论：若则车流(i，j)不应在站k改编。此时，称车流(i，j)在支点站k满足了绝对条件。【例】下图表示出5个支点站方向的6支直达车流量、各支点站的T集和t节。因为：所以，车流（4，1）和（2，0）满足了绝对条件，应当开行直达列流和，并归入最优编组方案中。 2.必要条件该支车流无改编
3、通过沿途支点站所获得的车小时总节省不小于该车流编开直达列流在列车始发站的集结车小时消耗，即若干支直达车流（设其中最短的车流为（i,j），总车流量为 ）合开的必要条件是：这些车流合并之后无改编通过沿途支点站所获得的车小时总节省不小于它们合开直达列流在列车始发站的集结车小时消耗，即3.充分条件一支（或几支合并的）长程车流不与某支（或几支相互衔接的）短程车流合并的充分条件是：长程车流在其超行区段无改编通过支点站的车小时总节省不小于该车流编开直达列流在始发站的集结车小时消耗。这里所谓“超行区段”，是指长程车流比短程车流多运行的那部分区段。A B C D E Cm 600 550 500 t节 2.5
4、3.0 2.012030013060110100250120180100例、按给定资料，用表格计算法求最优编组方案，并绘制到达站图。250250250改编能力v解：1）计算Nt节2）确定初始方案N14，N35满足绝对条件；N25满足必要条件；N15可以合并到N14中。600260390300120180150750625450A B C D E Cm 600 550 500 t节 2.5 3.0 2.0120300130601101002501201801001203001306011010025012018010012030013060110100250120180100v 3）调整6002
5、60390300120180150750625450（1）N25压缩发站，N25与N35合 并。节省550390=160车小时250250250（2）无法再调整，该方案即为 最优方案。检查沿途各站的改 编车数。180230604）画出列流图二、1616E.W.Dijkstra 算法（标号算法） 算法基本思路分析：（逐步向外搜索）521658289972212102527 5111212105756 679 910106 3 3xy起点到 该点的 最短距 离起点到 该点的 最短距 离的上 界三、最短路问题1717v路与最短路问题 v最短路问题 v例 选址问题（网络的中心、重心） v 南京军区某分
6、部7个仓库之间的现有交通道路如下图，边旁数值为 各仓库之间道路的长度（单位：百公里），点旁数值为各仓库每天所需军 用物资的量（单位：吨），现拟在某一仓库所在地建一物流中心，试问： v（1）若以仓库到物流中心的距离为标准，问物流中心应该建在何处，才 能使各仓库都离它较近？ v（2）若以物流的周转量（吨公里）为标准，问物流中心应该建在何处， 才能使总的物资周转量最小？1818v网络的中心、重心v1v3v4v5v6v7v27464 35712324230404535252050距离物资需求 量1919v路与最短路问题 v网络的中心、重心 v距离矩阵摹乘法 v求各点至各点的最短距离 v网络的距离矩阵
7、v 设一网络 N 中有n 个点，其中任意两点 vi 与 vj 之间都有一条边 ( vi, vj )，其权数为 wij - 。若 vi 与 vj 不相邻，则虚设一条边( vi, vj )，并令其权数wij = 。 v距离矩阵 W = （ wij ）2020v路与最短路问题 v网络的中心、重心 v距离矩阵摹乘法v1v3v4v5v6v7v2746435712324230404535252050W =v1 v2 v3 v4 v5 v6 V7 v1 0 3 4 7 v2 3 0 3 2 4 v3 4 3 0 5 7 v4 7 2 0 2 6 v5 4 5 2 0 1 4V6 7 1 0 2V7 6 4
8、2 02121v路与最短路问题 v网络的中心、重心 v距离矩阵摹乘运算 v记矩阵 Dk = （d（k）ij）nn v当 k = 1 时，令 v D1 = （d（1）ij）nn = （wij）nn = W v定义 Dk = Dk-1 Dk-1 ， （k = ，1，2，p）摹乘运算 v其中 v d（k）ij = min d（k-1）is + d（k-1）sj ，i ，j = 1，2，n v摹乘运算的含义： v 表示从各点走 2k-1 步达到各点的最短距离矩阵。而 D 即给出各 点到各点的最短距离。若计算中出现 Dk = Dk-1 ，也可结束。s2222v路与最短路问题 v网络的中心、重心 v设 D
9、 = （dij）nn 为一网络各点间的最短距离矩阵。v（ 1 ）网络的中心令： d( vi ) = max dij , i = 1, 2, , n若 d( vk ) = min d( vi ) 1in1jn则称点 vk 为网络的中心。2323v路与最短路问题 v网络的中心、重心v（ 2 ）网络的重心 v 设 gi 为点 vi 的权重（ i = 1, 2, , n ），令： h ( vj ) = gidij , j = 1, 2, , ni=1n若 h( vr ) = min h( vj ) 1jn则称点 vr 为网络的重心。2424v路与最短路问题 v网络的中心、重心 v前例vjviD = (
10、 dij )d( vi )= max dij 123456710345781010230324577343055688452502355 ( min )57452013768563102871078532010结论：（1）问中的 物流中心应该建在 v4 处（ v4处是网络的中心）。2525v路与最短路问题 v网络的中心、重心vjvigidij12345671012016020028032040027507550100125175318013502252252703604150601500609015051408010040020606280175210105350707500350400250
11、1501000h ( vj )13259201095870850 ( min )9251215结论： （2）问中物流中心应该建在 v5 处（ v5 处是网络的重心）。四、运输方案图上作业法运输线路成圈的图上作业法v 运输线路成圈，就是形成闭合回路的“环”形路线，包括一个圈（有三角形、四边形、多边形）和多个圈。成圈的线路流向图要同时达到既无对流现象、又无迂回现象的要求才是最优流向图。v 对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案，如表9-22所示。表9-22 成圈运输线路的图上作业法的步骤 步骤详 述去段破圈 确定初始 运输方案就是在成圈的线路中，先假设某两点间的线路“不通”，去
12、掉这段 线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成 圈的图上作业法，即可得到初始运输方案。检查有无 迂回现象因为为流向箭头头都统统一画在线线路右边边，所以圈内圈外都画有一些 流向。分别检查别检查 每个小圈，如果圈内和圈外流向的总长总长 度都不超过过全 圈总长总长 度的1/2 ，那么，全圈就没有迂回现现象了，这这个线线路流向图图 就是最优优的，对应对应 的就是最优优运输输方案。否则转则转 向第三步。重新去段 破圈，调 整流向在超过过全圈总长总长 1/2 的里（外）圈各段流向线线上减去最小运量， 然后在相反方向的外（里）圈流向线线上和原来没有流向线线的各段上， 加上减去的最小运量
13、，这样这样 可以得到一个新的线线路流向图图，然后转转到 第二步检查检查 有无迂回现现象。如此反复，直到得到最优线优线 路流向图为图为 止 。如果全圈存在两个及两个以上的圈，则则需分别对别对 各圈进进行是否存 在迂回线线路的检查检查 ，如果各圈的里、外圈都不超过过全圈总线长总线长 的 1/2 ，则则不存在迂回现现象，此方案为为最优优运输输方案。(13)(13)(18)(18)3030v树（Tree）和最小树 v树是图论中一类重要的图，实际中很多系统的结构都是树。 v树连通且不含圈的图，简记为 T 。 v 树的性质： （1）在树中，任意两个顶点间必有且仅有一条链； （2）在树中，在不相邻的顶点中添加一条树枝，则恰好得到 一个圈； （3）在树中，任意去掉一条树枝，就变成分离图； （4）设T是棵有n个顶点的树，则T的树枝数为n-1； （5）一棵树至少有两个悬挂点； （6）树是连通且边数最少的图。五、最小树问题与网络设计3131v最小树问题 v树（Tree）和最小树v树的权 若Tk是加权图G的一棵树，则树T的全部边的 权之和称为树Tk的权，记为 （ Tk ）= （e）； e Tk v最小树 T*是加权图G的一棵最小树，即（ T* ） =min (Tk) v最小树问题 v树
