Численное решение задачи оптимизации управления




Предположим, что функционал (6) обладает особенностями: 1) имеет только один ми-нимум (локальный, он же и абсолютный) на интервале определения k; 2) может не удовлет-ворять требованиям непрерывности и существования производной на интервале определения k. Функции, удовлетворяющие этим требованиям, называются унимодальными. Поиск мини-мума унимодальных функций может проводиться методом перебора, методом дихотомии, методом золотого сечения и методом чисел Фибоначчи [4]. Методы перечислены в порядке увеличения эффективности поиска. Таким образом, метод чисел Фибоначчи является са-мым эффективным. Поэтому поиск минимума функционала (6) будем проводить этим мето-дом.

Реализация метода связана с использованием последовательности целых чисел, откры-той итальянским математиком Леонардом Пизанским (Фибоначчи) в на­чале XIII века. Обоз-начим унимодальную целевую функцию через z = z (x). Необходимо найти точку х * при кото-рой целевая функция z имеет минимум: z *= z (x *)= z (x). При этом считаем, что х лежит в интервале [0, 1], поскольку любой другой интервал легко приводится к интервалу [0, 1].

Чтобы проследить за ходом развития схемы поиска х *, z *, предположим, что в нашем распо­ряжении имеется N экспериментов. Оценим ситуацию, которая возникает после того, как проведён N –1 эксперимент и остаётся выбрать последнее значе­ние х=xN. К этому момен-ту гарантированная длина интервала неопределённости становится равной LN –1, а сам интер-вал содержит точку хN –1 (рис.3), причём среди всех величин zq (q = ), полученных в пред­шествующих экспериментах, наибольшей является имен­но zN –1. Положение хN –1 на отре-зке LN –1 зависит от то­го, какой метод поиска была реализована на предыдущих шагах.

Длина конечного интервала неопределенности будет определяться не только выбирае-мым хN, но и уже имею­щимся хN –1. Очевидно, результат поиска окажется наи­лучшим тогда, когда хN –1 распо­ложится на расстоянии ε/2 от середины LN –1 (рис.3) (в этом случае достаточ-но разместить точку хN симме­трично хN –1 и найти LN =(LN –1+ε)/2 независимо от того, в каком отношении находятся zN и zN –1). Таким образом, первым требованием к исследуемой схеме явля­ется следующее: после проведения N –1 экспериментов точка хN –1 должна занять на LN –1 положение, указан­ное на рис.3.

       
 
   
 

 


Рис.3. Рис.4.

LN –1
LN –2
LN
xN
ε
xN –2
LN
Рис.5.
xN –1
xN –1
Пусть теперь стоит задача выбора двух последних значений х (xN –1 и xN) в условиях, когда N –2 экспе­римента проведены и найден интер­вал LN –2 , содержащий точку xN –2 , в кото-рой получено значение z=zN –2 , наилучшее (по смыслу задачи) в рассматриваемой серии опы-тов (рис.4). Начнём выбирать xN –1 (вну­три LN –2); как только xN –1 и соот­ветствующее zN –1 станут известны, можно будет указать новый интер­вал неопределённости, меньший LN –2. Поскольку заранее нельзя предсказать, будет ли zN –1> zN –2, лучше всего расположить точку xN –1 симметрично xN –2 несмотря на то,что рас-

стояние между xN –1 и xN –2 окажется наверняка боль­ше ε. Предложенный выбор xN –1 даёт гара-нтию того, что длина нового интервала неопределённости не превы­сит величины LN –1, отме-ченной на рис.4, причем LN –1 не может быть уменьшена, если задана точка xN –2. Зная теперь xN –1 и помня о требовании, отражённом в рис.3, при­ходим к выводу: чтобы получить резуль-тат LN –1, необхо­димо два последних эксперимента провести так, как по­казано на рис.5, вы-полнив тем самым условие: LN –2 = LN –1+ LN.

LN –3
Таблица 1.

LN –2
xN –2
xN –3
Номер

шага поиска q

Формула для интервала неопределённости Lq

LN –1
ε
xN –1
xN
LN –2
xN –2
xN –1
N

N –1

N –2

N –3

N –4

N –5

LN = LN LN –1 = 2 LN – ε LN –2 = 3 LN – ε LN –3 = 5 LN – 2ε LN –4 = 8 LN – 3ε LN –5 = 13 LN – 5ε ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙

LN –1
LN

Lq = FN q +1 LN FN q –1ε

Если сделать очередной шаг и поставить задачу: найти xN –2, xN –1, xN при известных LN –3, xN –3, zN –3, то окаже-тся, что рассуждения, приведенные выше, могут быть це-ликом перенесены и на этот случай. Таким обра­зом, при-ходим к равенству LN –3 = LN –2 + LN –1; далее схе­ма строится так, как показано на рис.6.

Теперь ясно, что основное соотношение, характери­зующее метод, имеет вид

L q –1= L q + L q +1 (q = ). (16)

Его анализ удобно начать с конкретизации выражений Lq (q = N, N— 1,...), сведя их в табл.1. Нетрудно заметить, что коэффициенты при LN и ε в формулах таблицы составляют последо-вательность чи­сел Фибоначчи (табл.2), задаваемую равенствами F 0= F 1=1, Fk = Fk –1+ Fk –2, где k— номер числа Фибоначчи, принимающий значения 2, 3, …. Используя это обстоятельство, можно дать общую запись выражения Lq, приведённую в ниж­ней строке табл.1, откуда сле-дует L 1 =FN LNFN –2 ε. Но L 1 есть исходный единичный интервал неопределён­ности (L 1=1), поэтому [4]

LN = (l + ε FN –2 ) / FN. (17)

Таблица 2. Числа Фибоначчи.

Число Фибоначчи Fk                          
Номер числа Фиб. k                          
Число Фибоначчи Fk               10 946  
Номер числа Фиб. k                  
                                           

Соотношение (17) позволяет оценить эффективность метода чисел Фибоначчи. Боль-шая эффективность метода чисел Фибоначчи связана с тем, что сокращение длины очередно-го интервала Lq требует проведения одного нового эксперимента, тогда как, например, в схе-ме дихотомии их требуется два.

Длина конечного интервала неопределённости LN должна быть меньше или равна 2ε. Из (17) следует

≤ 2ε 1+ ε FN –2 ≤ 2ε FN ε(FN –2 –2 FN) ≤ –1 ε(FN –2 –2 FN –1–2 FN –2) ≤ –1

ε(– FN –2 –2 FN –1)≤–1 ε(FN –2 +2 FN –1)≥1 ε(FN –2 + FN –1+ FN –1) ≥ 1 ε (FN + FN –1) ≥ 1 ε FN +1 ≥ 1.

Отсюда следует

FN +1. (18)

Таким образом, конечное число шагов поиска N определяется по формуле (18).

В заключение рассмотрим вопрос о выборе точки х 1и связанной с этим возможностью реализации мето­да. Из предыдущего анализа следует х 1=1– L 2; но L 2= FN –1 LN –ε FN –3 (см. табл. 1) или с учётом (17) L 2= FN [ FN –1+ε(FN -1 FN –2FN FN –3)]. Отсюда сле­дует, что сделать первый шаг здесь можно лишь тогда, когда назначено число N, т. е. х 1= х 1(N). Это является недостат-ком, затрудняющим в ряде случаев решение за­дачи из-за невозможности изменить N после начала экспериментов. Отметим, что метод золотого сечения не требует предварительного задания N и приближается по эффективности к исследованному методу чисел Фибоначчи [4].



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-04-20 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: