По своей природе во многих практических задачах исходные данные известны лишь приблизительно или могут изменяться в некоторых пределах. Использование интервальнозначных данных позволяет учитывать существующую неопределенность при моделировании систем, использующих такие значения. Данная работа посвящена разработке и реализации интервального расширения алгоритма Форда-Фалкерсона для решения задачи о максимальном потоке в условиях неопределенности исходных данных. В отличие от классического подхода, где пропускные способности ребер задаются скалярными значениями, предлагаемое решение использует интервальные данные, что позволяет с более высокой точностью моделировать реальные системы с параметрами, известными лишь с определенной точностью. Представлена реализация алгоритма, выполненная на основе реляционной системы управления базами данных PostgreSQL с созданием пользовательского типа данных для работы с интервальными данными. В работе описаны математические основы интервальной арифметики, методы сравнения интервальных величин, а также особенности интеграции алгоритма с системой управления базами данных. Представлены результаты вычислительного эксперимента на тестовом примере. Обсуждаются практические аспекты применения метода в задачах транспортного планирования, управления телекоммуникационными сетями и распределения ресурсов.
The initial data in many practical problems are known by their nature only approximately or can vary within certain limits. The use of interval-valued data allows one to take into account the existing uncertainty when modeling systems using such values. The article is devoted to the development and implementation of the interval extension of the Ford-Fulkerson algorithm for solving the maximum flow problem under conditions of uncertainty of the initial data. Unlike the classical approach where the edge capacities are specified by scalar values the proposed solution uses interval data which allows for more accurate modeling of real systems with parameters known only with a certain accuracy. The algorithm implementation is presented based on the PostgreSQL relational database management system with the creation of a user-defined data type for working with interval data. The paper describes the mathematical foundations of interval arithmetic, methods for comparing interval values, and features of integrating the algorithm with a database management system. The results of a computational experiment on a test example are presented. Practical aspects of the method application in problems of transport planning, telecommunication network management, and resource allocation are discussed.
The authors declare that there are no conflicts of interest present.