И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 87
Текст из файла (страница 87)
Найти линейную оценку В с минимальным уклонением для функции В(В, Н) ЬУ,(р У+Угйи) у и управляемой системы ВА«х» + В»х» + ОС»х»+~ + )9х»+1 + 1«(и) + дь (р) = 0 6=1, 2, ..., У, ... с наблюдаемыми значениями хо 1,(и), х„1»(и), ... 477 где матрица В (развязывающий оператор) определяется приравниванием правых частей (6.33) и (6.29) при условиях (6.31) и (6.32). Теорема 7. Если существует обратная матрица (б.ЗО), то управление и Д, й, с) является оптимальным решением и* задачи 7 и при этом в случае неизвестных элементов д ~ н Ь матриц 6 и Н соответственно при (1' Е У, и 11 Е Г!» и при неизвестном параметре р, принадлежащем заданному множеству Р.
Алгоритм У, 1. Вычисляем решение у системы ~, ~ у»!а»!»х»! = — р!г, (1Е Я'м (в.зв) определяющее развязывающий оператор для В в виде В(б, Н) = 2 (у, х, ((и)) + ~, Е у»д! (р), Й(у, х, 1(и)щ ~ ~у' (ч»(и)+ ~;(йю~х)~, +фхе) + + ~~ ~у!! рг! + ~ у! ~~ ~а!бхб 1 '~~~ й!! у/ 1 ~ у! ~ е!бхб и удовлетворяющее условию б! (р, у, Е) = аги ш(п гпах)г (р, у, Е) 1, г (р, у, Е),(.'» 1. + ~, ~ у»д!» (р). ь»ег»ег »=! ! (в.зт) И. Вычисляем оценку В в виде В(у, Е, х, ((и)) = В(у, х, 1(и)) — Ь с минимальным на г' уклонением ~ г (р, у, С) ). Теорема 8. В(0, Н) — В(у, 1., х, 1(и))+ Ь =г(р, у, 1,).
(в зз) 3 а д а ч а 10 (задача наблюдения и гарантированного (минимаксного) управления). Пусть х» Ь (хм х„..., х„), и» Ь (и„и», ... ...,и!),г»Й(г»,гм ..., г») и управляемая система описывается уравнениями А» (х», й», г», р) = О, й = 1, 2, ..., (6.39) где р — вектор неизвестных параметров системы, г, — вектор наблюдений на е-м этапе, удовлетворяющий равенствам С» (х», и», г», р) = О, й = 1, 2, ..., а и» вЂ” вектор управляющих воздействий (управлений). Требуется найти гарантирующее управление и» ~ и„(Р„г») ~ агд т! и гпах В (хч, (й»! г», р), ии, г», р) (вАо) ИААФ»ЕР» с помощью множеств Р,Ь(р(Р,(р)(а„зРЗ(Р„,)) Д Р»,, где а, = ( шах Р,(р)~ С7(х;, и,, г;, р) = О, 1 = 1, 2, ..., й). (в.44> »Ее» вЂ” 1 Замечание. Множества 5 (Р» ~), как и функции Р., обычно выбирают на Ьм этапе неформальными методами, преследуя при этом несколько противоречивые требования: уменьшить, с одной стороны, трудоемкость решения вспомогательных задач (6.40) и (6.4!), а с другой — обеспечитыэффективное» сужение множества неопределенности Р, содержащего неизвестный параметр р.
В качестве функций Р, часто удобно выбирать линейные функции. Для решения сформулированных (под) задач (6.40) и (6.41) можно использовать описанные выше алгоритмы максиминной оптимизации. В частности, для управляемой системы (6.28) и функционала (6.29) при 7" = 7" (р), й = й (р) и с = с (р) для решения задачи (6.40) можно использовать алгоритм 10. Алгоритм Ш Вычисляем матрицы Уы У», У„В с помощью алгоритма 7 и согласно (6.31) вычисляем решение задачи (6.40) по формуле и„(Р„, г») = Щ(р )+ У~И(р*) + У,с(р*), р» = ага шах В Й(Р), Й(Р) В общем случае для решения задачи (6.40) можно использовать методы асимптотически развязывающих операторов, которые основаны на локальной аппроксимации развязывающего оператора в окрестности заданной точки и функцией В - (асимптотически з,и развязывающим оператором в-го порядка), удовлетворяющей условию В, „" (и, г, ) = В(х„(и, г, ), и, г, р) + о (р* (и, и)), (р — метрика в пространстве управлений).
Алгоритм 11. 1. Выбираем д = 1, произвольные числа а„а,) О, а„а» ~ О, произвольный элемент и, р Ф. 11. Выбираем некоторую реализуемую аппроксимацию В„ о6 [1,в), функции В- и вычисляем элемента+1 ЕФ по формуле ьи ихы = агн ппп В,(и), »ае(»»»»! 479 где Е (Л,, и,) Ь (и ( р (и, и,) Е [Л„и»Л,), и Е Ф), Л, = 2™а,Л~ ы й! — минимальное натуральное число, удовлетво. ряющее неравенству В (хи (и,+ь ги), и,+и ги, р) ~ ~~ В(хи(и„гл), и, ги, р) — аЯ~'.
Теорема 9. Если Чи сФ В(хи(и, ги), и, ги) ~и») — оо, (В (и, ги) — В " (и, ги)(<а,ро(и, и), тодлялюбогое )Оза конечное число итераций д = д (е р сс» ач) будет вычислено е-экстремальное решение и, р-го порядка (элемент и, Е Ф называем з-экстремальным решением )»-го порядка для задачи (6АО), если не существует ветви роста р-го порядка, т. е. последовательности (и;),"=, Е Ф, удовлетворяющей условиям и;чьие, р(и;, и,) — ~0, ~' лир'(ир и»)~ври(ир и,), о ~л чф — и (ир и ) — О, и» = В(хл (и„ги), и„гл)— 1-Π— В(хи(и,, ги), ип ги)).
Способ вычисления требуемой функции В - для весьма общеьи го случая В (х, и, г) = В!у (В (х, и, г)) (В = (В„..., Вс), В!у: К~ -»- К' — заданная функция с логическими операциями, включая операции шах и ппп) дает теорема 10. Теорема 10. Если для А»~ ~ д„,А», с(с» д„,В, в точке (х (и, ги), и, ги) решение у (А, с') (с' ~ (сы ..., си)) системы (6.22) един- ственно и функции Аю В„д,,А», д,,В, непрерывны по х, и, то (и, ги) = В!у (В (и, ги)), еде и В,(и, ги) йВ,(х(и„ги), и, ги) (- ~, (у,(А, с'), А,(х(и„ги), и, ги)). » 1 Основные трудности реализации алгоритма 11 часто связаны с трудностями вычисления значений В (хи (и„ги), и, ги) для за- данных управлений и„. В таких случаях можно эффективно исполь- зовать метод разеязываюи4ей декомпозиции для упрощения матема- тической модели А (х, и) = 0 с помощью выбора таких функций А„А„А», А(х, и) =(А,(х„А,(х, и), и), А»(х, и)), х~~,(х„х»), 480 для которых упрощается решение задачи х, (о, и) = агд [А, (з, г о, и) = О!.
Это дает возможность искать иа как решение задачи минимизации функции В,(х„о, и)со В(х, и, х) + КД]о — А,(х, и)]]+ Кв]]Аа(х, и)]], Кт Ка6 В+ при упрощенных связях А, (х„о, и) = 0 (или вычислять ха (и) решением вспомогательной задачи (х,(и), о) = агя(А,(х,(и), х„и) = о, Аа(х,(и), х„и) = О)). Библиографические указания. При написании параграфа использованы результаты работ [22 — 26], [39 — 41], (135]. СПИСОК ЛИТЕРАТУРЫ 1. Абрамов А.
Н., Иванилов Ю. Н. Алгоритм решения задачи линейного программирования методом нагруженного функционала.— Журн, зычисл. математики н мат. физики, 1977, № 1, т. 17, с. 259 — 262. 2. Айда-Заде К. Р., Махмуд-Заде Р. Н., Новрузбехов И. Г. Метод полярных ко. ординат минимизации функций овражной структуры.— В кнл Численные мо годы нелинейного программирования: Тез. П Всесоюз. семинара. Харьков, 28 мая — 3 июня 1976 г. Харьков: Внща школа. Изд-во прн Харьк.
ун-те, 1976, с. 30 — 32. 3. Аймрман М. А., Браверман 3. М., Роэоноэр Л. И. Метод потенциальных функций в теории обучения машин.— М.: Наука, 1970.— 384 с. 4. Алгоритмы и программы случайного поиска / Под ред. Л. А. Растригина.— Рига: Зинатне, 1969.— 374 с. 5. Амвросиенхо В. В. Ускорение сходимости метода Брауна решения матрич. ных игр.— Экономика и мат. методы, 1965, т.
1, № 4, с. 570 — 575. 6. Антонов Г. Е., Катховних В. Я. Метод синтеза одного класса алгоритмов случайного поиска. — Автоматика и телемеханика, 1971, № 6, с. 154— 157. 7. Антонин А. С. О методе выпуклого программирования, использующем симметрическую модификацию функции Лагранжа.— Экономика и мат. методы, 1976, т. 12, № 6, с. 1164 — 1173. 8. Арбузова Н. И., Вересков А.'Н., Николаева Н, Д.
Некоторые задачи стохастического программирования (обзорК вЂ” Экономика и мат, методы, 1969, т. 5, № 3, с. 412 — 430. 9. Афанасьев А. Ю. О поиске минимума функции с ограниченной второй производной.— Журн. вычисл. математики и мат. физики, 1974, т. 14, № 4, с. 1018 †10. 1О.
Афанасьев А. Ю., Новиков В. А. О поиске минимума функции о ограниченной третьей производной. — Журн. вычисл.математики и мат. физики, 1977, т. 17, Ит 4, е. 1031 — 1034. 11. Ахметов П. А.. Малков У. Х. Повышение зффективностн мультипликативного алгоритма симплекс-метода при решении больших задач линейного програм- мнрованиянвЭВМ.— Экономика имат.
методы, 1970, т. б, вып, 3, с. 422— 426. 12. Бабич М. Д., Иванов В. В. Исследование полной погрешности в задачах мини. мизацин функционалов при наличии ограничений.— Укр. мат. журн., 1969, т. 21, № 1, е. 3 — 14. 13. Баженов Л. Г, Об условиях сходимости метода минимизации почти днфференцируемых функций.— Кибернетика, 1972, № 4, е. 71 — 72.
14. Баженов Л. Г., Гунал А. М. Об одном стохаотнчевком аналоге метода возмож. ных направлений.— Кибернетика, 1973, № 4, с. 94 — 95. 15. Баничуя Н. В., Петров В. М., Черноусьхо Ф. Л. Численное решение варнационных н краевых задач методом локальных вариапий.— Журн. вычнсл. математики н мат. физики, 1966, т. 6, № 6, с. 947 — 961. 16. Бартиш М. Я. Возмущенные аналоги методов типа Ньютона — Канторовича. Матем. сб.— Киев: Наук. думка, 1976, е. 59 — 62. 17.
Батии1вв Д. И. Поисковые методы оптимального проектирования.— М. з Сов. радио, 1975.— 216 с. 482 !8. Батищее Д. И., Бедная Р. И., Стролгил Р. Г. О выборе параметров алгоритмов поисковой оптимизации.— Автоматика н вычисл. технкка, 1972, № 4, с. 56 — 60. 19. Бахвалов Н. С. О свойствах оптимальных методов решения задач математической физики.— )Кури. вычисл. математики и мат. физики, 1970, т. 1О, № 3, с.
555 — 568. 20. Бахтин А. Е. Блочный способ решения задач линейного программирова. ния.— В кн.: Математические методы решения экономических задач. Ново. снбирск: Наука, 1971, с. 63 — 78. 21. Бахшин А. Е., Волков БХ И. Метод последовательного улучшения плана для решения одного класса задач линейного программирования.— Экономика и мат, методы, 1967, т. 3, вып. 4, с. 581 — 587. 22. Бейко И. В. Применение развязывающих операторов для решения задачи Ко. ши и построения экстремальных алгоритмов развязывающей декомпозиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
