Пример решения методами дихотомии и золотого сечения. Tag Archives: метод золотого сечения Функция золотого сечения
В этой блок-схеме y, z - точки деления отрезка ,причем y < z .
y = 0.618a + 0.382b
z = 0.382a + 0.618b
Fy = f(y) : Fz = f(z)
b - a < e b - a < e
z = y: Fz = Fy y = z: Fy = Fz
y = 0.618a + 0.382b z = 0.382a + 0.618b
Fy = f(y) Fz = f(z)
Вывод x, f(x)
Пример. Для оценки сопротивления дороги движению автомобиля при скорости v км/ч можно использовать эмпирическую формулу f(v) = 24 - 2/3*v + 1/30*v 2 (для шоссе). Определить скорость, при которой сопротивление будет минимальным.
Решение.
1) Данную задачу легко решить с помощью вычисления производной:
,
v = 10
км/ч.
2) Решение с помощью метода "золотого сечения". Начальные границы интервала неопределенности примем равными a = 5, b = 20.
Решение для первого этапа:
y = 0.618*5 + 0.382*20 » 10.7: z = 0.382*5 + 0.618*20 » 14.3
Fy = 24 - 2*10.7/3 + 10.7 2 /30 » 20.7: Fz = 24 - 2*14.3/3 + 14.3 2 /30 » 21.3
Результаты вычислений обычно представляют в виде таблицы. Расчеты проводятся в соответствии с блок-схемой с погрешностью e = 1 км/ч.
После пяти шагов оптимизации искомое значение скорости равно v = (8.6+10.7)/2 = 9.65 км/ч. После еще одного шага этот результат получается с меньшей погрешностью v = (9.4+10.7)/2 = 10.05 км/ч.
Оптимизация функции многих переменных Минимум функции нескольких переменных
Минимум дифференцируемой функции многих переменных u = f(x 1 , x 2 , … , x n) можно найти, исследуя ее значение в критических точках, которые определяются из решения системы дифференциальных уравнений
Отметить, что в данном случае критические точки могут соответствовать либо экстремальным, либо "седловым" точкам (точкам "минимакса"). Под этими точками понимаются такие точки, в которых по некоторым направлениям функция имеет минимум, а по остальным направлениям - максимум.
Пример постановки задачи. Пусть требуется спроектировать контейнер в форме прямоугольного параллелипипида объемом V=1 м 3 , причем на его изготовление необходимо израсходовать как можно меньше материала.
При постоянной толщине стенок это условие означает, что площадь полной поверхности контейнера S должна быть минимальной. Если обозначить через x 1 , x 2 и x 3 длины ребер контейнера, то задача сведется к минимизации функции:
S = 2 (x 1 x 2 + x 1 x 3 + x 2 x 3) .
Эта функция в данном случае является целевой, а условие V = 1 м 3 - ограничением-равенством, которое позволяет исключить один параметр:
.
Задача свелась к минимизации функции двух переменных. В результате ее решения будут найдены значения параметров оптимизации x 1 и x 2 , а затем и x 3 . В приведенном примере фактически получилась задача безусловной оптимизации, так как ограничение-равенство было использовано для исключения параметра x 3 .
Решение. После дифференцирования получим
Отсюда находят x 1 = x 2 =1 м, x 3 = 1/(x 1 x 2) = 1 м. Таким образом, оптимальной формой контейнера в данном случае является куб, длина ребра которого равна 1 м.
При таком подходе могут возникнуть серьезные трудности при решении системы нелинейных уравнений.
Вместе с тем, можно эту задачу усложнить. Например, потребуем, чтобы данный контейнер имел длину не менее 2 м. Это условие запишется в виде ограничения-неравенства на один из параметров, например, x 1 ³ 2 .
Таким образом, получили следующую условную задачу оптимизации: минимизировать функцию
учитывая ограничение-неравенство x 1 ³ 2 и найти оптимальные значения факторов x 2 , x 3 (x 2 ³0, x 3 ³0).
Графическое представление функции двух переменных: рассмотреть функцию
f(x 1 , x 2) = x 1 2 + x 2 2 .
Показать линии равного уровня для этой функции.
Дать общий вид трех возможных вариантов линий равного уровня, показать "овражные" функции.
В общем случае для поиска минимального значения целевой функции можно ввести дискретное множество точек (узлов) путем разбиения интервалов изменения параметров x 1 и x 2 на части с шагами h 1 и h 2 . В полученных узлах можно вычислить значения целевой функции и среди них найти наименьшее. Однако в многомерных задачах оптимизации такой подход требует слишком большого объема вычислений.
Метод золотого сечения
Рассмотрим такое симметричное расположение точек x 1 и х 2 на отрезке [а ; b ], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x ), так как другое значение уже найдено на одной из предыдущих итераций.
Рассмотрим сначала отрезок и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х 2 = , тогда симметрично расположенная точка х 1 = 1- (рис.2.2).
Рис. 2.2.
Пробная точка х 1 отрезка перейдет в пробную точку х 2 = 1- нового отрезка . Чтобы точки х 2 = , и х 2 = 1- делили отрезки и в одном и том же отношении, должно выполняться равенство или, откуда находим положительное значение … Таким образом, х 1 = 1- = , .
Для произвольного отрезка [а ; b ] выражения для пробных точек примут вид
1. Точки x 1 и х 2 обладают следующим свойством: каждая из них делит отрезок [а ; b ] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а ; b ].
2. На каждой итерации исключения отрезков с пробными точками одна из них переходит на следующий отрезок и значение f (x ) в этой точке вычислять не следует. Если новым отрезком становится [а ; х 2 ], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х 2 "= х 1) (рис. 2.2). В случае перехода к отрезку [х 1 ; b ] пробная точка исходного отрезка становится первой пробной точкой отрезка [х 1 ; b ].
3. Легко проверить, что х 1 =а+b -х 2 , и x 2 =а+b -х 1 . Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания.
4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков.
На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении, поэтому в результате п итераций его длина становится. Таким образом, точность n определения точки х* после п итераций находят из равенства, а условием окончания поиска точки х * с точностью служит неравенство n .
Пример решения методами дихотомии и золотого сечения
Дана функция, где d=2, e=1
Необходимо найти минимум на отрезке , где, т.е. на отрезке
Составить программу, которая выдаст число итераций при точности е=0,001
Решить двумя методами: дихотомии и золотого сечения
Решение методом дихотомии:
Так как f1 Так как f1 Решение методом золотого сечения: Так как f1 Так как f1 Так как f1 Листинг программы реализующей методы дихотомии и золотого сечения представлен в приложении А О методе Золотого Сечения:
Безусловно, простой и быстрый метод. И как водится, скорость не способствует аккуратности.
Это я о том, что если на заданном интервале поиска будут находиться несколько минимумов (максимумов),
то данный алгоритм легко может вернуть локальный (не самый большой, не абсолютный) экстремум. Задание:
Составить программу позволяющую протестировать алгоритм поиска экстремума методом Золотого Сечения
на примере пяти произвольных функций. Исходными данными для поиска должны являться границы интервала,
точность и тип экстремума (MAX или MIN). Программа должна отображать график функции
на заданном интервале
и координаты точки экстремума.
В программе есть смысл оформить следующие классы и модули
: Например, так...
Рис.1 Рабочий лист Excel с диаграммой, двумя командными кнопками и кнопками выбора функции Данная форма вызывается явно при щелчке по первой командной кнопке
(расположенной на листе Excel)
или косвенно, если в момент нажатия на вторую командную кнопку
(расположенную на листе Excel),
исходные данные не обеспечивают необходимых условий начала выполнения алгоритма. При открытии файла (если макросы включены) или включении макросов (если они были отключены на момент
открытия файла) выполняется обработчик события с целью задать (определить) одну из заготовленных функций,
как функцию для тестирования по умолчанию. Для этого достаточно отметить одну (например, первую) OptionButton
(или как часто называют - радиокнопку) и вызвать макрос назначенный этой кнопке. Private Sub Workbook_Open() Метод theAlgoritm
класса ExtremGC
, который, собственно, и выполняет
определение координат точки экстремума выглядит приблизительно так: "Нахождение экстремума функции на отрезке. Метод золотого сечения If Not BadDann Then Zc = (1 + Sqr(5)) / 2 End If Где Кому интересен остальной код – обращайтесь… исходный код уже открыт. Используйте
! Если у Вас не появляется форма ввода данных, значит вы забыли включить макросы… Хочу обратить внимание, что для первой функции значения аргумента не могут быть меньше или равны нулю. Чтобы увидеть, как ошибается алгоритм и находит локальный экстремум вместо абсолютного,
задайте достаточно большой интервал (например: от 0 до 25) для 4 или 5 функций, имеющих явную периодичность…
Метод золотого сечения имеет достаточно большое применение во многих сферах. Так как всё в мире имеет какую-либо форму: предметы, растения, животные, люди - всё. Что представляют собой эти формы? Любое целое обязательно разделено на части разных размеров. Эти части имеют отношения между собой и ко всему миру, имеют формы. А строение любой формы образуется при помощи симметрии и золотого сечения. Метод золотого сечения применяют в фотографии, живописи. Для фотографа метод золотого сечения - один из самых простых способов выделить главное на картинке. Применяется этот метод и в web-дизайне. В живописи же примером может послужить картина И.И. Шишкина "Сосновая роща". На этой знаменитой картине И.И. Шишкина с очевидностью просматриваются мотивы золотого сечения. Ярко освещенная солнцем сосна (стоящая на первом плане) делит длину картины по золотому сечению. Справа от сосны - освещенный солнцем пригорок. Он делит по золотому сечению правую часть картины по горизонтали. Слева от главной сосны находится множество сосен - при желании можно с успехом продолжить деление картины по золотому сечению и дальше. В архитектуре метод золотого сечения также нашёл своё применение. По законам золотого сечения были построены наиболее известные нам сооружения, такие как Парфенон (V в. до н.э.), собор Парижской Богоматери (Нотр-дам де Пари). Яркими примерами в русской архитектуре станут Смольный собор в Санкт-Петербурге и храм Василия Блаженного, в котором, если взять высоту собора за единицу, то основные пропорции, определяющие членение целого на части, образуют ряд золотого сечения. В основном же, метод золотого сечения применяют в программировании. Он является одним из простейших вычислительных методов решения задач оптимизации. Цель курсовой работы - рассмотреть численные методы поиска экстремума функций одной переменной, а именно метод золотого сечения. Исходя из поставленной цели, необходимо решить следующие задачи: Рассмотреть метод золотого сечения, его алгоритм выполнения; Рассмотреть метод чисел Фибоначчи и его алгоритм выполнения; Показать реализацию метода золотого сечения в программировании. Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования. Присутствие в названии дисциплины термина "программирование" объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово "programming" означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин "линейное программирование" был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование "математическое программирование" связано с тем, что целью решения задач является выбор оптимальной программы действий. Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман - математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Канторович - советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода. В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название "проблема выбора", метод решения получил название "венгерского метода". Канторовичем совместно с М.К. Гавуриным в 1949 году разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Канторовича, Немчинова, В.В. Новожилова, А.Л. Лурье, А. Брудно, Аганбегяна, Д.Б. Юдина, Е.Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф.Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования -- симплекс-метод -- был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ.), А. Таккера (англ.), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E.M.) и др. Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 году была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области. Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования. В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO. Пусть Х=. Положим х1=1/T. Так как Т2=Т+1,то 1-1/Т=1/Т2. Итак,отношение длины всего отрезка,к длине большей из его частей равно отношению длины большей части к длине меньшей части: 1/(1/Т)=(1/Т)/(1/Т2) Деление отрезка в таком отношении называется золотое сечение. Точку x2 выберем симметрично точке x1 относительно середины отрезка X:x2=1/T2. Сравнив значения f(x1) и f(x2),находим отрезок локализации минимума ( или ).Нетрудно увидеть, что лежащая внутри локализации точка, где вычисление проведено, делит отрезок в отношении золотого сечения. Алгоритм определяется условием одинаковым в методе Фибоначчи, то есть разница в выборе точки x1. На каждом шаге точка очередного вычисления выбирается симметрично относительно середины отрезка к лежащей внутри этого отрезка точке уже сделанного вычисления. Рисунок 1 - График взаимного расположения первых 2 вычислений по методу золотого сечения
Таблица 1 ? Взаимное расположение генерируемых алгоритмом точек Очевидно, что в случае X=, длина отрезка локализации минимума после N вычислений равна (b-a)/(TN-1).
Рис.2 Форма для ввода исходных данных
Для удобства пользователя, все элементы TextBox
допускают ввод только числовых значений.
При щелчке по кнопке «Отмена»
все
переменные получат значения, которые существовали на момент открытия формы.
" радиокнопки нумеруются в этой книге от 5 до 9.
" Поэтому по умолчанию выделяю первую кнопку.
Sheets(1).Shapes("Option Button 5").ControlFormat.Value = 1
SheetGoldCutting.OptBut1_Click
End Sub
Public Sub theAlgoritm(v1 As Double, v2 As Double, v3 As Double, v4 As Double, findMax As Boolean)
Dim x1 As Double, x2 As Double, y1 As Double, y2 As Double, sme As Double
FullArrayOnly v1, v2, v3, v4 "для проверки допустимости аргумента
n = 0 "количество разбиений (переменная модуля класса)
Do While b - a > ep
sme = (b - a) / zc
x1 = b - sme: x2 = a + sme
y1 = theFunc(x1): y2 = theFunc(x2)
If findMax Then
"поиск максимума
If y1
a = x1
Else
b = x2
End If
Else
"поиск минимума
If y1 >= y2 Then
a = x1
Else
b = x2
End If
End If
n = n + 1 "количество разбиений (переменная модуля класса)
Loop
dxk = Abs(b - a) " конечное значение шага
xe = (a + b) / 2: ye = theFunc(xe) " результат: координаты точки экстремума
End Sub
FullArrayOnly
- закрытый метод класса для проверки допустимости аргумента и заполнения массива точек графика;
BadDann
– флаг допустимости аргумента;
zc
– константа золотого сечения;
a, b
– границы интервала;
ep
– заданная точность поиска ε
;
findMax
– параметр, характеризующий режим поиска (при true
ищется максимум, при false
– минимум);
theFunc(x As Double) As Double
– метод класса, возвращающий значение тестируемой функции в зависимости от значение аргумента.
Если нужно что-то изменить в проекте под Ваши требования (например, заменить функции) – пожалуйста, проблем не будет!Введение
Метод золотого сечения
История появления метода золотого сечения
Понятие и определение метода золотого сечения
