Stochastic Sensitivity Analysis of Maximum Flow Networks

摘要

A maximum flow network is defined by a set of arcs and a set of points called nodes. Each arc joins two nodes and has associated with it a positive capacity which represents the maximum amount of flow that may pass over it. One of the nodes is designated as the source and another as the sink. From these nodes, arcs, and capacities the maximum amount of flow that may pass from source to sink may be calculated. This investigation is concerned with a sensitivity analysis on a class of such networks known as planar networks. Specifically, each arc of the network is subject to anywhere from one to n breakdowns which result in a reduction in its capacity. The amount of this reduction in capacity is a random variable with known mean and variance. It is desired to find the smallest possible value of F resulting from, at most, n breakdowns.