最短路应用问题课件

1、最短路应用问题课件 又如果已知不同役龄机器年末的处理价格如下表所示，那末在这计划期内机器的最优更新计划又会怎样？第1年末第2年末第3年末第4年末机器处理价（万元）2.01.61.31.1 解：关于第一问，把该问题看成一个最短路问题。设 v1 和 v5 分别表示计划期的始点和终点（x5 可理解为第4年年末）。图中各边 (vi , vj) 表示在第 i 年初购进的机器使用到第 j 年初（即第 j 1 年底），边旁的数字由表中的数据得到。 关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。 按照最短路算法可得最短路 v1, v2, v3, v5，即计划期内机器更新最优计划为

2、第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。 选址问题选址问题。选址问题是指为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值。选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准，有许多不同类型的选址问题。比较简单的两类选址问题是中心问题和重心问题。 中心问题：有些公共服务设施（例如一些紧急服务型设施如急救中心、消防战等）的选址，要求网络中最远的被服务点距离服务设施的距离尽可能小。例如：某城市要建立一个消防站，为该市所属的七个区服务，如下图所示。问应设在那个区，才能使它至最远区的路径最短。解：(1) 用 Floyd 算法求出距离矩阵 D

3、= (dij)vv： 05 . 15 . 55 . 86475 . 10475 . 45 . 25 . 55 . 54032475 . 8730571065 . 42502545 . 24720375 . 5710530D (2) 计算在各点 vi 设立服务设施的最大服务距离 S(vi) ，i = 1, 2, , v有：S(v1) = 10，S(v2) = 7，S(v3) = 6，S(v4) = 8.5，S(v5) = 7，S(v6) = 7，S(v7) = 8.5。 (3) 求出顶点 vk，使 ，则 vk 就是要求的建立消防站的地点。因为 S(v3) = 6最小，故应将消防站设在 v3 处。

4、此点称为图的中心点中心点。 max)(1ijjidvS)(min)(1iikvSvS选址问题选址问题2 2 现准备现准备在在 n 个个居民点居民点v1, v2, , vn中设置一银中设置一银行行. .问设在哪个点问设在哪个点, ,可使最大服务距离最小可使最大服务距离最小? ? 若设若设置两个银行置两个银行, ,问设在哪两个点问设在哪两个点? ? 模型假设模型假设 假设各假设各个个居民点都有条件设置银居民点都有条件设置银行行, ,并有路相连并有路相连, ,且路长已知且路长已知. . 模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi , vj 之间的最短

5、距离之间的最短距离, ,并用并用dij 表示表示. . 设置一个银行设置一个银行, ,银行设银行设在在 vi 点点的最大服务的最大服务距离为距离为.,.,2 , 1,max1niddijnji求求k, ,使使.min1inikdd 即若设置一个银行即若设置一个银行, ,则银行设在则银行设在 vk 点点, ,可使最可使最大服务距离最小大服务距离最小. . 设置两个银行设置两个银行, ,假设银行设假设银行设在在vs , vt 点点使最使最大服务距离最小大服务距离最小. .记记.,minmax),(1jkiknkddjid则则s, ,t 满足：满足：).,(min),(1jidtsdnji进一步进一

6、步, ,若设置多个银行呢？若设置多个银行呢？ 重心问题：有些设施（例如一些非紧急型的公共服务设施，如邮局、学校等）的选址，要求设施到所有服务对象点的距离总和最小。一般要考虑人口密度问题，要使全体被服务对象来往的平均路程最短。例如，某矿区有七个矿点，如下图所示。已知各矿点每天的产矿量q(vj)（标在图的各顶点上），现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小。 解：(1) 用 Floyd 算法求出距离矩阵 D = (dij)vv： (2) 计算各顶点作为选矿厂的总运力 m(vi) (3) 求 vk 使 ，则 vk 就是选矿厂应设

7、之矿点。此点称为图的重心重心或中位点中位点。 vidvqvmijjji , , 2 , 1 ,)()(1)(min)(1iikvmvm作业某公司在六个城市某公司在六个城市C1，C6有分公司，从有分公司，从Ci到到Cj的直接航程票记在下述矩阵的（的直接航程票记在下述矩阵的（i,j）位置上。该公）位置上。该公司想要一张任两城市间的票价最便宜的路线表，司想要一张任两城市间的票价最便宜的路线表，试作出这样的表格试作出这样的表格 055252510550102025251001020402010015252015050102540500实验作业实验作业 生产策略问题生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益。 某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增。若