Введение к работе
Актуальность темы исследования.
Работа посвящена качественным исследованиям свойств задач дискретной оптимизации, параметры которых подвергаются независимым возмущениям, при этом основное внимание уделяется изучению устойчивости решений.
Актуальность исследования поведения решений возмущенной задачи и их связи с решениями исходной задачи объясняется рядом факторов.
Во-первых, на практике параметры оптимизационной задачи (веса ребер графа, коэффициенты целевой функции и т.д.) всегда известны с некоторой степенью точности, поэтому исследование устойчивости регламентирует корректность задачи. Тем самым оно влияет на выбор алгоритма и в конечном счете на эффективность решения.
Во-вторых, с появлением теории NP-полноты и огромного числа последующих публикаций в этом направлении надежда на полиномиальную разрешимость NP-полных задач довольно мала, а существующие алгоритмы их решения экспоненциальны, то есть требуют больших затрат, поэтому естественно стремление увеличить эффективность решения таких задач за счет исследования их качественных свойств. При исследовании устойчивости мы по решению одной задачи получаем практически бесплатно решение континуума задач, лежащих в шаре устойчивости. При этом подобный подход эффективен не только для NP-полных задач.
В-третьих, в дискретной оптимизации актуальна такая постановка, когда необходимо получить решения конечной последовательности задач, в которой каждая следующая "незначительно" отличается от предыдущей. В этом случае строится алгоритм, ориентированный на решение всей последовательности задач. Построение его тесно связано с проблемой устойчивости.
Кроме того, внимание к исследованию устойчивости задач
дискретной оптимизации резко усилилось в последние 15 лет (до этого были лишь единичные публикации), однако до сих пор нет ясного понимания проблематики и ее места в исследованиях других качественных свойств задач дискретной оптимизации, что необходимо, так как изучение устойчивости тесно связано со многими математическими проблемами: числом решений, проблемой табулирования, вопросами сравнительной сложности, оценками качества алгоритмов и т.д. Имеющийся опыт по исследованиям устойчивости изобилует разнородностью подходов и понятий, поэтому необходимо исследование, на базе которого можно было бы сравнивать "ценность" и эффективность различных подходов.
Цель работы
- создание общего метода исследования устойчивости в
задачах на узкие места и получение с его помощью формул и
алгоритмов вычисления радиуса устойчивости для конкретных норм
ве"и типов возмущений;
исследование сравнительной сложности алгоритмов решения исходной задачи и алгоритмов анализа ее устойчивости;
изучение вопроса о вероятности единственности решения (в случае конечного набора весов) в зависимости от размерности задачи и мощности этого набора;
получение оценки мощности е-покрытия шарами устойчивости;
- построение алгоритмов вычисления радиуса устойчивости
для известных полиномиально разрешимых задач комбинаторной
оптимизации и классов таких задач. (Рассматриваются задачи на
матроидах и пересечениях матроидов, в частности, задача о
кратчайшем остове и о назначениях, задача о кратчайшем пути.)
построение и анализ алгоритмов вычисления радиуса устойчивости в NP-полных задачах.
изучение качественных свойств параметрических задач дискретной оптимизации, связанных с понятием устойчивости.
Методы исследования В работе использованы идеи, понятия и методы комбинаторного анализа, дискретной оптимизации, теории
матроидов, теории графов, математического анализа.
Научная новизна В работе с единой точки зрения разрабатываются алгоритмические аспекты исследования устойчивости задач дискретной оптимизации и связанные с постоптимальным анализом качественные свойства этих задач: построение количественных характеристик устойчивости для наиболее известных задач дискретной оптимизации, проблемы сложности, табулирования, вычислительные методы и алгоритмы, эвристики и оценки, связь с параметризацией. Все полученные результаты являются новыми и имеют, кроме того, наиболее общий характер по сравнению с известными результатами в области исследования устойчивости задач дискретной оптимизации.
Степень достоверности результатов. Все сформулированные положения доказаны в рамках принятых в современной математике логических стандартов строгости, являются обоснованными и получили квалифицированную апробацию.
Личное участие автора в получении научных результатов Все основные результаты, приведенные в выносимой на защиту диссертационной работе, получены лично автором. Часть результатов получена в соавторстве, что отмечено в тексте работы.
Теоретическая и практическая ценность. В значительной степени работа имеет теоретический характер и является существенным вкладом в теорию и методы решения дискретных экстремальных задач. Для случая минимаксного функционала проведены полные исследования устойчивости решений для широкого класса норм и произвольного множества стабильных элементов. Для задач с линейным функционалом получены формулы для радиуса устойчивости и построены алгоритмы его вычисления с учетом комбинаторной структуры конкретных хорошо известных оптимизационных проблем. Исследована зависимость трудоемкости алгоритмов от числа оптимальных решений. Получены критерии
конечнозначности параметрических задач дискретной оптимизации. Возможности для приложений обуславливаются следующими очевидными факторами: на практике параметры задач заданы с некоторой степенью точности, поэтому построенные методы и алгоритмы позволяют более адекватно разрабатывать и анализировать математические модели в экономике и производстве, которые используют задачи дискретной оптимизации. Кроме того, как уже указывалось выше, теоретические построения и алгоритмы, разработанные в диссертации, позволяют строить процедуры ориентированные на решение не одной задачи, а некоторого множества близких задач с уменьшением трудоемкости решения этих задач. Построение и исследование таких моделей проводятся, например, в ВЦ РАН, ИМ АН Белоруссии, ИК АН Украины.
Апробация работы. Основные результаты работы были доложены на международных конференциях: I Советско - итальянская конференция "Методы и приложения математического программирования" , Четраре, Италия, 1992; II Международная конференция "Комбинаторные методы и приложения" , Нойбранденбург, ГДР, 1989, "8 Fichland colloquem", Вустров, ГДР, 1988, "Дискретная математика и вопросы математической кибернетики", Мегдешпрунг, ГДР, 1988, "Дискретная математика и приложения в математической кибернетике", Иена, ГДР, 1986, на четырех советско-германских семинарах по комбинаторике и дискретной оптимизации ( Москва (1980), Самарканд (1984), Алма-Ата (1986), Ереван (1989)), на Всесоюзной конференции по теоретической кибернетике, Новосибирск, 1980, Всесоюном симпозиуме " Статистический анализ нечисловой информации. Экспертные оценки. Дискретная оптимизация" , Алма-вта, 1981, на двух Всесоюзных конференциях по теории графов и дискретной оптимизации ( Батуми, 1981, Батуми, 1990), на Республиканском семинаре "Методы дискретной оптимизации и их программное обеспечение", Ужгород, 1985, а такхе еще на семи всесоюзных и республиканских семинарах и конференциях и на ряде семинаров в институтах АН СССР и зарубежных институтах.
Публикации. По теме диссертации опубликовано 26 работ, из них 17 - в центральных научных журналах и периодических сборниках. Основное содержание диссертации отражено в публикациях Ш-ЕІ9].
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и библиографии (108 наименований). Общий объем работы 247 стр.
