最短路扩展应用问题

设备更新问题。某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（4年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制订今后4年的机器更新计划，使总的支付费用最少。第i年初1234购置费（万元）2.52.62.83.1使用年限1234每年的维修与运行费（万元）11.524又如果已知不同役龄机器年末的处理价格如下表所示，那末在这计划期内机器的最优更新计划又会怎样？年度第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}，即计划期内机器更新最优计划为第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万单位/月速度递增。