Dubuc, Serge; Kagabo, Issa
Numerical solutions of the mass transfer problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1 , p. 1-17
Zbl pre05140663 | MR 2248419
doi : 10.1051/ro:2006011
URL stable : http://www.numdam.org/item?id=RO_2006__40_1_1_0

Let μ and ν be two probability measures on the real line and let c be a lower semicontinuous function on the plane. The mass transfer problem consists in determining a measure ξ whose marginals coincide with μ and ν, and whose total cost c(x,y)dξ(x,y) is minimum. In this paper we present three algorithms to solve numerically this Monge-Kantorovitch problem when the commodity being shipped is one-dimensional and not necessarily confined to a bounded interval. We illustrate these numerical methods and determine the convergence rate.


[1] M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables. Washington, D.C. (1964). Zbl 0171.38503

[2] E.J. Anderson and A.B. Philpott, Duality and an algorithm for a class of continuous transportation problems. Math. Oper. Res. 9 (1984) 222-231. Zbl 0538.90057

[3] E.J. Anderson and P. Nash, Linear Programming in Infinite-Dimensional Spaces. Theory and Application. John Wiley & Sons, Chichester (1987). MR 893179 | Zbl 0632.90038

[4] P.E. Appell, Mémoire sur les déblais et les remblais des systèmes continus ou discontinus 181-208. JFM 20.0375.01

[5] P.E. Appell, Le problème géométrique des déblais et remblais. Gauthier-Villars, Paris (1928). Numdam | JFM 54.0527.03

[6] S. Dubuc and M. Tanguay, Déplacement de matériel continu unidimensionnel à moindre coût. RAIRO Rech. Oper., 20 (1986) 139-161. Numdam | Zbl 0601.90104

[7] M. Fréchet, Sur les tableaux de corrélation dont les marges sont données. Ann. Univ. Lyon 14 (1951) 53-77. Zbl 0045.22905

[8] M.D. Grigoriadis, An efficient implementation of the network simplex method. Netflow in Pisa (Pisa, 1983). Math. Program. Stud. 26 (1986) 83-111. Zbl 0594.90025

[9] F.L. Hitchcock, The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941) 224-230. JFM 67.0528.04

[10] W. Hoeffding, Masstabinvariante Korrelations-theorie. Schr. Math. Inst. Univ. Berlin 5 (1940) 181-233. JFM 66.0649.02

[11] L. Kantorovitch, On the translocation of masses. Doklady Akad. Nauk. SSSR 37 (1942) 199-201. Zbl 0061.09705

[12] H.G. Kellerer, Duality theorems for marginal problems. Z. Wahrsch. Verw. Gebiete 67 (1984) 399-432. Zbl 0535.60002

[13] V.L. Levin and A.A. Milyutin, The Problem of Mass Transfer with a Discontinuous Cost Function and the Mass Statement of the Duality for Convex Extremal Problems. Uspehi Mat. Nauk. 34 (1979) 3-68. Zbl 0437.46064

[14] G. Monge, Mémoire sur la théorie des déblais et des remblais. Mém. Math. Phys. Acad. Royale Sci., Paris (1781) 666-704.

[15] S.T. Rachev and L. Rüschendorf, Solution of some transportation problems with relaxed or additional constraints SIAM J. Control Optim. 32 (1994), 673-689. Zbl 0797.60019

[16] A.H. Tchen, Inequalities for distributions with given marginals Ann. Prob. 8 (1980) 814-827. Zbl 0459.62010