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

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

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

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 Результаты вычислительного эксперимента.
Заключение.
Литература


В частности, достаточно эффективными оказались фасетиые неравенства, порождаемые выпуклой оболочкой множества целочисленных решений []. Во многих задачах размещения предприятий, в том числе в задачах о р-мсдиаие и ПЗР, переменные соответствующей модели ЦЛП естественным образом делятся на две группы: целочисленные и непрерывные. Ввиду этого для их решения применяются декомпозиционные алгоритмы с отсечениями Вендерса [3,,], в которых решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных (непрерывных) подзадач. Для построения производственных подзадач используются дополнительные неравенства (отсечения Вендерса). Основное направление исследований метода Вендерса - разработка и экспериментальное исследование декомпозиционных алгоритмов для различных задач частично целочисленного программирования [,, ,]. С теоретической точки зрения указанные алгоритмы исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач, устойчивости алгоритмов при малых колебаниях исходных данных. При построении неравенств Вендерса выбор оптимальных значений двойственных оценок в общем случае неоднозначен и существенно влияет на эффективность алгоритмов. Исследования в этом направлении позволяют разрабатывать способы получения более сильных отсечений. В области целочисленного программирования (ЦП) получил развитие предложенный А. А.Колоколовым подход, основанный на регулярных разбиениях евклидова пространства [,]. Применение такого подхода позволило изучить структуру некоторых задач ЦП, ввести и исследовать новые классы отсечений, построить оценки числа итераций (отсечений) для ряда алгоритмов. Многие результаты получены на основе использования элементов 1-разбиения, называемых Ь-классами. В работах [. Ь-классов в сочетании с декомпозицией Вендерса применяется для решения задач размещения предприятий. Важное место в дискретной оптимизации занимают вопросы устойчивости задач и алгоритмов ЦП [,,,]. На практике исходные данные задачи могут быть неточными, и даже в случае их достаточно малых колебаний оптимальное решение задачи может сильно изменяться. Задачи, решение которых при этом остается прежним, либо меняется незначительно, называются устойчивыми в том или ином смысле. Некоторые последние результаты по устойчивости задач и алгоритмов получены с использованием Ь-разбиения [,]. Представляет интерес исследование устойчивости декомпозиционных алгоритмов с отсечениями Вендерса. Цель диссертации разработка, теоретическое и экспериментальное исследование декомпозиционных алгоритмов с отсечениями Вендерса для решения задачи о р-медиане (на максимум и минимум) и простейшей задачи размещения. Исследуемые в работе декомпозиционные алгоритмы отличаются от классической схемы тем, что в них не требуется решать задачу целочисленного программирования при нахождении очередного производственного плана. Нами построены оценки числа итераций этих алгоритмов для достаточно широкого класса задач. Установлено, что эффективность алгоритма существенно зависит от значений двойственных оценок, используемых при вычислении коэффициентов неравенств Вендерса. Предложены эвристические правила для получения более сильных отсечений. Проведенный вычислительный эксперимент показал перспективность данного подхода. Выделено семейство трудных задач для известных релаксационных алгоритмов ЦЛП: прямо-двойственного алгоритма перебора Ь-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Построены оценки числа итераций этих алгоритмов при решении задач из указанного семейства. Кроме того, для точного решения задачи о р-медиане на максимум предложен гибридный декомпозиционный алгоритм, в котором осуществляется лексикографический перебор допустимых решений в сочетании с релаксацией Лагранжа и отсечениями Вендерса. Сравнение полученных результатов с показателями других программных комплексов для решения задач ЦЛП подтверждают эффективность алгоритма.