Premium
Ripples, complements, and substitutes in generalized networks
Author(s) -
Gautier Antoine,
Granot Frieda
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199602)43:1<1::aid-nav1>3.0.co;2-f
Subject(s) - monotonic function , mathematics , arc (geometry) , flow (mathematics) , sensitivity (control systems) , sign (mathematics) , function (biology) , traverse , flow network , task (project management) , maximum flow problem , ripple , mathematical optimization , mathematical economics , mathematical analysis , geometry , economics , physics , management , geodesy , quantum mechanics , voltage , electronic engineering , evolutionary biology , engineering , biology , geography
We extend the qualitative theory of sensitivity analysis for minimum‐cost pure network flows of Granot and Veinott [17] to generalized network flow problems, that is, network flow problems where the amount of flow picked up by an arc is multiplied by a (positive) gain while traversing the arc. Three main results are presented. The ripple theorem gives upper bounds on the absolute value of optimal‐flow variations as a function of variations in the problem parameter(s). The theory of substitutes and complements provides necessary and sufficient conditions for optimal‐flow changes to consistently have the same (or the opposite) sign(s) in two given arcs, whereas the monotonicity theorem links changes in the value of the parameters to changes in optimal arc flows. Bounds on the rates of changes are also discussed. Compared with pure networks, the presence of gains makes qualitative sensitivity analysis here a much harder task. We show the profound effect on computational issues caused by the departure from the pure network structure. © 1996 John Wiley & Sons, Inc.