Article ID: | iaor20013562 |
Country: | Singapore |
Volume: | 17 |
Issue: | 2 |
Start Page Number: | 149 |
End Page Number: | 168 |
Publication Date: | Nov 2000 |
Journal: | Asia-Pacific Journal of Operational Research |
Authors: | Maruyama Yukihiro |
Keywords: | duality |
We study optimal (shortest or longest) path problems depending on a parameter in directed networks. In the parametric optimal path problems, path lengths are defined through various associative binary operations: addition, multiplication, fraction and so on. Solving a system of two interrelated functional equations, we simultaneously find both shortest and longest path lengths for all values of the parameter space which is a subset of the real line. Moreover, for every parametric problem (primal problem), we associate another closely related problem (dual problem) where each arc length is the complementary function and path lengths are defined through the associative binary operation which is related to it in the primal problem by DeMorgan's law. The main purpose of this paper is to derive duality theorems between the primal problem and the dual one.