Variables duales dans un programme continu de transport. (French) Zbl 0538.90058

Dubuc, Serge; Tanguay, Monique

Cah. Cent. Étud. Rech. Opér. 26, 17-23 (1984).

The mass transfer problem is the continuous linear program arising from two finite measures \(\mu\) and \(\nu\), the first on a compact space X, the second on Y and from a continuous cost function c(x,y) defined on the product \(X\times Y\). The problem is to minimize the linear program \(\int \int c d\sigma\) where \(\sigma\) is a measure whose respective projections on X and Y are \(\mu\) and \(\nu\); \(\gamma\) will denote the minimal cost in the program. This problem goes back to L. Kantorovitch [C.R. Acad. Sci. URSS, n. Ser. 37, 199-201 (1942; Zbl 0061.097)]. The dual program is to maximize the sum of two integrals \(\int u d\mu\) and \(\int v d\nu\) where u(x) and v(y) are two continuous functions for which \(u(x)+v(y)\leq c(x,y)\); \(\gamma^*\) will denote the maximal value of this sum. The strong duality theorem is that \(\gamma^*=\gamma\) and was proven by K. S. Kretschmer [Can. J. Math., 13, 221-238 (1961; Zbl 0097.147)]. Two continuous functions u(x) and v(y) such that \(u(x)+v(y)\leq c(x,y)\) and \(\int u d\mu +\int v d\nu =\gamma\) are called optimal dual variables. What we prove is that optimal dual variables always exist and we find a characterization of them. We conclude by a short discussion of the numerical solution of the mass transfer problem, one solution uses the primal problem, the other the dual problem. Other ideas about the numerical solution can be found in a more recent paper of E. J. Anderson and A. B. Philpott [Math. Oper. Res. 9, 222-231 (1984)].

MSC:

90C08	Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C05	Linear programming

Keywords:

duality; mass transfer problem; continuous linear program; optimal dual variables

Citations:

Zbl 0061.097; Zbl 0097.147