首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一个局部带优先权的最大多物资网络流问题
引用本文:程丛电,陈曦.一个局部带优先权的最大多物资网络流问题[J].数学的实践与认识,2014(3).
作者姓名:程丛电  陈曦
作者单位:沈阳师范大学数学与系统科学学院;辽宁工程技术大学理学院系统科学研究所;
基金项目:辽宁省教育厅科研基金(L2010514)
摘    要:给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.

关 键 词:多种物资网络流  紧急救援  优先权  松弛  算法

A Maximum Multicommodity Flow Problem with Local Priority
Abstract:We present a maximum multicommodity flow problem with local priority(MMFPLPRI),and prove the existence of its solutions.Moreover,we also propose the definition of η-relax solutions for the problem presented.By constructing the auxiliary network,and through implementing two partition search using the subprogram that designed by Cheng Cong-dian et al.basing on the multicommodity flow approximation scheme provided by Korte and Vygen(2000) from the works of Garg and Konemann(1998),Young(1995) and others for the approximation algorithm on Maximum Multicommodity Flow Problems,we design a pseudopolynomial algorithm to obtain the η-relax solution of MMFP-LPRI.Finally,we analyze the complexity of the algorithm and prove that the output of the algorithm designed is indeed an η-relax solution of MMFP-LPRI.
Keywords:multicommodity flow  emergency relief  priority  relax  algorithm
本文献已被 CNKI 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号