Введение к работе
Анализ допустимого множества решений и использование релаксационных задач позволяют либо повысить эффективность известных методов реаения, либо разработать новые методы решения задач дискретной и комбинаторной оптимизации. В диссертационной работе исследуется ЛП-релаксационная задача для задачи безусловного квадратичного программирования с -1,1-леременнными и задача на пересекающихся отрезках. Задача безусловной квадратичной оптимизации с -1,1-пёременными представляет интерес в связи с сводимостью к ней ряда известных HP-полных задач комбинаторной оптимизации и задач теории твердого тела по определению устойчивого состояния кристаллических решеток. Задача на непересекающихся отрезках является задачей на специальном классе комбинаторных конфигураций и обобщением задач на множестве перестановок. Она возникает в области проектирования интегральных схем и связывающих сетей.
Для обеих задач в качестве аппарата исследования применяются современные подходы полиэдральной комбинаторики по анализу структуры выпуклых оболочек допустимых множеств решений.
Сказанное и определяет аюуъдыюсть теш диссертации. Работа является продолжением исследований, проводимых в Белорусском государственном университете на факультете прикладной математики и информатики и выполнена в соответствии с индивидуальным планом аспирантской подготовки, госбюджетной темой "Разработка методов и алгоритмов решения задач оптимизации информационных потоков, распознавания образов и обработки естественно-языковой информации как модулей интеллектуальных автоматизированных систем", номер гос. регистрации 01920001546, выполняемой по плану АН Беларуси, и госбюджетной темой "Разработка теории устойчивого математического моделирования систем, логико-комбинаторных и вероятностно-статистических методов оптимизации и распараллеливания вычислительно-информационных процессов", план Бедгосуниверситета, приказ БГУ ОТ 25.09.91, N 97-Д.
Целью работы является: 1) описание мнодюства вершин ре;, .кса-ционного многогранника с полиномиальным числом ограничений для
задачи квадратичного программирования с -1,1-переменными и лрове-дение численного эксперимента по решению ЛП-релаксационной задачи; 2) определение характеристик выпуклой оболочки допустимого множества задачи на непересекающихся отрезках, свойств оптимального решения и разработка ка их основе полиномиального алгоритма для решения линейной задачи.
Научная новизна полученных результатов обусловлена впервые осуществленными постановками задач, исследуемых в диссертационной работе. Впервые получено описание множества целочисленных вершин для релаксационного многогранника задала квадратичного программирования с -1,1-переменными, определяемого 'толиномиальным числом ограничений, вводится понятие остовного многогранника и указано семейство гиперграней, включение которых в систему ограничений гарантирует остовность релаксационного многогранника.
Для задачи на непересекающихся отрезках определяется размерность, множество вершин и отношение смежности в нем для выпуклой оболочки множества допустимых решений. Установлены свойства оптимального решения, зависящие от знаков коэффициентов линейной целевой функции. Лается полиномиальный по времени алгоритм решения линейкой задачи. Описано семейство гиперграней выпуклой оболочки. Все результаты получены впервые.
Пракгтеская значимость полученных результатов состоит в том, что предложенная релаксационная задача и алгоритм решения задачи на непересекающихся отрезках могут применяться для решения научно-прикладных задач задач теории твердого тела и проектирования интегральных схем. укладывающихся в рамки рассматриваемых моделей. Теоретическая ценность работы заключается в возможности дальнейшего изучения свойств допустимых множеств задач оптимизации комбинаторного типа на основе полученных в работе результатов.
Основные положения диссертации, выносимые на защиту. В работе дается постановка задачи квадратичного программирования с -1,1 -переменными, описываются практические ситуации, приводящие к ней. Указывается взаимосвязь с известными задачами комбинаторной оптимизации. Приводятся известные основные характеристики многогранника эквивалентной задачи линейного программирования, опреде-
ляемого целевой Ф/нкцией и ограничениями исходной задачи. Дается определение релаксационной задачи через множество гиперграней многогранника эквивалентной задачи линейного программирования.
Центральное место занимает исследование релаксационной задачи с полиномиальным числом ограничений. Вводится понятие остовно-го релаксационного многогранника. Рассматривается многогранник релаксационной задачи и изучается множество его вершин. Показано, что он является остовным для многогранника эквивалентной задачи линейного программирования. Указано семействе его нецелочисленных вершин. Приводятся результаты численного эксперимента для релаксационной задачи.
Рассматривается также оптимизационная задача на множестве непересекающихся отрезков. Дается постановка практической задачи геометрического проектирования, приводящей к ней. Еводится в рассмотрение многогранник кепересекаюпдахся отрезков. Определена его размерность, описывается множество вершин и исследуется отношение смежности между вершинами. Приводится сем-эйство гиперграней для многогранника на непересекающихся отрезков. Предлагается полиномиальный по сложности алгоритм для линейной задачи на непересекающихся отрезках. Алгоритм иллюстрируется примерами.
Все основные результаты диссертационной работы получены автором саше тоятелъ но.
Апробация результатов диссертации. Результаты диссертационной работы докладывались на:
Международной конференции "Новые предприятия в процессе строительства Большой Европы", сентябрь 19S3 г.. Минск;
Межгосударственной научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение", 16-20 мая 1994 года, Минск;
Республиканской научно-мегодичеел-ой конференции, посвященной 25-летию ФПМИ Белгосуниверситета, 10-14 апреля 1995 года, Минск.
Результаты диссертационной работы опубликованы в шести работах.
Структура и объем диссертации. Диссертация состоит из введе-
ния, общэя характеристики работы, трех глав, выводов и спис:-» использованных источников.
Объем диссертационной работы - 61 страница, включая две таблицы и список использованной литературы, который содержит 137 наименований.