Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Как известно [56], числа Фибоначчи определяются так:

F n+2=

= / 7n+i+^n,

(/ i= l, 2,

...);

/7i = / 72 = 1 .

Нетрудно

показать,

что

F „ =

1 +

/ 5

1

— / 5

. / 5 .

Перейдем к описанию

плана

Фибоначчи Фп

(n^sl).

Пусть

J( « )e Q * [a ,

b\. При п— 1

план Ф\ прост:

берем «1

__

а

Ь

и вы­

числяем значение 1(щ ). Полагая

и[ = и1,

определим

точку

мини­

мума и* с погрешностью

К

— « ! | <

Ъ— а

6 — а

2

Пусть теперь п > 2 . Тогда план Ф„

начинается

с

выбора

двух

точек

«х = аЧ-----—— (6 — а),

и2 =

а + — п+1

(Ь — а) =

а +

Ь— их,

Рп+2

F n+2

расположенных на отрезке [а,

6]

симметрично,

и

вычисления значе­

ний

JijUj), J

(и2).

Если J

(%) < J (и2),

то

полагаем

а 2 =

а,

Ь2 = и2,

и 2 =

и1\ если же J (их)^> J

(и2), то а 2 =

ult

b2 — b,

и2 — и2. В резуль­

тате

получаем отрезок

[а2,

Ь2]

длины

р

(Ъ— а),

Ь2— а 2 = b — и1 = и2— а — —

Fn+2

содержащий

точку и*

и точку и2,

а 2< ы 2 < 6 2,

в

которой

J (и2) = min{J (их), J {и2)}.

Заметим, что

точка и2 совпадает с

одной

из точек '

щ =

а 2+

/ —

(р2 — а 2) =

а2 +

Гп+2

{b — а) (при J (их) <

J

(и2))

г Л+1

31ЛИ

ul = a 2+

F"~1■- {b, — а2) = а 2 +

^,1~1 - (6 — а) =

ГП+Х

* Л +2

= а2 +

Ъг — «2

(при J Ы

> 7 (и2)).

Далее на отрезке [а2, 62] выбираем следующую

точку и3 =

а 2-f b2—

— и2,

вычисляем 7 ( а 3)

и сравнением величин 7

(и2),

J

(us) находим

новый

отрезок [а3,

63]

и т.

д. (рис.

2).

В

общем случае,

пусть точ­

22

МИНИМИЗАЦИЯ ФУНКЦИИ одной ПЕРЕМЕННОЙ

\ГЛ. 1

ки

иъ

. . .

, ик (2 <

k < п)

уже

выбраны,

пусть

найден

отрезок

[ak,

bk\ длины

bk- a k = - ^ s - ( b - a ) ,

Рп+2

содержащий

точку и* и точку ик,

ак < ик •< Ьк,

с

вычисленным

зна­

чением

J

(ик) =

min J (U[),

причем

точка ик

совпадает с

одной

из

точек

= а* +

г n - f t + 8

(& * - * * ) = a* +

“ /7 + 2

(6 — a)

ИЛИ

“* = e* +

Фк — ak) = a* +

"4 ”—

- (6 — a) =

— uk.

Если

то на

отрезке

[ak, bk]

выбираем

следующую

точку:

uk+\=

ak +

Ьк — ик,

симметричную

с ик на этом отрезке и

совпада­

ющую

с одной из точек и'к, ик, отличной от ик.

Вычислим

значение

J (ик+ О

и сравним с

J{u k). Пусть для

определенности ик =

ик <^ ик=

= Uk+ 1

(случай Uk+i = u'k<

Uft = uk рассматривается

аналогично). Тог­

да при

J

(Uk) <

/ (Uk+i)

полагаем

ак+1 — ak,

bk+] = ик+и

uk+\ = ик.

Если же

J (ик) >

J (uk+i),

то ak+l =

ик,

bk+l =

bk,

ик+1 = ик+и В

ре­

зультате

получаем отрезок

[a^+i,

Ьк+1]

длины

bk+1 — ak+1 =

- 4

fe— Ф — a),

•»/2+2

содержащий точки и* и «*+1, afc+i <

•< bk+u

с известным

значе­

нием J(u k+ i)= min J (u£),

причем

точка ик+1

совпадает с

одной из

«ft+1 — Oft-fi

~

— (frft+i ~~ ak+i) — Oft+iЧ— тг~~ (b— а)

ИЛИ

* H -fc + S

*

Л + 2

«ft+1 =

Oft-j-i +

-

■(6ft+i — Oft+i) =

Г Л - f t + 2

— Oft+1 H—

г П +2

(b — a) =

aft+i +

bk+i — «ft+i,

и T. Д,

Если k = п, то процесс заканчиваем и

полагаем «^ =

«„

с

вы­

численным значением J

(ип) = m in /(«,).

Заметим,

что

при

/е = /г

длина отрезка

[ап, Ьп]

1<1<Л

равна

Ьп — а п =

F3

{ Ь - а )

2(6 — а)

Fп+ъ

гFЛ + 2

’

И ТОЧКИ

'

I

, и

\

,

6—а

ип = ап + —- ± — (Ь — а) = а п +

—

------,

* п+г

* * л + а

"

I

/**«

/*

ч

.

&—a

Цд =

ал + —р * ■-

(Ь — о) =

оя +

— ------

- '" л + 2

*

Л + 2

совпадают и делят отрезок [ап,

6„] пополам.

Таким

образом,

прини­

мая «л = ыя =

«„ = «п, мы допускаем

погрешность

,

»

* ___

Ь —а

|и — « л | < — -------

* л+2

независимо от выбора функции J (и) в Q* [а,

Ь].

Нетрудно видеть,

что

для функции J (и) =

и £ Q* [а, Ь]

план Фп дает

погрешность в опре­

делении и* — а, в точности

равную

ь ~ а. _

Следовательно,

F n + 2

б£(Ф я, b — а) = -^г— - (« > 1).

Л + 2

План Фибоначчи Ф„ полностью описан [56],

[230].

Отметим одно замечательное свойство плана Ф„: применение

плана Фл_б+ 1

к отрезку

[afe, Ьи], полученному

в

результате

пер­

должению плана Ф„ на этом отрезке [а;г, &ft],

Этот факт

вытекает из того,

что первые

две точки плана

Фя-/г-н

совпадают

с точками и*, и*,

или, что то

же самое, с точками uk,

«ft+i пла­

на Фп-

.

•

§ 6]

Оптимальный последовательный поиск для задачи

А

25

Таким

образом, стратегии Р п,

начинающиеся

с

выбора

двух

точек «ь и2,

a ^ .u i< u 2s^b,

где

заведомо

неоптимальны.

Аналогичные

рассуждения

показывают, что стратегии Р п с выбо­

ром точки

и2> и 2 также

не могут быть оптимальными.

Пусть

теперь

В худшем случае точка и* может на­

ходиться на отрезке [а, и{\ длиной

их—

— а = ——— (b — а),

Рп+г

*

(РП, ь - а ) > 6„А- 2 (Фп—2, Щ — а) —

Гп

Гп

=

=

Ь р -

= ЪКа(Ф п, Ь - а ) .

Таким

образом,

стратегии

Р п,

начинающиеся

с

двух

точек

U\, и2,

a^.Ui<Zu2^ .b,

где

,

заведомо

неоптимальны.

Ана­

логично

доказывается

неоптимальность

стратегии

Рп в случае

ы2 < “ 2.

Остается рассмотреть случай % = и*,

и2 = и2, когда первые

две

точки

стратегии Рп и

плана

Фп

совпадают,

и

сравнение

величин

J(u*),

J (и2) приведет к

отрезку

[а2,

Ь*2\,

содержащему

точки

и* и

« 2 с J

(и2) — min { J (и*),

J (и2)}. На поиск и*

на

этом отрезке в

на­

шем распоряжении остается

вычисление

значений функции

еще в

п — 1

(п > 2) точках,

включая точку и2.

Продолжением плана Ф„ на

отрезке

[а2,

Ь*2\ является план Ф»_1

на

этом

отрезке,

являющийся

единственной оптимальной последовательной

стратегией по

предполо­

жению индукции. Поэтому любое

отклонение

стратегии

Рп на [а2,

Ь2] от Фп приведет лишь к увеличению

гарантированной

погрешно­

сти:

8 А (Ря, b - а) > бА_! (Фп- и Ъ\ - а2) = 6

${Фп,Ь — а)

при Рп Ф Фп. Таким образом,

среди

стратегий Рп,

начинающихся с

выбора двух

точек их, и2£ [а, й] (s =

2),

наилучшей

является

план

Фибоначчи -Фп. В частности,

при /1 =

2

наилучшим будет план Ф2.