Алгоритм симплекс метода

Начальный этап. Пусть e> 0 - скаляр, используемый в критерии остановки, l – длина ребра симплекса, α – коэффициент уменьшения размеров симплекса. Выбрать начальную точку X₁, рассчитать вершины исходного симплекса X₁, X₂, …, Х_n+1, определить значение функции в этих вершинах f(X₁),…, f(X_n+1) и перейти к основному этапу.

Основной этап. Шаг 1. Определить из n+1 вершин вершину с максимальным значением функции и соответствующий ей номер j. Рассчитать новую вершину Х_n+2= . Если f(X_n+2)≤ f(X_j), то X_j=X_n+2 и перейти к шагу 1. В противном случае перейти к шагу 2.

Шаг 2. Если длина ребра £ e, то остановиться; в противном случае провести редукцию симплекса. Выбрать из n+1 вершин вершину с минимальным значением функции и соответствующий ей номер m. Рассчитать вершины нового симплекса X_i= ((1- α )X_m + Xi)/α для i ≠m, вычислить значения функции f(X₁),…, f(X_n+1) и перейти к шагу 1.

Пример расчета экстремума функции симплекс-методом.

Постановка задачи. Минимизировать f(X) = (x₁ - 2)⁴ + (х₁ - 2х₂)² с точностью e=0,01. Выбираем начальное приближение X⁽¹⁾ = [2.5, 2.5]^Т, длину ребра симплекса l=0.5 и коэффициент сжатия симплекса a = 2.

Результаты расчета для данных условий представлены в таблице 2.4, графическая интерпретация метода – на рисунке 2.4.

Таблица 2.4

Результаты расчета минимума функции f(X) = (x₁ - 2)⁴ + (х₁ - 2х₂)² симплекс методом.

Из таблицы видно, что на пятой итерации происходит зацикливание симплекса, так как отраженная вершина № 2 вновь становится «наихудшей». После редукции симплекса реализовано семь итераций, после чего вновь появляется эффект зацикливания. В результате чего вновь производится редукция. Полученный симплекс не находится в области экстремума функции. Поэтому проведенная редукция не дает желаемого результата, что говорит о плохой сходимости метода на функциях "овражного" типа.

Рис.2.4. Графическая иллюстрация поиска минимума функции симплекс-методом.

Метод Нелдера и Мида.

Отмеченные выше недостатки регулярного симплекса, а также отсутствие ускорения поиска и трудности при проведении поиска на искривленных “оврагах” и “хребтах” явились причиной разработки Нелдером и Мидом метода, в котором симплекс меняет свою форму, т. е. представляет деформируемый многогранник. Изменение формы многогранника происходит за счет операций растяжения, сжатия и редукции.

1. Построение начального многогранника. Выбирается произвольной формы многогранник с координатами вершин

X_i^(k) = [x_i1^(k), …, x_ij^(k), …, x_in^(k)]^Т, i = 1,…, n+1.

Индекс (k) будет обозначать k-й этап поиска. Значение целевой функции в X_i^(k) равно f(X_i^(k)).

2. Расчет координат центра тяжести. Определяют те векторы х многогранника, которые дают максимальное и минимальное значение f(X), а именно

f(X_h^(k)) = max{f(X₁^(k)), …, f(X_n+1^(k)); f(X_l^(k)) = min{ f(X₁^(k)), …, f(X_n+1^(k)).

Тогда координаты центра тяжести рассчитываются по формуле

, j = 1, …, n,

где индекс j обозначает координатное направление.

3. Отражение. Представляет проектирование X_h^(k) через центр тяжести в соответствии с соотношением

,

где a > 0 - коэффициент отражения;

X_h^(k) - вершина, в которой функция f(X) имеет наибольшее значение.

В обычном симплексе a = 1.

4. Растяжение. Происходит в случае, если . Вектор ( ) увеличивается в соответствии с соотношением

,

где g > 1 - коэффициент растяжения.

Если , то заменяется на и процедура продолжается с этапа 2 при k = k + 1. Иначе заменяется на и также осуществляется переход к этапу 2 при k = k + 1.

5. Сжатие. Если для всех i ¹ h, то вектор ( ) уменьшается в соответствии с формулой

,

где 0 < b < 1 - коэффициентом сжатия.

Затем заменить на и происходит возврат к операции 2 при k = k + 1.

6. Редукция. Происходит при условии, если . Все векторы ( ) уменьшаются в 2 раза с отсчетом от в соответствии с формулой

, i=1, …, n+1.

Затем возвращаемся к операции 2 для продолжения поиска на (k+1)-м шаге.

Для окончания поиска Нилдер и Мид используют критерий вида

£ e ,

где e- заданная точность поиска;

- значение функции в центре тяжести.