求解含负权弧的网络最小截问题

摘要：

对于经典网络最小截问题,所有弧权数非负,可运用最大流算法求解.但是对于广义最小截问题,若某些弧权数为负,则运用算法难以求解.针对含负权弧网络最小截问题,通过与经典最小截问题的对比,提出简单截集和复合截集概念,并给出广义网络最小截概念——截量最小的简单截集;引入负容量和负流量,给出求解含负权弧网络最小截问题的原理,并设计求解含负权网络最小截问题的网络流算法;最后,通过应用举例对算法进行演示.

关键词：运筹学、最小截、网络流算法、含负权弧的网络

所属期刊栏目：36

分类号：O221(运筹学)

资助基金：江西省教育厅科技项目GJJ161114

在线出版日期：2018-01-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：13-18