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

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

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

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

(4.1)

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

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

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

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

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

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

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

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

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

(4.2)

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

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

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

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

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

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

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

рис. 4.2, где х0, х1, х2 — вершины начального симплекса, а пунктиром указаны процедуры отражения.

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

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