guuvestВестник университетаVestnik Universiteta1816-42772686-8415State University of Management10.26425/1816-4277-2023-5-70-76guuvest-4489Research ArticleЭКОНОМИКА: ПРОБЛЕМЫ, РЕШЕНИЯ И ПЕРСПЕКТИВЫECONOMICS: PROBLEMS, SOLUTIONS AND PROSPECTSЗадачи дискретной оптимизации поставок разнородной продукцииDiscrete optimizations’ problems of deliveries of heterogeneous productshttps://orcid.org/0000-0003-4735-989XЕгоровВ. В.EgorovV. V.

Егоров Владислав Валерьевич, канд. физ.-мат. наук, доц. каф. математических методов в экономике и управлении

г. Москва

Vladislav V. Egorov Cand. Sci. (Phys. and Math.), Assoc. Prof. At the Department of Mathematical Methods in Economics and Management

yegoroff_vv@mail.ruГосударственный университет управленияРоссияState University of ManagementRussian Federation202321062023057076Copyright © Егоров В.В., 20232023Егоров В.В.Egorov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.guu.ru/jour/article/view/4489

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

The article touches upon issues related to the tasks of the national project «Smart City». The paper analyzes the problem of supplying a conditional consumer with heterogeneous products in accordance with his demand for deliveries from several suppliers in a situation with fixed surcharges, in addition to the cost of purchasing each unit of production. For the situation under study, a model of a reduced transport type with a discontinuous piecewise linear objective function of minimized total costs and with a system of linear constraints is constructed. A method for finding the optimal solution one of the many such solutions, based on the ideas of the Hungarian algorithm is proposed, the justification of which is given on the basis of the corresponding lemma. A refinement of the method is presented in the presence of some restrictions related to suppliers. The polynomial complexity of the method, i.e. the problem is quickly solvable, and the significant limitation of the applicability of the method within the framework of the model are noted. Further possible research directions of a stochastic or fuzzy nature are indicated.

Логистикамоделированиеоптимизацияразнородная транспортная задачафиксированные доплатычастично целочисленное математическое программированиедискретное программированиеLogisticsmodelingoptimizationheterogeneous transport problemfixed surchargespartial integer mathematical programmingdiscrete programmingReferencesМинистерство цифрового развития, связи и массовых коммуникаций Российской Федерации. Национальный проект «Цифровая экономика РФ». https://digital.gov.ru/ru/activity/directions/858/ (дата обращения: 08.03.2023).Ministry of Digital Development, Communications and Mass Media of the Russian Federation. National project “Digital Economy of the Russian Federation”. https://digital.gov.ru/ru/activity/directions/858/ (accessed 08.03.2023). (In Russian).Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации. Направление деятельности «Цифровые технологии» национального проекта «Цифровая экономика РФ». https://digital.gov.ru/ru/activity/directions/878/ (дата обращения: 08.03.2023).Ministry of Digital Development, Communications and Mass Media of the Russian Federation. Direction of activity «Digital technologies» of the national project «Digital Economy of the Russian Federation». https://digital.gov.ru/ru/activity/directions/878/(accessed 08.03.2023). (In Russian).Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Heidelberg: Springer Berlin; 2013. 686 с. https://doi.org/10.1007/978-3-662-21708-5Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Heidelberg: Springer Berlin; 2000. 2018. https://doi.org/10.1007/978-3-662-21708-5Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука; 1969. 368 с.Korbut A.A., Finkelshtein Yu.Yu., Discrete programming. Moscow: Nauka; 1969. (In Russian).Balinski M.L. Fixed-cost transportation problems. Naval Research Logistics Quarterly. 1961;8(1):41–54 с. https://doi.org/10.1002/nav.3800080104Balinski M.L. Fixed-cost transportation problems. Naval Research Logistics Quarterly. 1961;8(1):41–54 pp. https://doi.org/10.1002/nav.3800080104Göthe-Lundgren M., Larsson T. A set covering reformulation of the pure fixed charge transportation problem. Discrete Appl. Math. 1994;48(3):245–259 с. https://doi.org/10.1016/0166-218X(92)00177-NGöthe-Lundgren M., Larsson T. A set covering reformulation of the pure fixed charge transportation problem. Discrete Appl. Math. 1994;48(3):245–259 pp. https://doi.org/10.1016/0166-218X(92)00177-NKowalski K., Lev B. On step fixed-charge transportation problem. Omega. 2008;36(5):913–917 с. https://doi.org/10.1016/j. Omega.2007.11.001Kowalski K., Lev B. On step fixed-charge transportation problem. Omega. 2008;36(5):913–917 pp. https://doi.org/10.1016/j.omega.2007.11.001Raj K.A.A.D., Rajendran C. Fast heuristic algorithms to solve a single-stage Fixed-Charge Transportation Problem. International Journal of Operational Research. 2009;6(3):304–329 с. https://doi.org/10.1504/IJOR.2009.026936Raj K.A.A.D., Rajendran C. Fast heuristic algorithms to solve a single-stage Fixed-Charge Transportation Problem. International Journal of Operational Research. 2009;6(3):304–329 pp. https://doi.org/10.1504/IJOR.2009.026936Agarwal Y., Aneja Y. Fixed-charge transportation problem: Facets of the projection polyhedron. Operational Research.Agarwal Y., Aneja Y. Fixed-charge transportation problem: Facets of the projection polyhedron. Operational Research. 2012;60(3):638–654 pp. https://doi.org/10.1287/opre.1120.1041;60(3):638–654 с. https://doi.org/10.1287/opre.1120.1041Roberti R., Bartolini E., Mingozzi A. The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation. Management Science. 2014;61(6):1275–1291 pp. https://doi.org/10.1287/mnsc.2014.1947Roberti R., Bartolini E., Mingozzi A. The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation. Management Science. 2014;61(6):1275–1291 с. https://doi.org/10.1287/mnsc.2014.1947Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. The MIT Press; 2022. (In Russian).Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс; 2013. 1328 с.Bertazzi L., Maggioni F. A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach. European Journal of Operational Research. 2017;267(2):555–569 pp. https://doi:10.1016/j.ejor.2017.12.004Bertazzi L., Maggioni F. A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach. European Journal of Operational Research. 2017;267(2):555–569 с. https://doi:10.1016/j.ejor.2017.12.004Sudha G., Ganesan K. Interval-Fuzzy Fixed Charge Transportation Problems. International Journal of Fuzzy System Applications. 2022;11(3):1–14 pp. http://doi.org/10.4018/IJFSA.306281Sudha G., Ganesan K. Interval-Fuzzy Fixed Charge Transportation Problems. International Journal of Fuzzy System Applications. 2022;11(3):1–14 с. http://doi.org/10.4018/IJFSA.306281Cavada M., Rogers C., Hunt D. Smart Cities: Contradicting Definitions and Unclear Measures. Proceedings of the 4th World Sustainability Forum, 1–30 November 2014. Basel: MDPI; 2014. 12 p. https://doi.org/10.3390/wsf-4-f004Cavada M., Rogers C., Hunt D. Smart Cities: Contradicting Definitions and Unclear Measures. Proceedings of the 4th World Sustainability Forum, 1–30 November 2014. Basel: MDPI; 2014. 12 с. https://doi.org/10.3390/wsf-4-f004Ministry of Construction, Housing and Communal Services of the Russian Federation. National project «Smart City». https://russiasmartcity.ru/about (accessed 12.03.2023). (In Russian).Министерство строительства и жилищно-коммунального хозяйства Российской Федерации. Национальный проект «Умный город». https://russiasmartcity.ru/about (дата обращения: 12.03.2023).Russian Federation. Department of the City of Moscow on competition Policy, Department of Information Technologies of the city of Moscow. Supplier portal. Operational purchases of goods, works and services.https://zakupki.mos.ru/ (accessed 14.03.2023).Департамент города Москвы по конкурентной политике, Департамент информационных технологий города Москвы. Портал поставщиков. Оперативные закупки товаров, работ и услуг. https://zakupki.mos.ru/ (дата обращения: 14.03.2023).Департамент города Москвы по конкурентной политике, Департамент информационных технологий города Москвы. Портал поставщиков. Оперативные закупки товаров, работ и услуг. https://zakupki.mos.ru/ (дата обращения: 14.03.2023).

The authors declare that there are no conflicts of interest present.