Least d-Majorized Network Flows with Inventory and Statistical Applications.
Abstract
It is shown that for any feasible network flow model, there is a flow which simultaneously minimizes every d-Schur convex function of the flows emanating from a single distinguished node called the source. The vector of flows emanating from the source in the minimizing flow is unique and is the least d-majorized flow. This flow can be found by solving the problem for the special case where the d-Schur convex function is separable and quadratic. Once this flow is found, the solution of the dual problem is reduced to evaluating the conjugate of a function appearing in the dual objective function at the above flow. The computation is extremely simple when the function is separable. These results are extended to situations in which the variables must be integers. An important special case of the problem can be solved geometrically by choosing, from among all paths joining two points in the plane and lying between two given nonintersecting paths, the path with minimum Euclidian length. Applications of the results are given to deterministic production-distribution models, certain of the stochastic inventory-redistribution models examined by Ignall and Veinott, a deterministic price speculation and storage model, and a zero lead time case of the Clark-Scarf series multi-echelon model. In addition, applications are given to several maximum likelihood estimation problems in which the parameters satisfy certain linear inequalities. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 30, 1970
- Accession Number
- AD0714264
Entities
People
- Arthur F. Veinott Jr.
Organizations
- Stanford University