Ripples, complements, and substitutes in generalized networks

Antoine Gautier and Frieda Granot

Naval Research Logistics (NRL), 1996, vol. 43, issue 1, 1-21

Abstract: 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.

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199602)43:13.0.CO;2-F

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:43:y:1996:i:1:p:1-21

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().