Поиск экстремума симплекс -методом

ВВЕДЕНИЕ

Решение оптимизационной задачи в общем случае заключается в опреде- лении таких значений входных переменных исследуемого объекта, которым соответствует наилучшее (минимальное или максимальное) значение целевой функции. Технологические системы, как правило, являются многомерными, с большим количеством входных факторов, на значение которых к тому же на- кладываются дополнительные ограничения. Это требует использования мето- дов многомерной условной оптимизации. Многие из данных методов, однако, предполагают сведение задачи к безусловной оптимизации путем преобразова- ния целевой функции с дальнейшим применением соответствующих процедур. Поэтому изучение методов поиска экстремума функций нескольких перемен- ных без ограничений является не менее важной задачей.

В настоящих рекомендациях рассматривается постановка задачи много-

мерной безусловной оптимизации, аналитический анализ целевой функции,

теоретические основы часто используемых на практике численных методов - метода крутого восхождения, симплекс - метода и метода Хука и Дживса. Для наилучшего понимания сущности и особенностей этих методов, формирования навыков корректного задания входных параметров их работа иллюстрируется на примере функций двух переменных, когда возможна геометрическая интер- претация решения задачи.

В прил. 1 – 5 приводится пример выполнения практической работы, а так-

же варианты индивидуальных заданий.

ПОСТАНОВКА ЗАДАЧИ

Пусть задана функция n действительных переменных

n

f(x1, x2, x3, ..., xn) = f(x), определенная на множестве XR,

где x- вектор- столбец, обозначающий точку в n-мерном евклидовом простран-

стве с координатами x1, x2, x3, ..., xn .

Функция f(x) имеет локальный минимум в точке x*∈ X, если существует окрестность точки x* такая, что f(x*) ≤ f(x) во всех точках этой окрестности. В

n

случае глобального минимума в точке x* для всех xR

ство f(x*) ≤ f(x).

справедливо неравен-

Далее будем рассматривать задачу отыскания точек минимума функции

n

f(x), т.е. f(x) → min , xR. Для приведения же задачи максимизации к за-

даче минимизации достаточно изменить знак целевой функции.


Симплексные алгоритмы

Обычный симплекс- метод

Симплексом в пространстве n переменных называют выпуклый много- гранник, имеющий n+1 вершину. В пространстве двух переменных это тре- угольник, в пространстве трех переменных - тетраэдр. В обычном симплекс- методе используется правильный симплекс (все ребра которого равны).

Идея симплекс-метода, которая далее рассматривается на примере дву- мерного случая, заключается в следующем. Выбирается начальный симплекс с вершинами x(1)- x(2)- x(3). Размещение правильного симплекса в пространстве может быть осуществлено двумя путями (рис.1).

Поиск экстремума симплекс -методом - student2.ru

№ вершины   x1   x2
  x(1)    
  x(2) 3 + 1 2 2 3 − 1 2 2
  x(3) 3 − 1 2 2 3 + 1 2 2
1. Одна вершина симплекса помещается в начало координат, а остальные вершины располагаются так, чтобы ребра, выходящие из первой вершины, об- разовывали одинаковые углы с соответствующими координатными осями. То- гда для двумерного случая координаты вершин будут равны:

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru x2

x(3)

Поиск экстремума симплекс -методом - student2.ru xц.т.

x(4)

Поиск экстремума симплекс -методом - student2.ru x(2)

Q

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru x(1)

P x1

Рис. 1

В общем случае координаты вершин симплекса определяются матрицей:

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru

№ вершины x1 x2 x3 xn
P Q Q Q
Q P Q Q
n+1 Q Q Q P
P = 1 (

n +1 + n −1) ;

n 2

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru Q = 1 (

n +1 −1).

n 2

№ вершины   x1   x2
  x(1) 1 1 2 3
  (2) x 1 1 2 3
  x(3)  
Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru 2. Центр симплекса помещается в начало координат, а (n+1)-я вершина на ось xn. Остальные вершины располагаются симметрично относительно коорди- натных осей. В двумерном случае координаты вершин будут равны:

Поиск экстремума симплекс -методом - student2.ru x2 x(3)

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru x(1)

R1 V1

Рис. 2

x1

x(2)

В общем случае координаты вершин симплекса определяются матрицей:

№ вершины x1 x2 x3 xn
-R -R -R -R
V1 -R2 -R3 -Rn
V2 -R3 -Rn
V3   -Rn
n+1 Vn
1 2 3

n Ri

= 1 ;

Поиск экстремума симплекс -методом - student2.ru 2 ⋅i(i +1)

Vi =

Поиск экстремума симплекс -методом - student2.ru i .

2(i +1)

В первом и во втором случаях формулы получены для симплекса, длина ребра которого равна единице. Для произвольной длины каждую формулу нужно умножить на длину ребра. Если поиск осуществляется не из начала координат, а из начальной точки x(0), то к координатам вершин симплекса необходимо добавить координаты начальной точки- x1(0) и x2(0).

В вершинах исходного симплекса рассчитывается значение целевой функции f(x(1)), f(x(2)), f(x(3)). Из этих трех значений выбирается "наихудшая" точка (при поиске минимума это та точка, в которой функция принимает мак- симальное значение). Допустим, что это точка x(1). Через центр тяжести проти- волежащей грани xц.т.=(x(2) + x(3))/2 строится новая вершина симплекса x(4), сим- метричная "наихудшей" вершине x(1) (рис.1). Координаты новой вершины x(4) рассчитываются по формуле:

x(4)= xц.т.+ (xц.т.- x(1))= x(2) + x(3) - x(1)

В результате получается новый симплекс x(2) - x(3) - x(4), причем значение целевой функции в двух точках x(2) и x(3) уже известно. Поэтому вычисляется

значение функции в точке x(4) и среди всех вершин ищется вершина с "наихуд- шим" значением. Эта вершина вновь отображается через середину противоле- жащей грани и вся процедура повторяется. Признаком окончания поиска явля-

ется так называемая процедура зацикливания, когда вновь отображенная вер- шина оказывается "наихудшей". В этом случае, если заданная точность не дос- тигается, (точность определяется длиной ребра симплекса) необходимо умень- шить размеры симплекса. Процедура повторяется до тех пор, пока длина ребра

симплекса не станет меньше заданной точности.

В общем n – мерном случае, если обозначить отображаемую вершину симплекса за x(1), остальные вершины - x(2) , x(3) , x(n+1), отображенную вершину за x(n+2) , координаты центра тяжести грани, относительно которой производится отображение, определяются по формуле:

n+1

xц.т.

= 1x(i ) , а отображаемой вершины

n i=2

x(n+2) = x

ц.т.

+α(x

ц.т.

x(1) ). (4.1)

Здесь множитель α > 0 . При α =1 получаем зеркальное отображение x(1) и если

исходный симплекс был правильным, то при зеркальном отображении и новый

симплекс окажется правильным.

Поиск экстремума симплекс -методом

Начальную точку с координатами x(0) = (5; 6) берем за центр тяжести тре- угольника. Вокруг начальной точки строим треугольник -симплекс. Координа- ты вершин исходного симплекса рассчитываются по формулам:

x(1) = (x (0)

x(2) = (x (0)

x(3) = (x (0)

-a/2 ; x (0)

+a/2 ; x (0)

; x (0)

- 0,29·a);

- 0,29·a);

+0,58·a), где a- длина ребра симплекса,

которую выбираем произвольно. Пусть a=2, тогда координаты вершин исходного симплекса и соответствующее им значение целевой функции будут

равны:

№ точки x1 x2 y
x(1) x(2) x(3) 5,42 5,42 7,16 108,27 149,95 185,81

Из трех значений функции выбирается "наихудшая" точка: при поиске

минимума эта та точка, в которой функция принимает максимальное значение.

В нашем случае это точка с координатами x(3) = (5; 7,16).

Через центр противолежащей грани строится новая вершина симплекса,

симметричная "наихудшей" вершине.

Координаты новой вершины рассчитываем по формулам:

x
(4)

= x (1)

+ x (2)

- x (3)

; x (4)

= x (1)

+ x (2)

- x (3).

В результате получился новый симплекс с вершинами:

№ точки x1 x2 y
x(1) x(2) x(4) 5,42 5,42 3,68 108,27 149,95 82,52

Теперь " наихудшей" точкой будет вершина симплекса с координатами

x(2) = (6; 5,42). Дальнейшие расчеты приведены в таблице.

№ точки x1 x2 y
x(1) x(5) x(4) x(6) x(7) x(8) x(9) x(10) x(11) 5,42 3,68 3,68 1,94 1,94 0,2 0,2 -1,54 -1,54 108,27 51,8 82,52 36,16 16,41 10,88 2,08 6,66 8,82

№ точки x1 x2 y
x(9) x(10) x(11) 0,2 -1,54 -1,54 2,08 6,66 8,82
Координаты последнего симплекса приведены в таблице:

Таким образом, вершина x(8) отображенная в x(11) вновь оказалась "наихудшей". Этот случай называется процедурой

"зацикливания". Проверяем условие окончания алгоритма, сравнивая длину

Поиск экстремума симплекс -методом - student2.ru ребра симплекса с заданной точностью

(5 −1)2 + (−3,28−3,68)2 = 2

> 0,2 .

Для продолжения поиска необходимо произвести редукцию последнего симплекса.

№ точки x1 x2 y
x(9) x(12) x(13) 1,5 0,5 0,2 -0,67 -0,67 2,08 3,48 2,82
Выбирается вершина, в которой функция принимает минимальное значе- ние x(9) = (1; 0,2). Две другие вершины будут расположены на серединах приле- жащих к ней граней.

Таким образом, получился новый симплекс с длиной ребра, равной 1, и координатами

вершин:

№ точки x1 x2 y
x(22) x(23) x(24) x(25) x(26) x(27) -0,50 -0,375 -0,625 -0,75 -0,875 -0,75 0,635 0,8525 0,8525 0,635 0,8525 1,07 0,15 0,25 0,074 0,146 0,022 0.1073
зацикливание, уменьшаем ребро до 0,125
x(26) x(28) x(29) x(30) x(31) -0,875 -0,75 -0,8125 -0,9375 -1 0,8525 0,8525 0,9612 0,9612 0,8525 0,022 0,032 0,024 0,0021 0,0435
Дальнейшие расчеты приведены в таблице:

№ точки x1 x2 y
x(14) x(15) 0,5 0,2 1,07 0,68 2,46
зацикливание, уменьшаем ребро до 0,5
x(14) x(16) x(17) x(18) x(19) 0,5 0,25 -0,25 -0,5 0,2 0,2 0,635 0,635 0,2 0,68 1,13 0,92 0,28 0,73
зацикливание, уменьшаем ребро до 0,25
x(18) x(20) x(21) -0,25 -0,375 -0,125 0,635 0,4175 0,4175 0,28 0,34 0,42

Поскольку в послед- ней точке произошло за- цикливание, а длина ребра

симплекса 0,125 < ε=0,2,

условие окончания алго-

ритма выполняется.

Таким образом, за точку минимума принима-

ем вершину симплекса, со- ответствующую минимуму целевой функции после его

зацикливания, т.е.

x*≈x(30) = (-0,9375; 0,9612).

Траектория поиска

показана на рис.6.

Поиск экстремума симплекс -методом - student2.ru 5



Задача 1

Поиск экстремума симплекс -методом - student2.ru

Задача №2

Вариант№1

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Поиск экстремума симплекс -методом - student2.ru

Наши рекомендации