От Монжа до современной оптимизации транспортных потоков

Авторы

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

Ключевые слова:

транспортная задача, оптимизация в логистике, свойство Монжа, выпуклость матриц

Аннотация

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

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

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

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

Библиографические ссылки

  1. Monge G. Mémoire sur la théorie des déblais et des remblais. In: Mémoires de l’Academie. Paris: De l’Imprimerie Royale; 1781. p. 666–704.
  2. Tolstoi AN. [Methods of finding the total mileage when planning transportation in space]. Planirovanie perevozok. 1930;1:23–55. Russian.
  3. Kantorovich LV. On the displacement of masses. USSR Academy of Sciences. 1942;32(3):227–229. Russian.
  4. Kantorovich LV, Gavurin MK. [Application of mathematical methods in the analysis of cargo flows]. In: Zvonkov VV, editor. Problemy povysheniya effektivnosti raboty transporta [Problems of improving the efficiency of transport]. Moscow: AN SSSR; 1949. p. 110–138. Russian.
  5. Hitchcock FL. The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics. 1941;20(1–4):224–230. DOI: 10.1002/sapm1941201224.
  6. Koopmans TC. Optimum utilisation of the transportation system. Econometrica. 1949:17(supplement):136–146. DOI: 10.2307/1907301.
  7. Dantzig G. Application of the simplex method to a transportation problem. In: Koopmans TC, editor. Activity analysis of production and allocation. New York: John Wiley and Sons; 1951. p. 359–377.
  8. Ford L, Fulkerson D. Flows in networks. Princeton: Princeton University Press; 1962. 194 p.
  9. Emelichev VA, Kovalev MM, Kravtsov MK. Mnogogranniki, grafy, optimizatsiya [Polytopes, graphs and optimisation]. Moscow: Nauka; 1981. 344 p. Russian.
  10. Yemelichev VA, Kovalev MM, Kravtsov MK. Polytopes, graphs and optimisation. Cambridge: Cambridge University Press; 1984. 423 p. Russian.
  11. Bogachev VN, Kolesnikov AV. [The task of Monge – Kantorovich: achievements, connections and prospects]. Uspekhi matematicheskikh nauk. 2012;67(5):3–110. Russian. DOI: 10.4213/rm9490.
  12. Hoffman A. On simple linear programming problems. In: Klee V, editor. Convexity: proceedings of the seventh symposium in pure mathematics AMS; 1961 June 13–15; Washington, USA. Volume 7. Providence: American Mathematical Society; 1963. p. 317–327.
  13. Kovalev M. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: Universitetskoe; 1987. 220 p. Russian.
  14. Bein W, Brucker P, Hoffman A. Series parallel composition of greedy linear programming problems. Mathematical Programming. 1993;62:1–14. DOI: 10.1007/BF01585157.
  15. Bein WW, Brucker P, Park J, Pathak P. A Monge property for the d-dimensional transportation problem. Discrete Applied Mathematics. 1995;58:97–109.
  16. 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.
  17. Shamir R. A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs. Discrete Mathematics. 1993;114(1–3):435–444. DOI: 10.1016/0012-365X(93)90382-4.
  18. Adler I, Hoffman A, Schamir R. Monge and feasibility sequences in general flow problems. Discrete Applied Mathematics. 1993;44(1–3):21–38. DOI: 10.1016/0166-218X(93)90220-I.
  19. Park JK. A special case of the n-vertex traveling-salesman problem that can be solved in O(n) time. Informating Processiong Letters. 1991;40(5):247–254. DOI: 10.1016/0020-0190(91)90118-2.
  20. Beresnev VL, Gimadi EKh, Dement’ev VT. Ekstremal’nye zadachi standartizatsii [Extreme problems of standardisation]. Novosibirsk: Nauka; 1978. 333 p. Russian.
  21. Trubin V. [Effective algorithm for determining the location in a tree network]. Doklady AN USSR. 1976;231:547–550. Russian.
  22. Eisenstatt V, Kravchuk D. [Algorithm for finding the extremum of a linear form on a set of cycles in a special case]. Doklady AN BSSR. 1968;12:401– 404. Russian.
  23. Demidenko V. [The problem of a traveling salesman with symmetric matrices]. Izvestiya Natsional’noi akademii nauk Belarusi. Seriya fiziko-tekhnicheskikh nauk. 1978;1:29–35. Russian.
  24. Trubin V. [Two classes of location determination problems in tree networks]. Kibernetika. 1983;4:84–87. Russian.
  25. Gimadi EKh. [An effective algorithm for solving the problem of determining the location with the service area associated with an acyclic network]. Upravlyaemye sistemy. 1979;19:3–13. Russian.
  26. Aggarwal A, Bar-Noy A, Khuller S, Kravets D, Schieber B. Efficient minimum cost matching using quadrangle inequality. In: Proceedings of 33rd annual symposium on foundations of computer science; 1992 October 24–27; Pittsburgh, USA. Washington: Institute of Electrical and Electronics Engineers; p. 583–592. 1992. DOI: 10.1109/SFCS.1992.267793.
  27. Girlich E, Kovalev M, Moshchensky A. Conventy and Monge arrays. Magdeburg University [Preprint]. 1993;12:[22].
  28. Girlich E, Kovalev M, Zaporozhets A. Subcones of submodular functions. Otto von Guericke Universität Magdeburg [Preprint]. 1994;29:[28].
  29. Demidenko VM. [Conic characterisation of Monge matrices]. Kibernetika i sistemnyi analiz. 2004;4:87–98. Russian.
  30. Grishukhin V. Ekstremal’nye luchi konusa submodulyarnoi funktsii [Extremal rays of the cone of a submodular function]. CEMI of the Academy of Sciences of the Ukrainian SSR [Preprint]; 1982. [66 p.]. Russian.
  31. Rudolf R, Woeginger GJ. The cone of Monge matrices: extremal rays and applications. Zeitschrift für Operations Research. 1995;42:161–168. DOI: 10.1007/BF01415751.
  32. Burkard RE, Klinz B, Rudolf R. Perspectives of Monge properties in optimization. Discrete Applied Mathematics. 1996; 70(2):95–161. DOI: 10.1016/0166-218X(95)00103-X.
  33. Deineko V, Filonenko V. [On the reconstruction of special structured matrices]. In: Chernyshenko VM, editor. Aktual’nye problemy EVM i programmirovaniya [Actual problems of computers, programming]. Dnepropetrovsk: Dnipropetrovsk Humanitarian University; 1979. p. 43– 45. Russian.
  34. Deineko V, Woeginger G. Some problems around travelling salesmen, dartboards, and euro-coins. Bulletin of the European Association for Theoretical Computer Science. 2006;90:43–52.
  35. Pisaruk NN. Modeli i metody smeshanno-tselochislennogo programmirovaniya [Models and methods of mixed-integer programming]. Minsk: Belarusian State University; 2010. 230 p. Russian.
  36. Meindl B, Templ M. Analysis of commercial and free and open source solvers for linear optimization problems. Wien: Technische Universität Wien; 2012. 15 p.
  37. 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.
  38. Gasnikov AV, editor. Vvedenie v matematicheskie modelirovanie transportnykh potokov [Introduction to mathematical modeling of transport flows]. 2nd edition. Moscow: Moscow Centre for Continuous Mathematical Education; 2013. 428 p. Russian.
  39. Samoilenko NI, Kobets AA. Transportnye sistemy bol’shoi razmernosti [Transport systems of large dimension]. Kharkiv: NTMT; 2010. 214 p. Russian.

Загрузки

Дополнительные файлы

Опубликован

2021-07-30

Выпуск

№ 1 (2021): Журнал Белорусского государственного университета. Экономика

Раздел

C. Математические и количественные методы

Лицензия

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

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

Как цитировать

[1]
Королева, А.А. 2021. От Монжа до современной оптимизации транспортных потоков. Журнал Белорусского государственного университета. Экономика. 1 (июл. 2021), 26–36.