Студопедия — Методы минимизации функций одной переменных
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Методы минимизации функций одной переменных






Здесь рассматривается простейшая математическая модель оптимизации, в которой целевая функция зависит от одной перемен­ной, а допустимым множеством является отрезок вещественной оси:

f (x) ®min, (2.1)

хÎ [a; b].

Как уже отмечалось, максимизация целевой функции (f (x) ® max) эквивалентна минимизации противоположной величины (–f (x) ® min), поэтому мы будем рассматривать только задачи минимизации.

К математическим задачам вида (2.1) приводят прикладные задачи оптимизации с одной управляемой переменной. Кроме того, необходимость в минимизации функций одной переменной возникает при реализации некоторых методов ре­шения более сложных задач оптимизации.

Классический метод минимизации.

Шаг 1. Решить уравнение на интервале х Î (а; b), т.е. найти все стационарные точки x1,.., xk–1Î (а; b). Положить x0 = а, xk = b.

Шаг 2. Вычислить значения f (х) функции f (х) в точках xi, i = 0,.., k.

Шаг 3. Найти . Положить х* = xm.

Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.

Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f (х) в заданных точках.

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функ­цию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].

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

Разобьем отрезок [а; b] на п равных частей точками деления xi = а + i(b – а)/п, i = 0,.., n. Вычислив значения f (х) в точках xi, путем сравнения найдем точку xm, 0 £ т £ п, для которой

(2.9)

Далее, положим .

 

МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ

В методе перебора, рассмотренном выше, точки xi, в которых оп­ределяются значения f (x), выбирают заранее. Если же для выбора очередной точки вычисления (измерения) f (x) использовать информа­цию, содержащуюся в уже найденных значениях f (x), то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений f (x), как, например, в методе пораз­рядного поиска.

На один из путей такого более эффективного поиска точки х* ука­зывает свойство 3 унимодальных функций (см. формулу (2.3)).

Пусть а < x1<х2<b. Сравнив значения f (x) в точках x1 и х2 (проб­ных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х2], если или к отрезку m [x1; b] если (рис. 2.6). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку миниму­ма. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить , где – одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.

Первый метод деления отрезка пополам (дихотомии).

Шаг 1. Определить x1 и х2 по формулам , где d > 0 – малое число.. Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если , то перейти к отрезку [а; x2], положив b = x2, иначе – к отрезку [x1; b], положив а = x1.

Шаг 3. Найти достигнутую точность Если , то пе­рейти к следующей итерации, вернувшись к шагу 1. Если , то за­вершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить .

Метод золотого сечения. Шаг 1. Найти х1 и х2 по формулам . Вычислить f (x1) и f (x2). Положить , .

Шаг 2. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2, x2=x1, f (x2) £ f (x1), x1=b–t(b–a) и вычислить f (x1), иначе – положить a=x1, x1= x2, f (x1) = f (x2), x2=b+t(b–a) и вычислить f (x2). Положить en = ten и перейти к шагу 2.

Шаг 4. Окончание поиска: положить , .

метод парабол

Шаг 1. Выбрать точки x1, x2, x3, удовлетворяющие условиям х1 < х2 < х3, f (x1) ³ f (x2) £ f (x3). Перейти к шагу 2.

 

Шаг 2. Найти по формуле . На первой итерации перейти к шагу 4, на остальных – к шагу 3.

 

Шаг 3. Проверка на окончание поиска. Сравнить модуль разно­сти значений на данной и предыдущей итерациях D с числом e. Если |D| £ e, то поиск завершить, полагая х*» , f *» f (x), иначе – перейти к шагу 4.

Шаг 4. Вычислить значение f (). Перейти к шагу 5.

Шаг 5. Определить новую тройку чисел x1, x2, x3. Присвоить f (x1), f (x2) и f (x3) соответствующие значения f (x) найденные ранее. Пе­рейти к шагу 2.


 







Дата добавления: 2015-04-19; просмотров: 3521. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Методы анализа финансово-хозяйственной деятельности предприятия   Содержанием анализа финансово-хозяйственной деятельности предприятия является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих...

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Подкожное введение сывороток по методу Безредки. С целью предупреждения развития анафилактического шока и других аллергических реак­ций при введении иммунных сывороток используют метод Безредки для определения реакции больного на введение сыворотки...

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

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия