Математические методы принятия решений. Бодров В.И - 33 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

ряется до тех пор, пока в этом направлении не будет найден минимум, после чего только вычисляется гради-
ент и определяется новое направление наибыстрейшего убывания целевой функции.
По сравнению с методом градиента метод наискорейшего спуска оказывается более выгодным из-за
сокращения объема вычислений. Чем менее резко изменяется направление градиента целевой функции,
тем выгоднее использовать метод наискорейшего спуска, т.е. вдали от оптимума. Вблизи оптимума рас-
сматриваемый метод автоматически переходит в метод градиента. Окончание поиска происходит в со-
ответствии с теми же критериями, что и в методе градиента.
3.4.4 Метод квантования симплексов
Симплексный метод относится к группе безградиентных методов детерминированного поиска. Ос-
новная идея метода заключается в том, что по известным значениям функции в вершинах выпуклого мно-
гогранника, называемого симплексом, находится направление, в котором требуется сделать следующий
шаг, чтобы получить наибольшее уменьшение (увеличение) критерия оптимальности. Примером сим-
плекса на плоскости является треугольник, в трехмерном пространстве – четырехгранная пирамида, в n-
мерном пространстве – многогранник с n + 1 вершиной. Основным свойством симплекса является то, что
против любой из вершин симплекса расположена только одна грань, на которой можно построить новый
симплекс, отличающийся от прежнего расположением новой вершины, остальные вершины обоих сим-
плексов – совпадают.
Начало
задание u
0
,
H, ε, n, Q
вычисление Q
0
вычисление
δ
Q/
δ
u
i
Q
0
<Q
1
нет
да
вывод u
1
, Q
1
Конец
L = 0
u
1
= u
0
– H⋅δQ/δu
Q
1
= Q(u
1
)
возврат: u
1
= u
0
, Q
1
= Q
0
L = L + 1
Q
0
= Q
1
; u
0
= u
1
L = 0
да
нет
дробление шага
H = H/3
H <
ε
нет
да
Рис. 3.11 Блок-схема метода наискорейшего спуска
Наглядную иллюстрацию симплексного метода удобнее рассматривать на примере задачи отыска-
ния минимального значения целевой функции двух независимых переменных (рис. 3.11). Алгоритм по-
иска заключается в следующем.
1 Определяются значения целевой функции в трех точках S
10
,
S
20
, S
30
, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рас-
сматриваемом примере – это S
10
(рис. 3.12).

Страницы