Методы и алгоритмы для решения задач математического моделирования на основе вариационных неравенств тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Меленьчук, Николай Владимирович

• Меленьчук, Николай Владимирович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Меленьчук, Николай Владимирович

Введение

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Меленьчук, Николай Владимирович, 2011 год

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.