Алгоритм применения метода «золотого сечения».

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

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

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

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

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

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

2. Шаг 2. Рассчитывают начальные точки деления:

(2.1.4)

(2.1.5)

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

(2.1.6)

(2.1.7)

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

Иначе .

3. Шаг 3.

Если , то и останавливаемся.

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

Решение задач нелинейного программирования методом Фибоначчи.

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

Алгоритм применения метода Фибоначчи.

Шаг 1. Задаются начальные границы отрезка и число итераций n, рассчитывают начальные точки деления:

(2.2.1)

(2.2.2)

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

(2.2.3)

(2.2.4)

Шаг 2.

Если ,то

Иначе

Шаг 3.

Если , то и останавливаемся.

Иначе возврат к шагу 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. Замков О.О., Толстопятенко А.В., Черешных Ю.Н. Математические методы в экономике: Учебник. - М.: МГУ им. М.В.Ломоносова, Издательство «ДИС», 1997.

2. Конспект лекций по предмету «Основы математического моделирования социально-экономических процессов».

3. Минюк С.А. Математические методы и модели в экономике: Учеб. пособие / Минюк С.А., Ровба Е.А., Кузьмич К.К. - Мн.: ТетраСистемс, 2002.

4. Смородинский С.С., Батин Н. В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003.

5. Экономико-математические методы и модели/ Под. ред. А. В. Кузнецова. Мн.: БГЭУ.1999.