Численные методы расчёта, моделирования и проектирования технологических процессов и оборудования. Майстренко А.В - 124 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

124
лярного симплекса, который в N-мерном пространстве представляет
собой многогранник, образованный N + 1 равноотстоящими друг от
друга точками-вершинами. Например, в случае двух переменных сим-
плексом является равносторонний треугольник; в трёхмерном про-
странстве симплекс представляется собой тетраэдр.
Работа алгоритма симплексного поиска начинается с построения
регулярного симплекса в пространстве независимых переменных и
оценивания значений целевой функции в каждой из вершин симплек-
са. При этом определяется вершина, которой соответствует наихудшее
значение целевой функции. Затем найденная вершина проецируется
через центр тяжести остальных вершин симплекса в новую точку, ко-
торая используется в качестве вершины нового симплекса. Итерации
продолжаются до тех пор, пока не начнётся циклическое движение по
двум или более симплексам. В этом случае размеры симплекса умень-
шаются, и весь поиск повторяется, пока размеры симплекса не станут
меньше некоторой заданной точности.
Однако в таком варианте алгоритм симплексного метода работает
слишком медленно, так как полученная на предыдущих итерациях ин-
формация не используется для ускорения поиска. Этот недостаток час-
тично устранён в модифицированной процедуре поиска по симплексу,
разработанной Нелдером и Мидом, называемой методом Нелдера-
Мида или методом деформируемого многогранника, являющегося
одним из самых эффективных методов при
6
≤
n
.
Метод Нелдера–Мида допускает использование неправильного
симплекса, к которому могут быть применены операции отражения,
растяжения, сжатия и редукции.
Рассмотрим алгоритм метода деформируемого многогранника на
примере поиска min.
1. Строится начальный симплекс. Обычно (но не обязательно)
начальный многогранник выбирается в виде регулярного симплекса.
В вершинах симплекса вычисляются значения функции
(
)
(
)
(
)
112211
...,,,
++
===
nn
xffxffxff
.
2. Среди точек симплекса отыскивается наибольшее значение f
h
,
следующее за наибольшим значением функции f
g
, наименьшее значе-
ние функции f
l
и соответствующие им точки x
h
, x
g
, x
l
.
3. Ищется центр тяжести всех точек, за исключением x
h
:
∑
≠
=
hi
i
x
n
x
1
0
и
(
)
00
xff =
.
4. Выполняют отражение точки x
h
относительно точки x
0
с коэф-
фициентом отражения
0
>
α
:
(
)
(
)
rrhr
xffxxxx =−α+= ,
00
.

Страницы