Geodesic
On the submodularity of the profit function in a problem of transport planning
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 10 (2014), pp. 48-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper the possibility of using the method of successive calculations to solve the transportation problem on the maximum profit is investigated. The feature of this problem is that a set of consumers isn't defined and gets out from wider set of possible consumers by the criterion of a maximum of profit. Profit is calculated on the basis of consumer demand and prices, which are determined by the contract between the consumer and the company carrying out transportation. It is shown that this problem is reduced to maximization of the profit function defined on the set of all subsets of consumers. The submodularity of profit function is proved, that justified application of method of successive calculations to solve this problem.
Keywords: discrete optimization, partially ordered set, lattice, submodularity, supermodularity, method of consecutive calculations, plant location problem
Mots-clés : transportation problem. 
@article{VSGU_2014_10_a4,
     author = {V. M. Montlevich},
     title = {On the submodularity of the profit function in a problem of transport planning},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {48--54},
     year = {2014},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2014_10_a4/}
}
TY  - JOUR
AU  - V. M. Montlevich
TI  - On the submodularity of the profit function in a problem of transport planning
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2014
SP  - 48
EP  - 54
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/VSGU_2014_10_a4/
LA  - ru
ID  - VSGU_2014_10_a4
ER  - 
%0 Journal Article
%A V. M. Montlevich
%T On the submodularity of the profit function in a problem of transport planning
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2014
%P 48-54
%N 10
%U http://geodesic.mathdoc.fr/item/VSGU_2014_10_a4/
%G ru
%F VSGU_2014_10_a4
V. M. Montlevich. On the submodularity of the profit function in a problem of transport planning. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 10 (2014), pp. 48-54. http://geodesic.mathdoc.fr/item/VSGU_2014_10_a4/

[1] Birkhoff G., Lattice theory, Nauka, M., 1984, 566 pp. (in Russian)

[2] Lovasz L., “Submodular functions and convexity”, Mathematical programming: the state of the art, Bonn, 1982, 235–257 | MR

[3] Khachaturov V. R., Mathematical methods of regional programming, Nauka, M., 1989, 302 pp. (in Russian)

[4] Khachaturov V. R. et al., Combinatorial methods and algorithms for solving problems of discrete optimization with large dimensionality, Nauka, M., 2000, 354 pp. (in Russian)

[5] Khachaturov V. R., Lorer V. E., Research and minimization supermodular functions on atomic lattices, VTs AN SSSR, M., 1987, 40 pp. (in Russian)

[6] Khachaturov V. R., Shahazizyan A. L., Research of properties and minimization of supermodular functions on the lattice which is direct product of chains, VTs AN SSSR, M., 1985, 30 pp. (in Russian)

[7] Khachaturov V. R., Montlevich V. M., Minimization of supermodular functions on distributive lattices, VTs AN SSSR, M., 1999, 48 pp. (in Russian)

[8] Khachaturov V. R., Khachaturov Roman V., Khachaturov Ruben V., “Optimization of supermodular function (supermodular Programming)”, Journal of Computational Mathematics and Mathematical Physics, 52:6 (2012), 999–1000 (in Russian) | Zbl

[9] Khachaturov V. R., “Models and methods of solution of multiextreme allocation problems using properties of supermodular functions defined on Boolean lattices”, Algorithms and algorithmic languages. Packages of applied programs. Functional content, Nauka, M., 1986, 63–98 (in Russian) | Zbl

[10] Astakhov N. D., Montlevich V. M., “About the solution of multiindex allocation problems by algorithm of consecutive calculations”, Proceedings of the Academy of Sciences of the USSR. Technical Cybernetics, 1988, no. 3, 53–58 (in Russian)

[11] Montlevich V. M., “The allocation problem with standard production capacities and indivisible consumers”, Journal of Computational Mathematics and Mathematical Physics, 40:10 (2000), 1491–1507 (in Russian) | MR | Zbl