Введение к работе
Актуальность темы. Многие прикладные задачи, возникающие при планировании и реконструкции производства, формировании генеральных планов предприятий, проектировании печатных плат, в стандартизации и других отраслях сводятся к решению дискретных задач оптимального размещения.
В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные ж приближенные методы пх решения [1-4, 7-11,13-17,19-36]. В последние годы интенсивно разрабатываются подходы, основанные на аналогиях с природой (генетические алгоритмы, алгоритмы муравьиной колонии, имитации отжига и др.) [5,12] и методы локальной оптимизации [14,18].
Актуальность исследования дискретных задач размещения связана с NP-трудностью этих задач, а также с большими стоимостями проектов. Использование методов оптимизации для их решения может привести к значительному уменьшению затрат и повышению доходов. В связи с этим становится важной разработка алгоритмов решения таких задач и исследование их эффективности.
Цель работы. Целью данной работы является разработка и анализ точных и приближенных алгоритмов решения дискретных задач оптимального размещения производства и задач размещения взаимосвязанных объектов на линии и плоскости.
Методы исследования. В работе использованы теория и методы целочисленного программирования, комбинаторной оптимизации, современная методология экспериментальных исследований с примене-іием вычислительной техники.
Научная новизна. В диссертации подучили дальнейшее разви-
тие и применение методы декомпозиции и регулярных разбиений в дискретной оптимизации. С использованием этих подходов предложены новые варианты точных и приближенных алгоритмов решения ряда известных задач размещения производственно-транспортного типа, а также задач размещения взаимосвязанных объектов, имеющих широкий круг приложений.
Основные результаты диссертации заключаются в следующем.
-
Разработаны точные алгоритмы решения задачи размещения с ограничениями на объемы производства, простейшей задачи размещения и задачи о р-медиане, основанные на декомпозиции Бендерса и лексикографическом переборе элементов Z-разбиения. Разработана комбинация этих алгоритмов с различными эвристиками.
-
Для задачи оптимизации супермодулярной функции, которая представляет собой обобщение задачи о р-медиане, введено понятие крутизны ее целевой функции. Найдены теоретические оценки точности варианта приближенного алгоритма градиентного типа решения этой задачи с использованием крутизны п параметров допустимой области. Указан способ получения задач с заданной крутизной.
-
Построены приближенные алгоритмы решения задачи размещения с ограничениями на объемы производства, простейшей задачи размещения и задачи о р-медиане. Для задачи о р-медиане предложены варианты рандомизации одного из алгоритмов.
-
Для задач размещения взаимосвязанных объектов на линии в целочисленной постановке разработаны приближенные алгоритмы, основанные на использовании процедур округления, последовательно-одиночного размещения и методов линейного программирования. С помощью предложенных алгоритмов проверки размещения объектов на локальную оптимальность п его коррекции выполнена экспертиза проекта нефтехимической установки.
5. Выполнена реализация предложенных точных и приближенных алгоритмов, проведено их экспериментальное сравнение. Исследовано поведение рандомизированных эвристик при различных значениях крутизны целевой функции. Экспериментальные исследования показали перспективность построенных алгоритмов.
Практическая ценность. Предложенные точные и приближенные алгоритмы применимы в научных исследованиях и при решении прикладных задач. Разработанные программы и тестовые задачи используются в учебном процессе.
Апробация работы. Результаты диссертации докладывались на Школе "Декомпозиция и координация в задачах проектирования и управления" (Миасс, 1988), Всесоюзной конференции "Дискретная оптимизация и исследование операций" (Новосибирск, 1992), "Расширенных заседаниях одесской школы-семинара по дискретной математике и приложениям" (Одесса, 1993, 1994, 1997), Всесоюзной конференции "Математическое программирование и приложения" (Екатеринбург, 1993. 1995), 10 и 11 Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1995, 1998), "Втором Сибирском конгрессе по прикладной и индустриальной математике" (Новосибирск, 1996), Международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997), International Conference on Operations Research (Цюрих, Швейцария, 1998), "Международной сибирской конференции до исследованию операций" (Новосибирск, 1998), Symposium on Operations Research SOR'99 (Магдебург, Германия, 1999), Международной конференции "Распределенные системы: оптимизация и приложения & экономике и науках об окружающей среде" (Екатеринбург. 2000), Международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), на научных семинарах в ИИТПМ СО РАН (Омск), Омском филиале
Института математики СО РАН, Институте динамики систем и теории управления СО РАН (Иркутск).
Публикации. Основные результаты диссертации опубликованы в 17 работах. Их список приведен в конце автореферата.
Структура и объем работы. Диссертация изложена на 130 страницах и состоит из введения, четырех глав, заключения, списка литературы (130 наименований) и приложения.