Размещено на http://www.allbest.ru/

Содержание

Введение

Глава I. Теоретическая часть

1. Постановка задачи оптимизации

1.1 Необходимые и достаточные условия экстремума

1.2 Характеристика класса задачи и ее место в общей классификации оптимизационных задач

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

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

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

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

2.2 Проверка необходимых и достаточных условий экстремума для найденной точки минимума

2.3 Разработки программы проверки ограничений

Заключение

Список литературных источников

Введение

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

К примеру, это такие сферы как: распределение ресурсов в экономике, управленческие решения в социальной сфере, проектирование технических устройств и систем и это лишь некоторые сферы.

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

Задачи к выполнению курсовой работы:

1. Проверить необходимые условия существования экстремума многомерной функции для своего варианта функции.

Воспользоваться средствами Mathcad, составив программу.

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

Воспользоваться средствами Mathcad, составив программу.

3. Разработать машинный алгоритм и программу в Mathcad многомерной оптимизации.

4. Определить по составленной программе в Mathcad экстремум функции.

5. Проверить ограничения используя программу в 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.

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

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

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

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

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

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

Графическая интерпретация метода градиента для двумерного случая приведена на рисунке 1. Целевая функция отображена линиями уровней: F(x)=const=a, а траектория движения к точке оптимума - {х0, х1, х2, х3 , х4, х5}

Размещено на http://www.allbest.ru/

Рисунок 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 (+ для поиска максимума; - для поиска минимума),

где,

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

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

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

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

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

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

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

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

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

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

алгоритм градиентный многомерный оптимизация

Размещено на http://www.allbest.ru/

Рисунок 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 с.

Размещено на Allbest.ru