Методы нелинейной оптимизации

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования

«Нижегородский государственный архитектурно-строительный университет»

Международный факультет экономики, права и менеджмента

Расчетно-графическая работа

по дисциплине «Исследование операций и методы оптимизации»

по теме «Методы нелинейной оптимизации»

Выполнил студент Курс III

Группа ПИэ 13.13

Преподаватель Нижний Новгород

2015 год

1 Постановка задачи

2 Определение унимодальности функции

3 Точный метод поиска экстремума

4 Приближенные методы поиска экстремума

4.1 Метод перебора

4.2 Метод поразрядного поиска

4.3 Метод дихотомии

4.4 Метод золотого сечения

4.5 Метод средней точки

4.6 Метод хорд

4.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

Для аналитического определения унимодальности необходимо решить уравнение .

Графический способ

3 Точный метод поиска экстремума

1) Найти производную функции .

2) Найти стационарные точки (точки, подозрительные на экстремум), решив уравнение. Обратить внимание на точки, в которых не существует двусторонней конечной производной.

3) Выяснить, меняет ли производная свой знак в точках, подозрительных на экстремум. Если она меняет знак с минуса на плюс, то в этой точке функция имеет свой минимум. Если с плюса на минус, то максимум, а если знак производной не меняется, то экстремума в этой точке нет.

4) Найти значение функции в точках минимума (максимума).

3/|x-3|4;

3/|x-3|4? 0;

— глобальный минимум .

4 Приближенные методы поиска экстремума

4.1 Метод перебора Описание:

Метод перебора — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу).

Алгоритм:

1)Разобьем отрезок [а, b] на 10 равных частей точками деления:

=a+i*(b-a)/10, i=2,…2,9

2)Вычислив значения F (x) в точках. путем сравнения найдем точку

. где m — это число от 2 до 2,9. такую, что F () = minF () для всех i от 2 до 2,9.

3)Погрешность определения точки минимума функции F (x) методом перебора не превосходит E=(b-a)/n.

Для заданной функции

4.2 Метод поразрядного поиска Описание:

Метод поразрядного поиска. Этот метод представляет собой усовершенствование метода перебора. Поиск точки минимума функции осуществляется с переменным шагом.

Алгоритм:

1) Выбрать начальный шаг h=(b-a)/4. Положить х0=а. Вычислить F (x0).

2) Положить =+h. Вычислить F ().

3) Сравнить F () и F (). Если F ()>F (), то перейти к шагу 4, иначе — к шагу 5.

4) Положить =и F ()=F (). Проверить условие принадлежности хо интервалу [а, b]. Если, а <

5) Проверка на окончание поиска: если |h| <= e, то вычисления завершить, полагая х*=, Fmin=F (), иначе — перейти к шагу 6.

6) Изменить направление поиска: положить =, F ()=F (), h=-h/4.Перейти к шагу 2.

Для заданной функции:

Блок-схема:

4.3 Метод дихотомии

Описание:

Этот метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Алгоритм:

Дана функция F (x). Необходимо найти, доставляющий минимум (или максимум) функции F (x) на интервале [a, b] с заданной точностью .

1) На каждом шаге процесса поиска делим отрезок [a, b] пополам, x=(a+b)/2 — координата середины отрезка [a, b].

2) Вычисляем значение функции F (x ±вычисленной точки x.

3) Сравниваем F1 и F2 и отбрасываем одну из половинок отрезка [a, b].

Если F1

4) Деление отрезка [a, b] продолжается, пока его длина не станет меньше заданной точности, т. е.

Блок схема:

Для заданной функции

4.4 Метод золотого сечения Описание:

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

Алгоритм:

1) Задаются начальные границы отрезка [a; b] и точность .

2) Рассчитывают начальные точки:

и значения в них целевой функции:

Если (для поиска max изменить неравенство на), то

Иначе .

3)Если, то и останов. Иначе возврат к шагу 2.

Блок схема:

Для заданной функции

4.5 Метод средней точки Описание: основан на алгоритме исключения интервалов, на каждой итерации которого рассматривается одна пробная точка R. Если в точке R выполняется неравенство f'® < 0, то в следствии унимодальности функции точка оптимума не может лежать левее точки R. Аналогично, если f'® > 0, то интервал x>R можно исключить.

Алгоритм:

1) Определить =, на заданном отрезке [a;b].

2) Вычислить f '().

3) Проверить критерий окончания вычислений. Если f '(),, перейти к шагу 5, иначе — к шагу 4.

4) Перейти к новому отрезку локализации [a, b]. Если f '() > 0, то положить b =. Иначе положить a =. Перейти к шагу 2.

5) Положить 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,749 944 не попадает на отрезок [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)

Алгоритм:

1) В качестве начального приближения задается любой корень уравнения, который находится одним из прямых методов.

2) В точке F (x0) строится касательная к кривой у = F (x) и ищется ее пересечение с осью х. Точка пересечения принимается за новую итерацию. Метод Ньютона самый быстрый способ нахождения корней уравнений.

3) Высчитываем по формуле:

4) Итерационный процесс проходит до того времени, пока не будет выполнено условиее. где е — заданная точность.

Блок схема:

Для заданной функции:

Сравнение методов

Для данной функции самыми точными оказались: Точный метод, метод перебора, метод средней точки и метод поразрядного поиска Так же метод дихотомии и метод средней точки довольно хорошо себя показали. Метод хорд и метод Ньютона для данной функции оказались самыми неэффективными.