Субмодулярность в экономике

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

Аннотация

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

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

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

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

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

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

Литература

  1. Rodrik D. Ekonomika reshaet: sila i slabost’ «mrachnoi nauki» [Economics rules: the rights and wrongs of the «dismal science»]. Golovlyanitsyna E, translator. Moscow: Gaidar Institute Press; 2016. 256 p. Russian.
  2. Koroleva AA. Matematicheskii instrumentarii analiza razvitiya transportnoi logistiki v Belarusi [Mathematical tools for analysing the development of transport logistics in Belarus]. Minsk: Belarusian State University; 2022. 279 p. Russian.
  3. Koroleva AA. From Monge to modern optimisation of transport flows. Journal of the Belarusian State University. Economics. 2021;1:26–36. Russian.
  4. Koroleva AA. Submodular functions in economics and logistics. Journal of the Belarusian State University. Economics. 2021; 2:18–25. Russian.
  5. Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: URSS; 2020. 222 p. Russian.
  6. Demidenko VM. [Conic characterisation of Monge matrices]. Kibernetika i sistemnyi analiz. 2004;4:87–98. Russian.
  7. Grishukhin V. Ekstremal’nye luchi konusa submodulyarnoi funktsii [Extremal rays of the cone of a submodular function]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut Akademii nauk USSR; 1982. 66 p. Russian.
  8. Girlich E, Kovalev M, Moshchensky A. Convexity and Monge arrays. Magdeburg University [Preprint]; 1993. [22 p.].
  9. Girlich E, Kovalev M, Zaporozhets A. Subcones of submodular functions. Otto von Guericke Universität Magdeburg [Preprint];1994. [28 р.].
  10. Adler IJ, Hoffman A, Schamir R. Monge and feasibility sequences in general flow problems. Discrete Applied Mathematics. 1993;44:21–38. DOI: 10.1016/0166-218X(93)90220-I.
  11. Bein WW, Brucker P, Park J, Parthak P. Monge properties in higher dimensions. Discrete Applied Mathematics. 1995;58:97–109.
  12. Burkard RE, Klinz B, Rudolf R. Perspectives of Monge properties in optimisation. Discrete Applied Mathematics. 1996;70(2): 95–161. DOI: 10.1016/0166-218X(95)00103-X.
  13. Deineko V, Woeginger G. Some problems around travelling salesmen, dartboards, and eurocoins. Bulletin of the European Association for Theoretical Computer Science. 2006;90:43–52.
  14. Dietrich BL. Monge sequences, antimatroids, and the transportation problem with forbidden arcs. Linear Algebra and Its Applications. 1990;139:133–145. DOI: 10.1016/0024-3795(90)90393-Q.
  15. Shamir R. A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs. Discrete Mathematics. 1993;114:435–444. DOI: 10.1016/0012-365X(93)90382-4.
  16. 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.
  17. 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.
  18. Khachaturov VR, Veselovskii VE, Zlotov AV, Kaldybaev SU, Kaliev EZh, Kovalenko AG, et al. Kombinatornye metody i algoritmy resheniya zadach diskretnoi optimizatsii bol’shoi razmernosti [Combinatorial methods and algorithms for solving high-dimensional discrete optimisation problems]. Moscow: Nauka; 2000. 354 p. Russian.
  19. Khachaturov VR. Matematicheskie metody regional’nogo programmirovaniya [Mathematical methods of regional programming]. Moscow: Nauka; 1989. 304 p. (Ekonomiko-matematicheskaya biblioteka). Russian.
  20. 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.
  21. 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.
  22. Brodetskii GL, Gusev DA. Ekonomiko-matematicheskie metody i modeli v logistike: protsedury optimizatsii [Economic and mathematical methods and models in logistics: optimisation procedures]. Moscow: Akademiya; 2012. 195 p. Russian.
  23. Trubin V. [Two classes of location determination problems in tree networks]. Kibernetika. 1983;4:84–87. Russian.
  24. Danilov VI. Lektsii po teorii igr [Lectures on the theory of games]. Moscow: New Economic School; 2002. 140 p. Russian.
  25. 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, Canada. New York: Gordon and Breach; 1970. p. 69–87.
  26. Gospodarik CG, Kovalev MM. Collective economic security of the EAEU: statement of the problem, indicators, consolidated index. Belarusian Economic Journal. 2022;2:23–33. Russian. EDN: GLZCZD.
  27. Gospodarik CG, Kovalev MM. EAES – 2050: global’nye trendy i evraziiskaya ekonomicheskaya politika [EAEU – 2050: global trends and Eurasian economic policy]. Minsk: Publishing Centre of the Belarusian State University; 2015. 152 p. Russian.
  28. Pisaruk NN. [Representation of the lattice of optimal solutions in the submodular function minimisation problem]. Computational Mathematics and Mathematical Physics. 1989;29(9):1426–1431. Russian. DOI: 10.1016/0041-5553(89)90188-2.
  29. 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).
  30. 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.
  31. Schrijver A. A combinatorial algorithm minimizing submodular function in strongly polynomial time. Journal of Combinatorial Theory. Series B. 2000;80:346–355.
  32. Topkis DM. Supermodularity and complementarity. Princeton: Princeton University Press; 1998. 272 p. (Frontiers of economic research).
  33. Danilov VI. Tselochislennaya vypuklost’ [Integer convexity]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut RAN;2020. 19 p. Russian.
  34. Topkis DM. Minimizing a submodular functions on a lattice. Operations Research. 1978;26(2):305–321. DOI: 10.1287/opre. 26.2.305.
Опубликован
2024-12-19
Ключевые слова: субмодулярные функции, оптимизация, матрица Монжа, полиматроиды, субмодулярные полезности, субмодулярные игры
Как цитировать
Ковалёв, М. М., & Королёва, А. А. (2024). Субмодулярность в экономике. Журнал Белорусского государственного университета. Экономика, 2, 4-12. Доступно по https://journals.bsu.by/index.php/economy/article/view/6739
Выпуск
№ 2 (2024): Журнал Белорусского государственного университета. Экономика
Раздел
C. Математические и количественные методы

Copyright (c) 2024 Журнал Белорусского государственного университета. Экономика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).