Поиск экстремума симплекс -методом
ВВЕДЕНИЕ
Решение оптимизационной задачи в общем случае заключается в опреде- лении таких значений входных переменных исследуемого объекта, которым соответствует наилучшее (минимальное или максимальное) значение целевой функции. Технологические системы, как правило, являются многомерными, с большим количеством входных факторов, на значение которых к тому же на- кладываются дополнительные ограничения. Это требует использования мето- дов многомерной условной оптимизации. Многие из данных методов, однако, предполагают сведение задачи к безусловной оптимизации путем преобразова- ния целевой функции с дальнейшим применением соответствующих процедур. Поэтому изучение методов поиска экстремума функций нескольких перемен- ных без ограничений является не менее важной задачей.
В настоящих рекомендациях рассматривается постановка задачи много-
мерной безусловной оптимизации, аналитический анализ целевой функции,
теоретические основы часто используемых на практике численных методов - метода крутого восхождения, симплекс - метода и метода Хука и Дживса. Для наилучшего понимания сущности и особенностей этих методов, формирования навыков корректного задания входных параметров их работа иллюстрируется на примере функций двух переменных, когда возможна геометрическая интер- претация решения задачи.
В прил. 1 – 5 приводится пример выполнения практической работы, а так-
же варианты индивидуальных заданий.
ПОСТАНОВКА ЗАДАЧИ
Пусть задана функция n действительных переменных
n
f(x1, x2, x3, ..., xn) = f(x), определенная на множестве X R,
где x- вектор- столбец, обозначающий точку в n-мерном евклидовом простран-
стве с координатами x1, x2, x3, ..., xn .
Функция f(x) имеет локальный минимум в точке x* X, если существует окрестность точки x* такая, что f(x*) f(x) во всех точках этой окрестности. В
n
случае глобального минимума в точке x* для всех x R
ство f(x*) f(x).
справедливо неравен-
Далее будем рассматривать задачу отыскания точек минимума функции
n
f(x), т.е. f(x) min , x R. Для приведения же задачи максимизации к за-
даче минимизации достаточно изменить знак целевой функции.
Симплексные алгоритмы
Обычный симплекс- метод
Симплексом в пространстве n переменных называют выпуклый много- гранник, имеющий n+1 вершину. В пространстве двух переменных это тре- угольник, в пространстве трех переменных - тетраэдр. В обычном симплекс- методе используется правильный симплекс (все ребра которого равны).
Идея симплекс-метода, которая далее рассматривается на примере дву- мерного случая, заключается в следующем. Выбирается начальный симплекс с вершинами x(1)- x(2)- x(3). Размещение правильного симплекса в пространстве может быть осуществлено двумя путями (рис.1).
|
x2
x(3)
xц.т.
x(4)
x(2)
Q
x(1)
P x1
Рис. 1
В общем случае координаты вершин симплекса определяются матрицей:
|
n +1 + n 1) ;
n 2
Q = 1 (
n +1 1).
n 2
|
2. Центр симплекса помещается в начало координат, а (n+1)-я вершина на ось xn. Остальные вершины располагаются симметрично относительно коорди- натных осей. В двумерном случае координаты вершин будут равны:
x2 x(3)
x(1)
R1 V1
Рис. 2
x1
x(2)
В общем случае координаты вершин симплекса определяются матрицей:
|
n Ri
= 1 ;
2 i(i +1)
Vi =
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) берем за центр тяжести тре- угольника. Вокруг начальной точки строим треугольник -симплекс. Координа- ты вершин исходного симплекса рассчитываются по формулам:
| |
| |
| |
-a/2 ; x (0)
| |
| |
| |
- 0,29·a);
- 0,29·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 (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 |
|
Таким образом, вершина x(8) отображенная в x(11) вновь оказалась "наихудшей". Этот случай называется процедурой
"зацикливания". Проверяем условие окончания алгоритма, сравнивая длину
ребра симплекса с заданной точностью
(5 1)2 + (3,283,68)2 = 2
> 0,2 .
Для продолжения поиска необходимо произвести редукцию последнего симплекса.
|
Таким образом, получился новый симплекс с длиной ребра, равной 1, и координатами
вершин:
|
| № точки | 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.
5
Задача 1
Задача №2
Вариант№1
