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

• Автор: Величко, Андрей Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Владивосток
• Количество страниц: 116 с.

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

Классические методы декомпозиции линейных оптимизационных

задач.

Принцип, декомпозиции па основе методов решения задач педпф

фсрепцпрусмоП оптимизации.

Методы отсечений и декомпозиция оптимизационных задач .

1 Теория п практические приложения структурированных задач линейного программирования

1.1 Структурированные задачи линейного программирования .

1.2 Динамическая модель затратывыпуск.

1.3 Производственнотранспортная задача коксования углей . .

1.4 Задача двушагового стохастического программирования . .
1.5 Задача о репликации портфеля рыночных активов
2 Алгоритм двойственных отсечений АДО для двублочных структурированных линейных оптимизационных задач
2.1 Теоретическая постановка двублочиой структурированной линейной оптимизационной задачи.
2.2 Алгоритм двойственных ОТССЧСЧИЙ АДО
2.3 Вычислительные аспекты АДО.
3 Модификация АДО для структурированных линейных оптимизационных задач с нетривиальным носителем
3.1 Теоретическое обоснование способов модификации АДО . .
3.2 Особенности использования алтритма симнлексмстода для решения подзадач АДО
3.3 Модифицированный алгоритм двойственных отсечений МАДО
,3.4 Использование рестарта для решения подзадач АДО
4 Вычислительные эксперименты с МАДО и его параллели
4.1 Решение задачи о стационарном распределении температур в двумерной области сложной формы методом конечных элементов .
4.2 Теоретические основы параллелмзации МАДО.
4.3 Вычислительные эксперименты с МАДО и параллелизоваппого МАДО ПМАДО
4.4 Вычислительные эксперименты с МАДО для задачи двушагового стохастического программирования
4. Г Приложение ДО к задаче о репликации портфеля рыночных актинон.
Заключение
Список литературы


Особый интерес вызывают принципы декомпозиции в связи с парадигмой параллельных и глобальных (GRID) вычислений, ставших популярными в последнее время. Концепция параллельных вычислении позволяет организовать расчеты с данными, размещенными в распределенной памяти на разных вычислительных устройствах, и с использованием большого числа процессоров. Возможность использования этих двух перспективных направления развития алгоритмов математического программирования оправдывает дальнейшую разработку специальных алгоритмов для решения структурированных задач' линейного программирования большого объема на основе принципов декомпозиции и параллельных вычислений. Во введении сделан краткий обзор теории и практики методов декомпозиции. Можно отмстить, что особенно полно развита теория декомпозиции задач линейного программирования, где ее применение может существенно уменьшить вычислительные затраты. Для алгоритма симилекс-мстода для решения задач линейного программирования с п переменными и т ограничениями нссссмпстнчсская оценка объема вычислений имеет экспоненциальный вид 0(2mm(n’m/2)). Однако, алгоритмическая сложность в практических реализациях снмнлскс-метода имеет вид 0(п3) [). ЛОЖНОСТЬ, для которых оценки вычислительной сложности имеют вид где показатель степени обычно порядка 5. О цепка сложности итерационных методой имеет вид 0(пл 1 п(п/е)), где є - требуемая точность решения. Кроме этого и отих алгоритмах существенным являются и требования к памяти ЭВМ (порядка ? Вместе с тем, даже последняя улучшенная оценка но оставляет надежд па практическую эффективность применения этих методов для задач большой размерности общего вида. Для практических задач, где п ~ 4, даже полиномиальные оценки вычислительной и алгоритмической сложности предсказывают весьма значительный объем вычислений. Этот объем, однако, существенно снижается при уменьшении размерностей задач, что делает методы типа Кармаркара весьма перспективными с точки зрения решения локальных и координирующих подзадач, возникающих при декомпозиции исходном задачи. В реальных прикладных задачах матрица ограничений может иметь нескольких тысяч строк-столбцов. Как правило, она имеют специальную структуру со сравнительно небольшим количеством связывающих переменных или ограничений. В этом случае перспективным направлением развития алгоритмов решения таких задач являются схемы декомпозиции, одному из вариантов которых и посвящена настоящая работа. В первой главе рассматривается класс структурированных оптимизационных задач большой размерности, сформулированы постановки широко известных задач линейного программирования и показана их принадлежность этому классу. Все вышеперечисленное оправдывает дальнейшую разработку алгоритмов решения задач линейного программирования большого объема, основанных па модификациях спмплскс-мстода, в частности, для задач с ограничениями специального видя7для которых удается предложить более экономные алгоритмы решения. Во второ и главе структурированные линейные от иммзациоппые задачи сводятся к двублочному виду, что представляет возможности использования более простых схем декомпозиции. Рассматривается декомпозиционный алгоритм двойственных отсечений, разработанный Е. А. Нурмипскпм для которого была* показана высокая численная эффективность |]. При декомпозиции задач математического программирования возникает ряд теоретических и практических вычислительных проблем, связанных с неизбежной вырожденпостью подзадач, формулируемых в ходе процесса декомпозиции, желанием быстро получить приближенное решение задачи с заданной точностью, а также численной устойчивостью данных алгоритмов к накапливаемым в процессе вычислений погрешностям. В третьей главе изучается проблема вырождеиности координирующих и локальных подзадач, формируемых в процессе выполнения метода двойственных отсечений с позиций выпуклого анализа и теории двойственности для задач линейного программирования. С учетом этой проблемы этого обстоятельства модифицирован алгоритм декомпозиции и разработай его нараллелизоваииый вариант.