Введение к работе
Актуальность темы. Значительное число работ в области исследования операций посвящено решению проблем планировки и расположения объектов. Такие задачи возникают при размещении различных пунктов обслуживания, например, больниц, магазинов, пожарных депо, формировании генеральных планов предприятий, проектировании печатных плат, компоновке оборудования летательных аппаратов и выполнении других работ.
В настоящее время активно развиваются теория и методы решения задач размещения1, ведутся исследования их структуры и вычислительной сложности2, выделяются полиномиально разрешимые случаи3, предлагаются точные и приближенные алгоритмы их решения4. В последние годы для решения задач оптимизации широко разрабатываются методы локального поиска, а также подходы, основанные на аналогиях с природой5. Данные подходы являются перспективными и для задач размещения, которые, как правило, являются NP-трудными.
Использование оптимизационных методов для решения задач размещения на сетях приводит к снижению стоимости реализуемых проектов. Поэтому актуальной проблемой является разработка алгоритмов решения таких задач и исследование их эффективности.
1 Колоколов А А , Леванова ТВ Алгоритмы декомпозиции и перебора L-классов для решения некоторых задай размещения //Вестник Омского унта -Омск, 1996 -№1 -С 21-23
23абудский Г Г О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы - Новосибирск, 1990 - Выл 30 - С 35-45
3Панюков А В , Пельцвергер Б В Оптимальное размещение дерева в конечном множестве Ц
Журнал вычислительной математики и математической физики - 1988 - Т 28 - С 618-620
4Стрекаловский АС , Васильева А М Поиск глобального решения в задаче размещения //'Материалы международной конференции "Дискретный анализ и исследование операций" - Новоси бирск, 2000 - С 121
$КочетовЮ АВероятностныеметодылокальногопоискадлязадачдискретнойоптимизации // В сб лекций "Дискретная математика и притюжениУ - Москва. 2001 -С 84-117
[рос, национальная
Цель работы. Целью данной работы является исследование задач оптимального размещения взаимосвязанных объектов на сетях, разработка, анализ и реализация точных и эвристических алгоритмов их решения.
Методы исследования. В работе использованы теория и методы линейного программирования (ЛП), комбинаторной оптимизации, теория графов, современная методология экспериментальных исследований с применением вычислительной техники и пакетов прикладных программ для решения задач оптимизации.
Научная новизна и результаты, выносимые на защиту. В диссертации получили дальнейшее развитие теория и методы решения задач оптимального размещения взаимосвязанных объектов на сетях. Предложены новые варианты точных и эвристических алгоритмов решения минимаксной и минисуммной задач размещения.
Основные результаты диссертации, выносимые на защиту, заключаются в следующем:
Предложены достаточные условия оптимальности значения целевой функции в непрерывной минимаксной задаче на древовидной сети с ограничениями на максимально допустимые расстояния. Разработан полиномиальный алгоритм решения дискретного варианта задачи.
Разработан полиномиальный алгоритм получения точного решения для минисуммной задачи размещения на дереве с ограничениями на максимально допустимые расстояния.
Доказано, что задача определения совместности ограничений на максимально допустимые расстояния в случае размещения объектов в вершинах, а также дискретная минимаксная задача оптимального размещения на произвольной сети являются NP-трудными.
Получены необходимые условия существования допустимого размещения на произвольной сети для дискретного варианта задачи с ограничениями на максимальные расстояния. На их основе разработаны алгоритмы ветвей и границ для минимаксной и минисуммнои задач.
Разработаны эвристические алгоритмы: последовательного одиночного размещения, генетический алгоритм и поиск с запретами для решения указанных выше задач. Предложенные алгоритмы реализованы, проведено их экспериментальное сравнение, которое показало эффективность разработанных алгоритмов.
Практическая ценность. Предложенные точные и приближенные алгоритмы применимы в научных исследованиях задач оптимального размещения и при решении прикладных задач. Разработанные алгоритмы, программы и тестовые примеры могут использоваться в учебном процессе.
Апробация работы. Результаты диссертации докладывались на XI Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1999), Symposium on Operational Research (Магдебург, Германия, 1999), международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), научной молодежной конференции "Молодые ученые на рубеже третьего тысячелетия" (Омск, 2001), XII Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002), International Conference on Operations Research (Клагенфурт, Австрия, 2002), 12-й Всероссийской конференции "Математическое программирование и приложения" (Екатерин-
бург, 2003), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международном семинаре "Discrete Optimization Methods in Production and Logistics" (Омск-Иркутск, 2004), а также на научном семинаре "Математическое моделирование и дискретная оптимизация" в Омском филиале Института математики СО РАН им. СЛ.Соболева.
Публикации. Основные результаты диссертации опубликованы в работах [1-15].
Личный вклад автора состоит в получении достаточных условий оптимальности целевой функции в непрерывной минимаксной задаче на древовидной сети с ограничениями на максимально допустимые расстояния, доказательстве iVP-трудности дискретной минимаксной задачи размещения и построении необходимых условий существования допустимого размещения на произвольных сетях, разработке алгоритмов решения минимаксной и минисуммной задач на древовидных и произвольных сетях, проведении вычислительного эксперимента.
Структура и объем работы. Диссертация изложена на 94 страницах и состоит из введения, трех глав, заключения и списка литературы (102 наименования). В каждой главе использована своя нумерация параграфов, утверждений, теорем и формул.
