86088 (612638), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Метод золотого сечения. Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2 , обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = , тогда симметрично расположенная точка х1 = 1– (рис. 2.7).

Рис. 2.7. Определение пробных точек в методе золотого сечения

Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2 = 1– нового отрезка [0; т]. Чтобы точки х2 = , и х2 = 1– делили отрезки [0; 1] и [0; ] в одном и том же отношении, должно выполняться равенство

или

,

откуда находим положительное значение

…

Таким образом,

х1 = 1– = , .

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

;

В таблице 2 приведено решение задания по варианту.

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

Шаг 1. Найти х1 и х2 по формулам (2.15). Вычислить f (x1) и f (x2). Положить ,

.

Шаг 2. Проверка на окончание поиска: если n > , то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) f (x2) то положить b=x2 , x2=x1 , f (x2) f (x1), x1=b–(b–a) и вычислить f (x1), иначе – положить a=x1, x1= x2 , f (x1) = f (x2), x2=b+(b–a) и вычислить f (x2). Положить n = n и перейти к шагу 2.

Шаг 4. Окончание поиска: положить

, .

Результаты вычислений на остальных итерациях представлены в таблице 2 .

Таблица 2 - Метод золотого сечения

|a-b|=7.893370498E-3< ε, x*=(a+b)/2=3.1407091

f(x*)=-5.807126299

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

2 Прямые методы безусловной оптимизации многомерной функции

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

Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. В основном все методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Будем предполагать, что точка минимума существует. Однако в реальных задачах это предположение может не выполняться.

Для изучения прямых методов безусловной оптимизации многомерной функции была дана функция:

F(x1,x2)=a*x*y+(b*y+c*x)/x*y → min

a=5 b=3.5 c=2.5

x1=

x2=

2.1 Метод покоординатного циклического спуска

Суть метода заключается в том, что в начальном базисе закрепляется значение одной координаты, а переменными считаются остальные, и по этой координате производится одномерная оптимизация

базисная точка переносится в

,

базисная точка переносится в

Циклы повторяются до тех пор, пока в ε окрестности найденной базисной точки будет улучшение функции. Решением поставленной задачи является точка в ε окрестности которой функция не принимает значение, лучшие, чем в этой точке.

Для решения поставленной задачи выбрано приближение ε=0,01 α=0,15

Таблица 3 - Метод покоординатного циклического спуска

α/2< ε, x1=0,2295 x2=0,4145 Z(x1,x2)= -0,8479571

2.2 Метод Хука – Дживса

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке 4.

Характеристики

Список файлов курсовой работы