2017 г., Том 22, № 2, с.115-126

Рассмотрена задача о покрытии множества с интервальными весами подмножеств. Решение задачи основано на получении множества приближенных решений для всех возможных весов из заданных интервалов - объединенного приближенного множества решений задачи. Такой подход использует модификацию жадного алгоритма для решения задачи о покрытии на случай интервальных весов. Количество приближенных решений, содержащихся в объединенном приближенном решении, определяет вычислительную сложность его нахождения. Показано, что зависимость вычислительной сложности предложенного подхода от радиусов интервалов весов множеств является неубывающей кусочно-постоянной функцией. Приведен пример приложения подхода к решению задачи формирования рейсов для сети железных дорог при неопределенностях в стоимостях обслуживания рейсов. В заключение работы ставится задача коррекции численно неразрешимых задач о покрытии с интервальными весами.