Содержание к диссертации
Введение 4
Глава 1. Задачи оптимального размещения 11
L1 Постановки задач 11
Ri>i4H('.mhгелміая сложность задал шгп-шалмтго размещения предприятий 20
Методы решения задач размещения 22
Глава 2. Построение и анализ декомпозиционных
алгоритмов для простейшей задачи размещения ... 34
Метод регулярных разбиений 34
Анализ дробных накрытий задач 38
2.'3 Алгоритмы декомпозиции и перебора L-kjiucvok
для ПЗР 47
2А Оценки числа итераций для алгоритма
декомпозиции Бсидсрса 58
Глава 3. Разработка декомпозиционных алгоритмов
для двухуровневой задачи размещения 63
ЗЛ Задачи двухуровнекого программирования 63
Сведение к одноуровневой задаче Gfi
Декомпозиционные алпцжтмм / v і я д ну хуроиневой задачи . 71
Исследование декомпозиционных алгоритмов
для двухуровневой задачи . 77
Глава 4. Результаты экспериментальных исследований . 81
4.1 Особенности алгоритмов 81
4/2 Результати экспериментальных ж1 еле діжа ний
для нросіеишей задачи размещения 84
4.3 Вычислительный эксперимент
для двухуровневой задачи размещения 94
Заключение 99
Список литературы 100
\
.
\
в частности, двухуровневая задача размещения(ДЗР}, также являющаяся обобщением ПЗР [22, 27, 28, 34, 82]. Обширная литература посвящена и тесно связанной с ПЗР задаче о р-медиано [11, 102, 113, 129, 130, 135|. Задачи размещения второго тина изучаются, например, її [15, 39, 40, 80, 81, 91, 93, 97, 140, 150]. Данная диссертация посвящена задачам размещения предприятий.
Рассматриваемые задачи относятся к классу ТУЯ-трудных проблем дискретной оптимизации [135]. Вопросы сложности задач размещения предприятий и сводимости к ним известных задач изучаются, например, в [1, 31, 45, 59, 72, 113, 135], В связи с jVP-трудностыо задач применение алгоритмов, специально разработанных для их решения, позволяет существенно повысить размерность решаемых задач.
Во многих случаях дискретные задачи оптимального размещения удобно описывать с помощью моделей целочисленного программирования (ЦП). Условие целочисленное позволяет учесть неделимость размещаемых элементов, дискретность процессов, наличие альтернатив и другие факторы.
Основные методы решения задач целочисленного программирования могут быть разделены па две* основные группы:
Методы, базирующиеся на сведении исходной задачи целочисленного программирования к последовательности более "простых^задач, для которых применимы методы непрерывной оптимизации. Это, например, методы отсечения и множителей Лаграпжа, метод Лэнд и Дойг, перебор L-классои [41, 78, 83].
Методы, в которых применяются различные схемы перебора целочисленных точек. Наиболее известные точные методы второго типа - комбинаторные методы ветвей и границ и декомпозиции [8, 19, 22, G5, 73, 82, 90, 144|.
Достаточно широкое распространение получил метод декомпозиции
Введение к работе
При планировании развития производства, в сфере сервиса и других областях часто возникает необходимость в решении задач оптимального размещения предприятий. Во многих случаях такие задачи являются весьма сложными и требуют применения методов математического моделирования, разработки специальных алгоритмов и программного обеспечения.
Задачи оптимального размещения могут быть описаны в терминах дискретной оптимизации и образуют важное направление в этой области, которое включает изучение структуры и вычислительной сложности задач, разработку и анализ точных и приближенных методов их решения, выделение полиномиально разрешимые случаев, построение семейств "трудных" задач для определенных алгоритмов [4, 11, 38, 134].
Можно выделить два основных типа задач, относящихся к указанному классу: задачи размещения предприятий и задачи размещения взаимосвязанных объектов. В задачах первого типа предприятия необходимо расположить в ряде пунктов и назначить им потребителей, которых они будут обслуживать. Область размещения объектов в задачах второго типа может быть различной: линия, плоскость, сеть и т.д., причем эти обьекты могут быть связаны какими-либо коммуникациями.
Значительное число работ посвящено простейшей задаче размещения предприятий (ПЗР) и ее обобщениям, таким как задача размещения с ограничениями па обьемы производства [74, 138, 146|, многопродуктовая производственно-транспортная задача [8], динамическая задача размещения предприятий [11, 94|, многостадийная задача размещения предприятий [24, 25] и ряд других. В последнее время большой интерес вызывают задачи миогоуровневнего программирования, к которым относится,
Бепдерса [76, 90, 119, 123, 144], который часто используется в сочетании с другими методами, например, со схемой Балаша [8], перебором L-классов [127, 138]. С теоретической точки зрения метод декомпозиции Бендерса пока еще недостаточно изучен. В частности, актуальными являются вопросы получения оценок числа итераций, исследование глубины отсечений, выделение семейств "трудных"задач и другие. При построении отсечений Бендерса оптимальные значения двойственных переменных определяются неоднозначно, что существенным образом можно использовать для повышения эффективности алгоритмов.
В последнее время в области целочисленного программ ирования получил развитие предложенный А.А. Колоколовым подход, основанный на регулярных разбиениях евклидова пространства, в частности, на использовании L-разбиений и .^.-разбиений. Применение такого подхода к задачам целочисленного программирования позволяет изучать структуру задач, вводить и исследовать новые классы отсечений, получать оценки числа итераций алгоритмом, исследовать их устойчивость |6, 41, 43, 56, 57,60, 130].
Целью диссертации является является исследование простейшей задачи размещения предприятий и ее обобщения - двухуровневой задачи с использованием регулярных разбиений, разработка и анализ декомпозиционных алгоритмов с отсечениями Бендерса для решения этих задач.
Основными обьектами исследования в диссертации являются простейшая и двухуровневая задачи размещения предприятий. Для их решения разработаны и реализованы точные алгоритмы, основанные на применении декомпозиции Бендерса. В этих алгоритмах решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных подзадач. Для построения производственных подзадач используются дополнительные неравенства (отсечения Бендерса).
Рассматриваемые варианты декомпозиционных алгоритмов отличаются от классических тем, что в них не требуется решать задачу целочисленного программирования при нахождении очередного производственного плана. Эти планы выбираются среди допустимых решений производственной задачи с помощью алгоритма перебора L классов или направленным перебором булевых векторов.
Предложены гибридные варианты данных алгоритмов с различными эвристиками. Исследована глубина используемых отсечений и получены оценки числа итераций алгоритмов на построенных нами семействах задач. Проведен анализ эффективности отсечений в зависимости от способа выбора оптимальных значений двойственных оценок, используемых при их построении.
Кроме того, в работе построены семейства простейших задач размещения с мощными Lfc-разбиениями дробных накрытий задач. Проведены экспериментальные исследования эффективности различных вариантов предложенных алгоритмов.
Диссертация состоит из введения, четырех глав, заключения и списка литературы.
В первой главе содержатся постановки основных задач размещения предприятий: простейшая задача размещения на максимум и минимум, задача размещения с ограничением па обьемы производства, многопродуктовая производственно-транспортной задача, двухуровневая задача размещения, а также некоторые другие близкие к ним задачи, рассматриваются вопросы сложности решения этих задач.
Далее дается краткий обзор наиболее известных точных методов решения задач размещения, подробно излагается общая схема декомпозиции Бепдерса. Приводятся сведения о полиномиально разрешимых случаях простейшей и двухуровневой задач размещения.
В связи с высокой вычислительной сложностью рассматриваемых за-
дач актуально создание приближенных методов решения, а также получение оценок их точности. В главе приведены наиболее известные приближенные и эвристические алгоритмы, указаны оценки точности некоторых из них.
Во второй главе исследуется простейшая задача размещения. Описывается метод регулярных разбиений, в том числе L-разбиение и *-разбиение, излагается математический аппарат, необходимый для построения алгоритмов. Здесь же обсуждаются вопросы, касающиеся Z-структуры задач ЦП, н том числе простейшей задачи размещения. Предлагаются семейства ПЗР, обладающие мощными Lfc-накрытиями.
В данной главе описываются также реализованные автором декомпозиционные алгоритмы для решения ПЗР. В этих алгоритмах предусмотрено построение отсечений по целочисленным точкам, удовлетворяющим различным условиям (с использованием разных способов выбора оптимальных значений двойственных оценок); регулирование размерности матрицы ограничений производственной задачи и другие возможности. Разработаны варианты декомпозиционнного алгоритма, в которых на предварительном этапе для получения начального рекорда используются эвристические процедуры.
Приводятся оценки числа итераций для ряда декомпозиционных алгоритмов решения простейшей задачи размещения. Показано, что глубина отсечений Бендерса для ПЗР зависит от способа выбора оптимальных значений двойственных оценок, используемых при их построении, и может изменяться от 1 до величины, превышающей 2"-1, где п— число пунктов возможного размещения предприятий.
В третьей главе исследуется двухуровневая задача размещения предприятий. Дается краткий обзор задач двухуровневого программирования. Рассмотриваются различные варианты двухуровневой задачи размещения, а именно ДЗР в условиях однозначного и неоднозначного вы-
бора потребителей, кооперативная и антикооперативная модели. Далее исследуется двухуровневая задача размещения в условиях однозначного выбора потребителей. Ранее [26] были предложены различные способы сведения такой задачи к одноуровневой оптимизационной задаче. Здесь выбирается один из таких способов и для получающейся одноуровневой задачи предлагается алгоритм решения, аналогичный алгоритму декомпозиции Беидерса для ПЗР, учитывающий специфику задачи.
Рассмотрены вопросы, связанные с оценкой числа итераций декомпозиционных алгоритмов. Доказано, что глубина отсечений Бендерса для ДЗР может изменяться в тех же пределах, что и для ПЗР.
Четвертая глава посвящена экспериментальному исследованию описанных декомпозиционных алгоритмов для простейшей и двухуровневой задачи размещения. Эксперимент проводился на тестовых задачах из электронной библиотеки Института математики СО РАН и библиотеки OR-Library [104], на задачах из семейств, предложенных во второй и третьей главах диссертации, в том числе обладающих мощными Lk накрытиямии, а также на задачах со случайными данными. Исследовалась зависимость числа итераций алгоритмов от способа выбора оптимальных значений двойственных переменных, используемых при построении отсечений; правил выбора целочисленных точек, по которым строятся отсечения Беидерса; числа сохраняемых отсечений; предварительного применения эвристических алгоритмов.
Выполнено экспериментальное сравнение различных вариантов предложенных алгоритмов между собой, а также с известным пакетом CPLEX 6.5. На тестовых задачах из электронной библиотеки ИМ СО РАН декомпозиционные алгоритмы показали существенное преимущество по времени решения по сравнению с указанным пакетом.
Основные результаты диссертации опубликованы в работах [59, 61-63, G6, 85-89,128, 131] и докладывались на Международной научно-методи-
ческой конференции "Математика в вузе" (Великий Новгород, 2000), Международной конференции "XII Meeting of EURO Working Group on Location Analysis" (Барселона, 2000), конференции с международным участием "Новые технологии ж/д транспорту" (Омск, ОмГУПС, 2000), XII Международной Байкальской конференции "Методы оптимизации и их приложения" (Иркутск, 2001), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), Международной конференции "European Chapter on Combinatorial Optimization ECCO XVIII" (Минск, 2005), на заседаниях научных семинаров в Омском филиале Института математики им С.Л. Соболева СО РАН и Институте математики и механики УрО РАН.
Автор выражает благодарность научному руководителю д.ф.-м.н., профессору А.А. Колоколову за постоянное внимание к работе и всестороннюю поддержку, а также признательность к.ф.-м.п., доценту Т.В. Лева-новой за помощь и полезные советы.
