Градиентный метод оптимизации с равномерным поиском
Содержание
Введение
Глава I.
Теоретическая часть
. Постановка
задачи оптимизации
.1
Необходимые и достаточные условия экстремума
.2
Характеристика класса задачи и ее место в общей классификации оптимизационных
задач
.3 Описание
метода решения и расчетного алгоритма
Глава II.
Практическая часть
. Разработка
компьютерной программы для решения задачи оптимизации градиентным методом с
использованием равномерного поиска
.1 Разработка
блок-схемы машинного алгоритма и программы
.2 Проверка
необходимых и достаточных условий экстремума для найденной точки минимума
.3 Разработки
программы проверки ограничений
Заключение
Список
литературных источников
Введение
Область применения оптимизационных задач чрезвычайно широка, любая
деятельность связана с решением задач оптимизации.
К примеру, это такие сферы как: распределение ресурсов в экономике,
управленческие решения в социальной сфере, проектирование технических устройств
и систем и это лишь некоторые сферы.
Целью курсового проекта является применение полученных в данном курсе
знаний и умений на практике при решении задачи оптимизации с использованием
современного инструментария на основе встроенного прикладного программного
обеспечения вычислительных систем.
Задачи к выполнению курсовой работы:
1. Проверить необходимые условия существования экстремума многомерной
функции для своего варианта функции.
Воспользоваться средствами Mathcad,
составив программу.
. Проверить достаточные условия существования экстремума многомерной
функции для своего варианта функции.
Воспользоваться средствами Mathcad,
составив программу.
. Разработать машинный алгоритм и программу в Mathcad многомерной оптимизации.
. Определить по составленной программе в Mathcad экстремум функции.
. Проверить ограничения используя программу в Mathcad.
Исходные данные: Целевая функция
Z(x, y) = F(x) + H(y)
Где
Критерий оптимизации: точка экстремума (локальный экстремум)
Метод оптимизации: градиентный метод с использованием метода равномерного
поиска.
Компьютерные средства: Вычислительная среда Mathcad.
Глава I. Теоретическая часть
1. Постановка
задачи оптимизации
Оптимизация - выбор предпочтительного варианта проекта по принятым
критериям.
В основе оптимизации лежит функция цели Z(x,y), которая строиться на основе суммы
двух других целевых функций
и
, и
характеризует качество объекта.
1.1. Необходимые
и достаточные условия экстремума
Необходимым условием экстремума функции в точке Хо является равенство
нулю всех первых производных или равенство нулю градиента функции.
Достаточным условием минимума функции является положительная
определенность G[F(X)] |x=xo условием максимума является
отрицательная определенность G[F(X)] |x=xo ;
Матрица G[F(X)] положительно определенная, если
все миноры главной диагонали от 1 до n положительны, тогда F(Xm)=minF(X). Если все миноры главной диагонали отрицательны, то
F(Xm)=max F(X).
1.2. Характеристика
класса задачи и ее место в общей классификации оптимизационных задач
Задача, представленная в курсовой работе, имеет два критерия оптимизации x и y, следовательно, она многокритериальная. Так же она является
параметрической, так как область определения целевой функции Z(x,y) непрерывное
множество точек. Будем считать, что функция унимодальна и имеет параметрические
ограничения.
Представленная многокритериальная задача является многомерной, с
ограничениями, и будет решаться с помощью нелинейного программирования.
Градиентный метод, в соответствии с нашей задачей, можно классифицировать
как: многомерный, численный, поисковый, при ограничениях.
1.3. Описание
метода решения и расчетного алгоритма
Метод градиента основан на том, что вектор градиента в каждой точке Х Î ХN совпадает с направлением
наискорейшего возрастания функции.
Требуется найти: minF(X), если XÎ XN, x=x(x1, x2 ,.., xn), N=1,..,.n.
Алгоритм метода.
. Выбор стартовой точки Хо.
. Вычислить F(X) и gradF(X)
. Из точки х11 и из любой точки хi,k в антиградиентном направлении с
шагом hi в xi,k+1 и т.д. по формуле:
где « - » из-за антиградиентного направления.
. Вычисление F(X) на каждом
шаге, если Fk+1 < Fk, то
Графическая интерпретация метода градиента для двумерного случая
приведена на рисунке 1. Целевая функция отображена линиями уровней:
F(x)=const=a, а траектория движения к точке оптимума - {х0, х1, х2, х3 , х4,
х5}
Рисунок 1 - Траектория движения к точке оптимума по методу градиента
Вычисление градиента в точке x0 начинается с серии пробных шагов. Сначала величине x1 дается небольшое
приращение ∆ x1> 0, причем в это время x2 неизменно. Затем
определяется полученное при этом приращении значение ΔF, которое можно считать
пропорциональным значению величины частной производной в рассматриваемой точке.
Далее дается приращение величины x2. В это время значение x1 -постоянно.
Получаемое при этом приращение ∆F является мерой другой частной производной.
После нахождения составляющих градиента делаются шаги в направлении
вектора градиента, если стоит задача определения максимума и в направлении
противоположном, если решается задача поиска минимума.
Таким образом, определяются новые значения x1 и x2 в соответствующей
точке. После каждого шага оценивается приращение ΔF величины F.
Если ΔF>0
при поиске максимума или ΔF<0 при поиске минимума, то движение происходит в
правильном направлении, иначе необходимо уменьшить величину шага.
Численное значение координаты при движении по градиенту для переменной xi
в последующей k+1 точке вычисляется при помощи численного значения этой
координаты на предыдущем шаге по следующей формуле:
xi,k+1 = xi,k ± hk * Si,k (+ для поиска
максимума; - для поиска минимума),
где,
=1,2 , …
,n ; k=0,1,2, … ,.
n - число
варьируемых переменных, k - номер шага поиска.
Величина
называется
нормой градиента в соответствующей
точке
поиска экстремума целевой функции и вычисляется по формуле:
hk - шаг поиска
в точке, который выбирается произвольно.
Глава II. Практическая часть
2. Разработка
компьютерной программы для решения задачи оптимизации градиентным методом с
использованием равномерного поиска
2.1. Разработка
блок-схемы машинного алгоритма и программы
Программа для нахождения минимума будет начинаться с функции L(x0,y0,e), входными параметрами которой
являются x0 - точка приближения по x, y0 - точка приближения по 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)
2.2. Проверка
необходимых и достаточных условий экстремума для найденной точки минимума
Для проверки необходимого условия существования экстремума функции найдем
первую производную Zpr(x,y) от целевой функции Z(x,y) и подставим получившиеся координаты
точек x и y. Производная равна нулю (учитывая допустимую погрешность),
следовательно, необходимое условие существования экстремума выполнено.
А для проверки достаточного условия нужно построить матрицу Гессе и с
помощью встроенной функции в Mathcad
найти её определитель, подставив координаты полученной точки.
Реализуем алгоритм проверки необходимого условия в Mathcad. Листинг программы представлен на
рисунке 8.
Рисунок 8 - Листинг программы по проверке необходимого условия
Реализуем программу для проверки достаточного условия. Листинг программы
представлен на рисунке 9.
Рисунок 9 - Листинг программы по проверке достаточного условия
По выполненной программе на рисунке 9 можно сделать вывод, что матрица
Гессе положительно определена, это означает то что мы нашли точку минимума.
2.3. Разработки
программы проверки ограничений
Для проверки ограничений оптимизационной задачи рассмотренной в курсовой
работе, мной была разработана программа. Функция программы названа Proverka. Программа заключается в том что, мы
задаем два условия: если значение точки x попадает в промежуток от Ax до By и
если значение y попадает в промежуток от Ay и By, которые должны быть верными и перемножаем их, в итоге
программа должна выдать значение 1 (истина). На листинге программе приведенной
на рисунке 9, мы видим, что найденная точка попадает в область допустимых
значений.
Рисунок 10 - Листинг программы проверки ограничений
Заключение
В курсовой работе был рассмотрен градиентный метод оптимизации с
равномерным поиском. Составлена программа в Mathcad, реализующая этот метод. Была найдена точка оптимума,
являющаяся минимумом Z(x,y)=5.7332. В ней выполняются необходимые и достаточные
условия.
Градиентный метод является эффективным. Однако могут возникнуть трудности
с вычислением и исследованием матрицы вторых производных (матрицы Гессе).
Список
литературных источников
1. Сыроежкин
Е.В. Методические указания по дисциплине «Методы оптимизации в управлении». -
Москва, 2012 - 30с.
2. Жилинскас
А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности.- М.: Наука,
1989.- 128 с
3. Химмельблау
Д. Прикладное нелинейное программирование.- М.: Мир, 1975. -534 с.