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

  • Анна Анатольевна Королева Белорусский государственный университет, пр. Независимости 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
Ключевые слова: транспортная задача, оптимизация в логистике, свойство Монжа, выпуклость матриц
Как цитировать
Королева, А. А. (2021). От Монжа до современной оптимизации транспортных потоков. Журнал Белорусского государственного университета. Экономика, 1, 26-36. Доступно по https://journals.bsu.by/index.php/economy/article/view/3762
Раздел
C. Математические и количественные методы