10.1 Тездетіп түсу әдісі
Егер
функцияның
өсімшесі
нүктесінен
нүктесіне өткен кезде ең үлкен (
)
немесе ең кіші (
)
болатындай
таңдалынса, онда градиенттік әдіс
тездетіп
түсу әдісі деп
аталады.
функциясының
шартсыз, яғни шектеулер қойылмаған
жағдайдағы экстремумын табуды
қарастырайық. Шығару үрдісі итеративті
болып табылады.
Тездетіп
түсу әдісі бойынша
функциясы экстремумға жететіндей (8.9)
формуладан
таңдалынады.
Ескерту.
нүктесін тапқан кезде алдыңғы
нүктесі белгілі, яғни
және
– тұрақты шамалар болып табылады, ал
–
бір айнымалыдан тәуелді функция.
(8.9)
формуладағы
өрнегін және
нүктесіндегі градиенттің
өрнегін ескеріп
функциясын дифференциалдағанда
экстремумның қажетті шарты
төмендегі түрде болатынын аламыз:
. (8.10)
Егер векторлардың скаляр көбейтіндісін пайдалансақ, осы формуланы ықшамды түрде жазуға болады:
. (8.10’)
Осы
теңдеулерден
мәнін есептейміз,
нүктесін анықтаймыз. Егер алынған жаңа
нүктесінде
болса есептеу тоқтатылады, себебі
градиент бойымен әрі қарай жылжу мүмкін
емес. Егер
болса,
нүктесін бастапқы нүкте ретінде алып,
нөлдік градиент алынғанша есептеу
үрдісі жалғастырылады.
Теңдеулер мен теңсіздіктер түріндегі берілген шектеулері бар сызықтық емес программалау есебінде, яғни шартты оңтайландыру есебінде көбейткішін таңдау барысында қосымша шарттар қойылады: жаңа нүктесі жарамды шешімдер облысынан тыс болмауы керек.
(8.11)
шектеулерін қанағаттандыратын
(8.12)
дөңес программалау есебі берілсін.
Тездетіп түсу әдісінің алгоритмі
1.
Функцияның
градиентін табу керек және
теңдеуін шығара отырып (8.11)
жүйені қанағаттандыратын стационар
нүктелерді анықтау керек. Осы нүктелердегі
(8.12)
мақсат функциясының мәндерін есептеу
керек.
2.
функцияларының градиенттерін табу
керек және сәйкес облыстың
-ші
шекарасына тиісті стационар нүктелерді
анықтау керек. Ол үшін
(8.13)
теңдеулер жүйесін шығару керек:
(8.13)
жүйе шешімдерінің арасынан (8.11)
шарттарды және
шартын қанағаттандыратын шешімдерді
іріктеп алу керек. Осы нүктелердегі
мақсат функцияның мәнін есептеу керек.
3.
түріндегі
теңдеулер жүйесін шығарып, барлық
шекаралық гипербеттердің қиылысуын
анықтау керек, мұндағы
,
,
.
және
мәндеріндегі жарамды шешімдерді іріктеп,
осы шешімдердегі
мәндерін есептеу керек.
Егер
болса, онда жарамды шешімдер облысының
бұрыштық нүктелерін табу жеткілікті
және осы нүктелердегі мақсат функцияның
мәнін есептеу керек.
4. Мақсат функциясының 1-3 қадамдарда алынған барлық нүктелердегі мәндерін салыстырып, және – таңдау керек.
8.5-мысал.
функциясының
максимумын тездетіп түсу әдісімен
анықтау керек,
(шартсыз
оңтайландыру есебі).
Шығарылуы. Бастапқы нүктедегі функцияның градиентін анықтаймыз. Ол үшін бірінші дербес туындыларды табамыз:
,
.
,
.
Жаңа нүктесін таңдаймыз:
.
Жаңа нүктедегі градиентті табамыз:
.
теңдеуін шешеміз.
.
.
Осы нүктедегі градиент мәнін есептейміз:
.
Нөлдік
градиент алынды, демек,
стационар нүкте. Мақсат функция дөңес
болғандықтан берілген нүктеде максимум
мәні алынады.
.
Жауабы.
,
.
Осы мысалда біз бір итерацияда дәл оптимумды алдық. Бұл заңдылық емес. Практикада тиімді шешімі бірнеше итерацияда немесе итерацияның ақырлы қадамында жуық шешімі ғана алынуы мүмкін есептер де кездеседі.
8.6-мысал.
,
шектеулеріндегі
функциясының минимумын тездетіп түсу әдісімен анықтау керек (шартты оңтайландыру есебі).
Шығарылуы. Шектеулер жүйесін келесі түрде жазамыз:
Мақсат функциясының градиентін анықтаймыз:
.
Стационар
нүктені анықтаймыз:
,
.
Алынған стационар нүкте шектеулер жүйесін (1-ші және 2-ші теңсіздіктерді) қанағаттандырмайтындықтан жарамды емес болып табылады. Демек, жарамды шешімдердің ішінде мақсат функцияның экстремумы жоқ, ауқымды экстремум тек қана шекараларында немесе шешімдер облысының төбелерінде болуы мүмкін.
1.
шекаралық сызығын қарастырайық. Осы
сызық үшін (8.3) түріндегі жүйені құрамыз:
,
мұндағы
.
немесе
Осы
жүйені шеше отырып
,
,
мәндерін аламыз.
шектеулер жүйесін қанағаттандырады
және
.
Сондықтан,
нүктесі – стационар нүкте.
2.
Келесі
шекаралық сызығын қарастырамыз.
.
.
,
,
.
нүктесі
шектеулер жүйесін қанағаттандырмайды
(бірінші теңсіздікті). Сондықтан
шекаралық сызығында стационар нүктелер
жоқ.
3.
шекаралық сызығын қарастырамыз.
.
,
,
.
болғандықтан
шекаралық сызығында стационар нүктелер
жоқ.
4.
Келесі шекаралық сызық –
.
.
,
,
.
сондықтан
шекаралық сызығында стационар нүктелер
жоқ.
5.
Келесі шекаралық сызық –
.
,
,
.
сондықтан
шекаралық сызығында стационар нүктелер
жоқ.
Шекаралық сызықтардың теңдеулер жүйесін шешу нәтижесінде жарамды шешімдер облысының бұрыштық нүктелерін табамыз:
;
;
;
;
.
Осы
нүктелердегі және табылған стационар
нүктедегі
функциясының мәнін есептейміз:
;
;
;
;
.
Алынған
мәндердің арасынан ең кішісін таңдаймыз:
,
.
Жауабы. , .
11-лекция. Динамикалық программалау модельдері