Исследование задач размещения предприятий и разработка декомпозиционных алгоритмов их решения

• Автор: Рубанова, Наталия Алексеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 116 с. : ил.

Оглавление
Введение

Глава 1. Задачи оптимального размещения

1.1 Постановки задач

1.2 Вычислительная сложность задач оптимального размещения предприятий.

1.3 Методы решения задач размещения.

Глава 2. Построение и анализ декомпозиционных

алгоритмов для простейшей задачи размещения .

2.1 Метод регулярных разбиений

2.2 Анализ дробных накрытий задач.

2.3 Алгоритмы декомпозиции и перебора Ь классов

для ПЗР.
2.4 Оценки числа итераций для алгоритма
декомпозиции Вендерса.
Глава 3. Разработка декомпозиционных алгоритмов
для двухуровневой задачи размещения.
3.1 Задачи двухуровневого программирования
3.2 Сведение к одноуровневой задаче.
3.3 Декомпозиционные алгоритмы для двухуровневой задачи .
3.4 Исследование декомпозиционных алгоритмов
для двухуровневой задачи
Глава 4. Результаты экспериментальных исследований .
4.1 Особенности алгоритмов
4.2 Результаты экспериментальных исследований
для простейшей задачи размещения
4.3 Вычислительный эксперимент
для двухуровневой задачи размещения.
Заключение.
Список литературы


Проведен анализ эффективности отсечений в зависимости от способа выбора оптимальных значений двойственных оценок, используемых при их построении. Кроме тот, в работе построены семейства простейших задач размещения с мощными /^-разбиениями дробных накрытий задач. Проведены экспериментальные исследования эффективности различных вариантов предложенных алгоритмов. Диссертация состоит из введения, четырех глав, заключения и списка литературы. В первой главе содержатся постановки основных задач размещения предприятий: простейшая задача размещения на максимум и минимум, задача размещения с ограничением на обьемы производства, многоиро-дуктовая производствсиио-транспортной задача, двухуровневая задача размещения, а также некоторые другие близкие к ним задачи, рассматриваются вопросы сложности решения этих задач. Далее дается краткий обзор наиболее известных точных методов решения задач размещения, подробно излагается общая схема декомпозиции Вендерса. Приводятся сведения о полиномиально разрешимых случаях простейшей и двухуровневой задач размещения. В главе приведены наиболее известные приближенные и эвристические алгоритмы, указаны оценки точности некоторых из них. Во второй главе исследуется простейшая задача размещения. Описывается метод регулярных разбиений, в том числе //-разбиение и Ьс~разбиение, излагается математический аппарат, необходимый для построения алгоритмов. Здесь же обсуждаются вопросы, касающиеся //-структуры задач ЦП, в том числе простейшей задачи размещения. Предлагаются семейства ПЗР, обладающие мощными /^-накрытиями. В данной главе описываются также реализованные автором декомпозиционные алгоритмы для решения ПЗР. В этих алгоритмах предусмотрено построение отсечений по целочисленным точкам, удовлетворяющим различным условиям (с использованием разных способов выбора оптимальных значений двойственных оценок); регулирование размерности матрицы ограничений производственной задачи и другие возможности. Разработаны варианты декомпозиционнного алгоритма, в которых на предварительном этане для получения начального рекорда используются эвристические процедуры. Приводятся оценки числа итераций для ряда декомпозиционных алгоритмов решения простейшей задачи размещения. Показано, что глубина отсечений Вендерса для ПЗР зависит от способа выбора оптимальных значений двойственных оценок, используемых при их построении, и может изменяться от 1 до величины, превышающей 2П_1, где п— число пунктов возможного размещения предприятий. В третьей главе исследуется двухуровневая задача размещения предприятий. Дается краткий обзор задач двухуровневого программирования. Далее исследуется двухуровневая задача размещения в условиях однозначного выбора потребителей. Ранее [] были предложены различные способы сведения такой задачи к одноуровневой оптимизационной задаче. Здесь выбирается один из чаких способов и для получающейся одноуровневой задачи предлагается алгоритм решения, аналогичный алгоритму декомпозиции Вендерса для ПЗР, учитывающий специфику задачи. Рассмотрены вопросы, связанные с оценкой числа итераций декомпозиционных алгоритмов. Доказано, что глубина отсечений Вендерса для ДЗР может изменяться в тех же пределах, что и для ПЗР. Четвертая глава посвящена экспериментальному исследованию описанных декомпозиционных алгоритмов для простейшей и двухуровневой задачи размещения. Эксперимент проводился на тестовых задачах из электронной библиотеки Института математики СО РАН и библиотеки OR-Library [4], на задачах из семейств, предложенных во второй и третьей главах диссертации, в том числе обладающих мощными L/t накрытиямии, а также на задачах со случайными данными. Исследовалась зависимость числа итераций алгоритмов от способа выбора оптимальных значений двойственных переменных, используемых при построении отсечений; правил выбора целочисленных точек, но которым строятся отсечения Вендерса; числа сохраняемых отсечений; предварительного применения эвристических алгоритмов. На тестовых задачах из электронной библиотеки ИМ СО РАН декомпозиционные алгоритмы показали существенное преимущество по времени решения по сравнению с указанным пакетом.