0-1广义网络及网络设计问题

一、引言及模型网络和有向图相同的是,由节点和连结节点的弧的集合;此外,网络中每一条弧具有一个或多个权,以表示经过弧的流量的上、下界、费用等等.运输、供水、供电以及通讯网络都是这种网络的具体例子.网络设计中的一类重要问题,是对已有的网络系统加以扩充、更新、改造以使新的网络满足特定的要求,同时使新系统的运行费用加上更新改造投资总费用最小.由于投资费用是一次性的固定投入,因而这类问题是更广泛的固定支出问题的一种.Dantzig 等人在50年代初就建立了这样的模型,然而,正式发表是在1968年(见8]).用数学规划的语言,具有固定支出的网络设计问题,可以表示成以下0-1混合整数规划

0-1 GENERALIZED NETWORK AND NETWORK DESIGN PROBLEMS

Network degign with a fixed investment is a very difficult problem.In this paper a trans-formation of the problem into a 0-1 generalized network one is given and a new solution isobtained.Preliminary computation results indicate that the solution is quite efficient.