1. Нахождение безусловного экстремума

1. Нахождение стационарной точки

Целевая функция:

Частные производные по и :

Приравняв полученные выражения к нулю, получим систему уравнений:

Решение системы уравнений даёт результат:

Таким образом, экстремум целевой функции является точка с координатами , значение целевой функции, в которой: .

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

Так как гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы Гесса - положительные величины, все ведущие главные определители положительные величины), стационарная точка является точкой минимума.

Рисунок 1. Линии уровня функции и стационарная точка

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

2.1 Описание алгоритма

Суть метода заключается в исследовании целевой функции в вершинах некого "образца", построенного в пространстве вокруг "базовой" точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве - тетраэдр.

Работа алгоритма начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой точке. Затем определяется вершина с максимальным значением целевой функции и проектируется через центр тяжести оставшихся вершин в новую точку.

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

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

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

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

При заданной начальной точке и масштабном множителе , координаты остальных вершин симплекса в - мерном пространстве вычисляются по формуле:

Приращения и определяется по формулам:

Величина выбирается исследователем, исходя из характеристики решаемой задачи. При ребро симплекса имеет единичную длину.

Вычисление центра тяжести:

Если - точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:

Координаты новой вершины удовлетворяют уравнению:

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

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

2.2 Нахождение минимума целевой функции методом равномерного симплекса

Исходные данные:

- начальная точка

- масштабный множитель

Минимизируем целевую функцию до первого уменьшения размера симплекса

Пусть масштабный множитель -

1-я итерация:

- максимально, следовательно, заменяем;

2-я итерация:

- максимально, следовательно, заменяем;

3-я итерация:

- максимально, следовательно, заменяем

4-я итерация:

- максимально, следовательно, заменяем;

5-я итерация:

- максимально, следовательно, заменяем;

6-я итерация:

- максимально, следовательно, заменяем;

7-я итерация:

- максимально, следовательно, заменяем;

8-я итерация:

- максимально, следовательно, заменяем;

9-я итерация:

- максимально, следовательно, заменяем;

10-я итерация:

Так как наибольшее значение целевой функции соответствует , которое получено на предыдущей итерации, отбрасываем .

11-я итерация:

Так как наибольшее значение целевой функции соответствует , которое получено на предыдущей итерации, отбрасываем .

12-я итерация:

- максимально, следовательно, заменяем;

13-я итерация:

Так как наибольшее значение целевой функции соответствует , которое получено на предыдущей итерации, отбрасываем .

14-я итерация:

- максимально, следовательно, заменяем;

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

Таким образом, точка - точка минимума, значение функции в которой .

Рисунок 2. Графическое пояснение метода равномерного симплекса