| 最大利润流问题及算法 |
| |
| 引用本文： | 卢虎生,高学东,武森.最大利润流问题及算法[J].数学的实践与认识,2003,33(5):43-48. |
| |
| 作者姓名： | 卢虎生 高学东 武森 |
| |
| 作者单位： | 北京科技大学,北京,100083 |
| |
| 摘 要： | 最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .
|
| 关 键 词： | 最大利润流 最小费用流 最大流 |
| 修稿时间： | 2002年11月28 |
An Algorithm for Maximum Profit Flows |
| |
| LU Hu-sheng,GAO Xue-dong,WU Sen.An Algorithm for Maximum Profit Flows[J].Mathematics in Practice and Theory,2003,33(5):43-48. |
| |
| Authors: | LU Hu-sheng GAO Xue-dong WU Sen |
| |
| Abstract: | A maximum profit flows(MPF) problem is a network optimization problem aiming to get maximum transport profit. A feasible MPF can be decomposed into a few path flows and a few circle flows, and consequently the profit of MPF is divided into the profit of those path flows and circle flows. We present a basic algorithm to find the solution by augmenting flow on profit augmenting path until no path exists based on the proved theorem that a feasible flow f is a maximum profit flow if and only if there is no augmenting path with respect to f. |
| |
| Keywords: | maximum profit flow minimum cost flow maximum flow |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
