Stochastic Sensitivity Analysis of Maximum Flow and Shortest Route Networks

Abstract

This paper presents an algorithm that can be used to solve two types of network sensitivity problems. In the first, arcs are subject to breakdowns that degrade their capacities. It is required, within certain confidence limits, to find the maximum possible effect of n breakdowns on maximum flow. In the second, arcs are subject to improvements that reduce their lengths. It is required, also within certain confidence limits, to find the maximum possible effect n total improvements can have on shortest path length. Capacities resulting from breakdowns and lengths resulting from improvements are random variables specified by their mean values and variances.