计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2015年
8期
2268-2271
,共4页
网络优化%最大利润流%破圈算法%最大流%最小费用流%费用圈
網絡優化%最大利潤流%破圈算法%最大流%最小費用流%費用圈
망락우화%최대리윤류%파권산법%최대류%최소비용류%비용권
network optimization%maximum profit flow%circle-canceling algorithm%maximum flow%minimum cost flow%profit cycles
仿照最小费用最大流问题的物理意义,将网络上的费用参数转换成为一种利润参数,提出一个与最小费用最大流问题类似、但意义完全相反的最大利润最小流问题,并建立了该问题的数学规划模型.此外,提出了一个求解该问题最优解的破除可增利润圈算法,该算法通过不断破除网络上的可增利润圈增流,使目标函数值不断增长,最终得到问题的最优解及目标函数值;同时给出了关于该算法正确性的证明过程,并对算法的复杂度进行了分析,最后用示例对算法的求解过程进行了演示.结果表明,该算法能快速有效地求得该问题的最优解及目标函数值,且比一般的线性规划方法更加方便且直观得多.
倣照最小費用最大流問題的物理意義,將網絡上的費用參數轉換成為一種利潤參數,提齣一箇與最小費用最大流問題類似、但意義完全相反的最大利潤最小流問題,併建立瞭該問題的數學規劃模型.此外,提齣瞭一箇求解該問題最優解的破除可增利潤圈算法,該算法通過不斷破除網絡上的可增利潤圈增流,使目標函數值不斷增長,最終得到問題的最優解及目標函數值;同時給齣瞭關于該算法正確性的證明過程,併對算法的複雜度進行瞭分析,最後用示例對算法的求解過程進行瞭縯示.結果錶明,該算法能快速有效地求得該問題的最優解及目標函數值,且比一般的線性規劃方法更加方便且直觀得多.
방조최소비용최대류문제적물리의의,장망락상적비용삼수전환성위일충리윤삼수,제출일개여최소비용최대류문제유사、단의의완전상반적최대리윤최소류문제,병건립료해문제적수학규화모형.차외,제출료일개구해해문제최우해적파제가증리윤권산법,해산법통과불단파제망락상적가증리윤권증류,사목표함수치불단증장,최종득도문제적최우해급목표함수치;동시급출료관우해산법정학성적증명과정,병대산법적복잡도진행료분석,최후용시례대산법적구해과정진행료연시.결과표명,해산법능쾌속유효지구득해문제적최우해급목표함수치,차비일반적선성규화방법경가방편차직관득다.
