A large-scale linear assignment problem is considered under the assumption that the coefficients of the objective function are imperfectly known but have a probability distribution. Asymptotic approximations are derived by using the statistical theory of extremes. It is shown how the resulting approximate problem has an easily computable form, provides a closed-form solution which has the structure of a logit model, and is embedded by a mathematical program whose objective function is related to entropy.
Get full access to this article
View all access options for this article.
References
1.
DantzigGD, 1951, “Application of the simplex method to a transportation problem” in Activity Analysis of Production and Allocation, Cowles Commission Monograph 13 Ed. KoopmansT C (John Wiley, New York) chapter 23
2.
DomencichTMcFaddenD, 1975Urban Travel Demand: A Behavioral Analysis (North-Holland, Amsterdam)
3.
EvansS P, 1973, “A relationship between the gravity model for trip distribution and transportation problems in linear programming”Transportation Research739–61
4.
FisherR ATippetL H C, 1928, “Limiting forms of frequency distributions of the largest or smallest member of a sample”Proceedings of the Cambridge Philosophical Society24180–190
5.
FordL RJrFulkersonD R, 1956Solving the Transportation Problem Rand report RM-1798; Rand Corporation, Santa Monica, CA
6.
FréchetM, 1927, “Sur la loi de probabilité de l'écart maximum”Annales de la Société polonaies de Mathématique693
7.
GalambosJ, 1978The Asymptotic Theory of Extreme Order Statistics (John Wiley, New York)
8.
GnedenkoB V, 1943, “Sur la distribution limite du terme maximum d'une série aléatorie”Annalia Mathematica44423–453
9.
JacobsenS KKesselO, 1977, “The concept of entropy in OR-modelling” working paper of the Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Lyngby, Denmark
10.
JeffersonT RScottC H, 1979, “The analysis of entropy models with equality and inequality constraints”Transportation Research13B123–132
11.
LeonardiG, 1982, “The structure of random utility models in the light of asymptotic theory of extremes” WP-82-91, International Institute for Applied Systems Analysis, Laxenburg, Austria
12.
LeonardiG, 1983a, “Transient and asymptotic behavior of a random-utility based stochastic search process in continuous space and time” WP-83-108, International Institute for Applied Systems Analysis, Laxenburg, Austria
13.
LeonardiG, 1983b, “The use of random-utility theory in building location-allocation models” in Locational Analysis of Public Facilities Eds ThisseJ FZollerH G (North-Holland, Amsterdam)
14.
LuceR D, 1959Individual Choice Behavior: A Theoretical Analysis (John Wiley, New York)
15.
ManskiC F, 1973Structure of Random Utility Models PhD dissertation, Department of Economics, Massachusetts Institute of Technology, Cambridge, MA
16.
Von MisesR, 1936, “La distribution de la plus grande de n valeurs”; reprinted in Selected Papers II (1954)American Mathematical Society, Providence, RI; pp 271–294
17.
WillekensFPórARaquilletR, 1981, “Entropy, multiproportional, and quadratic techniques for inferring detailed migration patterns from aggregated data” in Advances in Multiregional Demography RR-81-006, Ed. RogersA, International Institute for Applied Systems Analysis, Laxenburg, Austria; pp 83–124
18.
WilsonA G, 1970Entropy in Urban and Regional Modelling (Pion, London)
19.
WilsonA G, 1974Urban and Regional Models in Geography and Planning (John Wiley, Chichester, Sussex)
