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

Актуальность темы

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

Универсальный подход к решению вариационных неравенств и оптимизационных задач — итерационные методы. Самыми распространенными из них являются градиентные методы. Для решения вариационных неравенств градиентные методы применимы, однако, они сходятся при наличии достаточно жестких предположений (к примеру, при сильной монотонности оператора, или компактности исходного множества). Ослабить эти условия позволяют экстраградиентные методы, предложенные впервые в работах А. С. Антипина и Г. М. Корпелевич в 80-х годах прошлого века. Актуальность этих методов заключается не только в возможности решения более широкого класса задач, но и в их сходимости из произвольной начальной точки области, что очень важно для прикладных задач, где нужна универсальность и возможность решать задачи без предварительного исследования. Двухшаговая конструкция экстраградиентных методов, предложенная в диссертации, с одной стороны, представляет интерес как новая вычислительная схема для итерационных методов, с другой стороны, большое значение имеет практическое применение двухшаговых экстраградиентных методов для численного решения и исследования сложных содержательных задач.

Диссертационная работа является продолжением исследований A.C. Антипина, A.B. Зыкиной, И. В. Коннова и расширяет аппарат математических методов моделирования сложных (в том числе, противоречивых) оптимизационных систем и экстраградиентных методов для их решения.

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

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

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

2. Разработать двухшаговый экстраградиентный метод для решения вариационного неравенства.

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

4. Реализовать разработанные методы в виде комплекса проблемно-ориентированных программ.

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

Научная новизна диссертационной работы состоит в следующем.

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

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

3. В ходе вычислительных экспериментов, проведенных на комплексе проблемно-ориентированных программ «Экстраградиентные методы», получены новые закономерности, характеризующие построенные математические модели и численные методы.

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

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

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

Изложение материала диссертации построено следующим образом.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ:

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

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

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

Заключение

.

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

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

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

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

Разработанный комплекс проблемно-ориентированных программ «Экстраградиентные методы» отвечает требованиям новизны и является вкладом в объединенный фонд электронных ресурсов «Наука и образование». Использование комплекса программ позволяет оценить эффективность построенных двухшаговых экстраградиентпых методов для решения задач, формализуемых вариационными неравенствами.