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

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

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





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

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




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


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


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


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

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Прием и регистрация больных Пути госпитализации больных в стационар могут быть различны. В цен­тральное приемное отделение больные могут быть доставлены: 1) машиной скорой медицинской помощи в случае возникновения остро­го или обострения хронического заболевания...

ПУНКЦИЯ И КАТЕТЕРИЗАЦИЯ ПОДКЛЮЧИЧНОЙ ВЕНЫ   Пункцию и катетеризацию подключичной вены обычно производит хирург или анестезиолог, иногда — специально обученный терапевт...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

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