Minimum Concave Cost Flows in Certain Networks

Willard I. Zangwill
Additional contact information
Willard I. Zangwill: University of California, Berkeley

Management Science, 1968, vol. 14, issue 7, 429-450

Abstract: The literature is replete with analyses of minimum cost flows in networks for which the cost of shipping from node to node is a linear function. However, the linear cost assumption is often not realistic. Situations in which there is a set-up charge, discounting, or efficiencies of scale give rise to concave functions. Although concave functions can be minimized by an exhaustive search of all the extreme points of the convex feasible region, such an approach is impractical for all but the simplest of problems. In this paper some theorems are developed which explicitly characterize the extreme points for certain single commodity networks. By exploiting this characterization algorithms are developed that determine the minimum concave cost solution for networks with a single source and a single destination, for acyclic single source multiple destination networks, and for acyclic single destination multiple source networks. An interesting theorem then establishes that for either single source or single destination networks the multi-commodity case can be reduced to the single commodity case. Applications to the concave warehouse problem, a single product production and inventory model, a multi-product production and inventory model, and a plant location problem are included.

Date: 1968
References: Add references at CitEc
Citations: View citations in EconPapers (55)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.14.7.429 (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:ormnsc:v:14:y:1968:i:7:p:429-450

Access Statistics for this article

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