Введение к работе
Актуальность роботи. Многие вопросы, связанные с исследованием сложных конечных систем и управлением в таких системах, приводят к моделям и задачам комбинаторной оптимизации. В последние десятилети интерес к методам комбинаторной оптимизации значительно вырос благодаря многочисленным приложениям, а также в связи с появлением совершенных вычислительных средств. Основные направления исследований в области комбинаторной оптимизации связаны с разработкой и анализом аффективных а^'орииов, с создание?* прпбликенных методов, о изучением структурных, характеристик задач. В последние ,ода особое внимание привлечено к вопросам сложности задач комбинаторной оптимизации ІШтопйз J., Gratachel If., Padberg II.її., Cook S.A., Karp R.U.). ' . .
Большое число работ посвящено изучению геометрических свойств задач": основой таких рассмотрений служит формализация их в виде задач - оптимизации линейных функций на конечных мнокествах в евклидовом пространстве, В этой связи естественно возникали описания алгоритмической сложности задач в терминах свойств ассоциированных шгагсгранников (Kuhn В.її., Beller 1 , Uor&oek J.. Вжелтев В.А., Леонтьев. В.К., Сарванов В.И., PapadintttHou СВ.). Основная цель такого рода построений заключается в отыскании аффективно описываемых характеристик задач, количественно свидетельотвуицих об их труднорешаемости.
Теория и практика.. приближенных методов комбинаторной
оптимизации далеки от своего завершения. След,''-' отметить относительное разнообразие приемов и ввристических идей, используемых при создании приближенных ' алгоритмов, соответствующая библиографы включа >т несколько тысяч названий работ; большинство разработанных алгоритмов направлено на решение за/пч при ограничениях достаточно произвольного характера, либо жестко связаны спецификой задачи. Поэтому возникает нрослема качественной оценки приближенных методов; традиционные подходы, основанные в большинстве случаев на вычислительном експерименте, обладают очеіидшми н достатками.
Эти обстоятельства объясняют ' актулыюсть разработки новых
направлений системного анализа задач- и алгоритмов комбинаторной
.оптимизации. '' .
Цель работы. Целью работы является разработка методов получения характеристик труднорешаемости задач комбинаторной оптимизации и исследование приближенных алгоритмов их решения.
Методы исследования. В ра зте используются методы теории выпуклыг многогранников, методы теории графов, методы теории алгоритмов, методы теории линейных неравенств.
Научная новизна. В диссертации формально описан класс алгоритмов комбинаторной оптимизации, включающий известные алгоритмы, использующие линейке сранения. Этот класс алгоритмов определен на основе , условий геометрического характера, обусловленных реализуемостью алгоритмов;
Обнаружена комбинаторно-геометрическая характеристика задач -плотность графа . ассоциированного . многогранника, которая полиномиальна по размерности задач для полиномиально разрешимых и экспоненциальна для труднорешаемых задач комбинаторная оптимемит. Установлено, что, вта характеристика служит не яеЯ
оценкой слокности задач в указанном классе алгоритмов.
В работе обнаружены и ефективно . описаны выпуклые многогранники, плотность графов которых экспоненциальна, но внешнее описание которых включает полиномиальное количества линейных ограничений. Существование таких многогранников дает возможность. использования полиномиальных алгоритмов линейного программирования (Хачшт Л.Т., КапюгЪаг N.A.) для комбинаторно труднсрешаемых задач.
Разработан метод объективного анализа приближенных (эвристических) алгоритмов, оспованный на исследовании качества использования исходной информации; о его помощью проведено подробное исследование "надного"-(greedy) алгоритма.
Теоретическая и прантчеасая ценность. Работа теоретическая. Иетоди, разработанные в диссертации, применимы к анализу широкого класса задач комбинаторной оптимизации, возникающих при разработке различных СЛ02НЫХ систем (економичесісих, вычислительных ir т.п.) л при опшянзацші упрявлени" в них. Результаты работы дают ответ на ряд прхшциштльпых качественных вопросов относительно причин труднорепшемости' задач,' позволяют объективно характеризовать приближенные методы реаения. Разработанные в диссертации методы анализа еффзкгшшо реализуемы; в частности, для большого числа классических задач я алгоритмов они позволили установить ряд новых фактов. .
Апробация рабояи. Результата диссертации докладывались на Международной конференции "Математические методы в исследовании операций" ( ..гя. 1993 г., 1937 г.), па Всесоюзной конференции "Проблемы теоретичесімй кибернетики" (Иркутск, 1985 г.; Волгоград, 1990 г.), на семинарах Института проблем управления РАН, Центрального оконаяжо-математичоского шстптута РАН, . Института
проблем передачи информации РАН,' Вычислительного центра РАН, Воронежского, . государственного университета, . Ярославского .государственного университета.
Публикации. Основные результаты диссертации опубликованы в 16 печатных работах.
Структура и овъел работы. Диссертация состоит из. введения, четырех глав и списка литературы. Диссертация' изложена на 148 страницах. Библиография содержит.72 наименования.