最短路应用问题课件.ppt

设备更新问题。某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（4 年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制订今后 4 年的机器更新计划，使总的支付费用最少。,又如果已知不同役龄机器年末的处理价格如下表所示，那末在这计划期内机器的最优更新计划又会怎样？,解：关于第一问，把该问题看成一个最短路问题。设 v1 和 v5 分别表示计划期的始点和终点（x5 可理解为第4年年末）。图中各边(vi,vj)表示在第 i 年初购进的机器使用到第 j 年初（即第 j 1 年底），边旁的数字由表中的数据得到。,关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。按照最短路算法可得最短路 v1,v2,v3,v5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。,选址问题。选址问题是指为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值。选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准，有许多不同类型的选址问题。比较简单的两类选址问题是中心问题和重心问题。,中心问题：有些公共服务设施（例如一些紧急服务型设施如急救中心、消防战等）的选址，要求网络中最远的被服务点距离服务设施的距离尽可能小。例如：某城市要建立一个消防站，为该市所属的七个区服务，如下图所示。问应设在那个区，才能使它至最远区的路径最短。,解：(1)用 Floyd 算法求出距离矩阵 D=(dij)vv：,(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 处。此点称为图的中心点。,选址问题2,现准备在 n 个居民点v1,v2,vn中设置一银行.问设在哪个点,可使最大服务距离最小?若设置两个银行,问设在哪两个点?模型假设 假设各个居民点都有条件设置银行,并有路相连,且路长已知.模型建立与求解 用Floyd算法求出任意两个居民点vi,vj 之间的最短距离,并用dij 表示.,设置一个银行,银行设在 vi 点的最大服务距离为,求k,使,即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小.设置两个银行,假设银行设在vs,vt 点使最大服务距离最小.,记,则s,t 满足：,进一步,若设置多个银行呢？,重心问题：有些设施（例如一些非紧急型的公共服务设施，如邮局、学校等）的选址，要求设施到所有服务对象点的距离总和最小。一般要考虑人口密度问题，要使全体被服务对象来往的平均路程最短。例如，某矿区有七个矿点，如下图所示。已知各矿点每天的产矿量q(vj)（标在图的各顶点上），现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小。,解：(1)用 Floyd 算法求出距离矩阵 D=(dij)vv：(2)计算各顶点作为选矿厂的总运力 m(vi)(3)求 vk 使，则 vk 就是选矿厂应设之矿点。此点称为图的重心或中位点。,作业,某公司在六个城市C1，C6有分公司，从Ci到Cj的直接航程票记在下述矩阵的（i,j）位置上。该公司想要一张任两城市间的票价最便宜的路线表，试作出这样的表格,实验作业,生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益。,某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增。若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元。假定生产率每调整一次带有固定的调整费C1=1万元，试问工厂如何制定当年的生产策略，使工厂的总损失最小？,返回,