Составители:
Рубрика:
28
()
(), min ();
xA
GfxA fx
∈
≤
(47)
()()
11
(), (), , ;GfxA GfxA A A
≥⊂
(48)
()
1
1
(), min ().
xA
GfxA fx
=
=
(49)
Алгоритм решения задачи следующий.
1. Множество A разбивают на непересекающиеся два A
1
и A
2
, нахо-
дят нижние границы G(A
1
) и G(A
2
) и выбирают наименьшую из них.
2. Если соответствующее подмножество состоит из одного элемента
(решения), то решение заканчивается. В противном случае переходят к
п. 1, в котором разбиению на два непересекающиеся подмножества под-
вергается выбранное с наименьшей нижней границей.
На рис. 5 показана функция f(x) c областью определения (a, b). Тре-
буется найти ее минимум f
min
(x) и соответствующее значение аргумен-
та x
opt
. Прежде всего, на основании анализа выражения, определяюще-
го функцию, устанавливается выражение для границы G(a, b), завися-
щей от области определения (a, b) и имеющей значение, не большее,
чем все значения функции f(x) ≤ G(a, b) в области ее определения. Да-
лее вся область (a, b) делится на несколько, чаще две, равные и непере-
секающиеся области (a, c) и (c, b). Для этих областей определяются две
границы G(a, c) и G(c, b). Так как G(c, b) < G(a, c), а минимальные
значения функции в этих областях находятся рядом с границами и
несколько выше их, то, вероятно, минимум функции в области (c, b)
f
min(a, b)
(x) также меньше минимума функции в области (a, c) f
min(a, c)
(x):
Рис. 5. Поиск f
min
(x) методом ветвей и границ
f(x)
f
min
(x)
G(a, c)
G(a, b)
G(c, d)
G(d, b)
G(c, b)
a
c
d
b
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
