Методы решения задач дополнительности и двухуровневого программирования

• Автор: Петрова, Елена Геннадьевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Иркутск
• Количество страниц: 129 с. : ил.

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

1 Оптимизационный подход к решению линейной задачи дополнительности

1.1 Постановка задачи. Различные формулировки

линейной задачи дополнительности

1.2 Редукция к задаче с.с. минимизации.

1.3 Специальный метод локального поиска.

1.4 Построение тестовых примеров и апробации

алгоритма локального поиска

1.5 Алгоритм глобального поиска

1.6 Вычислительный эксперимент

1.6.1 Выбор аппроксимации поверхности уровня
1.6.2 Согласование точностей локального и
глобального поиска
1.6.3 Решение серий задач
1.7 Основные результаты главы.
2 Поиск оптимистических решений в линейной двухуровневой задаче
2.1 Постановка линейной двухуровневой задачи
2.2 Сведение двухуровневой задачи к задаче с с.с. ограничением
2.3 Условия глобальной оптимальности для задачи минимизации
с б.с. ограничениемравенством
2.4 Минимизирующие последовательности.
2.5 Стратегия глобального поиска
2.6 Решение возмущенной задачи
2.7 Локальный поиск в задаче с с.с. ограничениемравенством
2.7.1 Генерация тестовых задач
2.7.2 Тестирование метода локального поиска.
2.8 Глобальный поиск в линейной двухуровневой задаче.
2.9 Вычислительный эксперимент.
2.9.1 Первый этап. Выбор аппроксимации поверхности уровня.
2.9.2 Второй этап. Оценка сложности задач.
2.9.3 Третий этап. Решение задач высокой размерности
2. Задача планирования производства в условиях неизвестного спроса
2. Основные результаты главы.
3 Методы решения уравнений с с.с. функциями
3.1 Решение одного уравнения с с1.с. функцией
3.2 Доказательство сходимости ПВК.
3.3 Вычислительный эксперимент.
3.4 Решение систем нелинейных уравнений
3.5 Особенности решения квадратичных систем уравнений .
3.6 Численное решение систем уравнений.
3.6.1 Квадратичные уравнения
3.6.2 Нелинейные уравнения
3.7 Основные результаты главы
Заключение
Список использованной литературы


Следующий же объект — линейная двухуровневая задача — может быть проинтерпретирован как некоторое усложнение предыдущей ЛЗД, поскольку после сведения двухуровневой задачи к оптимизационной, мы получаем задачу с линейной целевой функцией и схожими нелинейными комплементарными ограничениями. Для получения же допустимой точки в задачах оптимизации с равенствами требуется нахождение решения уравнения или системы уравнений. Актуальность темы диссертации обусловлена большим количеством практических приложений каждого из упомянутых объектов. Наличие же неявных и явных ограничений-равенств создает серьезные трудности на пути отыскания глобального решения в поставленных задачах. Основной целью диссертационного исследования является разработка эффективных алгоритмов численного решения указанных задач. Далее представим более подробно постановки задач и их особенности. Яп и вещественная, подчеркнем, знаконеопределенная (пхп)-матрица М заданы. Мх + 7) = 0, х > 0, Мх 4- 7 > 0. Теория линейной дополнительности, впервые представленная в работах Коттла [], Данцига [1], Лемке [2], интенсивно развивается три последних десятилетия, главной причиной чего служит связь ЛЗД с задачами линейного и квадратичного программирования []. Исторически задачу ЛЗД можно рассматривать в качестве объединяющей формулировки для задач линейного, квадратичного программирования и биматричных игр [0]. Отметим также, что задачи дополнительности тесным образом связаны с другим важнейшим объектом современной математики — вариационными неравенствами [4], имеющими широкие приложения в математической физике, в теории равновесий, а также в других областях. Решение ЛЗД в общем случае является нетривиальной задачей. Как известно [], получение ответа на вопрос, имеет ли решение ЛЗД с целочисленными коэффициентами, оказывается ИР-полной задачей [1]. Поэтому наиболее эффективными являются методы, ориентированные на использование свойств матрицы М} т. ЛЗД. Таковыми могут быть, в частности, задачи с матрицами, имеющими неотрицательные главные миноры (или Ро-матрицами) [,0]. Другим подобным классом могут быть задачи с матрицами, имеющими неположительные внедиагональные элементы (или Z-матрицами). Тогда можно построить эффективные методы решения как для ЛЗД, так и для ее нелинейных обобщений (напр. ЛЗД с неотрицательно определенными матрицами и с матрицами, имеющими положительные главные миноры. В качестве приоритетных можно выделить два основных направления развития. Первое направление — это методы крайних точек ("pivoting methods"), являющиеся, по сути, разнообразными модификациями метода Лемке-Хаусона [0]. S = {(х, ш) € iRn+n : w = q + /V/х, х > 0, W >0}. Каждая итерация метода соответствует движению из крайней точки множества S вдоль некоторого его ребра, почти удовлетворяющего условиям дополнительности, т. Этот метод является конечным вследствие конечного (но, возможно, очень большого) числа крайних точек многогранного множества. Однако нахождение решения ЛЗД (в случае его существования) гарантировано только при определенных условиях, налагаемых на матрицу М [], например, при положительности всех ее главных миноров. Кроме того, данные методы эффективны в основном на задачах малой и средней размерности. С ростом размерности задачи резко увеличивается количество перебираемых вершин (как известно, количество вершин многогранного множества возрастает экспоненциально). Второй подход к решению ЛЗД (который применяется в диссертационной работе) — это вариационный метод, заключающийся в минимизации некоторой целевой функции, например, скалярного произведения (х, w) на допустимом множестве S. Для решения такой задачи применяются, например, методы внутренних точек [, , , 0] и специализированные методы квадратичного программирования (3, 1G, , 6]. При решении вариационной задачи, как и в первом случае, успешность применяемых методов зависит от свойств матрицы М. Так, в случае знаконеопределенности матрицы М (что порождает невыпуклость в задаче), возникают проблемы с поиском глобального решения, поскольку стандартные методы выпуклой оптимизации в этом случае позволяют найти, в лучшем случае, локальное решение, а чаще — лишь стационарную точку, которая может быть далека от глобального оптимума. Приведем пример прикладной задачи линейной дополнительности. Пример 0.