3. Описание метода решения и расчетного алгоритма

Метод градиента основан на том, что вектор градиента в каждой точке Х  ХN совпадает с направлением наискорейшего возрастания функции.

Требуется найти: minF(X), если X XN, x=x(x₁, x₂ ,.., x_n), N=1,..,.n.

Алгоритм метода.

1. Выбор стартовой точки Хо.

2. Вычислить F(X) и gradF(X)

3. Из точки х₁₁ и из любой точки х_i,k в антиградиентном направлении с шагом h_i в x_i,k+1 и т.д. по формуле:

где « – » из-за антиградиентного направления.

4. Вычисление F(X) на каждом шаге, если F_k+1 < F_k, то

Графическая интерпретация метода градиента для двумерного случая приведена на рисунке 1. Целевая функция отображена линиями уровней: F(x)=const=a, а траектория движения к точке оптимума – {х₀, х₁, х₂, х₃ , х₄, х₅}

Рисунок 1 - Траектория движения к точке оптимума по методу градиента

Вычисление градиента в точке x₀ начинается с серии пробных шагов. Сначала величине x₁ дается небольшое приращение ∆ x₁> 0, причем в это время x₂ неизменно. Затем определяется полученное при этом приращении значение ΔF, которое можно считать пропорциональным значению величины частной производной в рассматриваемой точке.

Далее дается приращение величины x₂. В это время значение x₁ -постоянно. Получаемое при этом приращение ∆F является мерой другой частной производной.

После нахождения составляющих градиента делаются шаги в направлении вектора градиента, если стоит задача определения максимума и в направлении противоположном, если решается задача поиска минимума.

Таким образом, определяются новые значения x₁ и x₂ в соответствующей точке. После каждого шага оценивается приращение ΔF величины F.

Если ΔF>0 при поиске максимума или ΔF<0 при поиске минимума, то движение происходит в правильном направлении, иначе необходимо уменьшить величину шага.

Численное значение координаты при движении по градиенту для переменной x_i в последующей k+1 точке вычисляется при помощи численного значения этой координаты на предыдущем шаге по следующей формуле:

x_i,k+1 = x_i,k ± h_k * S_i,k

(+ для поиска максимума; – для поиска минимума),

где,

i =1,2 , … ,n ; k=0,1,2, … ,.

n – число варьируемых переменных, k – номер шага поиска.

Величина называется нормой градиента в соответствующей

точке поиска экстремума целевой функции и вычисляется по формуле:

h_k – шаг поиска в точке, который выбирается произвольно.

Глава II. Практическая часть

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

1. Разработка блок-схемы машинного алгоритма и программы

Программа для нахождения минимума будет начинаться с функции L(x0,y0,e), входными параметрами которой являются x₀ - точка приближения по x, y₀ - точка приближения по y и точность приближенного решения e. Равномерный поиск реализован основным соотношением:

Результатом функции будет значение аргументов функции, доставляющих минимум рассматриваемой функции, само значение этого минимума. Приведем блок-схему машинного алгоритма (Рисунок 2).

Рисунок 2 – Блок-схема программы

Реализация градиентного метода в Mathcad представлена на рисунке 3.

Рисунок 3 – Листинг программы в Mathcad

Результат выполнения программы представлен на рисунке 4.

Рисунок 4 – Результат выполнения программы

Результат, выданный программой, показывает координаты точки минимума x=0.67859 y=0.65174 и значение функции в этой точке Z(x,y)=5.73321.

Построим графики функций (Рисунок 5, Рисунок 6).

Рисунок 5 – График функции F(x)

Рисунок 6 – График функции H(y)

По графикам на рисунках 5 и 6 видно, что экстремум функции попадает в заданную область ограничений.

Так же построим 3D график нашей функции цели Z(x,y).

Рисунок 7 – 3D график функции цели Z(x,y)