Вопрос № 38. Оптимизация. Метод золотого сечения и метод перебора. Числа Фибоначчи.
Оптимизация.
Оптимальный – лучший вариант из всех возможных. Выбор оптимального решения проводится с помощью некоторой зависимой величины (функции), определяемой проектными параметрами. Эта величина называется целевой функцией (или критерием качества). Целевую ф-цию можно записать в виде y = f(x1, x2,…,xn), где число n проектных параметров x1, x2,…,xn характеризует сложность задачи оптимизации. В процессе решения задачи должны быть найдены такие значения проектных параметров, при которых целевая ф-ция имеет min(max).
Для одного проектного параметра y=f(x1) целевая ф-ция является ф-цией одной переменной и её график – некоторая кривая на плоскости.
Для двух проектных параметров y=f(x1, x2) целевая ф-ция является ф-цией двух переменных и её график – поверхность.
Задачи оптимизации:
- Безусловные (нет никаких ограничений);
- Условные (накладываются условия (ограничения)).
Одномерная оптимизация – это ф-ция одной переменной, т.е. y = f(x1). Задача формулируется след. образом: Найти наименьшее (наибольшее) значение целевой ф-ции на интервале и определить значение проектного параметра х, принадлежащего интервалу, при котором ф-ция принимает экстремальное значение.
Существование решения вытекает из теоремы Вейерштрасса: всякая ф-ция f(x) непрерывна на отрезке [a; b] и принимает на этом отрезке наибольшие и наименьшие значения, т.е. на отрезке [a; b] существуют такие точки x1 и х2, что для любого x, принадлежащего [a; b] имеют место неравенства f(x1) ≤ f(x) ≤ f(x2).
Теорема не доказывает единственности решения. Ф-ция может достигать своего наибольшего и наименьшего значения либо в граничных точках, либо в точках min и max. Последние точки должны быть обязательно критическими, т.е. f’(x)  в этих точках обращается в нуль. Это необходимое условие экстремума.
Следовательно, для наименьшего и наибольшего значений нужно вычислить её значения во всех критических точках данного отрезка и сравнить полученные значения.
Методы поиска экстремальных решений:
- Метод перебора.
- Метод деления отрезка пополам.
- Метод золотого сечения.
Необходимым условием метода золотого сечения является унимодальность ф-ции (т.е. ф-ция принимает на заданном отрезке 1 минимум или максимум).
Метод з.с. является наиболее эффективным, т.к. наилучшая точность достигается при ограниченном количестве вычислений.
Этот метод состоит в построении последовательности отрезков, стягивающихся к точке min(max). На каждом шаге, за исключением первого, вычисление значения ф-ции f(x) производится лишь один раз. Эту точку называют золотым сечением и выбирают специальным образом.
1. Выбираем 2 точки так, чтобы x1 < x2 (выбираем специальным образом!).
Находим f(x1) и f(x2).
Если f(x1) < f(x2), то min принадл. [a; x1] или [x1; x2]. Отбрасываем [x2; b], т.е. b замещает x2; x2 замещает x1.
2. Точка x2 перешла с 1 шага. Снова находим x1. Сравниваем значения ф-ции в этих точках, выбираем нужные интервалы и т.п.
Итерационный процесс продолжается до тех пор, пока |b - a| < ε. При этом проектный параметр оптимизации составляет ak < x < bk. В качестве оптимального значения принять можно x = (ak + bk) / 2
Как выбрать x1 и x2?
1.Рассмотрим отрезок [a; b] как стержень длиной l = 1.
2. Возьмём точку таким образом, что l1 < l2. Правило золотого сечения гласит: l1 / l = l2 / l1, где l = l1 + l2.
l1 / (l1 + l2) = l2 / l1
l12 = l2(l1 + l2)
l12 - l1 l2 + l22 (разделить на l12; l2 / l1 заменить на z)
1 – z – z2 = 0
z2 + z – 1 = 0
Решаем, находим z1 = 0,618 (отрицательное значение не подходит).
l1 / l = l2 / l1 = 0,618
l1 = 0,618 • l, где l = 1 (1 – 0,618 = 0.382)
x1 = 0,618•a + 0,382•b   
x2 = 0,382•a + 0,618•b- примерно одинаковое расположение от центра отрезка в соответствии с правилом золотого сечения метода Фибоначчи
Const eps = 1E – 3
Function F(x As Double) As Double
F = (x^3) / 3 – x^2
End Function
Sub Zolot (a As Double, b As Double, x As Double, min As Double)
Dim x1 As Double, x2 As Double
Cells(1, 1) = “x1 = ”
Cells(1, 3) = “x2 = ”
p = 2
x1 = 0.618*a + 0.382*b
x2 = 0.382*a + 0.618*b
Do
   If F(x1) < F(x2) Then
   b = x2
   x2 = x1
   Else a = x1
   x1 = x2
   x2 = 0.382*a + 0.618*b
   End If
Loop Until Abs(b – a) < eps
x = (a + b) / 2
min = F(x)
End Sub
Sub My_Pr()
Dim a As Double, b As Double, x As Double, min As Double
a = 1
b = 3
Zolot a, b, x, min
Cells(20, 1) = “x = ” & Format(x, “0.000”)
Cells(21, 1) = “min = ” & Format (min, “0.000”)
End Sub
Числа Фибоначчи.
Это элементы числовой последовательности, в которой каждый последующий член равен сумме предыдущих.
Sub My_Pr()
F1 = 1
F2 = 2
Cells(2, 1) = F1
Cells(2, 2) = F2
Cells(1, 5) = "числа Фибоначчи"
Range("E1").Font.ColorIndex = 3
Range("E1").Font.Italic = True
P = 3
Do
   F = F1 + F2
   Cells(4, P) = F1
   Cells(4, P + 1) = F2
   Cells(4, P + 2) = F
   P = P + 1
   F1 = F2
   F2 = F
Loop Until F > 144
End Sub