Субмодулярные функции в экономике и логистике
Аннотация
В современных экономических исследованиях выделяются разделы специальных хорошо решаемых задач, связанных с субмодулярными функциями. Приложения с субмодулярными функциями возникают в различных направлениях экономики - теории полезностей, теории игр, логистике. В статье анализируется роль субмодулярных функций в экономике, вводится широкий класс транспортных оптимизационных задач, ограничения и критерий в которых моделируются субмодулярными функциями, исследуются свойства этих задач, что позволяет построить эффективные алгоритмы оптимальных перевозок в транспортных сетях с супермодулярной целевой функцией затрат и субмодулярными ограничениями.
Литература
- 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.
- Cherenin VP. [Mechanisation calculations to plan the formation of trains]. Tekhnika zheleznykh dorog. 1954;1:79–96. Russian.
- 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.
- 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.
- 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.
- Topkis DM. Minimizing a submodular functions on a lattice. Operations Research. 1978;26(2):305–321. DOI: 10.1287/opre.26.2.305.
- 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).
- Fujishige S. Submodular functions and optimization. 2nd edition. Amsterdam: Elsevier; 2005. 410 p. (Annals of discrete mathematics; volume 58).
- Topkis DM. Supermodularity and complementarity. Princeton: Princeton University Press; 1998. 272 p. (Frontiers of economic research).
- 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.
- Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: Universitetskoe; 1987. 220 p. Russian.
- Russell C, Andrew J. Coordinating coordination failures in Keynesian models. The Quarterly Journal of Economics. 1988;103(3):441–463. DOI: 10.2307/1885539.
- Danilov VI. Lektsii po teorii igr [Lectures on the theory of games]. Moscow: New Economic School; 2002. 140 p. Russian.
- Chambers CP, Echenique F. Supermodularity and preferences. Journal of Economic Theory. 2009;144(3):1004–1014. DOI: 10.1016/j.jet.2008.06.004.
- Danilov VI, Koshevoi GA. [Economics with innovative goods]. Ekonomika i matematicheskie metody. 2009;45(1):44–55. Russian.
- 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.
- 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.
- 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.
- 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.
Copyright (c) 2021 Журнал Белорусского государственного университета. Экономика
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).