带有时间和费用限制的网络容量扩充问题

摘要

研究了带有时间和费用双重限制下的网络容量扩充问题,即在满足时间和费用约束条件下,如何扩充网络中某些弧的容量使扩充后的网络容量尽可能的大.通过将问题转化为求其最小生成树,给出了其求解算法.由于在扩充时两个约束条件一般有一者剩余,为了合理配置扩充资源,讨论了给定容量要求下关于时间和费用的Pareto优化解的情况并给出了有效算法,用实例来证明了算法的有效性.