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

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

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

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

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

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

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

x₁=b - ,

x₂=a +

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

Алгоритм

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

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

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

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

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

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

Шаг 2. Рассчитывают начальные точки деления: x₁=b - , x₂=a + и значения в них целевой функции: y₁=f(x₁), y₂=f(x₂).

Если y₁ ≥ y₂(для поиска max изменить неравенство на y₁ ≤ y₂), то a=x₁

Иначе b=x₂.

Шаг 3.

Если , то x = и останов.

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

Задача 2

Найти min функции f(x)=18 – 20х – 32 на отрезке [ 0 ; 40 ] за 8 шагов.

Решение:

F_n+1 = F₁₀ = 55;

F_n+1 = F₉ = 34;

F_n = F₈ = 21;

F_n-1 = F₇ = 13;

F_n-2 = F₆ = 8;

F_n-3 = F₅ = 5;

F_n-4 = F₄ = 3;

F_n-5 = F₃ = 2;

F_n-6 = F₂ = 1;

F_n-7 = F₁ = 1;

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

Х₁¹ = а + ∙( b - a ) = a + ∙( b – a ) = ∙ 40 = 15,2

X₂¹ = a+ ∙( b – a ) = a + ∙( b – a ) = ∙ 40 = 24,72

f (x₁¹)=18x² - 20x - 32= 18 ∙(15,2)² – 20∙ (15,2) - 32 = 4158,72 - 304 - 32 = 3822,72

f(x₂¹)= 18x² - 20x – 32=18∙(24,72)² – 20∙(24,72) - 32 = 10998 - 494,4 - 32=10471,6

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

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

x₁² = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 24,72 = 9,4

x₂² = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 24,72 = 15,4

f(x₁²) = 18x² - 20x – 32 = 18 ∙ ( 9,4 )² – 20 ∙ ( 9,4 ) – 32 = 1590,48 – 188 - 32 = 1370,48

f(x₂²)= 18x² - 20x – 32 = 18 ∙ ( 15,3 )² – 20 ∙ ( 15,3 ) – 32 = 4213,62 – 306 – 32 = 3875,62

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

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

x₁³= a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 15,3 = 5,8

x₂³= a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 15,3 = 9,5

f(x₁³) = 18x² - 20x – 32 = 18 ∙ ( 5,8 )² – 20 ∙ ( 5,8 ) – 32 = 605,52 – 116 – 32 = 457,52

f(x₂³) = 18x² - 20x – 32 = 18 ∙ ( 9,5 )² – 20 ∙ ( 9,5 ) – 32 = 1624,5 – 190 – 32 = 1402,5

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

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

x₁⁴ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 9,5 = 3,61

x₂⁴ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 9,5 = 5,8

f(x₁⁴) = 18x² - 20x – 32 = 18 ∙ ( 3,61 )² – 20 ∙ ( 3,61 ) – 32 = 234 – 72,2 – 32 = 129,8

f(x₂⁴) = 18x² - 20x – 32 = 18 ∙ ( 5,8 )² – 20 ∙ ( 5,8 ) – 32 = 605,52 – 116 – 32 = 457,52

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

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

x₁⁵ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 5,8 = 2,18

x₂⁵ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 5,8 = 3,63

f(x₁⁵) = 18x² - 20x – 32 = 18 ∙ ( 2,18 )² – 20 ∙ ( 2,18 ) – 32 = 85,5 – 43,6 – 32 = 9,9

f(x₂⁵) = 18x² - 20x – 32 = 18 ∙ ( 3,63 )² – 20 ∙ ( 3,63 ) – 32 = 237,06 – 72,6 – 32 = 132,46

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

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

x₁⁶ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 3,63 = 1,5

x₂⁶ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 3,63 = 2,2

f(x₁⁶) = 18x² - 20x – 32 = 18 ∙ ( 1,5 )² – 20 ∙ ( 1,5 ) – 32 = 40,5 – 30 – 32 = -21,5

f(x₂⁶) = 18x² - 20x – 32 = 18 ∙ ( 2,2 )² – 20 ∙ ( 2,2 ) – 32 = 87,12 – 44 – 32 = 11,12

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

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

x₁⁷ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 2,2 = 0,726

x₂⁷ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 2,2 = 1,47

f(x₁⁷) = 18x² - 20x – 32 = 18 ∙ ( 0,726 )² – 20 ∙ ( 0,726 ) – 32 = 9,486 – 14,52 – 32 = -37,034

f(x₂⁷) = 18x² - 20x – 32 = 18 ∙ ( 1,47 )² – 20 ∙ ( 1,47 ) – 32 = 38,88 – 29,4 – 32 = -22,52

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

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

x₁⁸ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 1,47 = 0,735

X₂⁸ = a + ∙ ( b – a ) = a + ∙ ( b – a ) = ∙ 1,47 = 0,735

f(x₁⁸) = 18x² - 20x – 32 = 18 ∙ ( 0,735 )² – 20 ∙ ( 0,735 ) – 32 = 9,72 – 14,7 – 32 = -36,98

f(x₂⁸) = 18x² - 20x – 32 = 18 ∙ ( 0,735 )² – 20 ∙ ( 0,735 ) – 32 = 9,72 – 14,7 – 32 = -36,98

f( x₁⁸ ) = f( x₂⁸ ) = -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/;

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