RIPPLES, COMPLEMENTS, AND SUBSTITUTES IN GENERALIZED NETWORKS

We extend the qualitative theory of sensitivity analysis for minimum-c ost pure network flows of Granot and Veinott [17] to generalized netwo rk flow problems, that is, network flow problems where the amount of f low picked up by an are is multiplied by a (positive) gain while trave rsing the are. Three main results are presented. The ripple theorem gi ves upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter(s). The theory of sub stitutes and complements provides necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposit e) sign(s) in two given arcs, whereas the monotonicity theorem links c hanges in the value of the parameters to changes in optimal are flows. Bounds on the rates of changes are also discussed. Compared with pure networks, the presence of gains makes qualitative sensitivity analysi s here a much harder task. We show the profound effect on computationa l issues caused by the departure from the pure network structure. (C) 1996 John Wiley & Sons, Inc.