Cost Minimization in Networks with Discrete Stochastic Requirements

Michael M. Connors and Willard I. Zangwill
Additional contact information
Michael M. Connors: IBM Scientific Center, Los Angeles, California
Willard I. Zangwill: University of California, Berkeley, California

Operations Research, 1971, vol. 19, issue 3, 794-821

Abstract: Multistage minimum-cost network-flow analysis solves many practical problems in production-inventory-distribution, marketing, personnel, and finance. Unlike previous network papers, which generally restricted themselves to a deterministic situation, this paper investigates the stochastic environment. Starting from the standard multistage network-flow problem, we create a stochastic network by permitting the node requirements to be discrete random variables with known conditional probability distributions. Our goal is to determine the minimum-expected-cost flow and thereby solve the problem. Although linear programming under uncertainty can determine this flow, it would ignore the special structure of network-flow problems that allows development of computationally efficient algorithms. In this paper, we instead exploit the underlying network structure to produce both a new structure that is not a network but maintains many of the properties of a network, and a new node that replicates flows instead of conserving them. The new nodes, called replication nodes, together with the new structure, allow the development of an efficient computational algorithm that is capable of solving problems much larger than those solvable by linear programming under uncertainty.

Date: 1971
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.3.794 (application/pdf)

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:inm:oropre:v:19:y:1971:i:3:p:794-821

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().