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

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

Описание метода

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

Метод золотого сечения - student2.ru

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

Метод золотого сечения - student2.ru = Метод золотого сечения - student2.ru = φ = Метод золотого сечения - student2.ru = 1.618…, где φ— пропорция золотого сечения.

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

x1=b - Метод золотого сечения - student2.ru ,

x2=a + Метод золотого сечения - student2.ru

То есть точка x1 делит отрезок [a, x2]в отношении золотого сечения. Аналогично x2 делит отрезок [x1, b]в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

1) На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.

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

3) На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.

4) Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

Формализация

Шаг 1. Задаются начальные границы отрезка a, b и точность Ɛ.

Шаг 2. Рассчитывают начальные точки деления: x1=b - Метод золотого сечения - student2.ru , x2=a + Метод золотого сечения - student2.ru и значения в них целевой функции: y1=f(x1), y2=f(x2).

Если y1 ≥ y2(для поиска max изменить неравенство на y1 ≤ y2), то a=x1

Иначе b=x2.

Шаг 3.

Если Метод золотого сечения - student2.ru , то x = Метод золотого сечения - student2.ru и останов.

Иначе возврат к шагу 2.

Задача 2

Найти min функции f(x)=18 Метод золотого сечения - student2.ru – 20х – 32 на отрезке [ 0 ; 40 ] за 8 шагов.

Решение:

Fn+1 = F10 = 55;

Fn+1 = F9 = 34;

Fn = F8 = 21;

Fn-1 = F7 = 13;

Fn-2 = F6 = 8;

Fn-3 = F5 = 5;

Fn-4 = F4 = 3;

Fn-5 = F3 = 2;

Fn-6 = F2 = 1;

Fn-7 = F1 = 1;

Интеграция 1.

Х11 = а + Метод золотого сечения - student2.ru ∙( b - a ) = a + Метод золотого сечения - student2.ru ∙( b – a ) = Метод золотого сечения - student2.ru ∙ 40 = 15,2

X21 = a+ Метод золотого сечения - student2.ru ∙( b – a ) = a + Метод золотого сечения - student2.ru ∙( b – a ) = Метод золотого сечения - student2.ru ∙ 40 = 24,72

f (x11)=18x2 - 20x - 32= 18 ∙(15,2)2 – 20∙ (15,2) - 32 = 4158,72 - 304 - 32 = 3822,72

f(x21)= 18x2 - 20x – 32=18∙(24,72)2 – 20∙(24,72) - 32 = 10998 - 494,4 - 32=10471,6

f(x11) < f(x21), следовательно отрезок ограничен [ 0 ; 24,72 ].

Интеграция 2.

x12 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 24,72 = 9,4

x22 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 24,72 = 15,4

f(x12) = 18x2 - 20x – 32 = 18 ∙ ( 9,4 )2 – 20 ∙ ( 9,4 ) – 32 = 1590,48 – 188 - 32 = 1370,48

f(x22)= 18x2 - 20x – 32 = 18 ∙ ( 15,3 )2 – 20 ∙ ( 15,3 ) – 32 = 4213,62 – 306 – 32 = 3875,62

f( x12 ) < f( x22 ), следовательно отрезок ограничен [ 0 ; 15,3 ].

Интеграция 3.

x13= a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 15,3 = 5,8

x23= a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 15,3 = 9,5

f(x13) = 18x2 - 20x – 32 = 18 ∙ ( 5,8 )2 – 20 ∙ ( 5,8 ) – 32 = 605,52 – 116 – 32 = 457,52

f(x23) = 18x2 - 20x – 32 = 18 ∙ ( 9,5 )2 – 20 ∙ ( 9,5 ) – 32 = 1624,5 – 190 – 32 = 1402,5

f( x13 ) < f( x23 ), следовательно отрезок ограничен [ 0 ; 9,5 ].

Интеграция 4.

x14 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 9,5 = 3,61

x24 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 9,5 = 5,8

f(x14) = 18x2 - 20x – 32 = 18 ∙ ( 3,61 )2 – 20 ∙ ( 3,61 ) – 32 = 234 – 72,2 – 32 = 129,8

f(x24) = 18x2 - 20x – 32 = 18 ∙ ( 5,8 )2 – 20 ∙ ( 5,8 ) – 32 = 605,52 – 116 – 32 = 457,52

f( x14 ) < f( x24 ), следовательно отрезок ограничен [ 0 ; 5,8 ].

Интеграция 5.

x15 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 5,8 = 2,18

x25 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 5,8 = 3,63

f(x15) = 18x2 - 20x – 32 = 18 ∙ ( 2,18 )2 – 20 ∙ ( 2,18 ) – 32 = 85,5 – 43,6 – 32 = 9,9

f(x25) = 18x2 - 20x – 32 = 18 ∙ ( 3,63 )2 – 20 ∙ ( 3,63 ) – 32 = 237,06 – 72,6 – 32 = 132,46

f( x15 ) < f( x25 ), следовательно отрезок ограничен [ 0 ; 3,63 ].

Интеграция 6.

x16 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 3,63 = 1,5

x26 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 3,63 = 2,2

f(x16) = 18x2 - 20x – 32 = 18 ∙ ( 1,5 )2 – 20 ∙ ( 1,5 ) – 32 = 40,5 – 30 – 32 = -21,5

f(x26) = 18x2 - 20x – 32 = 18 ∙ ( 2,2 )2 – 20 ∙ ( 2,2 ) – 32 = 87,12 – 44 – 32 = 11,12

f( x16 ) < f( x26 ), следовательно отрезок ограничен [ 0 ; 2,2 ].

Интеграция 7.

x17 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 2,2 = 0,726

x27 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 2,2 = 1,47

f(x17) = 18x2 - 20x – 32 = 18 ∙ ( 0,726 )2 – 20 ∙ ( 0,726 ) – 32 = 9,486 – 14,52 – 32 = -37,034

f(x27) = 18x2 - 20x – 32 = 18 ∙ ( 1,47 )2 – 20 ∙ ( 1,47 ) – 32 = 38,88 – 29,4 – 32 = -22,52

f( x17 ) < f( x27 ), следовательно отрезок ограничен [ 0 ; 1,47 ].

Интеграция 8.

x18 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 1,47 = 0,735

X28 = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = a + Метод золотого сечения - student2.ru ∙ ( b – a ) = Метод золотого сечения - student2.ru ∙ 1,47 = 0,735

f(x18) = 18x2 - 20x – 32 = 18 ∙ ( 0,735 )2 – 20 ∙ ( 0,735 ) – 32 = 9,72 – 14,7 – 32 = -36,98

f(x28) = 18x2 - 20x – 32 = 18 ∙ ( 0,735 )2 – 20 ∙ ( 0,735 ) – 32 = 9,72 – 14,7 – 32 = -36,98

f( x18 ) = f( x28 ) = -36,98 – точка min функции.

Ответ: min f(x)= -36,98

Заключение

Перечислим свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:

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

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

3. Целевая функция f может быть не дифференцируемой, что затрудняет применение классических методов математического анализа.

В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения.

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

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

Список использованной литературы

Сайт http://ru.wikipedia.org/wiki ;

Сайт http://revolution.allbest.ru;

Сайт http://fessagicadif.web44.net;

Карманов В.Г. Математическое программирование = Математическое программирование. — Изд-во физ.-мат. литературы, 2004

Кузнецов А.В. Математическое программирование: учебное пособие для вузов. – М.: Высшая школа, 1976. – 352с.

Павлова Т. Н. Линейное программирование: учебное пособие / Т. Н. Павлова, О. А. Ракова. – Д.: 2002.

Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие.

Сайт http://xreferat.ru/;

Джон Г.Мэтьюз, Куртис Д.Финк "Численные методы.

Наши рекомендации