Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2003
Автор:	Лиховид, А.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2003
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/84860
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 91-96. — Бібліогр.: 4 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84860
record_format	dspace
spelling	irk-123456789-848602018-03-24T11:38:03Z Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем Лиховид, А.П. Рассматривается исследование эффективности применения r-алгоритмов при решении некоторых практически важных задач оптимального управления с дискретным временем. Приведены результаты вычислительных экспериментов для тестовых задач с использованием различных модификаций r-алгоритма. Розглядається дослідження ефективності застосування r-алгоритмів при розв'язуванні деяких практично важливих задач оптимального керування з дискретним часом. Наведені результати обчислювальних експериментів для тестових задач з використанням різних модифікацій r-алгоритму. The investigation of efficiency of r-algorithms for solution of some practically important optimal control problems with discrete time is considered. The computational results for test problems with usage of various modifications of r-algorithm are given. 2003 Article Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 91-96. — Бібліогр.: 4 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84860 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается исследование эффективности применения r-алгоритмов при решении некоторых практически важных задач оптимального управления с дискретным временем. Приведены результаты вычислительных экспериментов для тестовых задач с использованием различных модификаций r-алгоритма.
format	Article
author	Лиховид, А.П.
spellingShingle	Лиховид, А.П. Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем Теорія оптимальних рішень
author_facet	Лиховид, А.П.
author_sort	Лиховид, А.П.
title	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
title_short	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
title_full	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
title_fullStr	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
title_full_unstemmed	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
title_sort	применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2003
url	http://dspace.nbuv.gov.ua/handle/123456789/84860
citation_txt	Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 91-96. — Бібліогр.: 4 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT lihovidap primenenieralgoritmovdlârešeniânekotoryhzadačoptimalʹnogoupravleniâsdiskretnymvremenem
first_indexed	2025-07-06T11:59:05Z
last_indexed	2025-07-06T11:59:05Z
_version_	1836898735767945216
fulltext	91 Теорія оптимальних рішень. 2003, № 2 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается исследование эффективности применения r- алгоритмов при решении некото- рых практически важных задач оптимального управления с дис- кретным временем. Приведены результа-ты вычислительных экс- периментов для тестовых задач с использованием различных моди- фикаций r-алгоритма.  А.П. Лиховид, 2003 ÓÄÊ 519.8 À.Ï. ËÈÕÎÂÈÄ ÏÐÈÌÅÍÅÍÈÅ R-ÀËÃÎÐÈÒÌÎÂ ÄËß ÐÅØÅÍÈß ÍÅÊÎÒÎÐÛÕ ÇÀÄÀ× ÎÏÒÈÌÀËÜÍÎÃÎ ÓÏÐÀÂËÅÍÈß Ñ ÄÈÑÊÐÅÒÍÛÌ ÂÐÅÌÅÍÅÌ∗∗∗∗ Как известно, методы недифферен-цируемой оптимизации на основе r -алгоритмов нашли широкое применение при решении разнооб- разных задач математического программиро- вания (см., например, [1]). Ниже рассматри- вается решение с помощью r -алгоритма не- которых практически важных задач опти- мального управления с дискретным време- нем. Постановка задачи. Предположим, что динамический процесс на временном интер- вале от 0 до T может быть представлен как многошаговый, т.е. этот интервал может быть разбит на n последовательных шагов длительности которых примем равными 1,...,0, −=∆ nktk . Пусть в евклидовом пространстве 2 R (ре- зультаты легко обобщаются и на случай про- странства большей размерности) имеется материальная точка массы 1=m , динамика которой описывается следующими разност- ными уравнениями: ,1,...,0 , 2 2 1 −= ∆ +∆+=+ nk tu tvxx kk kkkk (1) .1,...,0 ,1 −= ∆+=+ nk tuvv kkkk (2) ∗ Работа выполнена при частичной финансовой поддержке Украинского научно-технологического центра (грант №1625). ПРИМЕНЕНИЕ R-АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ОПТИМАЛЬНОГО … Теорія оптимальних рішень. 2003, № 2 92 Здесь вектор ),( 21 kkk xxx = имеет значение координат точки после 1−k -го шага, вектор ),( 21 kkk vvv = является вектором скорости после 1−k -го шага, вектор ),( 21 kkk uuu = – искомое управление на k -м шаге. Допустимые управ- ления – произвольные значения в шаре с заданным радиусом r , т.е. 22 ruk ≤ . Пусть заданы начальное и конечное состояния объекта, т.е. значения векто- ров 00 xx = , nn xx = и 00 vv = , nn vv = . Будем рассматривать следующую по- становку оптимизационной задачи: используя допустимые управления необхо- димо перевести объект за n шагов из начального состояния 00 , vx в заданное конечное состояние nx , nv с учетом минимизации критерия суммарной эконо- мии топлива, который можно принять пропорциональным значениям 2 ku (здесь ⋅ – евклидова норма). Предположим для простоты, что 0=nx , 0=nv , 1=r и 1,...,0,1 −==∆ nktk . Тогда вышеописанную задачу можно представить в сле- дующем виде: найти управления 1,...,0, −= nkuk , которые минимизируют це- левую функцию ∑ − = = 1 0 2 n k kuf (3) при ограничениях ,1,...,0,, 2 2 1 −=∈++=+ nkRx u vxx k k kkk (4) ,1,...,0,,, 22 1 −=∈∈+=+ nkRuRvuvv kkkkk (5) ,1,...,0,1 2 −=≤ nkuk (6) ,00 xx = (7) ,00 vv = (8) ,0=nx (9) .0=nv (10) Для учета ограничений (6) и (9)–(10) будем применять метод негладких штрафных функций. Тогда задачу (3)–(10) можно представить в следующем виде: ПРИМЕНЕНИЕ R-АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ОПТИМАЛЬНОГО … Теорія оптимальних рішень. 2003, № 2 93 }1,0{max 2 2 1 2 1 1 0 2 −ρ+ρ+ρ+= ∑∑∑ == − = k k u i niv i nix n k k uvxuf (11) при ограничениях ,1,...,0,, 2 2 1 −=∈++=+ nkRx u vxx k k kkk (12) ,1,...,0,,, 22 1 −=∈∈+=+ nkRuRvuvv kkkkk (13) ,00 xx = (14) .00 vv = (15) где 0,0,0 >ρ>ρ>ρ uvx – штрафные коэффициенты. Как легко заметить, целевая функция (11) зависит от состояния объекта в конце процесса, которое в свою очередь зависит от начального состояния, и примененных на каждом шаге управлений. Задача (11)–(15) является задачей недифференцируемой оптимизации. Для ее решения можно использовать алго- ритмы субградиентного типа, в частности различные модификации r-алгоритма [1, 2]. Аналогично можно рассматривать и другие модели, например, оптимальные по времени, с ограничением по скорости и т.п. Результаты вычислительных экспериментов. Для сравнения были выбра- ны r-алгоритм с адаптивной регулировкой шага [1], монотонная модификация r -алгоритма [2] и известный пакет LOQO [3]. Эксперименты проводились на персональном компьютере IBM PC/Pentium III/750МГц/256Мгб/Windows98. Ис- следовательские программы были реализованы на языке программирования С++. Для пакета LOQO, который решал задачу в виде квадратичной модели, входные данные готовились на языке AMPL [4]. В качестве метода поиска ми- нимума по направлению для монотонного алгоритма использовался алгоритм половинного деления. Счет монотонного r-алгоритма прекращался при выпол- нении условия 16 1 10)( − + ≤kf T k xgB , а r-алгоритма с адаптивной регулировкой шага – при выполнении 6 1 10− + ≤− kk xx (здесь k – номер итерации). Коэффи- циент растяжения α для обеих модификаций r-алгоритма полагался равным 2. В тестовых примерах значения всех штрафных коэффициентов были равны 1000. Ниже приводятся результаты вычислительных экспериментов для двух тес- товых примеров. В табл. 1 и 4 представлены сравнительные результаты для раз- личных алгоритмов полученного значения функции и времени решения, а в А.П. ЛИХОВИД 94 Теорія оптимальних рішень. 2003, № 2 табл. 2–3 и 5 приводятся полученные монотонным r-алгоритмом решения для некоторых задач. Пример 1. 1),0,0(),0,1( 00 === rvx . ТАБЛИЦА 1. Решение тестовых задач для примера 1 при различных n n r-алгоритм с адаптивной регулировкой шага Монотонный r-алгоритм LOQO * f t,c * f t,с * f t,с 2 2.0017744 0.01 2.0000000 0.05 1.9999999 0.01 9 0.0166666 0.06 0.0166666 0.06 0.0166666 0.02 19 0.0017543 0.16 0.0017543 0.22 0.0017543 0.11 29 0.0004926 0.28 0.0004926 0.44 0.0004926 0.22 ТАБЛИЦА 2. Полученное решение для примера 1 при n=2 k ku kx kv 0 -1 1 0 1 1 0.5 -1 2 – 5.59275e-013 -1.97331e-012 ТАБЛИЦА 3. Полученное решение для примера 1 при n=9 k ku kx kv 0 -0.0666667 1 0 1 -0.05 0.966667 -0.0666667 2 -0.0333333 0.875 -0.116667 3 -0.0166667 0.741667 -0.15 4 -2.50272e-010 0.583333 -0.166667 5 0.0166667 0.416667 -0.166667 6 0.0333333 0.258333 -0.15 7 0.05 0.125 -0.116667 8 0.0666667 0.0333333 -0.0666667 9 – -1.52656e-016 -2.77556e-017 ПРИМЕНЕНИЕ R-АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ОПТИМАЛЬНОГО … Теорія оптимальних рішень. 2003, № 2 95 Пример 2. 10),10,10(),100,100( 00 =−−== rvx . ТАБЛИЦА 4. Решение тестовых задач для примера 2 при различных n n r-алгоритм с адаптивной регулировкой шага Монотонный r-алгоритм LOQO * f t,c * f t,с * f t,с 9 184.5833333 0.05 184.5833333 0.11 184.5833334 0.05 19 15.9210526 0.11 15.9210526 0.21 15.9210523 0.16 29 13.3374384 0.16 13.3374384 0.33 13.3374384 0.27 ТАБЛИЦА 5. Полученное решение для примера 2 при n=9 k 1ku 1kx 1kv 2ku 2kx 2kv 0 -2.555 100 -10 -2.55556 100 -10 1 -1.6388 88.7222 -12.555 -1.63889 88.7222 -12.5556 2 -0.7222 75.3472 -14.194 -0.72222 75.3472 -14.1944 3 0.1944 60.7917 -14.9167 0.194444 60.7917 -14.9167 4 1.1111 45.9722 -14.7222 1.11111 45.9722 -14.7222 5 2.0277 31.8056 -13.6111 2.02778 31.8056 -13.6111 6 2.9444 19.2083 -11.5833 2.94445 19.2083 -11.5833 7 3.8611 9.09722 -8.63889 3.86111 9.09722 -8.63889 8 4.7777 2.38889 -4.77778 4.77778 2.38889 -4.77778 9 – 9.76e-015 0 – -3.55e-014 -1.77e-015 Обе модификации r-алгоритма нашли оптимальное решение для всех тесто- вых задач с высокой точностью, при этом время решения сравнимо с получен- ным для пакета LOQO. Результаты расчетов показывают, что для решения оп- тимизационных задач управления с дискретным временем можно эффективно использовать различные варианты r-алгоритма. О.П. Лиховид ВИКОРИСТАННЯ R-АЛГОРИТМІВ ДЛЯ РОЗВ'ЯЗУВАННЯ ДЕЯКИХ ЗАДАЧ ОПТИМАЛЬНОГО КЕРУВАННЯ З ДИСКРЕТНИМ ЧАСОМ Розглядається дослідження ефективності застосування r-алгоритмів при розв'язуванні де- яких практично важливих задач оптимального керування з дискретним часом. Наведені ре- зультати обчислювальних експериментів для тестових задач з використанням різних мо- дифікацій r-алгоритму. А.П. ЛИХОВИД 96 Теорія оптимальних рішень. 2003, № 2 O.P. Lykhovyd USING R-ALGORITHMS FOR SOLUTION OF SOME OPTIMAL CONTROL PROBLEMS WITH DISCRETE TIMES The investigation of efficiency of r-algorithms for solution of some practically important optim- al control problems with discrete time is considered. The computational results for test problems with usage of various modifications of r-algorithm are given. 1. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Boston-Dordrecht- London: Kluwer Acad. Publ., 1998. – 412 p. 2. Шор Н.З. Монотонные модификации r-алгоритмов и их приложения // Кибернетика и системный анализ. – 2002. – № 6. – C. 74-96. 3. Vanderbei R.J. LOQO: An interior point code for quadratic programming // Technical Report SOR-94-15, School of Engineering and Applied Science, Department of Civil Engineering and Operations Research, Princeton University. – 1994. – 198 p. 4. Fourer R., Gay D., Kernighan B. AMPL: A Modeling Language for Mathematical Program- ming. Duxbury Press-Brooks-Cole Publishing Company. – 1993. – 351 p. Получено 19.09.2003

Применение r-алгоритмов для решения некоторых задач оптимального управления с дискретным временем

Репозитарії

Схожі ресурси