Субмодулярные функции в экономике и логистике

  • Анна Анатольевна Королёва Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

Аннотация

В современных экономических исследованиях выделяются разделы специальных хорошо решаемых задач, связанных с субмодулярными функциями. Приложения с субмодулярными функциями возникают в различных направлениях экономики - теории полезностей, теории игр, логистике. В статье анализируется роль субмодулярных функций в экономике, вводится широкий класс транспортных оптимизационных задач, ограничения и критерий в которых моделируются субмодулярными функциями, исследуются свойства этих задач, что позволяет построить эффективные алгоритмы оптимальных перевозок в транспортных сетях с супермодулярной целевой функцией затрат и субмодулярными ограничениями.

Биография автора

Анна Анатольевна Королёва, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

кандидат физико-математических наук, доцент; декан экономического факультета

Литература

  1. Cherenin VP, Petrov AP. [Improvement of the method of drawing up a plan for the formation of trains]. Zheleznodorozhnyi transport. 1948;3:60–71. Russian.
  2. Cherenin VP. [Mechanisation calculations to plan the formation of trains]. Tekhnika zheleznykh dorog. 1954;1:79–96. Russian.
  3. Cherenin VP. Reshenie nekotorykh kombinatornykh zadach optimal’nogo planirovaniya metodom posledovatel’nykh raschetov [Solving some combinatorial problems of optimal planning by the method of successive calculations]. Novosibirsk: [s. n.]; 1962. 21 p. (Materialy k Konferentsii po opytu i perspektivam primeneniya matematicheskikh metodov i elektronnykh vychislitel’nykh mashin v planirovanii). Russian.
  4. Khachaturov VR. Nekotorye voprosy i prilozheniya metoda posledovatel’nykh raschetov k resheniyu zadach razmeshcheniya proizvodstva [Some questions and applications of the method of sequential calculations to solving problems of production placement] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut Akademii nauk SSSR; 1968. 164 p. Russian.
  5. Edmonds J. Submodular functions, matroids and certain polyhedra. In: Guy R, Hanani H, Sauer N, Schӧnheim J, editors. Combinatorial structures and their applications. Proceedings of the Calgary International conference; 1969 June 2–14; Calgary, Alberta, Canada. New York: Gordon and Breach; 1970. p. 69–87.
  6. Topkis DM. Minimizing a submodular functions on a lattice. Operations Research. 1978;26(2):305–321. DOI: 10.1287/opre.26.2.305.
  7. Fujishige S. Submodular systems and related topics. In: Korte B, Ritter K, editors. Mathematical Programming at Oberwolfach II. Berlin: Springer-Verlag; 1984. p. 113–131 (Mathematical programming studies; volume 22).
  8. Fujishige S. Submodular functions and optimization. 2nd edition. Amsterdam: Elsevier; 2005. 410 p. (Annals of discrete mathe­matics; volume 58).
  9. Topkis DM. Supermodularity and complementarity. Princeton: Princeton University Press; 1998. 272 p. (Frontiers of economic research).
  10. Lovasz L. Submodular functions and convexity. In: Bachem A, Grötschel M, Korte B, editors. Mathematical programming. The state of the art. Bonn, 1982. Berlin: Springer-Verlag; 1983. p. 235–257.
  11. Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: Universitetskoe; 1987. 220 p. Russian.
  12. Russell C, Andrew J. Coordinating coordination failures in Keynesian models. The Quarterly Journal of Economics. 1988;103(3):441–463. DOI: 10.2307/1885539.
  13. Danilov VI. Lektsii po teorii igr [Lectures on the theory of games]. Moscow: New Economic School; 2002. 140 p. Russian.
  14. Chambers CP, Echenique F. Supermodularity and preferences. Journal of Economic Theory. 2009;144(3):1004–1014. DOI: 10.1016/j.jet.2008.06.004.
  15. Danilov VI, Koshevoi GA. [Economics with innovative goods]. Ekonomika i matematicheskie metody. 2009;45(1):44–55. Russian.
  16. Khachaturov VR. Algoritmy maksimizatsii supermodulyarnykh funktsii i ikh primenenie v zadachakh optimal’nogo raspredeleniya investitsii v regionakh [Algorithms for maximising supermodular functions and their application in problems of optimal investment distribution in regions] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut RAN; 2002. 95 p. Russian.
  17. Khachaturov VR. [Basic properties of cube lattices, algorithms for their construction and application possibilities in discrete optimisation]. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki. 2015;55(1):121–134. Russian. DOI: 10.7868/S004446691501010X.
  18. Montlevich VM. On the submodularity of the profit function in a problem of transport planning. Bulletin of Samara State University. Natural Science Series. 2014;10:48–54. Russian.
  19. Gasnikov AV, editor. Vvedenie v matematicheskoe modelirovanie transportnykh potokov [Introduction to mathematical modelling of transport flows]. 2nd edition. Moscow: Publishing House of the Moscow Center for Continuous Mathematical Education; 2013. 426 p. Russian.
Опубликован
2021-12-14
Ключевые слова: субмодулярные функции, дискретная выпуклость, сетевая транспортная задача
Как цитировать
Королёва, А. А. (2021). Субмодулярные функции в экономике и логистике. Журнал Белорусского государственного университета. Экономика, 2, 18-25. Доступно по https://journals.bsu.by/index.php/economy/article/view/4198
Раздел
C. Математические и количественные методы