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

• Карюкина, Юлия Геннадьевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Карюкина, Юлия Геннадьевна

ВВЕДЕНИЕ

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

§1.1 Общие и вспомогательные утверждения

§1.2 Описание метода и сходимость

ГЛАВА 2. РЕГУЛЯРИЗОВАННЫЕ КОНЕЧНОШАГОВЫЕ

МЕТОДЫ ПРОЕКЦИИ И УСЛОВНОГО ГРАДИЕНТА В ВЫПУКЛЫХ ЗАДАЧАХ ОПТИМИЗАЦИИ.

§2.1 Вспомогательные утверждения

§2.2 Аппроксимация множеств для ограничений типа неравенств

§2.3 Конечношаговые методы проекции и условного градиента

§2.4 Регуляризованный метод для двойственной задачи

ГЛАВА 3. ЗАДАЧА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДЛЯ ОДНОЙ ЭКОНОМИЧЕСКОЙ МОДЕЛИ.

§3.1 Постановка задачи. Свойства параметров модели

§3.2 Определение вида множества достижимости

§3.3 Исследование задачи оптимального управления.

Введение диссертации (часть автореферата) на тему «Методы решения выпуклых задач оптимизации и управления системами с сосредоточенными параметрами»

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

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

Теория управления представляет собой довольно обширную область науки. Она находит применение в различных сферах человеческой деятельности, начиная с управления конкретными объектами и кончая управлением в области политики и общественных отношений. Во всех этих сферах работают свои законы, определяющие динамику соответствующих систем. Взаимодействие материальных точек и системы твердых тел описываются законами механики, которые достаточно хорошо изучены. Известны также законы молекулярного и атомного взаимодействия. Во многих случаях они выражаются четкими математическими соотношениями. Тогда основные понятия теории управления и свойства управляемых систем можно сформулировать в математических терминах и на этой основе получать новые закономерности в достаточно общем виде (см., например [37, 54, 31]). Гораздо сложнее ситуация в сфере экономики и общественных отношений. Математические зависимости в этой сфере человеческой деятельности удается получить лишь в отдельных случаях. Тем не менее, основные понятия теории управления (управляемость, наблюдаемость, оптимальность и т.д.) здесь используются достаточно широко.

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

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

Многие процессы важные для современной техники и экономики управляемы, то есть, эти процессы могут протекать различными способами в зависимости от воли человека. В связи с этим возникает вопрос, как управлять процессом наилучшим образом (оптимально), как применять для этих целей математические методы. Математически сформулированные вопросы являются задачами оптимального управления. Поданной тематике опубликовано множество работ (см., например, [2, 5,10, 12, 38, 52, 72, 74, 76, 77, 79, 83, 84]).

При моделировании, разработке методов и численном решении прикладных задач оптимального управления, как и в других областях вычислительной математики, возникает проблема построения эффективных и обоснованных численных методов. При этом важно априори знать, является ли рассматриваемая задача устойчивой по отношению к возмущениям, и иметь оценки скорости сходимости уклонения решений. Основы теории и методов устойчивости и аппроксимации экстремальных задач заложены в работах Б.М.Будака, Ф.П.Васильева, В.В.Васина, Р.Ф.Га-басова, А.Дончева, А.И.Егорова, Ю.М.Ермольева, Ю.Г.Евтушенко, В.Г.Карманова, М.М.Потапова, А.З.Ишмухаметова, Ф.М.Кирилловой, В.Б.Колмановского, П.С.Краснощекова, А.Б.Куржанского, Ж.Л.Лионса, П.Ж.Лорана, Н.Н.Моисеева, Ю.С.Осипова, В.И.Плотникова, А.Н.Тихонова, В.М.Тихомирова и многих других (см. [13-15, 19-25, 28, 33, 50, 60, 66, 69, 80, 81]). По данной тематике опубликованы монографии и большое число научных статей отечественных и зарубежных авторов, среди которых [1, 7, 42, 44, 47, 58, 59, 62, 67, 82].

В теории оптимизации, в частности, в задачах математического программирования при разработке численных методов актуальными являются вопросы их практической реализуемости, эффективности и доведения их до алгоритмов. К таким вопросам относятся разработка методов, алгоритмов без бесконечных внутренних вычислительных процедур, поиск и формулировка критериев, правил останова. Отметим, что данной проблеме посвящено большое количество работ. Библиографию по этим работам можно найти, например, в [6, 8, 18, 29, 50, 63, 75, 85, 87, 88].

Предлагаемые в данной работе методы направлены на решение этих вопросов. Они построены на основе метода регуляризации (см., например, [3, 21, 35, 36, 42, 68, 69]), методов проекции, условного градиентов и двойственного метода [18, 29, 43, 50]. Для них получены критерии останова, доказаны оценки скорости сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов и к нормальному оптимальному элементу. Они в абстрактном, для бесконечномерных гильбертовых пространств предложены в [41, 46]. В конечномерных задачах они имеют свои особенности, в частности, это связано с эквивалентностью слабой и сильной топологий, отсутствием конечномерных аппроксимаций, присущей для бесконечномерных задач. Кроме того отметим, что обоснование методов проводится при условии непрерывности градиентов целевой и функций ограничений и рассматриваются случаи, когда параметр регуляризации можно положить равным нулю, т.е. при отсутствии регуляризации. Предлагаемые методы эффективны для решения задач с квадратичными целевыми функциями и с квадратичными функциями, задающих ограничения на допустимые элементы; выпуклыми целевыми функциями и с квадратичными функциями-ограничений [56]. В этом случае методы сводятся к последовательному решению систем линейных алгебраических уравнений.

Также в данной работе рассматривается динамическая модель управления производством, хранением и сбытом товаров повседневного спроса. Модель потенциально позволяет учитывать особенности рыночной экономики при производстве потребительских товаров. Также показывается, что для адекватного описания процессов необходимо учитывать их динамический характер, поскольку только в этом случае можно дать правильную интерпретацию особенностей наблюдаемых явлений и выбрать правильную стратегию производства и развития. Описан способ реализации стратегии производства, обеспечивающей его максимальную доходность. Разработанная модель, в некотором смысле, является базовой: на ее основе могут строиться новые модели, учитывающие влияние других факторов. Отметим работы в этом направлении [26, 27, 70].

Диссертация состоит из введения, трех глав и приложения.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Карюкина, Юлия Геннадьевна

Основные результаты диссертации содержатся в работах [4, 33, 47, 48, 50].

Автор выражает д.ф.м.н. зав. отдела методов нелинейного анализа А.З.Ишмухаметову признательность за руководство данной работой и благодарит к.ф.м.н. Е.Н.Хайлова за постановку конкретной экономической задачи и обсуждение результатов исследований. Автор также выражает благодарность участникам семинара отдела методов нелинейного анализа галвному научному сотруднику, проффе-сору Е.А.Гребеникову, профессору В.В.Дикусару и другим.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Карюкина, Юлия Геннадьевна, 2006 год

1. Аваков Е.Р. Условия регуляризации аппроксимирующего семейства экстремальных задач. //Вестник МГУ. Сер. 15. Вычисл. мат. и киберн, 1982, №10. С. 1659-1665.

2. Алексеев В.М, Тихомиров В.М, Фомин С.В. Оптимальное управление. М.: Наука, 1979.

3. Антипин А.С. Методы регуляризации в задачах выпуклого программирования. //Экономика и мат. методы. 1975. Т. И. № 2. С. 336-342.

4. Антипин И.П, Ишмухаметов А.З, Карюкина Ю.Г. Двойственный регуляризованный метод в выпуклых конечномерных задачах оптимизации. // ВЦ РАН, Вопр. модел. и анализа в зад. прин. реш., М., 2004, С.100-108.

5. Афанасьев А.П, Дикусар В.В, Милютин А.А, Чуканов С.А. Необходимое условие в оптимальном управлении. М.: Наука, 1990.

6. Бакушинский А.Б, Гончарский А.В. Итеративные методы решения некорректных задач. М.: Наука, 1989.

7. Банк Б, Белоусов Е.Г, Мандель Р, Черемных Ю.Н, Широнин В.М. Математическая оптимизация: вопросы разрешимости и устойчивости. М.: Изд-во МГУ, 1986.

8. Бахвалов Н.С., Жидков Н.П, Кобельков Г.М. Численные методы. М.: Наука, 1987.

9. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. М.: Радио и связь, 1987.

10. Болтянский В.Г. Математические методы оптимального управления. Москва Наука. 1968.

11. И. Борисов Б.Ф., Зеликин М.И. Режимы учащающихся переключений в задачах оптимального управления // Труды МИ АН СССР, 1991. Т. 197, С.85-167

12. Брайсон, Хо-Юши. Оптимальные управления

13. Будак Б.М., Берткович Е.М., Соловьева Е.Н. О сходимости разностных аппроксимаций для задач оптимального управления. //Ж. Вычисл. мат. и мат. физ., 1969, 9, №3. С. 522-547.

14. Будак Б.М., Берткович Е.М., Соловьева Е.Н. Об аппроксимации экстремальных задач. 1,11. //Ж. Вычисл. мат. и мат. физ., 1971, 2, №3. С. 580-596; №4. С. 870-884.

15. Будак Б.М., Васильев Ф.П. Некоторые вычислительные вс-пекты задач оптимального управления. М.: Изд-во МГУ, 1975. 16. Бутковский А.Г. Методы управления системами с распределенными параметрами. М.: Наука, 1975.

16. Ваниер Г., Хайрэр Э. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. М.: Мир, 1999.

17. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.

18. Васильев Ф.П. Методы решения экстремальных задач. М., Наука,1981.

19. Васильев Ф.П. Численные методы решения экстремальных задач. М., Наука, 1988.

20. Васильев Ф.П. Регуляризация некоторых методов минимизации высокого порядка при неточных исходных данных. //Ж. Вычисл. мат. и мат. физ., 1985, 25, №4 С.492-499.

21. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М., Факториал, 1998.

22. Васин В.В. Устойчивая дискретизация экстремальных задач и ее приложения в математическом программировании. //Мат. заметки,1982, 31, №2. С.269-280.

23. Габасов Р.Ф., Кириллова Ф.М. Особые оптимальные управления.

24. Габасов Р.Ф., Кириллова Ф.М. Качественная теория оптимальных процессов. М.: Наука, 1971.

25. Горский А.А., Колпакова И.А., Локшин Б.А. Динамическая модель процесса производства, хранения и сбыта товара повседневного спроса // Ж. Известия РАН. Серия Теория и системы управления. 1998, М. С. 144-148.

26. Горский А.А., Колпакова И.А., Локшин Б.А., С.А. Покровская. Об одной динамической модели процесса производства, хранения и сбыта //Ж. Известия РАН. Серия Техническая кибернетика. 1992, №3. С. 190-193.

27. Дончев А. Системы оптимального управления. Возмущения, приближения и анализ чувствительности. М.: Мир, 1987.

28. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

29. Егоров А.И. Об устойчивости и оптимизации систем с распределенными параметрами. //Прикл. мат., 1984, 20, №4, С.95-100.

30. Егоров А.И. Основы теории управления. М.: Физматлит, 2004.

31. Ермольев Ю.Н., Гуленко В.П. О численных методах решения задач оптимального управления. //Кибернетика, 1966, №1. С.120-121.

32. Ермольев Ю.Н., Гуленко В.П. Конечно-разностный метод в задачах оптимального управления. //Кибернетика, 1967, №3. С.1-20.

33. Есенков А.С., Ишмухаметов А.З., Карюкина Ю.Г. Регуляри-зованные методы проекции и условного градиента в выпуклых конечномерных задачах оптимизации. // ВЦ РАН, Вопр. модел. и анализа в зад. прин. реш., М., 2004, С.127-142.

34. Заболотская Е.Н., Ишмухаметов А.З. Двойственный регуляри-зованный метод в задаче оптимального управления параболической системой.//Вопросы моделирования и анализа в задачах принятиярешений, М: ВЦ РАН, 2002.

35. Заболотский Е.В., Ишмухаметов А.З. Двойственный регуляри-зованный метод в задаче оптимального управления гиперблической системой.//Вопросы моделирования и анализа в задачах принятия решений, М: ВЦ РАН, 2002.j

36. Зубов В.И. Лекции по теории управления. М.: Наука, 1975.

37. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

38. Ильин В.А., Позняк Э.Г. Математический анализ. Москва Наука. 1986., т.1, С. 156-157.

39. Иосида К. Функциональный анализ. М.: Мир, 1967.

40. Ишмухаметов А.З. Двойственный метод решения одного класса выпуклых задач минимизации.//ЖВМиМФ, 2000, т.40, N 7, С. 1045-1060.

41. Ишмухаметов А.З. Об условиях аппроксимации и регуляризации в экстремальных задачах. //Прикл. мат. и мат. обеспеч. ЭВМ. М.: Изд-во МГУ, 1981, С.25-27.

42. Ишмухаметов А.З. Методы решения задач оптимизации. М.: Изд-во МЭИ, 1998.

43. Ишмухаметов А.З. Моделирование процессов управления линейными системами: устойчивость и аппроксимация. //Итоги науки и техники. ВИНИТИ: Вычисл. Науки, 1991, т.7. С.3-38.

44. Ишмухаметов А.З. Регуляризованные методы оптимизации с конечношаговыми внутренними алгоритмами.//ДАН, 2003, т. 390, N 3, с. 304-308.

45. Ишмухаметов А.З. Регуляризованные приближенные методы проекции и условного градиента с конечношаговыми внутренними алгоритмами. //ЖВМиМФ, 2003, т. 43, N 12, с. 1896-1909.

46. Ишмухаметов А.З. Условия аппроксимации и устойчивостизадач минимизации. //Ж. вычисл. мат. и мат. физ., 1993. Т. 33, №7, С.1012-1029.

47. Ишмухаметов А.З, Карюкина Ю.Г. О некоторых конечношаго-вых методах оптимизации в выпуклых задачах.// Иркутск, Байкал2005, Мет. оптим. и их прил., Труды школы семинара: Мат. программирование. С. 163-167.

48. Ишмухаметов А.З, Карюкина Ю.Г, Хайлов Е.Н. Задача оптимального управления для модели производства, хранения и сбыта товара. // ВЦ РАН, Вопр. модел. и анализа в зад. прин. реш, М, 2006.

49. Карманов В.Г. Математическое программирование. М.: Физмат-лит, 2000.

50. Карюкина Ю.Г. Исследование одной задачи оптимального управления. //Центрально-Черноземное книжное изд-во, Воронеж2006. Совр. методы теор. краев, задач. С. 79.

51. Киселев Ю.Н. Оптимальное управление.

52. Колмогоров А.Н, Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1976.

53. Красовский Н.Н. Теория управления движением. М.: Наука, 1968.

54. Лебедев В.И. Функциональный анализ и вычислительная математика. М.: Физматлит. 2000.

55. Левиков А.А. О предельных свойствах динамических систем с выпуклыми ограничениями. //Ж. вычисл. мат. и мат. физ, 1979,19, т, с.30-39.

56. Левин А.Ю. Неосцилляция решений уравнения х^ + • • • + Pn{t)x — 0. Успехи математических наук. 1969, т.24, №2. С. 43-96.

57. Лепп Р.Э. Дискретная аппроксимация экстремальных задач соператорными ограничениями типа неравенств. //Ж. вычисл. мат. и мат. физ., 1990, 30, №6, С.817-825.

58. Лигун А.А., Капустян В.Е., Волков Ю.И. Специальные вопросы теории приближений и оптимального управления распределенными параметрами. Киев: Выща школа, 1990, 208 с.

59. Лионе Ж.Л, Оптимальное управление системами, описываемыми уравнениями с частными производными. М.: Мир, 1972.

60. Ли Маркус. Исследование множества достижимости.

61. Лоран П.Ж. Аппроксимация и оптимизация. М.: Мир, 1975.

62. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1989.

63. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

64. Михайлов В.П. Дифференциальные уравнения в частных производных. М.: Наука, 1983.

65. Моисеев Н.Н. Численные методы в теории оптимальных систем. М.: Наука, 1971.

66. Мордухович Б.Ш. Методы аппроксимации в задачах оптимального управления. М.: Наука, 1988.

67. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987.

68. Осипов Ю.С., Васильев Ф.П., Потапов М.М. Основы метода динамической регуляризации. Изд-во МГУ, 1999.

69. Параев Ю.И. Решение задачи об оптимальном производстве, хранении и сбыте товара //Ж. Известия РАН. Серия Теория и системы управления. 2000, №2. С. 103-107.

70. Питтель Б.Г. Об одной задаче оптимального управления, связанной с минимизацией функционала типа максимум отклонения. Дифференциальные уравнения. 1965, Т. 1., №11. С. 1493-1508.

71. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

72. Понтрягин JI.C. Обыкновенные дифференциальные уравнения. М.: Наука, 1970.

73. Понтрягин JI.C., Болтянский В.Г., Гамкридзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М: Наука. 1983. С. 23-27.

74. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

75. Сиразетдинов Т.К. Оптимизация систем с распределенными параметрами. М.: Наука, 1977.

76. Стрекаловский А.С. Оптимизация линейных распределенных систем. Иркутск: Изд-во Иркутского ун-та, 1982.

77. Степанов В.В. Курс дифференциальных уравнений. М.: Наука, 1975.

78. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

79. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986.

80. Тихонов А.Н., Васильев Ф.П. Методы решения некорректных экстремальных задач.//Math. Models and Numer. Methods. Warszawa: Bahach Center Pubis, 1978. С 297-342.

81. Уайлд Д.Дж. Методы поиска экстремума. М.: Наука, ГРФМЛ, 1967.

82. Федоренко Р.П. Приближенные методы решения задач оптимального управления. М.: Наука, 1978.

83. Флеминг И., Ришел Р. Оптимальное управление детерминированными и стохастическими системами. М.: Мир, 1978.

84. Черноусько Ф.Л. Колмановский В.Б. Вычислительные и приближенные методы оптимального управления. //Итоги науки и техн.

85. Мат. анализ. ВНИИТИ. 1977, 14, С.12-31.

86. Чеботарев Н.Г. Алгебраические функции. M.-JL: Гостехиздат, 1947.

87. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач. Экономика и мат. методы, XII, N.2, 1976.

88. Kaplan A., Tichatschke R. Stable methods for ill-posed problems. V. 3. Mathematical topics. Berlin: Akad. Verl., 1994.