| 最小费用增益流 |
| |
| 引用本文： | 金旺春
,左垲,刘根泉.最小费用增益流[J].五邑大学学报(社会科学版),1989(3). |
| |
| 作者姓名： | 金旺春 左垲 刘根泉 |
| |
| 作者单位： | 中国科技大学北京研究生院，中国科技大学 |
| |
| 摘 要： | 本文研究了具有分段线性费用的最小费用增益流问题。由于求满足边界条件的最短轨问题是NP完全问题4,5],因此我们采用了线性规划的方法。本文提出了一系列与分段线性费用相对应的定理和概念,在此基础之上描述了一个初始对偶算法,它是Jewell算法3]的自然推广,它完善了初始化的算法,是有效的, 计算复杂度为o((m n)~3n)。
|
| 关 键 词： | 最小费用 增益 分段线性费用 初始—对偶 单纯形算法 网络 计算复杂度 |
The Minimum Cost Flows in a Network with Gains |
| |
| Jin Wangchun Zuo Kai Liu Genquan.The Minimum Cost Flows in a Network with Gains[J].Journal of Wuyi University(Social Sciences Edition),1989(3). |
| |
| Authors: | Jin Wangchun Zuo Kai Liu Genquan |
| |
| Institution: | Jin Wangchun Zuo Kai Liu Genquan |
| |
| Abstract: | This paper studies the problem of the Minimum Cost Flows in a Network with Gains,in which each edge's cost is the piecewise-linear cost. Since the problem of finding the shortest path subject to side constraints is HP-complete, we suggest and describe a Primal-Dual Simplex Algorithm for Solving it.It is a natural generalization of Jewell's Algorithm 3],and perfects iaitializatioa of the algorithm.It is effective.It's computational complexity is O((m n) 3n) . |
| |
| Keywords: | Minimum cost Gain Piecewise-Linear Cost primal-dual Simplex Algorithm Network Computational Complexity |
| 本文献已被 CNKI 等数据库收录！ |
