Интервальное расширение алгоритма Форда-Фалкерсона поиска максимального потока в транспортной сети и его программная реализация на уровне СУБД

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

1. Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. Cambridge: MIT Press; 2022. 1332 p.

2. Шарый С.П. Конечномерный интервальный анализ. Новосибирск: XYZ; 2025. 671 c.

3. Allahviranloo T., Pedrycz W., Esfandiari A. Advances in Numerical Analysis Emphasizing Interval Data. Boca Raton: CRC Press; 2022. 218 p. https://doi.org/10.1201/9781003218173

4. Ahuja R.K., Magnanti Th.L., Orlin J.B. Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice Hall; 1993. 846 p.

5. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. Berlin, Heidelberg: Springer; 2012. 660 p. https://doi.org/10.1007/978-3-642-24488-9

6. Ding S. The α-Maximum Flow Model with Uncertain Capacities. Applied Mathematical Modelling. 2015;39(7):2056–2063. http://doi.org/10.1016/j.apm.2014.10.021

7. Liu B. Theory and Practice of Uncertain Programming. Berlin, Heidelberg: Springer; 2009. 202 p. https://doi.org/10.1007/978-3-540-89484-1

8. Hansen E., Walster G.W. Global Optimization Using Interval Analysis. New York: Marcel Dekker; 2004. 489 p.

9. Mayer G. Interval Analysis and Automatic Result Verification. Berlin, Boston: Walter de Gruyter GmbH; 2017. 532 p.

10. Sakr Sh. Storing and Querying Graph Data Using Efficient Relational Processing Techniques. In: Information Systems: Modeling, Development, and Integration: Third International United Information Systems Conference: Volume 20, 21–24 April 2009, Sydney, Australia. Berlin, Heidelberg: Springer; 2009. P. 379–392. http://doi.org/10.1007/978-3-642-01112-2_39

11. Angles R., Gutierrez C. Survey of Graph Database Models. ACM Computing Surveys. 2008;40(1). https://doi.org/10.1145/1322432.1322433

12. Погодаев А.К., Галкин А.В., Сараев П.В., Мирошников А.И. Сравнение интервальных типов данных в системе MS SQL Server. Системы управления и информационные технологии. 2018;(1):68–72.

13. Pogodaev A.K., Galkin A., Saraev P., Miroshnikov A.I. The Development of Interval Data Type for Analytical Information Processing. In: Recent Developments and the New Direction in Soft-Computing Foundations and Applications: Selected Papers from the 7th World Conference on Soft Computing, 29–31 May 2018, Baku, Azerbaijan. Cham: Springer; 2021. P. 509–520. https://doi.org/10.1007/978-3-030-47124-8_41