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

4847928

МЕЛЕНЬЧУК Николай Владимирович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Челябинск-2011

2 6 МАЙ 2011

4847928

МЕЛЕНЬЧУК Николай Владимирович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математическиж наук

Челябинск-2011

Работа выполнена на кафедре прикладной математики и фундаментальной информатики Омского государственного технического университета

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

ЗЫКИНА Анна Владимировна

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

УХОБОТОВ Виктор Иванович

Защита состоится 17 июня 2011 г. в 14.00 часов на заседании диссертационного совета Д 212.298.14 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

кандидат физико-математических наук ГОЛИКОВ Александр Ильич

Ведущая организация: Казанский (Приволжский)

федеральный университет

Автореферат разослан 19 мая 2011г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Л. Б. Соколинский

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Всероссийской научно-технической конференции «Россия молодая: передовые технологии в промышленность» (Омск, 2008, 2009, 2010),

- VII Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 2009),

- Российской конференции «Дискретная оптимизация и исследование операций» (республика Алтай, 2010),

- VI Московской международной конференции по исследованию операций (Москва, 2010),

- XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011).

Публикации. По теме диссертационной работы опубликовано 13 научных работ. Основные публикации приведены в конце автореферата. В их

числе 4 статьи из перечня журналов, рекомендованных ВАК [1-4], и одно свидетельство об отраслевой регистрации программ для ЭВМ [9]. В совместных работах [1-3] Зыкиной А.В. принадлежат постановки задач, Меленьчуку Н.В. принадлежат все полученные результаты.

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

Содержание диссертационной работы

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

Первая глава, «Связанные ограничения в математическом моделировании», состоит из пяти разделов. В разделе 1.1 приводятся сведения об основных объектах, рассматриваемых в данной диссертационной работе, основные понятия из теории вариационных неравенств и оптимизационных задач. Приводятся постановки задач о седловой точке, игр п лиц, задач дополнительности и обратных задач дополнительности, вариационных неравенств и вариационных неравенств со связанными ограничениями.

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

(Н(х*),у-х')> 0 УуеП, (1)

решить вариационное неравенство со связанными ограничениями - значит найти вектор V* 6 П, удовлетворяющий условиям:

(Н(и*),1и-у*)> 0, в(ь*,п)< 0 УгубП, (2)

где Я : М" К", С : Л" х К" -> Лт, П - выпуклое, замкнутое множество, П' С К".

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

Рассматривается задача производства, в которой требуется выбрать интенсивности х — (хх,..., хп)Т работы предприятия такие, чтобы гарантировать

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

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

Введем дополнительные параметры у = (уг,..., ут)т, характеризующие рыночную стоимость ресурсов. При этом объемы запасов ресурсов и издержки производства естественно считать зависящими от параметров у.

В результате получаем задачу параметрического (по параметру у) программирования:

тт{Р(х, у) | Рг(х) < В (у), х е X}, у 6 К™ (3)

X

Здесь отображение ^(я) = (/1(2), ■ ■■,/т{х))Т - технологический процесс, или количество ресурсов /¿(я), г = 1 ,...,т, необходимое для производства с интенсивностями х £ X, X С М"; отображение В (у) = (61(1/),..., Ьт{у))т -объемы запасов ресурсов, где функции г = 1, ...,тп, - запасы ресурсов, зависящие от их рыночной стоимости у £ К™; F : К" х М+ —К - целевая функция, характеризующая издержки производства.

Для решения поставленной задачи (3) вводятся дополнительные условия

(у,Р1(х)-В(у)) = 0, (4)

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

В результате эквивалентных преобразований модели (3)-(4) получаем новую математическую модель с использованием аппарата вариационных неравенств со связанными ограничениями в следующем виде:

(Н(У*),-Ш-У*) >0 С(и*,ш) <0, УшеЛ. (5)

Здесь у = [х\,у\\, IV = [х2,у2] для хих2 € X, уХ)у2 е М+; П = X х К™; Н(ь) = - градиент для 2 (и, к;) = Р{х2,У\) - (2/2,^1(^1) - В{у2))

по переменной ги; С (у, ии) = [^(хг) - В{у\), ^1(2:1) — -В(у2)].

Построенная модель является обобщением предложенной А. В. Зыкиной задачи обратной дополнительности, моделирующей экономическую задачу минимизации затрат на производство из ограниченных запасов ресурсов в условиях рыночных цен на ресурсы. Приведение модели (3)-(4) к виду (5). расширяет класс задач, для которых возможно применение разработанных в диссертации экстраградиентных методов. *

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

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

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

Вторая глава, «Двухшаговые экстраградиентные методы», состоит из шести разделов и содержит схемы и обоснование двухшаговых экстраградиентных методов для вариационных неравенств и смежных задач.

В разделе 2.1 приводится обзор экстраградиентных методов. Экстраградиентные методы называют ещё прогнозными, так как перед каждым шагом основного хода делается прогнозный шаг. Рассматриваются экстраградиентные методы, построенные А. С. Антипиным, А. В. Зыкиной, И. В. Конновым, Г. М. Корпелевич, Л. Д. Поповым, Е. Н. Хоботовым.

Экстраградиентный метод Г. М. Корпелевич для вариационного неравенства (1) выглядит следующим образом:

хк = Рп(хк - аН(хк)), . .

яг*+1 = Ра(я* ~ аН(хк)). ■ { '

Здесь а > 0 - числовой параметр, отвечающий за величину шага, Ра - оператор проектирования на множество П.

Поскольку в методе Г. М. Корпелевич прогнозный шаг - один, то будем называть этот метод одношаговым экстраградиентным методом.

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

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

хк = Ра(хк - аН(хк)),

хк = Рфк - аН(хк)), (7)

хк+1 = Рп(хк-аН(хк)).

Как видно, главным отличием метода (7) является наличие двух прогнозных шагов вместо одного в (6). Таким образом, предложенный метод делает два прогнозных шага в направлении градиента, «смотрит» направление градиента в полученной точке и делает шаг из начальной точки с полученным направлением. Для схемы (7) доказана следующая теорема.

Теорема 2.1 Пусть для вариационного неравенства (1) выполняются условия:

а) множество Г1 замкнуто и выпукло;

б) оператор Н(х) монотонный: (Н(х) — Н(у),х — у) > О V х, у £ П, удовлетворяющий условию Липшица: \\Н(х) — Н(у)\\ < L\\x — y\\ Vx, у £ П;

в) множество решений X* вариационного неравенства (1) naS2 не пусто;

г) параметр а, отвечающий за величину шага, удовлетворяет двойному неравенству: 0 < а < -^щ.

Тогда последовательность {хк}, определяемая рекуррентными соотношениями (7), сходится по норме к некоторому решению х* 6 X* вариационного неравенства (1).

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

При выполнении дополнительного к условиям теоремы 2.1 условия остроты: (Н{у),у — х*) > 7(|г/ — £*Ц Vt/ S Q, доказана сходимость к решению вариационного неравенства (1) за конечное число итераций (Теорема 2.2).

В разделе 2.3 рассматривается седловая задача.

Седловой точкой [х*,у*] G Q х S функции <р(х,у) называется точка, удовлетворяющая условиям: у) < <р{х*,у*)У у £ S; <р(х*,у*) < <р(х,у*) Ух Е Q. Здесь Q С К", S С Шт, tp : Q х S Ж,

Седловая точка для функции tp(x,y) может быть не единственной. Рекуррентные выражения двухшагового экстраградиентного метода решения седловой задачи (задачи о седловой точке): .

хк = PQ(xk -а<рх(хк,ук)), ук = Ps(yk+ aipy(xk,yk)),

хк = PQ(xk.-a<px(xk,yk)), ук =Ps(yk + a<py(xk,yk)), (8)

xk+1 = PQ(xk - a<px(xk, yk)), yk+1 = Ps(yk + a^(xk,y%

где a > 0 - числовой параметр, отвечающий за величину шага, Pq, Р$ - операторы проектирования на соответствующие множества, ipx, <ру - операторы градиентов функции ¡р(х,у) по соответствующим переменным. Сходимость итерационного 'процесса (8) доказана в следующей теореме.

Теорема 2.3 Пусть для функции <р(х,у) : К™ х Rm —> М, определённой на Q х S С R™ х Rm, выполняются условия:

а) множества Q и S замкнуты и выпуклы;

б) функция <р(х, у) выпуклая по переменной х и вогнутая по переменной у;

в) функция ip(x, у) дифференцируемая и ее частные производные удовлетворяют условию Липшица с константой L;

г) множество седловых точек X* х Y* функции tp(x,y) не пусто;

д) параметр а, отвечающий за величину шага, удовлетворяет двойному неравенству: 0 < а < -^щ.

Тогда последовательность {[xk,yk]}, определяемая рекуррентными соотношениями (8), сходится по норме к некоторой седловой точке \х*,у*\ € X* х Y* функции (р(х,у).

В разделе 2.4 для задачи линейного программирования и двойственной к ней

(с, х) -> min, (Ь, у) max,

АТх > b, Ау < с, (9)

х>0, у> О,

где с, х е Шп, b,y е TRm, А - матрица размерности п х т, на основе двухшагового экстраградиентного метода (8) строится вычислительная схема:

xk = [хк + а{Аук - с)]+, ук = [ук - а{АТхк - 6)]+,

хк = [хк + а{Аук- с)]+, ук = [ук -а(Атхк -Ь)}+, (10)

хш = [хк + а(Аук - с)]+, уш = [ук - а(Атхк - Ь)]+,

где [-]+ означает проекцию на положительный ортант соответствующей размерности. По сути схема (10) решает седловую задачу с седловой функцией

L(x,y) = (c,x) + (b,y)-(Ay,x). (И)

Для схемы (10) доказана следующая теорема.

Теорема 2.4 Пусть для пары задач линейного программирования (9) выполняются следующие условия:

а) билинейная функция Лагранжа (11) на множестве х >0, у > 0 имеет единственную седловую точку [х*,у*];

б) переменная а, отвечающая за величину шага, удовлетворяет двойному неравенству 0 < а < ■

Тогда последовательность {\хк, ук\}, определяемая рекуррентными соотношениями (10), сходится по норме к седловой точке \х*, у*\ со скоростью геометрической прогрессии:

_ ^ + уШ _ у*||2 < _ + ук _ у.||2); о < д <

Заметим, что условие единственности седловой точки функции Лагранжа (11) не является обязательным для сходимости последовательности {[х^, ук}} к некоторому решению пары задач (9). Условие единственности обеспечивает сходимость со скоростью геометрической прогрессии.

Раздел 2.5 посвящен вариационным неравенствам со связанными ограничениями (2). Для построения методов решения вариационных неравенств со связанными ограничениями обычно требуется предположение о симметричности вектор-функции С (у, ад), отвечающей за связанные ограничения. Поскольку любая вектор-функция единственным образом раскладывается в сумму симметричной и антисимметричной вектор-функций, то определяя симметричную и антисимметричную вектор-функции следующим образом: Т(у,ъи) = ги) + С(го, и)) и Г(щ,ги) = -С(ги,и)), можно сфор-

мулировать вариационное неравенство со связанными ограничениями:

{Н{у*),и} — V*) > 0, Т(ь*,ш) <0 V ги € П. (12)

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

Модификация двухшагового экстраградиентного метода для решения вариационного неравенства со связанными ограничениями (2):

йк = [ик + акС(ук,ук)}+, ук =Рп{ук-ак(Н(ук)-Ч1С(укУ)ик)), йк =[йк+ ьк)]+, Ук =Рп(ук-ак(Н{ук)-Ч1С{ук,ьк)йк)),

ик+1 = + акс\ук,ук)}+, уш = Рп{ук - ак{Н(ук) - Ч1С{Ък,ук)йк)),

(13)

здесь ак > 0 - числовой параметр, отвечающий за величину шага, [-]+ - проекция на положительный ортант соответствующей размерности, Рп - оператор проектирования на Г2, - якобиан вектор-функции С(ь, ги) по соответствующей переменной.

Сходимость схемы (13) определяет следующая теорема. Теорема 2.5 Пусть для вариационного неравенства со связанными ограничениями (2) выполняются следующие условия:

а) множество О замкнуто и выпукло;

б) оператор Н(у) монотонный : (Н(у) — Н(ш),у — ~ш)> О V V, и> £ П;

в) множество решений V* задачи (2) не пусто;

г) вектор-функция С(у,и>) симметричная, дифференцируемая и выпуклая по и/ для любого ?> € Г2;

д) сужение С(у,ю)|ш=1) на диагонали квадрата - выпуклая функция;

е) операторы Н(у),С(ь,ги),\7иО(у,ю) удовлетворяют условию Липшица; Тогда существует последовательность параметров {а^}, такая что последовательность {ук}, порожденная методом (13), сходится по норме к некоторому решению у* € V* задачи (2).

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

Третья глава, «Комплекс программ и численные эксперименты»,

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

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

Основная программа решает задачи двумя методами и сравнивает полученные результаты. Главный модуль программы выступает в роли оболочки,

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

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

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

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

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

Раздел 3.5 содержит выводы по третьей главе. Подведены итоги численных

экспериментов, обозначены основные закономерности эффективного применения двухшагового экстраградиентного метода.

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

Основные результаты диссертационной работы

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

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

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

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

Публикации по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

1. Меленьчук Н. В., Зыкина А. В. Двухшаговый экстраградиентный метод для вариационных неравенств // Известия вузов. Математика. Казань: КГУ, 2010. №9. С. 82-85.

2. Меленьчук Н. В., Зыкина А. В. Двухшаговый экстраградиентный метод для задачи управления ресурсами // Моделирование и анализ информационных систем. Ярославль: ЯГУ, 2010. Том 17, №1. С. 65-75.

3. Меленьчук Н. В., Зыкина А. В. Вариационные неравенства со связанными ограничениями в модели дефицита ресурсов // Омский научный вестник. Омск: ОмГТУ, 2010. № 3(93). С. 77-86.

4. Меленьчук Н. В. Двухшаговый экстраградиентный метод для решения седловых задач // Омский научный вестник. Омск: ОмГТУ, 2009. № 3(83). С. 33-36.

Другие публикации

5. Меленьчук Н. В. Новый экстраградиентный метод для решения оптимизационных задач: тез. докл; межд. конф. / Динамика систем, механизмов и машин. Омск : ОмГТУ, 2009. Т. 3. С. 91-93.

6. Меленьчук Н. В., Зыкина А. В., Запорожец Д-Н. Эффективность двух-шагового экстраградиентного метода решения вариационных неравенств: материалы Росс. конф. / Дискретная оптимизация и исследование операций. Новосибирск : ИМ СО РАН, 2010. С. 87.

7. Меленьчук Н. В., Зыкина А. В. Двухшаговый экстраградиентный метод решения вариационных неравенств со связанными ограничениями: материалы межд. конф. / VI Московская международная конференция по исследованию операций. Москва : ВЦ РАН, 2010. С. 117-120.

8. Меленьчук Н. В., Зыкина А. В., Запорожец Д. Н. Экстраполяционные методы для решения вариационных неравенств и смежных задач: материалы Всеросс. конф. / Математическое программирование и приложения. Екатеринбург: ИММ УрО РАН, 2011. С. 41-42.

Свидетельство о регистрации программы

9. Экстраградиентные методы : свидетельство № 16330 / Меленьчук Н. В., Запорожец Д. Н.; правообладатель ГОУ ВПО «Омский государственный технический университет». - 50201050071; заявл. 27.10.2010; зарегестр. 08.11.2010. Реестр программ для ЭВМ.

Работа выполнялась при поддержке аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2011 годы)» (проекты № 2763,9260).

Печатается в авторской редакции

. ИД № 06039 от 12.10.2001 г.

Подписано в печать 29.04.11. Формат 60x84 Бумага офсетная. Отпечатано на дупликаторе. Усл. печ. л. 2,00. Уч.-изд. л. 2,00. Тираж 100 экз. Заказ 327.

Издательство ОмГТУ. 644050, г. Омск, пр. Мира, 11; т. 23-02-12 Типография ОмГТУ

Введение

1. Связанные ограничения в математическом моделировании

1.1. Модели задач со связанными ограничениями

1.2. Метод моделирования задачи планирования производства

1.3. Задача транспортного типа со связанными ограничениями

1.4. Несобственная задача линейного программирования

1.5. Итоги главы

2. Двухшаговые экстраградиентные методы

2.1. Экстраградиентные методы

2.2. Двухшаговый экстраградиентный метод для вариационного неравенства.

2.2. 1. Сходимость за конечное число итераций.

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

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

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

2.5. 1. Симметризация.

2.5. 2. Построение метода.

2.6. Итоги главы

3. Комплекс программ и численные эксперименты

3.1. Структура комплекса программ

3.2. Реализация.

3.3. Численные эксперименты.

3.3. 1. Тестовые задачи.

3.3. 2. Задача Розенброка.

3.3. 3. Задачи квадратичного программирования.

3.3. 4. Задачи линейного программирования.

3.3. 5. Задачи транспортного типа.

3.4. Итоги главы

Актуальность темы. Вариационные неравенства являются обобщением классических постановок задач оптимизации и имеют многочисленные приложения (к примеру, равновесие транспортных потоков, вопросы ценового равновесия, баланса спроса и предложения, выбор портфеля ценных бумаг). Особого внимания заслуживают вариационные неравенства со связанными ограничениями, описывающие наиболее сложные модели. С содержательной точки зрения связанными ограничениями задаются дополнительные условия, позволяющие стабилизировать противоречивую моделируемую ситуацию или учитывать внешние воздействия на систему. Разработкой математических методов моделирования таких сложных систем и численных методов для их решения занимаются многие известные российские и зарубежные ученые (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-го века. Вариационные неравенства со связанными ограничениями объединяют многие классы задач (в том числе перечисленные выше) и их использование в математическом моделировании является эффективным инструментом исследований.

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

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

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

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

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

2. Антипин А. С. Об одном методе отыскания седловой точки модифицированной функции Лагранжа // Экономика и математические методы. 1977. Т. 13, № 3. С. 560-565.

3. Антипин А. С., Недич А., Ячимович М. Трехшаговый метод линеаризации для задач минимизации // Известия вузов. Математика. 1994. № 12. С. 3-7.

4. Антипин А. С. Равновесное программирование: проксимальные методы // Журнал вычислительной математики и математической физики. 1997. Т. 37, № 11. С. 1327-1339.

5. Антипин А. С. Методы решения вариационных неравенств со связанными ограничениями // Журнал вычислительной математики и математической физики. 2000. Т.40, № 9. С. 1291-1307.

6. Антипин А. С. Экстрапроксимальный метод решения равновесных и игровых задач // Журнал вычислительной математики и математической физики. 2005. Т. 45, № 11,12. С. 1969-1990, 2102-2111.

7. Антипин А. С. О равновесной модели дифицита ресурсов // Нелинейная динамика и управление. М. : Физматлит, 2007. № 5. С. 241-250.

8. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М. : Мир, 1982. 583 с.

9. Байокки К., Капело А. Вариационные и квазивариационные неравенства. Приложение к задачам со свободной границей. М. : Наука, 1988. 448 с.

10. Бакушинский А. В., Поляк Б. Т. О решении вариационных неравенств // Доклады АН СССР. 1974. Т. 219, № 5.

11. Берщанский Я. М., Мееров М. В. Теория и методы решения задач дополнительности // Автоматика и телемеханика. 1983. № 6. С. 5-31.

12. Булавский В. А. Методы релаксации для систем неравенств. Новосибирск : НГУ, 1981. 82 с.

13. Васильев Ф.П. О регуляризации некорректных экстремальных задач // Доклады АН СССР. 1978. Т. 241, № 5. С. 1001-1004.

14. Васильев Ф. П., Недич А. О трехшаговом регуляризованном методе проекции градиента для решения задач минимизации с неточными исходными данными // Известия вузов. Математика. 1993. № 12. С. 35-43.

15. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М. : Наука, 1984. 320 с.

16. Голиков А.И. Об одной постановке обратной задачи нелинейного программирования // Обратные задачи математического программирования. М. : ВЦ РАН, 1992.

17. Голынтейн Е. Г., Третьяков Н. В. Модифицированные функции Лагранжа // Теория и методы оптимизации. М. : Наука, 1989. 400 с.

18. Демьянов В. Ф., Певный А. Б. Численные методы разыскания сед-ловых точек // Журнал вычислительной математики и математической физики. 1972. Т. 12, № 10. С. 1099-1127.

19. Еремин И. И., Мазуров Вл. Д. Нестационарные процессы математического программирования. М. : Наука, 1979. 288 с.

20. Еремин И. И., Мазуров Вл. Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. М. : Наука, 1983. 336 с.

21. Еремин И. И. Противоречивые модели оптимального планирования. М. : Наука, 1988. 160 с.

22. Еремин И. И. Теория линейной оптимизации. Екатеринбург : УрО РАН, 1998. 248 с.

23. Еремин И. И., Мазуров Вл. Д., Скарин В. Д., Хачай М. Ю. Математические методы в экономике. Екатеринбург : УрО РАН, 2000. 280 с.

24. Еремин И. И. Двойственность в линейной оптимизации. Екатеринбург : УрО РАН, 2001. 180 с.

25. Зыкина А. В. Обратная задача оптимизации и задача Лагранжа // Омский научный вестник. 2005. № 2(31). С. 81-84.

26. Зыкина А. В. Обратная задача для линейной задачи дополнительности // Омский научный вестник. 2005. № 3(32). С. 77-80.

27. Зыкина А. В. Обратная дополнительность: постановки, методы, приложения // Научный вестник НГТУ. 2006. № 2(23). С. 91-104.

28. Зыкина А. В. Обобщенная двойственность для задачи математического программирования // Омский научный вестник. 2006. № 8(44). С. 60-65.

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

30. Канторович Л. В. Экономический расчёт наилучшего использования ресурсов. М. : АН СССР, 1959. 344 с.

31. Канторович Л.В., Акилов Г.П. Функциональный анализ. М. : Наука, 1977. 744 с.

32. Коннов И. В. Комбинированные релаксационные методы для поиска точек равновесия и решения смежных задач // Известия вузов. Математика. 1993. № 2. С. 46-53.

33. Коннов И. В. Комбинированный релаксационный метод для поиска векторного равновесия // Известия вузов. Математика. 1995. № 12. С. 54-62.

34. Коннов И. В. Система прямо-двойственных вариационных неравенств в условиях монотонности // Журнал вычислительной математики и математической физики. 2003. Т. 43, № 10. 1459-1466.

35. Коннов И. В. Методы двойственного типа для обратных задач оптимизации и их обобщений // Доклады РАН. Математика. 2004. Т. 395, № 6. С. 1-3.

36. Коннов И. В. Метод нелинейного спуска для вариационного неравенства на невыпуклом множестве // Известия вузов. Математика. 2009. №1. С. 66-75.

37. Корпелевич Г. М. Экстраградиентный метод для отыскания седло-вых точек и других задач // Экономика и математические методы. 1976. Т. 12, № 4. С. 747-756.

38. Малинов В. Г. Орегуляризованном двухшаговом проекционном методе для задач минимизации с ограничениями // Журнал вычислительной математики и математической физики. 2000. Т. 40, № 1. С. 65-71.

39. Поляк Б. Т. Градиентные методы минимизации функционалов // Журнал вычислительной математики и математической физики. 1963. Т. 3, № 4.

40. Попов Л. Д. Модификация метода Эрроу-Гурвица поиска седловых точек // Математические заметки. 1980. Т. 28, № 5. С. 777-784.

41. Попов Л. Д. Метод обобщенного градиентного спуска для задачи последовательного программирования // Методы аппроксимации несобственных задач математического программирования. Свердловск : УНЦ АН СССР. 1984. С. 76-82.

42. Попов Л. Д. О схемах формирования ведущей последовательности в регуляризованном экстраградиентном методе решения вариационных неравенств // Известия высших учебных заведений. Математика. 2004. № 1. С. 70-79.

43. Тихонов А. В., Арсеиин В. Я. Методы решения некорректных задач. 2-ое изд., перераб. и доп. М. : Наука, 1979. 285 с.

44. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М. : Физматгиз, 1960. 656 с.

45. Хоботов Е. Н. О модификации экстраградиентного метода для решения вариационных неравенств и некоторых задач оптимизации // Журнал вычислительной математики математической физики. 1987. Т. 27, № 10. С. 1462-1473.

46. Arrow К. J., Hurwicz L., Uzava Н. Studies in in linear and nonlinear programming // Stanford university press. Standford. 1958.

47. Cottle R. W., Dantzig G. B. Complementary pivot theory of mathematical programming // Linear Algebra and Its Applications. 1968. № 1. P. 103-125.

48. Facchinei F., Kanzow C. Beyond monotonicity in regularization methods for nonlinear complementarity problems // SIAM Journal. Control and Optimization. 1999. V. 37, № 4. P. 1150-1161.

49. Harker P. Т., Pang J. S. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications // Mathematical Programming. 1990. V. 48, № 2. P. 161— 220.

50. Kaneko I. Jsotone solutions of parametric linear complementarity problems // Mathematical Programming. 1977. № 12. P. 48-59.

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

52. Konnov I. V. Dual approach for a class of implicit convex optimization problems // Mathematical Methods of Operations Research. 2004. V. 60, № 1. P. 87-99.

53. Kose T. Solutions of saddle value problems by differential equations // Econometrica. 1956. № 24. P. 59-70.

54. Nikaido H., Isoda K. Note on noncooperative convex games // Pacific Journal Mathematics. 1955. V. 5, № 1. P. 807-815.

55. Pang J. S. and Chang D. Iterative methods for variational and complementarity problems // Mathematical Programming. 1982. № 24. P. 284-313.

56. Меленьчук H. В. Об инструменте исследования сложных систем: тез. докл. Всерос. конф. / Россия молодая: передовые технологии в промышленность. Омск : ОмГТУ, 2008. Т. 2. С. 67-70.

57. Меленьчук Н. В. Методы распараллеливания и их применение: тез. докл. Всерос. конф. / Россия молодая: передовые технологии в промышленность. Омск : ОмГТУ, 2009. Т. 2. С. 57-61.

58. Меленьчук Н. В. Системы для распределенных вычислений: тез. докл. межд. конф. / Динамика систем, механизмов и машин. Омск : ОмГТУ, 2009. Т. 1. С. 307-309.

59. Меленьчук Н. В. Новый экстраградиентный метод для решения оптимизационных задач: тез. докл. межд. конф. / Динамика систем, механизмов и машин. Омск : ОмГТУ, 2009. Т. 3. С. 91-93.

60. Меленьчук Н. В. Двухшаговый экстраградиентный метод для решения седловых задач // Омский научный вестник. 2009. № 3(83). С. 33-36.

61. Меленьчук Н. В. Зыкина А. В. Двухшаговый экстраградиентный метод для задач управления ресурсами // Моделирование и анализ информационных систем. 2010. Т. 17, № 1. С. 65-75.

62. Меленьчук Н. В., Зыкина А. В. Двухшаговый экстраградиентный метод для вариационных неравенств // Известия вузов. Математика. 2010. № 9. С. 82-85.

63. Меленьчук Н. В., Зыкина А. В., Запорожец Д.Н. Эффективность двухшагового экстраградиентного метода решения вариационных неравенств: материалы Росс. конф. / Дискретная оптимизация и исследование операций. Новосибирск : ИМ СО РАН, 2010. С. 87.

64. Меленьчук Н. В., Зыкина А. В. Двухшаговый экстраградиентный метод решения вариационных неравенств со связанными ограничениями: материалы конф. / VI Московская международная конференция по исследованию операций. Москва : ВЦ РАН, 2010. С. 117-120.

65. Меленьчук Н. В., Запорожец Д. Н. Вариационные неравенства со связанными ограничениями в модели планирования производства: материалы Всерос. конф. / Россия молодая: передовые технологии в промышленность. Омск : ОмГТУ, 2010. Т. 1. С. 276-278.

66. Меленьчук Н. В., Зыкина А. В. Вариационные неравенства со связанными ограничениями в модели дефицита ресурсов // Омский научный вестник. 2010. №3(93), С. 77-86.

67. Экстраградиентные методы : свидетельство № 16330 / Меленьчук Н. В., Запорожец Д. Н.; правообладатель ГОУ ВПО «Омский государственный технический университет». 50201050071; заявл. 27.10.2010; зарегестр. 08.11.2010. Реестр программ для ЭВМ.

68. Меленьчук Н. В., Зыкина А. В., Запорожец Д. Н. Экстраполяци-онные методы для решения вариационных неравенств и смежных задач: материалы Всеросс. конф. / Математическое программирование и приложения. Екатеринбург: ИММ УрО РАН, 2011. С. 41-42.