3.2.2 Метод Ньютона-Рафсона

Условие задания:

=[1;3]

Данный метод дает решение задачи за 1 шаг. Очередная точка поиска вычисляется в соответствии с выражением:

где – матрица Гессе функции;– обратная по отношению кматрица.

Градиент F(x):

;

.

где det H – определитель матрицыH;AdjH– присоединенная кHматрица (транспонированная матрица алгебраических дополнений).

Найдем определитель матрицы Гессе:

Найдем транспонированную матрицу алгебраических дополнений AdjH:

Теперь найдем матрицу обратную по отношению к - матрицу:

тогда:

Следовательно, в точке функцияF(x)достигает максимального значения:

3.3 Нахождение экстремального значения функцииF(X) с учетом системы ограничений задачи

3.3.1 Метод допустимых направлений Зойтендейка

Условие задания:

.

Тогда координаты очередной точки:

Здесь решение совпадает с первой итерацией метода наискорейшего спуска (Подъёма), тогда:

Определяем интервал допустимых значений для ⁰, при котором точкаx¹будет принадлежать ОДЗП. Для этого подставим координаты точкиx¹в ограничения задачи:

=>

Тогда:

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

Движение в направлении антиградиента выводит за пределы ОДЗП, поэтому очередную точку поиска вычисляем исходя из выражения:

где - новое направление, которое составляет минимальный острый угол с вектором градиента и направлено либо внутрь, либо по границе ОДЗП. При этом очередная точка должна принадлежать ОДЗП, а функция цели при переходе к очередной точке должна уменьшаться максимальным образом.

Направление находим, как решение задачи:

Найдем направление очередного шага: т.к.x¹лежит на, то условие(где- вектор коэффициентов при переменных в первом ограничении, на котором находится точкаx¹) запишется:

При движении из точки x¹ в точкуx² следует двигаться по граничной прямой в направлении.

Координаты точки x²определяются выражением:

или

Находим интервал изменения , при котором точка принадлежит ОДЗП, причем ограничение отбросим:

Получим интервал:

Найдем такое ¹, которое обеспечит максимумF(x)в направлении. Для этого координаты точкиx² подставляются в функциюF(x),тогда:

Значение ¹ не принадлежит ранее найденному интервалу, поэтому для расчета координат точки принимается=:

Вычисляются составляющие вектора градиента в точке x²:

_{Вектор градиента не перпендикулярен вектору S1, но при выборе дальнейшего направления из условия:}

_{И при движении вдоль оси ординат не происходит улучшения экстремального значения функции, следовательно, мы находимся в точке экстремума функции с учетом ограничений. А значение функции цели в этой точке равно:}

Рисунок 3.3 - Графическая интерпретация метода допустимых направлений Зойтендейка

3.3.2 Метод линейных комбинаций

Условие задания:

Вычислим градиент функции F(x):

;

.

На следующем этапе вычислим значение градиента в точке x₀:

Суть метода линейных комбинаций заключается в линеаризации функции F(x) и замене ее линейной функцией в соответствии с выражением:

Решаем задачу линейного программирования при следующих ограничениях:

Процедура решения задачи иллюстрируется следующей симплекс таблицей:

Таблица 3.1

Таблица 3.2

Получено оптимальное допустимое решение, которое имеет вид:

Произведем корректировку найденного решения в соответствии с выражением:

Найдем значение , которое доставляет экстремальное значение функцииF(x¹):

Определяем интервал допустимых значений для ⁰, при котором точкаx¹будет принадлежать ОДЗП. Для этого подставим координаты точкиx¹в ограничения задачи:

=>

Тогда:

Величина , не входит в наш интервал, тогда=1. Координаты точкии значение градиента функции в этой точкеопределяются выражениями

Линеаризуем функцию F(x) относительно точки x1 и заменим ее линейной функцией w(x1):

Решаем задачу линейного программирования при следующих ограничениях:

Процедура решения задачи иллюстрируется следующей симплекс таблицей:

Таблица 3.3

Таблица 3.4

Решение данной таблицы допустимо и оптимально, следовательно решение имеет вид:

Так как полученная точка является точкой предыдущего шага, следовательно, нет продвижения к точке экстремума, мы находимся в точке экстремума задачи с учетом ограничений.

Значение функции цели в этой точке равно:

Рисунок 3.4 - Графическая интерпретацияметода линейных комбинаций.