目录
- 例 1: 设备更新问题
- 例 2: 重心问题
某种工程设备的役龄为 4 年, 每年年初都面临着是否更新的问题: 若卖旧买新, 就要支付一定的购置费用; 若继续使用, 则要支付更多的维护费用, 且使用年限越长维护费用越多. 役龄期内每年的年初购置价格, 当年维护费用及年末剩余净值如下表所示. 为该设备制定一个 4 年役龄期内的更新计划, 使总的支付费用最少.
可以把这个问题化为图论中的最短路问题.
构造赋权有向图 
讯享网, 其中顶点集 , 这里 表示第 年年初的时刻, 表示第 4 年年末的时刻, 为边集, 邻接矩阵 , 这里 为第 年年初至第 年年初 (或 年年末) 期间所支付的费用, 计算公式为
其中 为第 年年初的购置价格, 为使用到第 年当年的维护费用, 为使用
则邻接矩阵
则制定总的支付费用最小的设备更新计划, 就是求有向图 从顶点 到页点
求得 到 的最短路径为 , 最短路径的长度为67. 即设备更新计划为第1年年初买进新设备, 使用到第 1 年年底, 第 2 年年初购进新设备, 使用到第 2 年年底, 第 3 年年初再购进新设备, 使用到第 4 年年底.
重心问题指有些公共服务设施 (例如邮局, 学校等) 的选址, 要求设施到所有服务对象点的距离总和最小. 一般要考虑人口密度问题, 或者全体被服务对象来往的总路程最短. 例如下面的问题:
某矿区有六个产矿点, 如图所示, 已知各产矿点每天的产矿量 (标在图中的各顶点旁) 为
令 表示顶点 与 之间的距离. 若选矿厂设在 并且各产矿点到选矿厂的总运力为 , 则确定选矿厂的位置就转化为求 , 使得 .
由于各产矿点到选矿厂的总运力依赖于任意两顶点之间的距离, 即任意两顶点之间最短路的长度, 因此可首先利用 Dijkstra (或 Floyd) 算法求出所有顶点对之间的最短距离, 然后计算出顶点 设立选矿厂时各产矿点到 的总运力
最后利用
计算的 Python 程序如下:
, 所以
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/180977.html