采矿系统工程4.pptVIP

最短路问题 引例：在企业的经营活动和日常生活中，经常会遇到所谓最短路问题。当你从家中出发上班时，面临着走怎样的路线才能在最短时间内到达单位；当你假日外出旅游时，怎样选择旅游路线使花费最省；在企业经营中，譬如要运送一批物资到达某地，应沿着怎样的路线运输，才能使其运输费用最省，还有诸如管道铺设，设备更新等问题，都属于最短路问题。 最短路问题就是要求从始点V1到终点V9的一条有向路线，使其在所有以V1到V9的有向路线中，它是权数最小的一条。 算法 算法开始时给发点s标上固定标号P（s）=0，这表示从s到s的最短距离为零。其余顶点标上临时标号T（j）=∞。 例：用迪克斯屈拉法求图中①-⑥的最短路距离和其路线。（最短距离和路线 ） （4）与顶点③直接相连的为顶点②和⑤，其T类标号改为： T’（2）=min[T（2），P（3）+W32]=min[4，3+2]=4 T’（5）=min[T（5），P（3）+W35]=min[∞，3+2]=5 （10）对于顶点④有： T’（6）=min[T（6），P（4）+W46]=[9，7+3]=9. 思路：反向逆算。 具体：与⑥直接相连的为④，⑤，而P（6）与P（4）、P（5）之差分别为2和4，而与顶点⑥相连的弧长中只有⑤—⑥的距离为4。因此顶点⑤在顶点⑥之前。类似可以得出顶点③在顶点⑤之前，而最短路①—③—⑤—⑥；或者可以得出顶点②在顶点⑤之前，顶点1在顶点2之前，即另一条最短路为①—②—⑤—⑥。其最短距离都为9。 设备更新问题例：某企业使用一种设备，在每年年初，决策者需要决定是否购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的，需要支付一定的维修费用。现在的问题是如何制定一个五年计划，使总的支付费用最少，表1为设备在各年年初的价格，表2为使用不同时间的设备所需要的维修费用。 解：（1）分析：显然可以选择的设备更新方案是很多的。例如每年 都更新一台新设备，其购置费用为（11+11+12+12+13）万元=59万元，而每年支付的维修费用为5万元，五年的合计为25万元，于是五年的支付费用为（59+25）=84万元。 又如可决定在第一，三，五年各购置一台，这个方案的设备购置费用为（11+12+13）=36万元，维修费用为（5+6+5+6+5）=27万元，五年总费用为63万元。 （2）用点Vi代表“第i年年初购金进一台新设备”这种状态（V6为第5年年底的末状态。从Vi到Vi+1—V6各画出一条弧，弧（Vi，Vj）表示第i年年初购进的设备一直使用到第j年年初）。 每条弧的权可按已知资料计算出来。如（V1，V4）是第一年年初购进的一台设备（支付购置费用为本11万元），一直使用到了第3年年底（支付维修费用为5+6+8=19万元），故（V1，V4）权重为30万元。 选址问题（即在一指定的区域内选择服务性设施如医院、学校等最佳位置问题。解决这类问题的关键是求出相应的图中所有最短路。例：已知一个村庄的距离如图所示，各村的小学生人数如表所示。现计划在这片区域內建设一个小学。问学校建在哪个村使最远的村庄到学校的距离最短？又问学校建在哪个村使得所有学生上学走得路程最短？ 解：利用最短路解法首先求出任意两点Vi，Vj间的最短路线Sij，用矩阵表示，如图所示。 学校建在哪个村使得所有学生上学走得路程最短？ 设想小学建立在Vj，则其他村庄的小学生们所走的路程是： 50S1j+40S2j+60S3j+20S4j+70S5j+90S6j 对每一个点求出这个数值，它们的最小数值所对应的Vj就是要选择的最佳位置，这相当于： C=（50，40，60，20，70，90） C·S=（2130，1670，1070，1040，1050，1500）一个 所以建立在V4。 练习题：1、某车队要从甲市运送一批货物到乙市，中间可穿行的市镇与行车道如下图所示，试找出甲市到乙市的最短路线。 * * 例：从油田铺设管道，把原油运到原油加工厂。要求管道必须沿下图所给定的管线铺设。图中V1点为油田，V9点为原油加工厂，赋权为该条管道的长度，要求使管道总长最短的铺设方案。 V4 V2 V1 4 6 4 2 V7 4 V5 2 4 4 4 6 V3 V8 V6 V9 8 6 解：显而易见，方案较多：如沿V1→V2→V4→V7→V9，V1→V3→V5→V8→V9，V1→V3→V6→V8→V9 思路：对每一个顶点给定一个标号。标号分临时标号T （ T标号,Temporary）和固定标号P （P标号,Permanent ）。顶点i的临时标号记成T（i），它表示始点S到顶点i的最短距离的上界；顶点i的固定标号记