При наложено ограничение от вида
Изтегляне 129.55 Kb.
|
| Лекция 2
Оптимизация при целеви функции с един управляващ параметър. Постановка на задачата. Класификация на методите за оптимизация с един управляващ параметър. Методи на сканирането. Интерполационни методи.Примери за формулиране на задачи като оптимизационни с една независима променлива от инженерната химия. ПОСТАНОВКА НА ЗАДАЧАТА Нека задачата на математичното програмиране е формулирана като задач на нелинейното програмиране, като е зададена целева функция, която е нелинейна и зависи от един управляващ параметър. Системата от ограничения са сведени до ограничената област на изменение на независимата променлива x.т.е.:  (1)
При наложено ограничение от вида:  (2)
Задачата е да се определи такава стойност на х, която пренадлежи на (2) и осигурява минимум или максимум на целевата функция (1). Класификация на методите за оптимизация с един управляващ параметър Методите за едномерна оптимизация могат да се разделят на две основни групи:
Методи на сканирането Метод на сканирането с постоянна стъпка Методите на сканирането при оптимизация с един управляващ параметър използуват последователно изследване на целевата функция през определени интервали на управляващия параметър, наречени стъпка на сканирането .В случаите когато стъпката на сканирането остава постоянна по време на цялото решение, то сканирането се прави с постоянна стъпка.  Точността на локализация на екстремума е равна на стъпката на сканирането. Предимства на метода:
Недостатъци на метода
Сканиране с променлива стъпка За отстраняване на основния недостатък на метода на сканирането с постоянна стъпка може да се направи сканиране с променлива стъпка както е показано на фигурата.  Идеята на метода е следната:
Тази процедура се извършва до тогава докато стъпката на сканирането не стане по-малка от изискуемата точност на локализация на екстремума. Алгоритъма на метода е следния:
Предимства на метода:
Недостатъци на метода:
Метод на сканирането с променлива възвратна стъпка При някои технологични задачи е възможно горната граница на областта на търсене b да не бъде зададена. В такива случаи се препоръчва сканиране с променлива възвратна стъпка. Графическата интерпретация на метода е показана на фигурата. Метода се прилага в случаите, когато една от границите на независимата променлива не е зададена т.е. 
 Препоръчва се всяка следваща стъпка да се определя, като предидущата се дели на 4 т.е.:  (1)
Предимства на метода:
Недостатъци на метода:
Метод на “дихотомията” Метод на “деление на половина”
Алгоритъма на метода е следния:
Както се вижда от графическата интерпретация на алгоритъма на всяка итерация областта на изследване се намалява наполовина, а останалата неизследвана област на две равни части, всяка от които при следващата итерация се дели още на две и т.н. до достигане на желаната точност. Оттук идва и названието на метода – “дихитимия” или “деление на половина”.  Метод на “златното сечение” Оказва се, че по-бърза сходимост при едномерната оптимизация може да се постигне, ако интервалът на изследване [ a,b] , в който се намира екстремума, се дели не на цяло число, както в предидущия метод, а на ирационално число. При метода на “златното сечение” интервалът [ a,b] се дели на две части, отношението на които удовлетворява т. Нареченото “Златно сечение”
l1 l2
0.62 l l 0.38 l т.е. отношението на цялата отсечка към по-голямата част е равно на отношението на по-голямата към по-малката отсечка. Не е трудно да се докажр, че голчмата отсечка е разделена в пропорцията 0.62 и 0.38 Едно от основните свойства на разделяне на отсечка по правилото на “златното сечение” е, че ако нанесем от края на по-голямата отсечка по-малката , то по-голямата отсечка се разделя по-правилото на “златното сечение”, като се изпълнява условието:  (2)
За унимодални функции са възможни следните три случая на разположение на екстремума и определянето на областта, в която да се продължи търсенето.
Предимства на метода:
Недостатъци на метода:
 Метод на Кифер-Джонсън с използуване на числата на Фибоначи
Всяко число от реда на Фибоначи се използува от сумата на предидущите две по рекурентното съотношение 
при 
В таблицата е дадена част от реда на Фибоначи:
За работа на метода се изисква точността за достигане на решението да бъде зададена предварително. Алгоритъмът гарантиращ достигане на сходимост при унимодални функции е следният: Предполага се, че са зададени
 Предимства на метода:
Недостатъци на метода:
Метод на Кифер – Джонсън при дискретен управляващ параметър При много оптимизационни задачи управляващия параметър има само дискретни стойности. Интервала на дискретизация може да бъде равномерен или неравномерен. Повечето от методите за оптимизация при непрекъснат управляващ параметър не са пряко приложими и при дискретни. Последователното сканиране на всички възможни точки може да се окаже недопустимо поради голямият брой на изчисленията. Някои от разгледаните методи може да се приложи при решаване и на задачи с дискретни променливи. 
ИНТЕРПОЛАЦИОННИ МЕТОДИ Тези методи се използуват в случаите, когато интервала на изменение на независимата променлива не е известен. Основната идея на тези методи е намиране на полиномиална апроксимация от втора или по-висока степен на целевата функция по няколко изчислени нейни стойности и определяне на текущия максимум 
Ако за целевата функция  са изчислени три стойности  ,  и  , съответно при управляващи параметри  ,  ,  , функцията може да се апроксимира по трите точки с полином от втора степен:
Коефициентите  , могат да се изчислят по формулите:
Екстремумът на целевата функция се оценява с приближение при  откъдето:
Интерполационните методи както за едномерно, така и за многомерно търсене на екстремума се различават по различната организация при намиране на трите точки, необходими за полиномиалната апроксимация на . На тази основа са предложени различни методи като:
Каталог: www systems engineerig laboratory -> Distance learning systmeng -> Distance course 2 -> Lekcii Course 2 -> Lekcii Course 2 DOC Distance learning systmeng -> Качествен анализ на модели Distance learning systmeng -> На работа в науката и администрацията Distance learning systmeng -> Оптимални разписания при многопродуктови периодични химични системи Distance learning systmeng -> Проф. Д-р асен златаров Distance learning systmeng -> 1. Кои са решаващите фактори за формиране на черноморската флора и фауна? Distance learning systmeng -> Здраве и безопасност в пристанищни райони Distance learning systmeng -> Цонка Консулова Distance learning systmeng -> Планиране в екологията и реновация на пристанищата в България Distance learning systmeng -> Инструменти за екологичен мениджмънт на пристанищни райони Lekcii Course 2 DOC -> Безградиентни методи за оптимизация Изтегляне 129.55 Kb. Сподели с приятели:
|
, където L= 4-5
, където L= 4-5
и кординатата и 
.
, търсенето се прекратява и 
и 
р алгоритъмът продължава от т.3.
(1)
, 
и интервалът 
се отхвърля.
, максимумът се намира меду 
и интервалът 
се отхвърля.
, максимумът се намира меду 
и интервалът 
по формули:
и алгоритъма се повтаря в т.1
(случай 1):
и 
приема стойността на 
, т.е. 
, 
приема стойността на 
, т.е. 
.
; 
, 
от реда на Фибоначи, т.е. 
л Ако стъпката е удачна, по-добрият резултат се запомня като QM, а условията x за него – като XM
р запомня се 
и се прави 
следващата стъпка се прави от последната удачна стъпка в обратно направление с число на Фибоначи, притежаващо номер, с единица по-малък от предидущото, използувано в неудачната стъпка:
, резултатът за целевата функция в последната удачна стъпка QM и координатите и XM определят търсения максимум с точност 
търсенето започва пак от началото с число на Фибоначи 
, което е равнозначно на преместване на горната граница b в точката 
по апроксимиращия полином.
