Симплексный метод

Основная идея метода заключается в том, что по найденным значениям целевой функции в вершинах многогранника, называемого симплексом, определяется направление движения экстремума. При этом под симплексом в n-мерном пространстве независимых переменных, понимается геометрическая фигура, имеющая n+1 вершину.

Одним из важнейших свойств симплекса является то, что против каждой из его вершин находится только одна грань, на которой может быть построен новый симплекс, отличающийся от исходного расположением новой вершины.

Рассмотрим основную стратегию метода на примере функции двух переменных:

По известному значению целевой функции в исходной точке S₁ определяются вершины исходного сиплекса(S_1, S_2, S₃) По любому из правил построения треугольника. Далее определяется вершина, в которой функция принимает наихудшее значение(S₁). Построение нового симплекса происходит путем замены вершины S₁ на вершину S₄ , для этого вершина S₁ отражается симметрично центру противоположной грани на расстояние, равное расстоянию от S₁ до центра. В новом симплексе процедура повторяется( S₂ заменяется на S₅).

На промежуточных этапах поиска может возникнуть этап зацикливания, в этом случае уменьшается расстояние, на которое переносится новая вершина.

Для многомерного поиска вычислительный алгоритм может быть представлен следующим образом:

….

Х^A – координаты центра противоположной грани

Суммирование осуществляется по векторам, образующих противоположную грань.

Вектор U, характеризующий расстояние от центра до наихудшей вершины может быть определен по правилу:

U=x^(A)-x^(j)

И тогда координаты новой вершины могут быть определены по следующему условию:

Целесообразнее всего при поиске использовать правильные фигуры. В этом случае направление движения к экстремуму совпадает с направлением градиента.