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