Об исследовании устойчивости задач на матроидах
1
УДК 004.056:519.854
Об исследовании устойчивости задач на матроидах
© Э.Н. Гордеев
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
За последние двадцать лет появились десятки статей, посвященных исследованию
устойчивости в задачах оптимизации, при этом многие результаты, опублико-
ванные в отечественных научных журналах в 1970–1980-е годы, игнорируются, а
более поздние публикации цитируются как базовые и оригинальные. Цель данной
статьи — обратить на это внимание на одном примере — исследование устойчи-
вости в задачах на матроидах. Для случая нормы Чебышева в пространстве воз-
мущений параметров задачи проблема устойчивости всесторонне изучена в рабо-
тах 1980-х годов, на которые авторы публикаций 1990-х и более поздних годов
вообще не ссылаются. Для случая метрики l
1
задача является технически более
сложной, поэтому нельзя говорить о полной эквивалентности опубликованных
ранее результатов и появившихся позднее. Однако эти результаты тесно между
собой связаны, что и показано в данной статье. При этом область теории мат-
роидов взята просто в качестве примера. Аналогичные ситуации возникают и для
других задач.
Ключевые слова:
оптимизационные задачи на матроидах, радиус устойчивости,
алгоритм исследования устойчивости.
В работах [1–7] рассматривались различные подходы к исследо-
ванию устойчивости в задачах дискретной оптимизации. Некоторые
из этих работ, в частности [4–6], относятся к периоду 1979–1987 гг.
В одностраничных тезисах [8] для задачи о кратчайшем остове при-
ведена постановка проблемы устойчивости решения задачи и сфор-
мулирован результат, касающийся простого случая одноэлементных
возмущений (без доказательств).
Задачи на матроидах исследованы в работах [1] и [6] для разных
классов метрик, типов функционалов и способов возмущения пара-
метров задач. Частичный обзор основных результатов приведен
и в [2]. Однако в настоящее время в качестве исходных цитируются
работы [8–10], хотя результаты работы [8] являются частными случа-
ями или простым следствием ранее полученных результатов, а по-
становка задачи в [9] и [10], в общем случае не сводящаяся только к
исследованию устойчивости, в частных случаях практически эквива-
лентна такому исследованию. Об этом уже упоминалось в [1], но, ви-
димо, требуются дополнительные пояснения в виде соотнесения по-
лученных результатов.
