【摘要】 提出了点和边都带有成本约束的最短路问题 ,证明了该问题是NP 完全的 .建立了这类问题的数学规划模型 ,并采用拉格朗日松弛算法对模型进行求解 ,给出了次梯度优化求解算法的一般步骤 .考虑到算法在实际求解过程中收敛速度较慢的问题 ,进一步对拉格朗日松弛算法进行了2个方面的改进 ,一方面确定适当的迭代步长 ,另一方面选择较好的迭代方向 .算法实例表明 ,改进后的拉格朗日松弛算法迭代步数显著减少 ,证明算法是有效的更多还原

【Abstract】 The shortest path (SP) problem with constraints of node’s cost and edge’s cost is put forward, and it is proven to be NP complete. A mathematics programming model of this modified SP is proposed. To solve this model Lagrangean relaxation algorithm is adopted. The general algorithm steps based on subgradient optimization mathematics method are presented. In view of the weak convergence performance in this algorithm, the Lagrangean relaxation algorithm is modified in two points, i.e. determining a proper step length and choosing a better iterative direction. Computational examples show that the modified subgradient optimization algorithm for Lagrangean relaxation can reduce the iterative steps obviously, and is proved to be efficient.更多还原