9. Симплексные методы решения задач безусловной оптимизации.

Обычный симплекс – метод.

Симплексом в пространстве n переменных называют выпуклый многогранник, имеющий n+1 вершину. В обычном симплекс-методе используется правильный симплекс (все ребра которого равны). На примере двумерного случая рассмотрим решение задачи оптимизации. Выбирается начальный симплекс – треугольник, т.к. двумерное пространство, с вершинами х⁽¹⁾ – х⁽²⁾ – х⁽³⁾. Размещение правильного симплекса в пространстве может быть осуществлено двумя путями:

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

2.Центр симплекса перемещается в начало координат, а (n+1)-я вершина на ось х₀. Остальные вершины располагаются симметрично относительно координатных осей.

В вершинах исходного симплекса рассчитывается значение целевой функции ,,. Из этих трех значений выбирается «наихудшая» точка. Через центр тяжести противолежащей грани х_ц.т. строится новая вершина симплекса х⁽⁴⁾. В результате получается новый симплекс х⁽²⁾-х⁽³⁾-х⁽⁴⁾. Вычисляется значение целевой функции в х⁽⁴⁾. Среди новых вершин ищется «наихудшая». Эта вершина вновь отображается через середину противолежащей грани, вся процедура повторяется. Признаком окончания поиска является процедура зацикливания, когда вновь отображенная вершина оказывается «наихудшей». В этом случае необходимо уменьшить размеры симплекса. Процедура повторяется до тех пор, пока длина ребра не станет меньше заданной точности.

Метод деформируемых многогранников (метод Нельдера – Мида).

Данный метод более эффективен, чем обычный симплекс – метод, так как симплекс меняет свою форму от цикла к циклу.

1.        Выбирают начальный симплекс и рассчитывают целевую функцию в вершинах.

2.        Из найденных значений ищут  и .

3.        Отображают «наихудшую» вершину относительно центра тяжести противоположной грани. .

4.        а) , то происходит растяжение симплекса, β > 1 ,

Если , следовательно,  - новая вершина симплекса, иначе, за новую вершину берется точка, полученная после отображения .

б) , то сжатие β < 1.

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