Студопедия Главная Случайная страница Обратная связь

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

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





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

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; просмотров: 3572. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Объект, субъект, предмет, цели и задачи управления персоналом Социальная система организации делится на две основные подсистемы: управляющую и управляемую...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит...

Кран машиниста усл. № 394 – назначение и устройство Кран машиниста условный номер 394 предназначен для управления тормозами поезда...

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