| 带有时间和费用双重限制的网络容量扩充问题 |
| |
| 引用本文： | 王里平,王书振,徐国华.带有时间和费用双重限制的网络容量扩充问题[J].计算机工程与应用,2003,39(11):176-178. |
| |
| 作者姓名： | 王里平 王书振 徐国华 |
| |
| 作者单位： | 1. 吕梁高等专科学校计算机系,离石,033000
2. 西安电子科技大学机电工程学院,西安,710071 |
| |
| 摘 要： | 该文将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题的一般模型。通过网络变换,将带有时间限制的容量扩充问题转化为线性最小费用流问题,并给出了具体证明和求解容量扩充问题的算法。该模型和算法不仅适用于各种情形的容量扩充问题,而且还可应用于网络流规划。最后通过具体例子的求解,说明了模型和算法的正确性和有效性。
|
| 关 键 词： | 网络流 容量扩充 瓶颈问题 |
| 文章编号： | 1002-8331-(2003)11-0176-03 |
| 修稿时间： | 2003年2月1日 |
The Network Capacity Expansion Problem with the Time and Cost Constraints |
| |
| Wang Liping,Wang Shuzhen,Xu Guohua.The Network Capacity Expansion Problem with the Time and Cost Constraints[J].Computer Engineering and Applications,2003,39(11):176-178. |
| |
| Authors: | Wang Liping Wang Shuzhen Xu Guohua |
| |
| Affiliation: | Wang Liping 1 Wang Shuzhen 2 Xu Guohua 21 |
| |
| Abstract: | In this paper,the network capacity is defined as the value of the maximum s-t flow,and a unified model is introduced for the network capacity expansion with the time and cost constraints(NCE).By the transformation of the network,it is converted to a minimum cost flow problem instead.Also developed are the valid proofs for the transformation and the algorithm for the NCE.The model and algorithm allow to not only capture various types of capacity expansion,but also are useful in network flow programming.Finally,the validity of the model and algorithm is illustrated by two examples. |
| |
| Keywords: | Network flow Capacity expansion Bottleneck problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
