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

• Шимялене, Регина Нийоле
• кандидат физико-математических наук
• 1999

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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА I. ДИСКРЕТНАЯ КВАДРАТИЧНАЯ ЗАДАНА

МНОГОШАГОВОЙ ОПТИМИЗАЦИИ

1. Смешанные задачи

2. Выпуклость в алгоритмах решения

ГЛАВА II. ДИСКРЕТНЫЕ ПРОЦЕССЫ ОПТИМАЛЬНОГО

УПРАВЛЕНИЯ С ЗАПАЗДЫВАНИЕМ

1. Постановка задачи

2. Сведение задачи с запаздыванием к обыкновенной задаче дискретного управления

3. Алгоритм приближенного решения

ГЛАВА III. ОПТИМИЗАЦИЯ ИТЕРАЦИОННОГО ПРОЦЕССА

РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ

1. Формулировка задачи

2. Монотонный алгоритм решения

ЛИТЕРАТУРА

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

ВВЕДЕНИЕ

Исследуется приложение принципа максимума для решения различных задач многошаговой оптимизации, когда множество решений либо дискретное, либо связное. Для решения этих задач разработаны новые методы типа динамического программирования и принципа максимума, которые рассматривались в работах [1] -[4], [9]-[16], [19]-[22], [53].

В диссертационной работе к решению известных и частных задач многошаговой оптимизации применяется дискретный принцип максимума. Исходные задачи оптимизации аппроксимируются нового типа задачами управления, для которых дискретный принцип максимума является достаточным условием оптимальности. Для приложения принципа максимума в дискретном и непрерывном вариантах и других классических методов оптимизации к решению задач многошаговой оптимизации исследованы типы смешанных задач, описанных либо задачами непрерывного управления, либо задачами дискретно - непрерывного управления. Смешанные задачи рассматриваются В. Бистрицкасом в работах [5] - [8].

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

1 И }0 Т М им

л = а , л и ), х = а.

(2)

и е [и и Сг»))=ЫсЯт

Здесь X - П -вектор, ¿^ - Г-вектор, Ср (х)й заданные функции, - фиксированный /^-вектор, ^ /с ^ м + -заданные моменты времени^ к ~ О} • • • ; N~~ ОПРЕДЕЛЕНИЕ. Задачу оптимального управления

ГУ с л"-!.

вир

(4)

А

т т

г п ' ■ ■ -ч

V € V = (и X

К А I к I с ¿ = 1 с

с Со и (5)

назовем смешанной задачей, если удовлетворено условие

тахЭЛ\чЛл )=тахУ({и\ )

иси с инси 1 «>0 ■

где О О П. - выпуклая оболочка множества (у[ СХ ^

I/с/г; и =

к

Таким образом, если V* ( к = О, ... . N-4) .

К

оптимальное решение задачи (4) - (5), имеюущее вид

т т

А

то в оптимальном смешанном решении задачи (1) - (3) точка Ц, (¿) на А -ом шагу выбирается с вероятностью

С

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

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

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

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

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

Процессы оптимального управления (4) - (5) используются для исследований смешанных решений процессов (1) - (3). Эта методика применяется для исследований дискретных многошаговых процессов управления запасами. Рассматриваются задачи многошаговой оптимизации, описываемые рекуррентными уравнениями динамического программирования, а также дискретными процессами оптимального управления. В работе [6] исследуется связь между процессами динамического программирования и процессами оптимального управления. Эта связь часто используется. В последнее десятилетие исследуются задачи управления запасами, рассматриваемые в работах [26], [41] - [49]. Многошаговые задачи разных видов управления запасами аппроксимируются смешанными задачами. Классические методы оптимизации, дискретный и непрерывный принцип максимума применяются для исследований этих аппроксимаций. Классические оптимизационные методы эффектны в исследовании смешанных решений этих дискретных аппроксимаций.

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

1. Дискретная квадратичная задача многошаговой оптимизации.

2. Дискретная задача оптимального управления с запаздыванием по управлению.

3. Принцип максимума для оптимизации итерационного процесса решения систем уравнений.

Диссертация состоит из трех глав.

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

Ы-1

г Т т

! х 0, X + и, Я, и. + , и ч-

и к ^к к к к к к к

к-О

т т 7

+ В X, + X, Р и, ] —^ /т?/>7 (1)

к к к к н у

ик

х = А х + А и , хл = а (2)

+ 4 к к а л > о >

и е и с о)

л

Если множество и дискретное, то её обозначим ип и рассмотрим случаи, когда = \ и (4). ....и (ПО) / С

^г д I ) ; J

С /? •

Здесь и. (¿) - заданные векторы ( £ - , , . /71 )

, ^-заданные

матрицы соответствующих размеров К1 X П ? П X Г? Г) X П^ Г X Г 4 * Г 4 X П ? П X Г.

ЕСЛИ = И, ^ - В, - /?А = /?

для всех ку ; 7 - нулевые матрицы, то

для задачи (1) - (3) в случае связного множества управления 1у1 получена смешанная задача [7].

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

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

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

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

N-1 г

к-О и ^ а

/ л

¿А

к-4 г

\ / 4>*(*>х1> ин-1 ^ * ^

ч

Здесь у*= ...; ?Нп), {им} = {и01..

^ (Ь^Х^ ^ (£; X ^ Ы-~) - заданные функции,

- /7 -вектор состояния, - А"-вектор управления,

Л ^

¿2. -заданный /7 -вектор, t - моменты времени.

К л

Эта задача сведена к обычной задаче дискретного управления:

УКе и с вг} к= 0} N-1.

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

Задача дискретного управления с запаздыванием по управлению поступила по заказу при решении частной задачи теории информации. Она обобщалась и в рассмотренном виде она является в некотором случае общей дискретной задачей оптимального управления с непрерывным временем и интегральными ограничениями, которая рассматривалась в работах [9], [25], [42], [50] - [52]. В данной работе эта задача аппроксимируется обычной задачей дискретного управления, к решению которой возможно применить упомянутую методику исследования оптимального управления.

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

П 2

т. (х^) -ГП1П}

¿^ Н и, ГО

к

X ^ = У - и, (-1) [7 у (лк) Д

к+4 к к / а /

'А-И к А / к /г

^ / ^

"л

и и (¿)*0 ¿=4,2,

к /г ^ ^

А = О ..

? ? 7

где

п

2

(х)= Ц /. Сх).

J Ь

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

Обычно для численного решения систем уравнений с числовыми неизвестными используются итерационные методы математического программирования незаботясь о скорости сходимости этих алгоритмов. Если итерационный процесс сходится медленно, то целесообразно использовать предлагаемый оптимизационный алгоритм. Кроме того, уменьшение числа шагов итераций ускоряет время вычислений при сложной функции ^^^ ■ Увеличение числа шагов предлагаемого алгоритма программу удлиняет незначительно, так как в некоторых шагах вычисление происходит по тем же самим формулам, например шаг 5, шаг 8 и

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

Проведём грубый сравнительный анализ сложности предлагаемых алгоритмов. Теорему о выпуклости функции целесообразно использовать в алгоритмах принципа максимума, в которых выбираются значения сопряженных переменных и критерий минимизируется по начальным значениям сопряженных переменных. Это прямой алгоритм принципа максимума, алгоритм приближения по граничным условиям, алгоритмы М.А. Крылова и Ф.Л. Черноусько, алгоритмы дополнительного шага и другие, если значения начальных сопряженных переменных устанавливаются не однозначно.

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

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

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

Основные результаты работы докладывались и обсуждались на ряде конференций Литовского математического общества, на II и III Всесоюзных школах "Понтрягинские чтения. Оптимальное управление. Геометрия и анализ" в Сибири, на 14-том Международном симпозиуме по математическому

программированию в Амстердаме, на Конференции по комбинаторной оптимизации С092 в университете Охфорда, на XIII Всемирной конференции по исследованию операций IFORS 93 в Лисабоне, на Конференции по комбинаторной оптимизации С094 в Амстердаме, на Международной конференции по исследованию операций в Берлине, на Третьем международном конгрессе по индустриальной и прикладной математике ICIAM 95 в Гамбурге, на Ежегодних встречах GAMM: GAMM 96 в Праге, GAMM 97 в Регенсбурге, GAMM 98 в Бремене, на Международном конгрессе математиков ЮМ 1998 в Берлине.

Результаты диссертации опубликованы в работах [26 - 49]. Диссертант приносит искреннюю благодарность академику Э.Й. Вилкасу, доктору физико-математических наук В.Б. Бистрицкасу, доктору физико-математических наук И.П. Ячяускасу за постановку задачи, постоянное внимание к работе и плодотворные обсуждения.

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

ЛИТЕРАТУРА

1. Ащепков Л.Т. Методы оптимизации и их приложения. Новосибирск: Наука. Сиб. отд-ние, 1990.

2. Беллман Р. Динамическое программирование. М.: ИЛ, 1960.

3. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

4. Болтянский В.Г. Оптимальное управление дискретными системами. М.: Наука, 1973.

5. Бистрицкас В. Дифференциальная форма линейных выпуклых дискретных процессов управления // Кибернетика. 1979. No. 3. С.48 - 52.

6. Бистрицкас В. Приближенное решение задачи оптимизации дискретного управления // Liet. matem. rink. 1988. T. 28, No. 1. С.23 - 32. ISSN 0132 - 2818.

7. Бистрицкас В. Смешанные задачи календарного программирования // Liet. matem. rink. 1990. T. 30, No.4 С. 651 -665.

8. Бистрицкас В. General Mixed Solutions of Discrete Control Processes // Liet. matem. rink. 1992. T. 32, No. 1.

9. Биттнер Л. Ein Model fur eine Klasse von Aufgaben optimaler Steuerung // Zamm 58. 1978. C. 251 - 260.

10. Виттвер Г. Оптимальное управление запасами при частичном возврате // Теория вероятностей и её применения. М.: Наука, 1971, T. XVI, вып. 3. С. 514-523.

11. Габасов Р. Об оптимальности особых управлений // Дифференц. уравнения. 1968. Т. 4, No. 6. С. 1000- 1011.

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

13. Габасов Р., Кириллова Ф.М. Оптимизация линейных систем. Минск: Изд-во Белорус, ун-та, 1973.

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

15. Габасов Р., Кириллова Ф.М. Принцип максимума в теории оптимального управления. Минск: Наука и техника, 1974.

16. Габасов Р., Кириллова Ф.М., Мансимов К.Б. Необходимые условия оптимальности второго порядка (обзор) // Минск, 1982. (Препринт / Ин-т математики АН БССР. No. 30 (155)).

17. Крылов И.А., Черноусько Ф.Л. Алгоритм метода последовательных приближений для задачи оптимального управления //Ж. вычисл. матем. и матем. физ. 1972. T. Il, No. I.

18. Любушин A.A. Модификации и исследование сходимости метода последовательных приближений для задач оптимального управления // Ж. вычисл. матем. и матем. физ. 1979. Т. 19, No. 6.

19. Михалевич B.C. Методы решения сложных задач математического программирования. Киев, 1985.

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

21. Полак Э. Численные методы оптимизации. Единый подход. М.: Мир, 1974.

22. Пропой А.И. Элементы теории оптимальных дискретных процессов. М.: Наука, 1973.

23. Руткаускас П., Бистрицкас В. Непрерывный аналог процесса распределения динамического программирования // Liet. matem. rink. 1972. Т. XII, No. 2. С. 133 - 140.

24. Руткаускас П., Бистрицкас В. Оптимальный непрерывный аналог процесса распределения динамического программирования // Математические методы в социальных науках. Вильнюс, 1976. Вып. 8. С. 9 - 21.

25. Руткаускас П., Шмидт В. Условия оптимальности для дискретных и непрерывных процессов управления с запаздыванием // Liet. matem. rink. 1983. Т. 23, No. 3. С. 117 -126.

26. Шимялене Р.-Н. Принцип максимума для дискретной задачи управления запасами при частичном возврате // Республиканская конференция "Применение теории вероятностей и математической статистики". Вильнюс, 1979. С. 12.

27. Шимялене P.-H. Метод дополнительных шагов для итерационных процессов // Liet. matem. rink. 1983. T. 23, No. 4. С. 144 - 146.

28. Шимялене P.-H., Бистрицкас В. О связи решений стохастических уравнений динамического программирования с задачами оптимизации систем дискретного управления // XXIV конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1983. С. 30-31.

29. Шимялене Р.-Н. Оптимизация итерационного процесса решения системы уравнений // XXV конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1984. С. 304 - 305.

30. Шимялене Р.-Н., Бистрицкас В., Пашис Р. Дискретные процессы оптимального управления с запаздыванием по управлению. Применение математических методов в народном хозяйстве республики. Материалы республиканской конференции. Вильнюс, 1984. С. 185-191.

31. Шимялене Р.-Н. Непрерывный аналог задачи оптимизации итерационного процесса решения систем уравнений // XXVI конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1985. С. 293 - 294.

32. Шимялене Р.-Н. Динамическое программирование в оптимизации итерационного процесса Полака для решения системы нелинейных уравнений // XXVII конференция

Литовского математического общества. Тезисы докладов. II. Вильнюс, 1986. С. 147- 148.

33. Шимялене Р.-Н. Трихотомическая задача оптимизации итерационного процесса решения систем уравнений // XXIX конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1988. С. 208-209.

34. Шимялене Р.-Н. Приложение оптимального управления при решении систем уравнений // Всесоюзная школа "Оптимальное управление. Геометрия и анализ". Тезисы докладов. Кемерово, 1988. С. 113.

35. Шимялене Р.-Н. Оптимизация итерационного процесса решения системы уравнений // Liet. matem. rink. 1989. Т. 29, No. 3. С. 608 - 614.

36. Шимялене Р.-Н. Смешанное и чистое решения квадратичных -билинейных задач дискретного оптимального управления // XXX конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1989. С. 199-200.

37. Шимялене Р.-Н. Смешанная задача для квадратичной задачи оптимального управления // XXXI конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1990. С. 143 - 144.

38. Шимялене Р.-Н. Выпуклость по начальным значениям сопряженных переменных минимума критерия качества // III Всесоюзная школа "Понтрягинские чтения". Оптимальное

управление. Геометрия и анализ". Тезисы докладов. Кемерово, 1990. С. 220.

39. Шимялене Р.-Н. Maximum Principle for the Quadratic Discrete Optimal Control Problem // XXXII конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1991. С. 112 - 113.

40. Шимялене Р.-Н., Бистрицкас В., Пашис Р., Гурклис P. Maximum Principle for the Discrete Calendar Programming // XXXII конференция Литовского математического общества. Тезисы докладов. Вильнюс, 1991. С. 110-111.

41. Simeliene N., Bistrickas V. Mixed Solutions of Discrete Control Processes // 14th International Symposium on Mathematical Programming. Program & Abstracts. Amsterdam, 1991.

42. Simeliene N. Maximum Principle Algorithms // Combinatorial Optimization Conference C092. Wadham College, University of Oxford. C092 Abstracts. Oxford, 1992.

43. Simeliene N. Maximum Principle Algorithms for the Discrete Optimal Control Problems // XIII World Conference on Operations Research IFORS 93. Theme-OR: Expanding Horizons. Sessions and Abstracts. Lisbon, 1993.

44. Simeliene N. Convexity for the Quadratic Control Problem // Combinatorial Optimization Conference C094. Program & Abstracts. Amsterdam, 1994.

45. Simeliene N., Bistrickas V. Analytical Solutions in the Calculate Algorithms of Discrete Multistage Optimization // International Conference of Operations Research. Program and Abstracts. Berlin, 1994.

46. Simeliene N., Bistrickas V. Algorithms of Inventory Problems // The Third International Congress on Industrial and Applied Mathematics ICIAM 95. Book of Abstracts. Hamburg, 1995.

47. Simeliene N., Bistrickas V. Mixed Control Approximations of Inventory Processes // GAMM 97. Final Programme. Regensburg, 1997.

48. Simeliene N., Bistrickas V. Fundamental Models for the Inventory Control Problems // GAMM 98. Book of Abstracts. Bremen, 1998.

49. Simeliene N., Bistrickas V. Fundamental Models for Several Levels Inventory Control Processes // International Congress of Mathematicians ICM 1998. Abstracts of Short Communications and Poster Sessions. Berlin, 1998.

50. Шмидт В., Бистрицкас В. Условия оптимальности дискретного интегрального процесса управления с выбором моментов времени и их приложения // Применение математических методов в народном хозяйстве республики. Материалы Республиканской конференции. Вильнюс, 1984. С. 192-201.

51. Schmidt W. Maximum Principles for Processes Governed by Integral Equations in Banach Spaces as Sufficient Optimality Conditions // Beitrage zur Analysis. 1981. B. 17. C. 85 - 93.

52. Schmidt W. Necessary Optimality Conditions for Discrete Integral Processes in Banach Spaces 11 Preprint - Reihe MathematiK. Greifswald, 1979. No. 4. C. 15 - 24.

53. Хэдли Дж. Нелинейное и динамическое программирование. М.: Мир, 1967.