Введение к работе
Диссертация посвящена теоретическому исследованию полиэдральных свойств задач размещения с предпочтениями клиентов и построению новых оценок оптимальных значений этих задач, а также разработке и реализации численных методов поиска оптимальных решений.
Актуальность темы. Задачи размещения представляют большой интерес для специалистов как с теоретической, так и с практической точки зрения. Большинство таких задач относится к классу NP-трудных, поэтому разработка эффективных алгоритмов поиска оптимальных решений задач размещения в настоящее время является актуальной проблемой в области методов оптимизации. С другой стороны, актуальность исследований задач размещения объясняется широким спектром важных практических приложений в технике, экономике и экологии. В частности, модели размещения возникают при проектировании сетей обслуживания, решении задач стандартизации, кластерного анализа и т.д. Кроме того, внимание специалистов в области оптимизации в последнее время привлекают задачи с иерархической структурой, уровни иерархии в которых неравноправны.
Задачи размещения с предпочтениями клиентов (ЗРПК) представляют собой один из вариантов двухуровневых обобщений базовых моделей задач размещения: простейшей задачи размещения и задачи о р-медиане. В них учитывается дополнительная информация о предпочтениях клиентов, которые могут отличаться от пожеланий поставщика, определяемых минимизацией транспортных затрат.
Исследованию задач размещения различных классов посвящено большое количество работ. В России такие задачи исследуются с 70-х годов XX века под руководством В.Т. Дементьева, В.Л. Вереснева, Э.Х. Гимади1-1, А.А. Колоколова и др.
Насколько известно, впервые модель ЗРПК была предложена и исследована P. Hanjoul и D. Peeters2-1. Позже аналогичные задачи изучались, в том числе, в работах В.Т. Дементьева, В.Л. Вереснева, Э.Х. Гимади, А.А. Колоколова, Ю.А. Кочетова, Л.Е. Горбачевской.
Для разработки методов поиска оптимальных решений задач размеще-
1^В.Л. Береснев, Э.Х. Гимади, В.Т. Дементьев. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978.
2)р. Hanjoul, D. Peeters. A facility location problem with clients' preference orderings // Regional Sci. Urban Econom. - 1987 . - V. 17. - P. 451-473.
ния используются модели целочисленного линейного программирования (ЦЛП). Традиционным подходом к решению задач ЦЛП является метод ветвей и границ и его модификации, например, метод ветвей и отсечений. При этом решающую роль в обеспечении скорости работы этих методов играют верхние и нижние оценки оптимального значения исследуемой задачи, использующиеся для сокращения полного перебора допустимых точек.
Для построения нижних оценок в ЗРПК могут быть использованы так называемые правильные неравенства, которые определяют полупространства, содержащие допустимую область задачи (см., например, работы Л.Е. Горбачевской, М. Labbe с соавторами), а также формулировки задачи в пространстве переменных большей размерности — расширенные формулировки (работы Ю.А. Кочетова, Е.В. Алексеевой).
Таким образом, улучшение известных нижних оценок посредством построения новых семейств правильных неравенств, а также разработка новых методов и алгоритмов для поиска оптимальных решений с использованием методов отсечений для этих семейств неравенств является актуальной задачей дискретной оптимизации.
Целью работы является исследование допустимой области ЗРПК и построение новых семейств правильных неравенств для улучшения известных оценок оптимальных значений, а также разработка и реализация численных методов поиска оптимальных решений на основе построенных неравенств.
Предмет и объект исследования. Объектом исследования являются модели ЗРПК в целочисленной постановке.
Предмет исследования — построение эффективных методов поиска оптимальных решений в задачах размещения с двухуровневой структурой.
Методы исследования. В работе используются современная теория комбинаторной оптимизации, теория и методы целочисленного программирования (алгоритмы отсечений, ветвей и границ, ветвей и отсечений), элементы линейной алгебры и теории выпуклого анализа, а также современная методология экспериментальных исследований с применением вычислительной техники и коммерческих пакетов прикладных программ для решения задач оптимизации.
Научная новизна результатов диссертации заключается в улучшении известных к настоящему времени нижних оценок оптимальных значений ЗРПК на основе исследования взаимосвязей этих задач с задачей упаков-
ки множества и с задачей о паре матриц.
Предложено новое семейство правильных неравенств для многогранников ЗРПК, которое уточняет нижние оценки оптимальных значений, полученные с помощью целочисленных постановок задач о паре матриц.
Разработан новый метод поиска оптимальных решений ЗРПК, основной составляющей которого является метод отсечений, адаптированный для предложенного в работе нового семейства правильных неравенств. Эффективность построенного метода подтверждается тестированием на известных из литературы сериях примеров и одной прикладной задаче кластерного анализа.
Достоверность и обоснованность результатов диссертации обусловлена использованием апробированных научных методов и средств, полнотой и корректностью исходных посылок, строгостью математических выкладок и подтверждается результатами вычислительных экспериментов.
Теоретическая и практическая значимость работы. Теоретические результаты диссертации, в частности, новая нижняя оценка оптимального значения ЗРПК, новые правильные неравенства вместе с адаптированным для них методом отсечений и алгоритмом поиска оптимальных решений могут быть использованы при исследовании более сложных задач размещения с двухуровневой структурой (например, задачи об (г,р)-центроиде). Разработанный алгоритм также применим для решения ЗРПК большой размерности. Полученные в диссертации результаты могут быть использованы при исследовании прикладных задач, моделирующих различные процессы в технике, экологии, экономике и других областях.
Исследования по теме диссертации проводились в рамках проектов по программам СО РАН: "Поиск глобальных решений в невыпуклых задачах исследования операций и оптимального управления" (№ гос. регистрации 01.2.007 08581) с 2007 по 2009 гг., программа СО РАН "Математическая теория управления при возмущениях и неопределенности"; "Нелокальные методы в теории управления динамическими системами" (№ гос. регистрации 01201001345) в 2010 г., программа "Теория управления динамическими системами и методы их исследования" а также в рамках комплексного интеграционного проекта СО РАН 1.3 "Исследование задач двухуровневого и равновесного программирования" (2006-2008 гг.); проекта фонда "Научный потенциал" №153 "Задачи комбинаторной оптимизации в мето-
дах кластерного анализа и классификации данных" (2007-2008 гг.).
Соответствие диссертации паспорту научной специальности.
В соответствии с паспортом специальности 05.13.01, в диссертации проведено теоретическое исследование сложных задач комбинаторной оптимизации (задач размещения с предпочтениями клиентов); разработан и программно реализован метод решения этих оптимизационных задач; разработано специальное математическое и программное обеспечение для решения оптимизационной задачи (пп. 1, 4, 5 области исследований).
Апробация работы. Результаты диссертации докладывались и обсуждались на Всероссийской конференции "Дискретная оптимизация и исследование операций" (7 - 14 сентября 2007 г., Владивосток), XIV Байкальской школе-семинаре "Методы оптимизации и их приложения" (2 -8 июля 2008 г., Иркутск, Байкал), конференции "Ляпуновские чтения и презентация информационных технологий" (19 - 23 декабря 2008 г., Иркутск), Школе-семинаре молодых ученых "Информационные технологии и моделирование социальных эколого-экономических систем" (1-6 октября 2008 г., Иркутск (Россия) - Ханх (Монголия)), X и XI Всероссийских конференциях молодых ученых по математическому моделированию и информационным технологиям (8-11 июня 2009 г., Иркутск (Россия) - Ханх (Монголия); 15 - 21 марта, 2010 г., Иркутск - Байкал), IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (29 июня - 4 июля 2009 г., Омск), XL Annual Conference Italian Operational Research Society (AIRO 2009) (September 8 - 12, 2009, Siena (Italy)), Российской конференции "Дискретная оптимизация и исследование операций" (27 июня - 3 июля 2010 г., республика Алтай).
Результаты диссертации обсуждались на научных семинарах в Институте вычислительной математики и математической геофизики СО РАН (руководитель д.ф.-м.н., проф. В.К. Попков), Институте математики им. С.Л. Соболева СО РАН (руководитель д.ф.-м.н., проф. В.Т. Дементьев) и Омском филиале Института математики им. С. Л. Соболева СО РАН (руководитель д.ф.-м.н., проф. А.А. Колоколов), а также на Инженерном факультете Университета Саннио, г. Беневенто (Италия), на семинаре в Университете г. Сиена (Италия) и неоднократно на семинарах Института динамики систем и теории управления СО РАН.
Публикации и личный вклад автора. По материалам диссертации опубликовано 12 работ, в том числе статьи [1-3] в журналах, рекомендованных ВАК РФ.
В работах [1, 2] соавтору И.Л. Васильеву принадлежит идея исследования полиэдральной структуры ЗРПК на основе взаимосвязей с задачами о паре матриц и упаковки множества. Теоремы, касающиеся нового семейства правильных неравенств и новой нижней оценки, были сформулированы и доказаны автором лично.
Разработка и реализация нового метода ветвей и отсечений, предложенного в диссертации, осуществлялись автором лично. Из совместных публикаций с Ю.А. Кочетовым, А.В. Плясуновым, Е.В. Алексеевой на защиту выносятся только результаты, полученные автором лично.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 177 наименований. Общий объем диссертации составляет 124 страницы, из которых 107 страниц основного текста, включающего 3 рисунка и 11 таблиц. Результаты главы 2 опубликованы в работах [1,2,5,7]. Результаты главы 3 опубликованы в работах [1,3,4,6-12].
