Курсовая работа: Методы нелинейной оптимизации
Содержание
Постановка задачи
Определение унимодальности функции
Точный метод поиска экстремума
Приближенные методы поиска экстремума
.1 Метод перебора
.2 Метод поразрядного поиска
.3 Метод дихотомии
.4 Метод золотого сечения
.5 Метод средней точки
.6 Метод хорд
.7 Метод Ньютона
Сравнение методов
Дата добавления на сайт: 14 февраля 2025
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Нижегородский государственный архитектурно-строительный университет»
Международный факультет экономики, права и менеджмента
Расчетно-графическая работа
по дисциплине «Исследование операций и методы оптимизации»
по теме «Методы нелинейной оптимизации»
Выполнил студент
Курс III
Группа ПИэ 13.13
Преподаватель
Нижний Новгород
год
Содержание
Постановка задачи
Определение унимодальности функции
Точный метод поиска экстремума
Приближенные методы поиска экстремума
.1 Метод перебора
.2 Метод поразрядного поиска
.3 Метод дихотомии
.4 Метод золотого сечения
.5 Метод средней точки
.6 Метод хорд
.7 Метод Ньютона
Сравнение методов
1 Постановка задачи
Знакомство с оптимизационными задачами, изучение различных методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций.
Нахождение минимума функции 1/|x-3|3 методами перебора, поразрядного поиска, дихотомии, золотого сечения, средней точки, хорд и Ньютона на интервале [2;4] cточностью до e=0,05, а также сравнение методов по скорости вычисления и точности.
2 Определение унимодальности функции
нелинейный оптимизация минимум функция
Функция F(x) является унимодальной на отрезке [A, B] в том и только в том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки х* и принимаем значения f``(x)≥0.
Определим унимодальность заданной функции 1/|x-3|3 двумя способами.
Аналитический способ. Найдем последовательно первую и вторую производные функции:
3/|x-3|4
-12/|x-3|5
Для аналитического определения унимодальности необходимо решить уравнение .
Графический способ
| x | f(x) | f\'(x) | f\'\'(x) |
| 2 | 1 | 3 | 12 |
| 2,1 | 1,371742 | 4,572474 | 20,32211 |
| 2,2 | 1,953125 | 7,324219 | 36,62109 |
| 2,3 | 2,915452 | 12,49479 | 71,39882 |
| 2,4 | 4,62963 | 23,14815 | 154,321 |
| 2,5 | 8 | 48 | 384 |
| 2,6 | 15,625 | 117,1875 | 1171,875 |
| 2,7 | 37,03704 | 370,3704 | 4938,272 |
| 2,8 | 125 | 1875 | 37500 |
| 2,9 | 1000 | 30000 | 1200000 |
| 3 | #ДЕЛ/0! | #ДЕЛ/0! | #ДЕЛ/0! |
| 3,1 | 1000 | 30000 | -1200000 |
| 3,2 | 125 | 1875 | -37500 |
| 3,3 | 37,03704 | 370,3704 | -4938,27 |
| 3,4 | 15,625 | 117,1875 | -1171,88 |
| 3,5 | 8 | 48 | -384 |
| 3,6 | 4,62963 | 23,14815 | -154,321 |
| 3,7 | 2,915452 | 12,49479 | -71,3988 |
| 3,8 | 1,953125 | 7,324219 | -36,6211 |
| 3,9 | 1,371742 | 4,572474 | -20,3221 |
| 4 | 1 | 3 | -12 |
| Функция унимодальна на [2;2,9] |
3 Точный метод поиска экстремума
1) Найти производную функции .
) Найти стационарные точки (точки, подозрительные на экстремум), решив уравнение .Обратить внимание на точки, в которых не существует двусторонней конечной производной.
) Выяснить, меняет ли производная свой знак в точках, подозрительных на экстремум. Если она меняет знак с минуса на плюс, то в этой точке функция имеет свой минимум. Если с плюса на минус, то максимум, а если знак производной не меняется, то экстремума в этой точке нет.
) Найти значение функции в точках минимума (максимума).
3/|x-3|4;
/|x-3|4 ≠ 0;
- глобальный минимум .
4 Приближенные методы поиска экстремума
.1 Метод перебора
Описание:
Метод перебора - простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум , на минимум , на определённую константу).
Алгоритм:
)Разобьем отрезок [а, b] на 10 равных частей точками деления:
=a+i*(b-a)/10, i=2,...2,9
)Вычислив значения F(x) в точках . путем сравнения найдем точку
. где m - это число от 2 до 2,9. такую, что F() = minF() для всех i от 2 до 2,9.
)Погрешность определения точки минимума функции F(x) методом перебора не превосходит E=(b-a)/n.
Для заданной функции
| x | f(x) | Fmin= | 1 |
| 2 | 1 | x*= | 2 |
| 2,1 | 1,371742 | ||
| 2,2 | 1,953125 | ||
| 2,3 | 2,915452 | ||
| 2,4 | 4,62963 | ||
| 2,5 | 8 | ||
| 2,6 | 15,625 | ||
| 2,7 | 37,03704 | ||
| 2,8 | 125 | ||
| 2,9 | 1000 |
Описание:
Метод поразрядного поиска. Этот метод представляет собой усовершенствование метода перебора. Поиск точки минимума функции осуществляется с переменным шагом.
Алгоритм:
) Выбрать начальный шаг h=(b-a)/4. Положить х0=а. Вычислить F(x0).
2) Положить =+h. Вычислить F().
) Сравнить F() и F(). Если F()>F(), то перейти к шагу 4, иначе - к шагу 5.
) Положить =и F()=F(). Проверить условие принадлежности хо интервалу [а, b]. Если а :
Если (для поиска max изменить неравенство на ), то
Иначе .
)Если , то и останов. Иначе возврат к шагу 2.
Блок схема:
Для заданной функции
| E= | 0,05 | | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| номер итерации | a | b | x1 | x2 | f(x1) | f(x2) | anew | bnew | En | En 0, то интервал x>R можно исключить. Алгоритм: 1) Определить = , на заданном отрезке [a;b]. ) Вычислить f \'(). ) Проверить критерий окончания вычислений. Если кf \'() кЈe, ,перейти к шагу 5, иначе - к шагу 4. ) Перейти к новому отрезку локализации [a, b]. Если f \'() > 0, то положить b = . Иначе положить a = . Перейти к шагу 2. ) Положить x* ». Вычислить f(x*). Блок-схема: Для заданной функции
4.6 Метод хорд Описание: Ориентирован на нахождение корня уравнения f\'(x) в интервале [a;b], в котором имеются две точки N и P, в которых знаки производных различны. Алгоритм метода хорд позволяет аппроксимировать функцию f\'(x) \"хордой\" и найти точку, в которой секущая графика f\'(x) пересекает ось абсцисс. Алгоритм: В этом методе кривая f(x) заменяется прямой линией - хордой. В зависимости от знака выражения f(a)*f //(a) метод хорд имеет два варианта. Если f(a) f //(a)>0, то x0=b и . Если же f(a) f //(a)<0, то x0=a и . Окончание итерационного цикла в этом методе происходит по условию: |f(x1)| < ε или . Блок-схема: Для заданной функции:
Так как x*=1,749944 не попадает на отрезок [2;2,9], то приравняем x к самому наиближайшему числу на отрезке. x=2 , следовательно Fmin = 1. 4.7 Метод Ньютона Описание: Ориентирован на нахождение корня уравнения f\'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Работа алгоритма начинается из точки xo, которая представляет начальное приближение корня уравнения f\'(x)=0. Далее строится линейная аппроксимация функции f\'(x) в точке x1, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения. Если точка xk принята в качестве текущего приближения к оптимальной точке, то линейная функция, аппроксимирующая функцию f\'(x) в точке xk, записывается в виде f\'(x,xk) = f\'(xk) + f\'\'(xk)(x-xk) Алгоритм: ) В качестве начального приближения задается любой корень уравнения, который находится одним из прямых методов. ) В точке F(x0) строится касательная к кривой у = F(x) и ищется ее пересечение с осью х. Точка пересечения принимается за новую итерацию. Метод Ньютона самый быстрый способ нахождения корней уравнений. ) Высчитываем по формуле: ) Итерационный процесс проходит до того времени, пока не будет выполнено условиее . где е - заданная точность. Блок схема: Для заданной функции:
Сравнение методов
Для данной функции самыми точными оказались: Точный метод , метод перебора, метод средней точки и метод поразрядного поиска Так же метод дихотомии и метод средней точки довольно хорошо себя показали. Метод хорд и метод Ньютона для данной функции оказались самыми неэффективными. Комментарии:Вы не можете оставлять комментарии. Пожалуйста, зарегистрируйтесь. ▲ ▼ |