Получение оптимальных проектных решений и их анализ с использованием математических моделей. Литовка Ю.В. - 45 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

S
0
= ),(
0
2
0
2
0
1
0
1
ххxх −− , т.е. h
0
= argmin( f
0
(X
0
+ hS
0
).
Значение h
0
отыскивается любым из методов одномерной минимизации. Для локализации отрезка [h′, h″],
содержащего минимум по
h, необходимо использование процедуры локализации, описанной выше. При этом
очевидно, что в точке
Х
0
h
0
= 0, в точке
0
Х
h
0
= 1.
Следующие итерации выполняются аналогично.
Симплексный метод. Множество (n + 1)-й равноудаленной точки в n-мерном пространстве называется
правильным симплексом. В случае
n = 2 правильным симплексом является равносторонний треугольник. Идея
симплексного метода состоит в сравнении значений функции в (
n + 1) вершинах симплекса и перемещении его
в направлении наилучшей точки. Симплексный метод, допускающий как правильные, так и неправильные сим-
плексы, является одним из самых эффективных методов нулевого порядка при
n ≤ 6.
Алгоритм решения задачи симплексным методом может быть представлен в виде следующей последова-
тельности шагов.
1. Задаются
n + 1 точка Х
1
, Х
2
, ..., X
n+1
, являющиеся вершинами начального симплекса.
2. Вычисляются величины
f
1
= f
0
(X
1
), …, f
n+1
= f
0
(X
n+1
).
3. Определяются вершины
h, g, l, для которых f
h
– наибольшее значение среди всех f
i
, i = l, … , n + 1; f
g
– сле-
дующее за наибольшим;
f
l
– наименьшее значение.
4. Определяется центр тяжести
Х
C
всех точек, кроме Х
h
,
1
1
∑
≠
=
=
n
hi
i
iC
X
n
X
и вычисляется значение целевой функции
f
0
в точке Х
C
– f
C
.
5. Выполняется операция отражения точки
Х
h
относительно точки X
C
с коэффициентом отражения α и по-
лучением точки
X
0
(рис. 2.8). При этом X
0
– X
C
= α(X
C
– X
h
), откуда X
0
= (1 + α)X
C
– αX
h
. Вычисляется значение
целевой функции
f
0
, в точке Х
0
– f
0
.
6. Значение
f
0
сравнивается со значениями f
1
и f
g
. Возможны три случая:
6.1. Если
f
0
< f
1
, то направление из точки X
C
в точку Х
0
является наиболее предпочтительным для переме-
щения. В этом случае выполняется операция растяжения симплекса с коэффициентом растяжения
β и получе-
нием точки
X
r
. При этом X
r
– X
C
= β (X
0
– X
C
), откуда X
r
= (1 – β)X
C
– βX
0
.
Далее вычисляется значение целевой функции
f
0
в точке Х
r
– f
r
и осуществляется его сравнение со значени-
ем
f
1
. Возможны два случая:
Х
r
Х
0
Х
c
Х
h
Х
1
Х
2
Рис. 2.8. Операция отражения и растяжения симплекса
6.1.1. Если
f
r
< f
1
, то точка Х
h
перемещается в точку Х
r
, образуя новый симплекс, текущая итерация закан-
чивается и выполняется переход к шагу 10 для проверки критерия останова.
6.1.2. Если
f
r
≥ f
1
, то точка X
r
отбрасывается, так как перемещение было выполнено слишком далеко. В
этом случае точка
Х
h
перемещается в точку Х
0
, образуя новый симплекс, текущая итерация заканчивается и вы-
полняется переход к шагу 10 для проверки критерия останова.
6.2. Если
f
1
< f
0
≤ f
gх
, то Х
0
является не самой плохой точкой. В этом случае точка Х
h
перемещается в точку
Х
0
и выполняется переход к шагу 10.
6.3. Если
f
0
> f
g
, то выполняется переход к шагу 7.
7. Выполнение операции сжатия симплекса. Возможны два варианта сжатия в зависимости от значений
f
0
и
f
h
.
7.1. Если
f
0
< f
h
, то результатом операции сжатия является точка X
S
, определяемая из условия
X
S
– X
C
= γ (X
0
– X
C
) или X
S
= γX
0
+ (1 – γ)X
C
.
В этом случае точка Х
S
будет лежать между X
C
и Х
0
(рис. 2.9, а).
7.2. Если
f
0
≥ f
h
, то результатом операции сжатия является точка Х
S
, определяемая из условия
X
S
– X
C
= γ (X
h
– X
C
) или X
S
= γX
h
+ (1 – γ)X
C
.
В этом случае точка
X
S
будет лежать между X
h
и X
C
(рис. 2.9, б). Далее вычисляется значение целевой функции
в точке
X
S
– f
S
.

Страницы