авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

На правах рукописи

ЗАПОРОЖЕЦ Дмитрий Николаевич

ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ

ЗАДАЧ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

НА ОСНОВЕ ВАРИАЦИОННЫХ НЕРАВЕНСТВ

05.13.18 –Математическое моделирование,
численные методы и комплексы программ

Автореферат
диссертации на соискание ученой степени
кандидата физико-математических наук

Челябинск – 2013

Работа выполнена на кафедре

прикладной математики и фундаментальной информатики

ФГБОУ ВПО «Омский государственный технический университет»

Научный руководитель: доктор физико-математических наук, профессор ЗЫКИНА Анна Владимировна.

Официальные оппоненты: доктор физико-математических наук, профессор

ПАНЮКОВ Анатолий Васильевич,

заведующий кафедрой «Экономико-математические методы и статистика»

ФГБОУ ВПО «Южно-Уральский государственный университет» (НИУ);

доктор физико-математических наук, профессор,

ЖАДАН Виталий Григорьевич,

заведующий отделом прикладных проблем оптимизации Федерального государственного бюджетного учреждения науки Вычислительного центра им. А. А. Дородницына Российской академии наук.

Ведущая организация: ФГБОУ ВПО «Новосибирский национальный исследовательский государственный университет»

Защита состоится 1 октября 2013 г. в 15 часов

на заседании диссертационного совета Д 212.298.14

при ФГБОУ ВПО «Южно-Уральский государственный университет» (НИУ)

по адресу: 454080, Челябинск, пр. Ленина, 76, ауд.1001.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Южно-Уральский государственный университет» (НИУ).

Автореферат разослан «___» августа 2013 г.

Ученый секретарь

диссертационного совета,

доктор физ.-мат. наук, доцент Келлер Алевтина Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Актуальность использования вариационных неравенств как современного инструмента моделирования и численного решения оптимизационных задач обусловлена их универсальностью и применимостью при решении задач исследования операций в экономике, логистике, технике и других областях.

Научный вклад в разработку математических моделей, методов и эффективных алгоритмов решения вариационных неравенств внесли известные ученые: А. С. Антипин, В. А. Булавский, В. Г. Жадан, С. И. Зуховицкий, А. В. Зыкина, В. В. Калашников, И. В. Коннов, Г. М. Корпелевич, А. В. Панюков, А. Б. Певный, Б. Т. Поляк, Л. Д. Попов, М. Е. Примак, Е. Н. Хоботов, K. Arrow, G. Debreu, P. Harker, J. Pang, R. Solow и другие.

Универсальными методами решения вариационных неравенств являются итерационные методы, наиболее распространенные из них – градиентные методы. Однако их применение требует выполнения достаточно жестких условий (к примеру, сильной монотонности оператора вариационного неравенства или компактности исходного множества). Ослабить эти условия, а значит, расширить применимость вариационных неравенств позволяют экстраградиентные методы.





Общим недостатком классических итерационных методов является последовательное выполнение итераций, что приводит к неэффективному использованию ресурсов современных вычислительных машин. Опережающее развитие высокопроизводительной вычислительной техники по сравнению с развитием программного обеспечения делает востребованными методы и алгоритмы, использующие несколько процессоров. В связи с этим разработка параллельных методов и алгоритмов решения, а также распараллеливание существующих алгоритмов являются актуальными направлениями в развитии современных технологий математических методов моделирования сложных оптимизационных систем и итерационных методов для их решения.

Цель и задачи исследования. Целью диссертационной работы является разработка и теоретическое обоснование новой технологии построения итерационных методов, использующих особенности архитектуры современных многоядерных компьютеров, с оценкой эффективности использования новых разработанных параллельных методов для решения задач математического моделирования на основе вариационных неравенств.

Для достижения цели работы поставлены следующие задачи:

  1. Разработать метод математического моделирования в задачах оптимального резервирования.
  2. Разработать технологию итерационных методов: итерационный метод с памятью, преобразующий последовательные итерационные методы в новый класс параллельных методов.
  3. Построить и обосновать итерационные методы с памятью для градиентных и экстраградиентных методов решения вариационных неравенств.
  4. Реализовать исследуемые последовательные итерационные методы и их параллельные модификации с памятью в виде программного комплекса.
  5. Построить и исследовать математическую модель оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли с применением разработанной технологии математического моделирования на основе вариационных неравенств.

Научная новизна диссертационной работы заключается в том, что разработанный метод моделирования задачи оптимального резервирования основан на использовании аппарата вариационных неравенств в моделировании двухуровневых задач. Разработана новая технология итерационных методов: итерационный метод с памятью. Доказана сходимость по норме итерационных методов с памятью к решению задач для градиентных и экстраградиентных методов, получены оценки скорости сходимости. Впервые разработана математическая модель оптимального резервирования возобновляемых ресурсов, для решения которой применимы разработанные в диссертации численные методы.

Теоретическая значимость работы состоит в том, что разработанный метод моделирования задачи оптимального резервирования развивает теорию математического моделирования и может быть использован для качественного и численного исследования моделей на основе вариационных неравенств. Разработанная технология итерационных методов с памятью и построенные параллельные алгоритмы вносят вклад в развитие методов математического программирования, теории вариационных неравенств, теории параллельных вычислений.

Практическая значимость работы. Программный комплекс MMSolver позволяет решать сводящиеся к вариационным неравенствам актуальные задачи математического моделирования из различных областей знаний, в том числе, задачу оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли, экономическую задачу «Продавец – Покупатель», техническую задачу из теории смазки (задачу о смазке подшипника).

Методология и методы исследования. В работе используются методы математического моделирования, математического программирования, теория вариационных неравенств, теория параллельных вычислений.

Положения, выносимые на защиту:

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

2. Разработана новая технология итерационных методов: итерационный метод с памятью, позволяющий преобразовать существующие итерационные методы и получить новый класс параллельных методов решения.

3. Разработаны новые итерационные методы с памятью для градиентных и экстраградиентных методов, доказана сходимость методов по норме к решению задач, получены оценки скорости сходимости.

4. Разработана программа «Экстраградиентные методы» и программный комплекс MMSolver, реализующие исследуемые итерационные методы. В ходе вычислительных экспериментов, проведенных на программном комплексе, подтверждена эффективность разработанных алгоритмов, методов и подходов.

Степень достоверности и апробация результатов. Разработанные в диссертационной работе методы, алгоритмы и результаты вычислительных экспериментов докладывались на следующих международных и всероссийских конференциях: Российская конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2010); Всероссийская молодежная научно-техническая конференция «Россия молодая: передовые технологии – в промышленность» (Омск, 2010); Российская молодежная научно-практическая конференция «Прикладная математика и фундаментальная информатика» (Омск, 2011, 2013); Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 2011); Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Иркутск, 2011); Всероссийская конференция «Статистика. Моделирование. Оптимизация» (Челябинск, 2011); Международная научно-техническая конференция «Динамика систем, механизмов и машин» (Омск, 2012); Международная научная конференция «Параллельные вычислительные технологии» (Челябинск, 2013); Международная конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2013).

Работа выполнялась при поддержке Министерства образования и науки Российской Федерации (соглашение № 14.B37.21.1123) и РФФИ (проекты № 12-01-31360, № 12-07-00326).

Публикации. По теме диссертации опубликовано 17 научных работ, в их числе 4 статьи в ведущих российских рецензируемых научных журналах и изданиях, рекомендованных ВАК [1–4], и 2 свидетельства о государственной регистрации программ для ЭВМ. Список работ приведен в конце автореферата.

В совместных с научным руководителем работах [2, 3, 4, 9, 11, 13, 17] научному руководителю принадлежат постановки задач, Запорожцу Д. Н. – все основные полученные результаты.

Из остальных работ, выполненных в соавторстве, в диссертацию включены только те результаты, которые были получены лично Запорожцем Д. Н. и не затрагивают интересов других соавторов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов основного содержания, заключения, списка литературы из 106 наименований и приложений. Полный объем диссертации составляет 135 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении представлена постановка задачи, рассматриваются актуальность, цели и задачи работы, научная новизна, теоретическая и практическая значимость, апробация работы, методы исследования.

Первый раздел, «Математическое моделирование в двухуровневой оптимизации», состоит из шести подразделов и содержит основные сведения из теории вариационных неравенств, методов оптимизации и параллельных вычислений. На основе анализа разработанных моделей, методов и эффективных алгоритмов А. С. Антипина1, А. В. Зыкиной2, В. Г. Жадана3, И. В. Коннова4, А. В. Панюкова5 предлагается метод математического моделирования задач оптимального резервирования на основе вариационных неравенств в различных предметных областях.

В п. 1.1 приводятся способы сведения различных классов оптимизационных задач (задач дополнительности, задач линейного и выпуклого программирования, задач о седловой точке) к вариационным неравенствам.

Решить вариационное неравенство – значит найти такой вектор , удовлетворяющий условиям:

(1)

где , – выпуклое, замкнутое множество.

Приводятся постановки смешанных вариационных неравенств, вариационных неравенств со связанными ограничениями и вариационно-подобных неравенств.

В п. 1.2 для задачи оптимального резервирования разрабатывается метод математического моделирования с использованием вариационных неравенств в задачах двухуровневой оптимизации.

Задача двухуровневой оптимизации выглядит следующим образом

(2)

____________________________

1Антипин, А. С. О методе выпуклого программирования, использующем симметрическую модификацию функции Лагранжа // Экономика и математические методы. – 1976. – Т. 12. – № 6. – С. 1164–1173.

2Зыкина, А.В. Обратная дополнительность в модели управления ресурсами // Журнал вычислительной математики и математической физики. – 2008. – Т. 48. – № 11. – С. 1968-1978.

3Евтушенко,Ю.Г., Жадан, В.Г. Релаксационный метод решения задач нелинейного программирования // Журнал вычислительной математики и математической физики. – 1977. – Т. 17, № 4. – С. 890–904.

4Konnov, I. V. Combined relaxation methods for variational inequalities. – Berlin etc. : Springer, 2001. – 181 p.

5Панюков, А. В., Латипова, А.Т. Численные методы определения положения равновесия в модели Неймана // Журнал вычислительной математики и математической физики. – 2008. – Т. 48, № 11 – С. 1999 – 2007.

Здесь функция – выпуклая, дифференцируемая по x для любого , функция – выпуклая, дифференцируемая по y для любого – выпуклая по x функция для любого , – выпуклая по y функция для любого , , – выпуклые компакты.

При указанных условиях задача (2) записана в терминах вариационных неравенств.

В п. 1.3 построена математическая модель задачи оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли. На верхнем уровне решается задача максимизации выручки от продажи зерна:

где – посевная площадь, занятая семенами i-го сорта k-й репродукции, га; – цена реализации семян i-го сорта k-й репродукции, руб/ц; – урожайность i-го сорта k-й репродукции, ц/га; – семенной фонд i-го сорта k-й репродукции, который необходимо заготовить, ц; – обшая посевная площадь, га; – подмножество номеров сортов, –минимальная и максимальная допустимая посевная площадь под группу сортов k-й репродукции, га, соответственно; – норма высева, ц/га.

Задача второго уровня – минимизация затрат на покупку новых семян

где– цена семян i-го сорта k-й репродукции, руб/ц.

В п. 1.4 и 1.5 разработанный аппарат моделирования используется для моделирования экономической задачи «Продавец – Покупатель» и технической задачи из теории смазки (задачи о смазке подшипника).

В п. 1.6 подводятся итоги по разделу 1, сделан вывод о месте диссертационного исследования в развитии методов математического моделирования. Использование вариационных неравенств для моделирования двухуровневых задач показывает применимость предложенного нового метода математического моделирования к большому количеству не только экономических задач (задача оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли, задача «Продавец – Покупатель»), но и к задачам, имеющим физический смысл (задача о смазке подшипника).

Второй раздел, «Итерационные методы», состоит из пяти подразделов и содержит итерационные методы решения вариационных неравенств: градиентные методы с постоянным шагом, с убывающим шагом, одношаговый и двухшаговый экстраградиентные методы.

В п. 2.1 приводится описание градиентных методов для решения вариационного неравенства (1). Вычислительная схема методов имеет вид

,

где – длина шага метода, H – оператор вариационного неравенства, – оператор проецирования на множество .

В п. 2.2 рассматриваются одношаговый и двухшаговый экстраградиентные методы. Одношаговый экстраградиентный метод для решения вариационного неравенства (1) задается следующими рекуррентными выражениями

,.

Основное отличие экстраградиентного метода от градиентного заключается в вычислении прогнозной точки .

Двухшаговый экстраградиентный метод для решения вариационного неравенства (1) задается рекуррентными выражениями

,,

.

В отличие от одношагового экстраградиентного метода двухшаговый метод для вычисления очередной точки использует две прогнозные точки и .

В п. 2.3 предлагаются итерационные методы с памятью как новый подход к распараллеливанию итерационных методов и создания новых вычислительных методов.

Вычислительная схема итерационных методов с памятью строится следующим образом. Пусть задан итерационный процесс,где F – некоторая процедура, последовательность действий, необходимая для получения следующей итерационной точки.

Вектором движения итерационного процесса на k-й итерации называется разность точек, полученных на k-й и (k–1)-й итерациях:.

На k-й итерации строится вспомогательная точка. Выражение для вычислительной схемы итерационного метода с памятью на основе итерационного процесса F задается следующим образом:

, (3)

где условие называется критерием одного направления.

Предлагаемый подход заключается в том, что используя направление, вычисляем вспомогательную точку. Затем вычисляем , а на другом процессоре – . И если удовлетворяет критерию одного направления, а именно, попадает в некоторую область, то в качестве следующей точки следует брать .

У полученных новых методов с памятью есть два отличия от исходных методов. Во-первых, на очередной итерации используется информация о направлении движения на предыдущей итерации. Во-вторых, вычислительная схема допускает распараллеливание, что позволяет повысить их эффективность, сокращая не только количество итераций и время решения задачи, но и наиболее полно используя потенциал современных многоядерных компьютеров.



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.