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