Лабораторная работа № 12

РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ МЕТОДОМ "ЗОЛОТОГО СЕЧЕНИЯ"

 

1. Цель работы.

 

Изучить методику нахождения экстремума функции одной переменной с использованием "золотой пропорции".

 

2. Исходные данные

 

Целевая функция и область допустимых значений аргумента принимаются по табл.1 лаб. работы № 11 в зависимости от номера варианта . Точность поиска решения 0,001 .

 

3. Содержание работы

 

3.1. Разработать алгоритм и программу для определения экстремума функции методом "золотого сечения".

3.2. Рассчитать на ЭВМ оптимальное значение аргумента и соответствующее экстремальное значение функции. В процессе расчета на печать выводить координаты граничных точек отрезка локализации экстремума.

3.3. Сравнить число итераций, необходимых для нахождения экстремума функции при поиске методами дихотомии и “золотого сечения”.

 

4. Теоретические основы работы

 

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

 

 

 

 

Рис.1

 

Границы отрезка [а,в] обозначаются через Х0 и Х3 соответственно. Внутри отрезка

локализации экстремума [Х0,Х3] выбираются точки Х1 и Х2 ( рис 1.) таким образом, чтобы:

1) они находились на равном расстоянии от концов отрезка, т.е.

Х1 - Х0 = Х3 - Х2 ;

2) каждая из точек делила отрезок в "золотой пропорции"

 

(Х3 – Х2)/(Х2-Х0)=(Х2-Х0)/(Х3-Х0);

( Х1-Х0)/(Х3-Х1)=(Х3-Х1)/(Х3-Х0)

 

Затем вычисляют значения функции в точках Х1 и Х2. Если f (X1) < f (X2), то вторым отрезком локализации экстремума будет отрезок [Х0 , Х2]; если же f (X1) > f (X2), то второй отрезок - [ Х1 , Х3 ].

Точка, находящаяся внутри второго отрезка локализации (для отрезка [Х0 , Х2] - это точка Х1, а для отрезка [Х1 , Х3] – точка Х2), делит этот отрезок в "золотой пропорции".

В соответствии с рис. 1 второй отрезок локализации [Х0⁽¹⁾ , Х3⁽¹⁾] делится в "золотой пропорции" точкой Х1, которая обозначается Х2⁽¹⁾ .

Следующий шаг поиска минимума состоит в определении точки Х1⁽¹⁾ ,симметричной точке Х2⁽¹⁾ относительно концов отрезка [Х0⁽¹⁾ , Х3⁽¹⁾ ]. Далее вычисляется значение функции f (X1⁽¹⁾ ), проводится сравнение f (X1⁽¹⁾ ) с f (X2⁽¹⁾ ) (значение функции f (X2⁽¹⁾ ) равно значению f (Х1) и определено ранее), выбирается очередной отрезок локализации

[X0⁽²⁾ , X3⁽²⁾ ] и т.д.

Итерационный процесс поиска продолжается до тех пор, пока очередной отрезок локализаци не станет меньше заданной погрешности определения оптимального значения Х.

При составлении алгоритма поиска рекомендуется придерживаться следующей схемы:

1) определить положение точек Х1 и Х2, делящих начальный отрезок локализации экстремума [X0 , X3] в "золотой пропорции":

 

Х1 = Х3 ─G(X3 ─ X0) ,

X2 = X0 + G(X3 ─ X0) ,

где

 

2) вычислить значение функции Y1 = f (Х1), Y2= f (Х2);

3) сравнить Y1 и Y2 : если Y2 < Y1 - исключить отрезок [X0 , X1], для чего вычислить d = Х3 - Х1, присвоить Х0 = Х1, Х1 = Х2, Y1=Y2 и определить Х2 = Х0 + G*d, Y2 = f (Х2), затем перейти к п.5;

4) если Y2 >= Y1 - исключить отрезок [X2 , X3], для чего вычислить d = Х2 - Х0, присвоить Х3 = Х2, Х2 = Х1, Y2 = Y1 и определить Х1 = Х3 ─ G*d, Y1 = f (Х1);

5) напечатать значения Х0 и Х3 ;

6) проверить условия окончания поиска : d < Е и, если условие не выполняется -перейти к п.3 ;

7) в случае окончания поиска оптимальное значение аргумента принять равным Х1, а экстремальное значение функции - Y1.

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

 

5. Содержание отчета

 

5.1. Цель работы.

5.2. Исходные данные.

5.3. Теоретические основы метода.

5.4. Схема алгоритма оптимизации.

5.5. Распечатка программы и результатов расчета.

5.6. Выводы.