东南大学学报(自然科学版)
東南大學學報(自然科學版)
동남대학학보(자연과학판)
JOURNAL OF SOUTHEAST UNIVERSITY(NATURAL SCIENCE EDITION)
2003年
1期
111-114
,共4页
最短路问题%点、边带约束成本%拉格朗日松弛算法%次梯度算法
最短路問題%點、邊帶約束成本%拉格朗日鬆弛算法%次梯度算法
최단로문제%점、변대약속성본%랍격랑일송이산법%차제도산법
提出了点和边都带有成本约束的最短路问题,证明了该问题是NP-完全的.建立了这类问题的数学规划模型,并采用拉格朗日松弛算法对模型进行求解,给出了次梯度优化求解算法的一般步骤.考虑到算法在实际求解过程中收敛速度较慢的问题,进一步对拉格朗日松弛算法进行了2个方面的改进,一方面确定适当的迭代步长,另一方面选择较好的迭代方向.算法实例表明,改进后的拉格朗日松弛算法迭代步数显著减少,证明算法是有效的.
提齣瞭點和邊都帶有成本約束的最短路問題,證明瞭該問題是NP-完全的.建立瞭這類問題的數學規劃模型,併採用拉格朗日鬆弛算法對模型進行求解,給齣瞭次梯度優化求解算法的一般步驟.攷慮到算法在實際求解過程中收斂速度較慢的問題,進一步對拉格朗日鬆弛算法進行瞭2箇方麵的改進,一方麵確定適噹的迭代步長,另一方麵選擇較好的迭代方嚮.算法實例錶明,改進後的拉格朗日鬆弛算法迭代步數顯著減少,證明算法是有效的.
제출료점화변도대유성본약속적최단로문제,증명료해문제시NP-완전적.건립료저류문제적수학규화모형,병채용랍격랑일송이산법대모형진행구해,급출료차제도우화구해산법적일반보취.고필도산법재실제구해과정중수렴속도교만적문제,진일보대랍격랑일송이산법진행료2개방면적개진,일방면학정괄당적질대보장,령일방면선택교호적질대방향.산법실례표명,개진후적랍격랑일송이산법질대보수현저감소,증명산법시유효적.
