Метод правильного симплекса

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

В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 - правильного тетраэдра.

Если х° - одна из вершин правильного симплекса в En, то координаты остальных n вершин х1,..., xn можно найти, например, по формулам (4.1)

(4.1)

где , , а - длина ребра. Вершину х° симплекса, построенного по формулам (4.1), будем называть базовой.

В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины, например, симметрично относительно центра тяжести x^С остальных вершин симплекса. Новая и старая вершины и x^k связаны между собой соотношением: ,где

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

вершинами Таким образом, происходит перемещение симплекса в пространстве E2.

Поиск точки минимума функции f(x) с помощью правильных симплексов производится следующим образом. На каждой итерации сравниваются значения fx) в вершинах симплекса.Затем проводится описанная выше процедура отражения для той вершины, в которой fx) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходит к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0, старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f(x) заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми.

Опишем один из вариантов алгоритма симплексного метода.

Шаг 0. Выбрать параметр точности е, базовую точку x⁰, длину ребра a и построить начальный симплекс по формулам (4.1). Вычислить функцию f(x⁰).

Шаг 1. Вычислить значения f(x) в вершинах симплекса x¹,..., xⁿ.

Шаг 2. Упорядочить вершины симплекса x⁰,..., xⁿ так, чтобы

Шаг 3. Проверить условие

(4.2)

если оно выполнено, то вычисления прекратить, полагая .В противном случае перейти к шагу 4.

Шаг 4. Найти и выполнить отражение вершины xⁿ:

Если , то положить и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Найти и выполнить отражение вершины . Если, ,то положить и перейти к шагу 2. Иначе - перейти к шагу 6.

Шаг 6. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершину x⁰. Остальные n вершин симплекса найти

по формуле Перейти к шагу 1.

Геометрическая иллюстрация работы алгоритма в пространстве E2 показана на

рис. 4.2, где х⁰, х¹, х² - вершины начального симплекса, а пунктиром указаны процедуры отражения.

Замечания:

1. Следует иметь в виду, что если функция f(x) многомодальна, то описанным методом может быть найдена точка локального (ближайшего), а не глобального минимума f(x).

2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.