Параллельные методы и алгоритмы для решения задач математического моделирования на основе вариационных неравенств

• Автор: Запорожец, Дмитрий Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 135 с. : ил.

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

1 Математическое моделирование в двухуровневой оптимизации

1.1 Вариационные неравенства в математическом моделировании

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

резервирования на основе вариационных неравенств

1.3 Двухуровневая математическая модель в сельском хозяйстве

1.4 Двухуровневая математическая модель

«Продавец-Покупатель»

1.5 Двухуровневая математическая модель в задаче теории смазки

1.6 Итоги раздела
2 Итерационные методы
2.1 Градиентные методы
2.2 Экстраградиентные методы
2.3 Итерационные методы с памятью
2.4 Сходимость методов
2.5 Итоги раздела
3 Программный комплекс MMSolver
3.1 Описание модуля MatrixCalc
3.2 Описание модуля Task
3.3 Описание модуля Method
3.4 Особенности реализации методов с памятью
3.5 Интерфейс программного комплекса MMSolver
3.6 Итоги раздела
4 Вычислительные эксперименты
4.1 Тестовые задачи
4.2 Двухуровневая задача оптимального резервирования в
сельском хозяйстве
4.3 Итоги раздела

Заключение
Словарь терминов
Список литературы
Приложение А Вычислительные эксперименты решения СЛАУ .... 107 Приложение Б Вычислительные эксперименты решения линейной задачи дополнительности
Приложение В Вычислительные эксперименты решения нелинейного
вариационного неравенства
Приложение Г Вычислительные эксперименты решения задачи МП . . 120 Приложение Д Вычислительные эксперименты решения задачи ЛП

Введение
Актуальность темы исследования. Актуальность использования вариационных неравенств как современного инструмента моделирования и численного решения оптимизационных задач обусловлена их универсальностью и применимостью при решении задач исследования операций в экономике, логистике, технике и других областях.
Научный вклад в разработку моделей, методов и эффективных алгоритмов решения вариационных неравенств внесли такие известные ученые как A.C. Антипин, В.А. Булавский, В.Ф. Демьянов,.В.Г. Жадан, С.И. Зуховицкий, A.B. Зыкина, В.В. Калашников, И.В. Коннов, Г.М. Корпелевич, A.B. Панюков, А.Б. Певный, Б.Т. Поляк, Л.Д. Попов, М.Е. Примак, Е.Н. Хоботов, K.J. Arrow, G. Debreu, P.T. Harker, Т. Kose, J.S. Pang, R.M. Solow и другие.
Универсальным методом решения вариационных неравенств являются итерационные методы, наиболее распространенными из них являются градиентные методы. Однако их применение требует выполнения достаточно жестких условий (к примеру, сильной монотонности оператора вариационного неравенства или компактности исходного множества). Ослабить эти условия, а значит, расширить класс решаемых задач позволяют экстраградиентные методы. Экстра-градиентные методы применимы при условии монотонности оператора вариационного неравенства и замкнутости исходного множества.
Степень разработанности темы исследования. Общим недостатком классических итерационных методов является последовательность процесса вычислений итераций, невозможность начать вычисление очередной итерации, пока не закончится вычисление предыдущей, что приводит к неэффективному использованию ресурсов современных вычислительных машин. В связи с активным развитием технологий параллельных вычислений в последнее десятилетие и опережающим развитием высокопроизводительной вычислительной техники по сравнению с развитием программного обеспечения для таких систем востребованными являются методы и алгоритмы, использующие несколько про-

последовательной, также как и у одношагового экстраградиентного метода и у градиентных методов.
Подсчитаем количество операций произведения и сложения, которое выполняется за одну итерацию двухшагового экстраградиентного метода. Пусть оператору вариационного неравенства Н{х) требуется ст операций произведения и са операций сложения. По аналогии с одношаговым экстраградиентным методом, вычисление промежуточной точки Xk потребует ст + п операций произведения и са + п операций сложения. Столько же операций понадобится для вычисления ötk и Хк+1. Таким образом, всего за одну итерацию двухшагового экстраградиентного метода выполняется 3Сщ + 3п операций произведения и Зса + 3п операций сложения.
Применительно к вариационным неравенствам со связанными ограничениями (9) A.C. Антипиным предложен одношаговый экстраградиентный метод [4], а A.B. Зыкиной, Н.В. Меленьчуком предложен двухшаговый экстраградиентный метод [29,32].
Одношаговый экстраградиентный меотд для вариационного неравенства со связанными ограничениями задается следующими рекуррентными соотношениями:
Уп = (yn + anf(xxn))+, хп = Рп(х'г - ап(Н(х") + f(xn, хп)уп)),
Vn+1 =(yn + anf(xn,xn))+, xn+1 = Pn(xn ~ an(H(xn) + /Tf(xn,xn)yn))-
Двухшаговый экстраградиентный метод для вариационного неравенства со связанными ограничениями задается следующими рекуррентными соотношениями:
Уп =(yn + anf(xn,xn))+,
Г = Р„(хп - ап(Н(хп) + 4yf{xn. хи)у”)),
Г =(yn + anf(xn.xn))+, хп = Рп(хп - ап(Н(хп) + VTyf{xn„ хп)Г)),
Уп+1 =(yn + anf(xn,in))+, xn+l = Рп(хп - ап(Н(хп) + S7yf(xn, хп)уп)).