Задачи дискретной оптимизации поставок разнородной продукции

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

1. Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации. Национальный проект «Цифровая экономика РФ». https://digital.gov.ru/ru/activity/directions/858/ (дата обращения: 08.03.2023).

2. Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации. Направление деятельности «Цифровые технологии» национального проекта «Цифровая экономика РФ». https://digital.gov.ru/ru/activity/directions/878/ (дата обращения: 08.03.2023).

3. Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Heidelberg: Springer Berlin; 2013. 686 с. https://doi.org/10.1007/978-3-662-21708-5

4. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука; 1969. 368 с.

5. Balinski M.L. Fixed-cost transportation problems. Naval Research Logistics Quarterly. 1961;8(1):41–54 с. https://doi.org/10.1002/nav.3800080104

6. Gö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-N

7. Kowalski K., Lev B. On step fixed-charge transportation problem. Omega. 2008;36(5):913–917 с. https://doi.org/10.1016/j. Omega.2007.11.001

8. Raj 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.026936

9. Agarwal Y., Aneja Y. Fixed-charge transportation problem: Facets of the projection polyhedron. Operational Research.

10. ;60(3):638–654 с. https://doi.org/10.1287/opre.1120.1041

11. Roberti 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.1947

12. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс; 2013. 1328 с.

13. 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 с. https://doi:10.1016/j.ejor.2017.12.004

14. Sudha 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.306281

15. Cavada 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-f004

16. Министерство строительства и жилищно-коммунального хозяйства Российской Федерации. Национальный проект «Умный город». https://russiasmartcity.ru/about (дата обращения: 12.03.2023).

17. Департамент города Москвы по конкурентной политике, Департамент информационных технологий города Москвы. Портал поставщиков. Оперативные закупки товаров, работ и услуг. https://zakupki.mos.ru/ (дата обращения: 14.03.2023).