×

Staircase transportation problems with superadditive rewards and cumulative capacities. (English) Zbl 0799.90091

Summary: A cumulative-capacitated transportation problem is studied. The supply nodes and demand nodes are each chains. Shipments from a supply node to a demand node are possible only if the pair lies in a sublattice, or equivalently, in a staircase disjoint union of rectangles, of the product of the two chains. There are (lattice) superadditive upper bounds on the cumulative flows in all leading subrectangles of each rectangle. It is shown that there is a greatest cumulative flow formed by the natural generalization of the South-West Corner Rule that respects cumulative- flow capacities; it has maximum reward when the rewards are (lattice) superadditive; it is integer if the supplies, demands and capacities are integer; and it can be calculated myopically in linear time. The result is specialized to earlier work of Hoeffding (1940), Fréchet (1951), Lorentz (1953), Hoffman (1963) and Barnes and Hoffman (1985). Applications are given to extreme constrained bivariate distributions, optimal distribution with limited one-way product substitution and optimal sales with age-dependent rewards and capacities.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.R. Barnes and A.J. Hoffman, ”On transportation problems with upper bounds on leading rectangles,”SIAM Journal on Algebraic and Discrete Methods 6 (1985) 487–496. · Zbl 0589.90056 · doi:10.1137/0606048
[2] C. Derman and M. Klein, ”Inventory depletion management,”Management Science 4 (1958) 450–456. · doi:10.1287/mnsc.4.4.450
[3] M. Fréchet, ”Sur les tableaux de corrélation dont les marges sont données,”Annales de l’Université de Lyon Section A 14 (1951) 53–77.
[4] W. Hoeffding, ”Maßstabinvariante Korrelationstheorie,”Schriften des Mathematischen Instituts und des Instituts für Angewande Mathematik der Universität Berlin 5 (1940) 179–233. [Originally published under the name W. Höffding.] · JFM 66.0649.02
[5] A.J. Hoffman, ”On simple linear programming problems,” in: V. Klee, ed.,Convexity. Proceedings of the Symposium on Pure Mathematics No. 7 (American Mathematical Society Providence, RI, 1963) pp. 317–327. · Zbl 0171.17801
[6] A.J. Hoffman and A.F. Veinott, Jr., ”Staircase transportation problems with superadditive rewards and cumulative capacities,” Research Report RJ 7399 (69201), IBM Research Division (Yorktown Heights and Almaden, April 3, 1990), 13 pp. · Zbl 0799.90091
[7] G.G. Lorentz, ”An inequality for rearrangements,”The American Mathematical Monthly 60 (1953) 176–179. · Zbl 0050.28201 · doi:10.2307/2307574
[8] I. Olkin and S.T. Rachev, ”Distributions with given marginals subject to certain constraints,” Technical Report No. 270, Department of Statistics, Stanford University (Stanford, CA, July 1990) 28 pp.
[9] S.T. Rachev, ”The Monge–Kantorovich mass transference problem and its stochastic applications,”Theory of Probability and its Applications 29 (1985) 647–676. [Translated from:Teoriya Veroyatnostei i ee Primeneniya (1984).] · Zbl 0581.60010 · doi:10.1137/1129093
[10] D.M. Topkis, ”The structure of sublattices of the product ofn lattices,”Pacific Journal of Mathematics 65 (1976) 525–532. · Zbl 0333.06002
[11] D.M. Topkis and A.F. Veinott, Jr., ”Monotone solution of extremal problems on lattices (Abstract),”Abstracts of 8th International Symposium on Mathematical Programming (Stanford University, Stanford, CA, 1973) 131.
[12] D.M. Topkis and A.F. Veinott, Jr., ”Meet-representation of subsemilattices and sublattices of product spaces (Abstract),”Abstracts of 8th International Symposium on Mathematical Programming (Stanford University, Stanford, CA, 1973) 136.
[13] A.F. Veinott, Jr., ”Representation of general and polyhedral subsemilattices and sublattices of product spaces,”Linear Algebra and its Applications 114/115 (1989) 681–704. · Zbl 0669.06002 · doi:10.1016/0024-3795(89)90488-6
[14] W. Whitt, ”Bivariate distributions with given marginals,”Annals of Statistics 4 (1976) 1280–1289. · Zbl 0367.62022 · doi:10.1214/aos/1176343660
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.