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

• Шомполова, Ольга Игоревна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Шомполова, Ольга Игоревна

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

Глава 1. Применение факторного анализа для решения задач линейного программирования.

1 Модель факторного анализа.

2. Неопределённость факторных решений.

3 Метод интерполяции.

4 Метод Якоби.

5. Продолжение решений по параметру.

6 Итеративная декомпозиция матрицы Якоби.

7 Снижение размерности матрицы Я при дискретизации дифференциального уравнения. 8 Программы факторного анализа.

9 Различные формы задач линейного программирования.

10 Двойственность в задачах ЛП.

11 Обобщенная задача ЛП.

12 Метод оценки решения задачи ЛП.

Глава 2. Принцип максимума для линейных систем со смешанными ограничениями

2.1 .Постановка задачи оптимального управления.

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

2.3. Линейные параметрические модели с ограничениями смешанного типа.

2.4. Условия оптимальности для линейных задач.

2.5. Задачи оптимального управления А и Б.

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

3.1. Построение конечно-разностной аппроксимации модели.

3.2. Схема решения параметрических задач оптимального управления.

3.2.1.Получение аппроксимации решения прямой задачи.

3.2.2.Построение аппроксимации решения сопряженной задачи.

3.3. Сходимость дискретных аппроксимаций.

3.4. Общая схема решения линейных задач ОУ.

3.4.1 .Случай исключения ограничений типа равенства. .81 3.4.2. Схема решения линейной задачи ОУ.

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

3.6. Применение схем дискретизации с переменным шагом.

3.7. Анализ устойчивости дискретной аппроксимации на основе критерия оптимальности.

Глава 4 МИНИМИЗАЦИЯ ДОЛГА ПРОМЫШЛЕННОГО ПРЕДПРИЯТИЯ.

4.1. Содержательное описание особенностей моделируемой системы.

4.2. Математическая формулировка модели.

4.2.1. Обозначения для количественных характеристик системы.

4.2.2. Динамические соотношения системы.

4.2.3. Ограничения на фазовые переменные и управления системы.

4.2.4.Целевая функция.

4.3. Общая формулировка задачи.

4.4. Решение задачи.

4.4.1 .Решение дискретной аппроксимации с помощью факторного анализа.

4.5. Применение различных схем дискретизации.

4.5.1. Применение схем дискретизации разных порядков точности.

4.6. Каноническая задача Дубовицкого-Милютина.

4.7. Нерегулярные точки.

4.8.Формулировка и решение параметрической задачи

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

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

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

Исследуемые в диссертации СЛАУ являются несовместными, а задачи ЛП - несобственными. Хорошо известно, что совместность или несовместность линейных моделей, заданных системами уравнений, неравенств или смешанными системами уравнений и неравенств представляют собой фундаментальные свойства, связанные так называемыми теоремами об альтернативах - классической основой теорем существования решений задач оптимизации и возможным инструментом их эффективного численного решения, развитым в работах Бирюкова А.Г., А.И. Голикова, Дикусара В.В., Ю.Г.Евтушенко, Жадана В.Г., Капорина И.Е., Посыпкина М.А., Чекарева Д.А., Умнова Е.А., Умнова Е.Е. и др. Метод штрафных функций и функций Лагранжа является универсальным средством решения экстремальных задач различной природы.

Актуальность исследования несобственных математических объектов была хорошо обозначена И. И. Ереминым, в частности, он указал, что в теории математических моделей и классов задач прослеживается эволюция в сторону ослабления требований, накладываемых на исследуемый математический объект. Возникает последовательность постановок задач: единственность решения и устойчивость; единственность, неустойчивость (некорректность); неединственность и неустойчивость; несобственность; несобственность и плохая формализуемость; гибкое моделирование и т.д.

Несовместная (несобственная) модель не позволяет получить содержательную информацию об исследуемом процессе или явлении непосредственно. Для этой цели требуется исправление модели и ее коррекция. Виды и способы коррекции могут быть различными. Наиболее общая форма коррекции заключается в изменении коэффициентов левых и правых частей соответствующих уравнений и неравенств. Соответствующую коррекцию называют матричной. Систематическое исследование несобственных задач линейного и выпуклого программирования было начато в 70-х гг. прошлого столетия И. И. Ереминым и его учениками. В работах H.H. Астафьева, A.A. Ватоли-на, В.Д. Мазурова, JI. Д. Попова, В.Д. Скарина, С.П. Трофимова, В.Н. Фролова и др. рассматривались несобственные задачи линейного и выпуклого программирования, проводилась классификация, строилась и исследовалась теория двойственности. При этом вводились и исследовались дискретные аппроксимации решений, т.н. комитетные конструкции. Отметим, что в большинстве исследований рассматривалась коррекция по вектору правой части ограничений и коэффициентом вектора целевой функции.

Матричная коррекция впервые была рассмотрена в работах A.A. Ватолина. Исследования A.A. Ватолина были продолжены в ВЦ им. A.A. Дородницына РАН и МПГУ В.А. Гореликом и его учениками: В. А. Кондратьевым, О.В. Муравьевым, P.P. Ибатулиным, Р.В. Печенкиным, В.И. Ерохиным и др. Указанными авторами были уточнены результаты A.A. Ватолина. В методах матричной коррекции остались нерешенными очень многие важные проблемы. Первая проблема связана с неединственностью решения задачи матричной коррекции. Естественно, что в прикладных задачах важна единственность и устойчивость решения скорректированной линейной модели. Следует признать, что систематизированное исследование указанной проблемы и методов их решения в настоящее время не существует. Другой аспект связан с выбором показателя качества матричной коррекции, который диктуется прикладной задачей. Он, например, связан с некоторой статистической гипотезой (Евклидова норма - нормальное распределение ошибок, чебышевская норма — равномерное распределение, октаэдрическое - наличие случайных выбросов). Указанные обстоятельства влияют на методы исследования и решения задач матричной коррекции .

Цель и задачи исследования

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

В соответствии с целью исследования поставлены следующие задачи:

1. разработка численно-аналитических схем решения линейных задач оптимального управления со смешанными ограничениями, основанных на совместном решении пары задач ОУ, сводимых к двойственным задачам ЛП в банаховых пространствах;

2. анализ и приведение к виду, удобному для использования, достаточных условий экстремума в рассматриваемых задачах;

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

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

5. исследование способов повышения точности приближенных численных решений задачи ОУ, анализ сходимости и устойчивости дискретной аппроксимации исходной задачи;

Объект исследования

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

Теоретические и методологические основы исследования

Теоретическую и методологическую основу диссертации составляют труды российских ученых-математиков по методам решения задач ОУ, задач ЛП, методам оптимизации, теории и методов факторного анализа.

Научная новизна исследования

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

Практическая значимость

Модели, методы и алгоритмы, разработанные в исследовании, применялись для решения практических задач оптимального управления в Московском Физико-Техническом институте и в Вычислительном Центре РАН.

Публикации

Основные результаты исследования отражены в 14 публикациях автора общим объемом 5.3 п.л. и 5-и статьях в изданиях, рекомендованных ВАК РФ, объемом 2.9 п.л. Результаты в совместных работах принадлежат авторам в равных долях.

Апробация работ

Работа выполнена при финансовой поддержке РФФИ (коды проекта 10-08-00624,11-07-00201)

Основные положения исследования докладывались и обсуждались на научных конференциях МФТИ., на международной конференции Computer Algebra Systems in Teaching and Research, 4 International Workshop, CASTR 2007. Siedlce(nOJIbIIIA),Ha научных семинарах в ИСА РАНДЭМИ РАН, ИЛУ РАН,ИПМ РАН,ВЦ РАН

Структура и объем работы

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

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

Основные результаты проведенного диссертационного исследования следующие:

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

На основе предложенного подхода:

1. На базе схемы Дубовицкого-Мипютина и методов факторного анализа создана методика численного решения линейных параметрических задач ОУ со смешанными ограничениями.

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

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

4. предложен модифицированный метод Якоби для вычисления собственных чисел матрицы наблюдений.

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

Список литературы диссертационного исследования кандидат физико-математических наук Шомполова, Ольга Игоревна, 2012 год

1. Дубовицкий А.Я.,Милютин A.A. Необходимые условия экстремума в некоторых линейных задачах со смешанными ограничениями.В сб. "Вероятностные процессы и управление". М.: Наука,1978. Стр

2. Хачай М.Ю. Комитетные решения несовместных систем ограничений и методы обучения распознаванию. Автореферат докторской дисс. М.: ВЦ РАН, 2004.

3. Харман Г. Современный факторный анализ М.: Статистика, 1972.

4. Голиков А.И., Евтушенко Ю.Г. Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности. ЖВМиМФ, 2004, том 44, №9. С. 1564-1573.

5. Умнов А.Е., Умнов Е.А., Чекарев Д.А. Параметрический двухуровневый метод решения задач оптимального управления со смешанными ограничениями. // Моделирование процессов управления: Сб.ст./Моск. физ.-тех. ин-т. М., 2004.

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

7. В.В. Дикусар, Д.А.Чекарев. Численно-аналитический метод решения задач оптимального управления. Препринт. ВЦ РАН, 2004.

8. Тер-Крикоров A.M. Оптимальное управление и математическая экономика. М.: Наука, 1977.

9. Ю.Дубовицкий А.Я.,Милютин А.А.Необходимые условия экстремума в некоторых линейных задачах со смешанными ограничениями.В сборнике "Вероятностные процессы и управление". М.,Наука, 1978.-С.42-74.

10. П.Жадан В.Г.Численные методы линейного и нелинейного программирования.М.:ВЦ РАН,2002.

11. Харман Г. Современный факторный анализ. М., Статистика, 1972.

12. З.Дубровский С. А.,3ейгер Е. М., Френкель А. А. Факторный анализ. Методы и приложения. В кн. Многомерный статистический анализ в социально-экономических исследованиях; под ред. Т. В. Рябушкина М., Наука, 1974.

13. Благуш П. Факторный анализ с обобщениями. М., Финансы и статистика, 1989.

14. Ким Дж-о, Мьюллер Ч. У., Клекка У. Р., Олдендерфер М. С., Блэшфилд Р. К. Факторный, дискриминантный и кластерный анализ. М., Финансы и статистика, 1989.

15. ИберлаК. Факторный анализ. М., Статистика, 1980.

16. Айавзян С. А. Мхитарян В. С. Прикладная статистика и основы эконометрики. М., ЮНИТИ, 1998.

17. Тихонов А. Н., Уфимцев М. В. Статистическая обработка результатов эксперимента. М., МГУ, 1988.

18. Ледерман У. (редактор). Справочник по прикладной статистике. Том 2. М., Финансы и статистика, 1990.

19. Белашов В. Ю. Чернов Н. М. Эффективные алгоритмы и программы вычислительной математики. Дальневосточное отделение РАН. Магадан, 1997.

20. Калиткин Н. Н. Численные методы. М., Наука, 1978.

21. Виленкин С. Я. (редактор). Сборник научных программ на фортране.Руководство для программиста. Вып. 1. М., Статистика, 1974.

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

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

24. Аоки М. Введение в методы оптимизации. М., Наука, 1977

25. Голиков А.И., Евтушенко Ю.Г. Отыскание нормальных решений в задачах линейного программирования. ЖВМ и МФ, 2000, т.40, №12, с.1766-1786.

26. Сухарев А.Г., Тимохов A.B., Федоров В.В, Курс методов оптимизации. М., Физматлиз, 2005.

27. Дикусар В.В. Обобщенная задача линейного программирования, Доклады РАН,том 248, №6, 1996, с. 1-3 28.Stoer J, Bulirsch P., Introduction to Numerical Analysis. Springer-Verlag, 1990.

28. Афанасьев B.H., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. -М.: Высш. школа, 2003.

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

30. Бетт Дж. Сведение задачи оптимального управления к задаче нелинейного программирования большой размерности. Корпорация Боинг. 1998.

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

32. ЗЗДанциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966.

33. Дику cap В.В. Методика численного решения краевых вариационных задач для системы обыкновенных дифференциальных уравнений. Автореферат дисс. д.ф.-м.н., Дубна, ОИЯИ, 1982.

34. Дику cap В.В., Милютин А. А, Качественные и численные методы в принципе максимума. М., Наука, 1989.

35. Дикусар В.В., Кошъка М., Фигура А. Методы продолжения решений в прикладных задачах оптимального управления. М., МФТИ, 2001.

36. Дикусар В.В., Кошъка М., Фигура А. Задачи оптимального управления при наличии ограничений общего вида. М., МФТИ, 2001.

37. Дикусар В.В., Кошъка М, Фигура А. Методы решения плохо обусловленных линейных систем. М.: ВЦ РАН, 2001.

38. Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом: Сообщ. по прикл. матем. / ВЦ РАН. М., 2000.

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

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

41. Ермольев Ю.М., Гуленко В.П., Царенко Т.Н. Конечно-разностный метод в задачах оптимального управления. -Киев: Наукова думка, 1978.

42. Измайлов А.Ф., Третьяков A.A., 2-регулярные решения нелинейных задач. М., Физматгиз, 1999.

43. Коротких М.П. Язык «L» моделирования динамических систем. МФТИ, 1993.

44. Кривоножко В.Е., Чеботарев С.П. О методе факторизации в задачах линейного динамического программирования. Автоматика и телемеханика, 1976. № 6. Стр. 80-90.

45. Милютин A.A., Илютович А.Е., Осмоловский Н.П., Чу-канов C.B. Оптимальное управление в линейных системах. М., Наука, 1993.

46. Морозов В.А. Алгоритмические основы методов решения некорректно поставленных задач. Сб. "Численныйанализ: теория, приложения, программы". М.: МГУ, 1999, Стр. 3-2 6.

47. Петров А.А. Проблемы математического описания экономических процессов и системного анализа экономики. Сб. "Математическое моделирование: Методы описания и исследования сложных систем". М.: Наука, 1989.

48. Поляк Б. Т. Об одном методе решения задач линейного и квадратичного программирования большого объема. М.: МГУ, 1969, вып. 12, Стр. 10-17.

49. Пропой А.И., Ядыкин А.Б. Модифицированные соотношения двойственности в задачах линейного динамического программирования. Автоматика и телемеханика, 1975, №5. Стр. 106 114.

50. Умное А.Е. Система содействия принятию решений «Баланс». -М.: МФТИ, 1991.

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

52. Чуканов C.B. О непрерывной зависимости решений задачи оптимального экономического планирования от условий задачи. Автоматика и телемеханика, 1978. № 5. Стр. 113

53. Шикин Е.В. Линейные пространства и отображения. М.: МГУ, 1987.

54. Дмитрук А.В.,Каганович А.М.Принцип максимума для задач оптимального управления с промежуточными ограничениями.Нелинейная динамика и управление.Сборник статей.Вып.б.М. :Физматлит,2008. Стр. 101-136.

55. Барсегян В.Р.Управление поэтапно меняющимися линейными динамическимисистемами с ограничениями на значения частей координат фазового вектора в промежуточные моменты времени Труды ИСА РАН.Т.53(3),2010.Стр.7-18.

56. Голиков А.И.,Евтушенко Ю.Г. Метод решения задач линейного программирования большой размерности. Доклады РАН,2004.т.397,№6,с.727-732.

57. Шевцов Г.С.Линейная алгебра.Теория иприкладные аспекты.М.¡Финансы и статистика,2003.

58. По теме диссертации опубликованы следующие работы:

59. Трушин В.Б., Трушин Ю.В., Шомполова О.И. О монотонности и коэрцитивностиодного отображения // Современные проблемы фундаментальных и при-кладныхнаук / Программа 49 научной конференции МФТИ. Москва-Долгопрудный, 2006.-С. 153.

60. Трушин В.Б., Трушин Ю.В., Шомполова О.И. Сведение систем линейныхуравнений к вариационному неравенству // Современные проблемыфундамен-тальных и прикладных наук / Программа 49 научной конференцииМФТИ. Москва-Долгопрудный, 2006.-С. 154.