ISSN:
1436-4646
Keywords:
Transportation problem
;
assignment problem
;
supply
;
demand
;
staircase
;
capacity
;
lattice
;
sublattice
;
superadditive
;
subadditive
;
greatest element
;
myopic
;
greedy
;
integral
;
linear time
;
complexity
;
bivariate distribution
;
correlation
;
distribution
;
substitution
;
inventory
;
age
;
FIFO
;
LIFO
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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, generalizing results of Derman and Klein (1958), optimal sales with age-dependent rewards and capacities.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585166
Permalink
