计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
3期
446-451
,共6页
双费用权网络%最小双费用流%双层原始对偶算法%复杂度
雙費用權網絡%最小雙費用流%雙層原始對偶算法%複雜度
쌍비용권망락%최소쌍비용류%쌍층원시대우산법%복잡도
double-cost network%minimum double-cost flow%two-layer primal-dual algorithm%complexity
多目标优化是网络最优化的一个重要子问题.通过实际应用案例,抽象出一种带容量限制的双费用权网络模型,并由此提出了相应的最小双费用流问题.之后,借鉴网络分层的思想,根据双费用权网络的特点设计出一个求解该问题的双层原始对偶算法,并严谨地证明了算法的正确性,估计出算法的复杂度为O(n2v0).此外,对算法进行了推广改进,使其能求解一般k费用权网络中的最小k费用流问题.最后,通过一个实例来演示算法的执行.
多目標優化是網絡最優化的一箇重要子問題.通過實際應用案例,抽象齣一種帶容量限製的雙費用權網絡模型,併由此提齣瞭相應的最小雙費用流問題.之後,藉鑒網絡分層的思想,根據雙費用權網絡的特點設計齣一箇求解該問題的雙層原始對偶算法,併嚴謹地證明瞭算法的正確性,估計齣算法的複雜度為O(n2v0).此外,對算法進行瞭推廣改進,使其能求解一般k費用權網絡中的最小k費用流問題.最後,通過一箇實例來縯示算法的執行.
다목표우화시망락최우화적일개중요자문제.통과실제응용안례,추상출일충대용량한제적쌍비용권망락모형,병유차제출료상응적최소쌍비용류문제.지후,차감망락분층적사상,근거쌍비용권망락적특점설계출일개구해해문제적쌍층원시대우산법,병엄근지증명료산법적정학성,고계출산법적복잡도위O(n2v0).차외,대산법진행료추엄개진,사기능구해일반k비용권망락중적최소k비용류문제.최후,통과일개실례래연시산법적집행.
