用对偶原理求解最小费用流的一种新算法

J4 ›› 2011, Vol. 46 ›› Issue (6): 99-102.

用对偶原理求解最小费用流的一种新算法

熊德国1, 胡勇文1, 施建明2

1. 河南理工大学能源科学与工程学院, 河南焦作 454000;
2. 室兰工业大学情报工学科, 日本北海道室兰, 0500071

收稿日期:2010-10-17 出版日期:2011-06-16 发布日期:2011-12-19
作者简介:熊德国(1964- ),男,副教授,博士,主要从事系统优化与应用方面的研究. Email: xiongdg@hpu.edu.cn
基金资助:
国家自然科学基金资助项目(51074066);河南理工大学教改重点项目(2009JGD42)

A new algorithm for solving minimum cost flow with the duality principle

XIONG Deguo1, HU Yongwen1, SHI Jianming2

1. School of Energy Science and Engineering, Henan Polytechnic University, Jiaozuo 454000, Henan, China;
2. College of Information and Electronic Engineering, Muroran Institute of Technology, Muroran, 0500071, Hokkaido, Japan

Received:2010-10-17 Online:2011-06-16 Published:2011-12-19

摘要/Abstract

摘要：

基于对偶原理提出了求解最小费用流的一种新算法,该算法不需要传统方法中的构造剩余网络以及求最短路等步骤,而是保持互补松弛条件不变,通过在原网络中修改节点的势,给节点标号寻求目标流。并给出了新算法正确性的证明。算例表明该算法可明显减少迭代步骤。

关键词: 最小费用流;对偶原理;新算法

Abstract:

A new algorithm is proposed to solve the problem of minimum cost flow by a dual approach, which held complementarity conditions to the dual problem and found a desired flow by modifying the potential and labeling for each node of the network. Unlike existing algorithms, the new algorithm did not construct a residual network nor find the shortest path. The validity of the new algorithm is proved, and an example is given to illustrate the behavior of the proposed algorithm.

Key words: minimum cost flow; duality principal; new algorithm

熊德国1, 胡勇文1, 施建明2. 用对偶原理求解最小费用流的一种新算法[J]. J4, 2011, 46(6): 99-102.

XIONG Deguo1, HU Yongwen1, SHI Jianming2. A new algorithm for solving minimum cost flow with the duality principle[J]. J4, 2011, 46(6): 99-102.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed