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

Симплексом в n -мерном пространстве называют фигуру, со­держащую n +1 вершину. На плоскости — это треугольник, в трехмерном пространстве — тетраэдр и т.д. Если все вершины симплекса равно удалены друг от друга, то такой симплекс назы­вается регулярным. В литературе можно встретить и другое название метода — метод деформируемого многогранника. В организации алгоритма поиска используется важное свойство симплекса: против каждой вершины находится только одна грань. Суть метода заключается в следующем. В окрестности начальной точки х° строим симплекс, затем находится самая "пло­хая" его вершина (т.е. та, в которой наихудшее значение критерия оптимальности) и на противоположной грани строится новый симплекс, отличающийся от исходного только одной вершиной. Эта вершина получается симметричным отражением выбрасы­ваемой вершины относительно центра противолежащей грани. Центр грани определяется геометрически, как среднее значение по каждой проекции из всех вершин грани. Алгоритм получения новой вершины записывается следующим образом:

где х ¹, х ²,...— вектора вершины симплекса (координаты вер­шин), x^j — вектор выбрасываемой вершины, x^j — новая верши­на в новом симплексе. В скалярном представлении для каждой координаты будет аналогичная формула.

После построения нового симплекса требуется лишь одно вы­числение критерия оптимальности: только в новой вершине, так как в остальных углах они вычислены. Далее все повторяется сно­ва.

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

Х^j = 3/(2n) (x¹+x²+…xⁿ⁺¹) – (1+3/(2n))x^j.

Процесс сжатия происходит многократно, до тех пор пока размеры симплекса не будут меньше заданных.