КІРІСПЕ. Оңтайландыру есебінің шешімі жалпы жағдайда зерттеліп отырған объекттің кіріс айнымалы шамаларының мақсатты

Оңтайландыру есебінің шешімі жалпы жағдайда зерттеліп отырған объекттің кіріс айнымалы шамаларының мақсатты функцияның ең жақсы мәні (минимал немесе максимал) сәйкес келетін мәнін табуға негізделген. Технологиялық жүйелер - мәніне қосымша шектеулер қойылған көптеген кіріс факторлары бар көп өлшемді жүйелер. Бұл көп өлшемді шартты оңтайландыру әдісін қолдануды талап етеді. Алайда, берілген әдістердің көбісі есеп мағлұматтарын мақсатты функцияны түрлендіру және одан ары сәйкес процедураларды қолдану жолы арқылы шарттсыз оңтайландыруға ұйғарады. Сондықтан, бірнеше шектеусіз айнымалылар функцияларының экстремумын іздеу әдістерінің зерттелуі маңызды мәселе болып табылады.

Берілген ұсынымда көп өлшемді шартсыз оңтайландырудың міндет қойылымы, мақсатты функцияның аналитикалық анализі, сандық әдістерде жиі қолданылатын – тік өр әдісінің, симплекс әдісінің, Хук және Дживс әдістерінің теориялық негіздері қарастырылады. Бұл әдістердің болмысы мен ерекшеліктерін түсіну, кіріс шамалардың дұрыс тапсырмасының дағдысын қалыптастыру үшін, мысал түрінде есеп шешімінің геометриялық интерпретациясы мүмкін болатын, екі айнымалылардың функциясы алынған.

1. ЕСЕПТІҢ ҚОЙЫЛЫМЫ

n шынайы айнымалылардың функциясы берілген болсын

-да анықталған

мұндағы х – координаттары болатын n-өлшемді евклид кеңістігіндегі нүктені көрсететін бағана-вектор.

Егер нүктесінің қандай да бір аймағы бар болатын болса, және сол аймақтың барлық нүктесінде шарты орындалса, онда нүктесінде функциясының локальді минимумы бар болады. нүктесінде глобальді минимум болған жағдайда барлық үшін шарты орынды.

Ары қарай функциясының минимум нүктелерін табу мәселесін қарастырамыз, яғни . Максимизация тапсырмасын минимизация тапсырмасына ауыстыру үшін мақсатты функцияның таңбасын өзгерту жеткілікті.

2. ФУНКЦИЯ ЭКСТРЕМУМЫНЫҢ АНАЛИТИКАЛЫҚ АНАЛИЗІ

нүктесінде бірнеше айнымалы функциясының экстремумының бар болуының қажетті шарты: осы нүктедегі барлық дербес туындылардың нөлге тең болуы:

Яғни, функция градиенті нөлдік векторға тең.

Берілген жүйенің бір немесе бірнеше шешімі бар болуы мүмкін. нүктелері стационар нүктелер деп аталады. Экстремумға алынған нүктелерді тексеру үшін екінші дербес туындыларға зерттеу жүргізу қажет. Оған қоса, нүктесінде алынған екінші

дербес туындыларының квадрат матрицасын көрсететін Гессе матрицасы есепке алынады. Оң анықталған матрица минимумның жеткілікті шарты болып табылады, ал максимумға – теріс анықталған.

Екі айнымалысы бар функция үшін келесі белгілеулерді енгізейік:

Екі жағдай болуы мүмкін: Бірінші жағдайда функцияның экстремумы бар екені жайлы шешім жасалынбайды. Екінші жағдайда болғанда табылған нүкте функцияның минимумы, ал болғанда функцияның максимумы болып табылады.

3. ФУНКЦИЯНЫҢ ГРАФИКАЛЫҚ АНАЛИЗІ. ДЕҢГЕЙ СЫЗЫҒЫН ТҰРҒЫЗУ

Қолайлы шешім анықталатын функция облысы көп өлшемді кеңістікте қандай да бір бет ретінде ұсынылады. Бұл бет дыбыс беру (отклик) беті деп аталады. Берілген бетті n=2 жағдайы үшін де графикалық суреттеп көрсету қиын, сондықтан жазықтықта оны әдетте мақсатты функциясының мәні бірдей болатын, көптеген нүктелермен көрсетілген деңгей сызығы көмегімен бейнелейді.

Деңгей сызығын тұрғызу үшін бір айнымалыны екінші айнымалы арқылы көрсету және мақсатты функцияны көрсету қажет. Кейін функция мәндерін бере отырып, екінші айнымалымен көшіруді орындау қажет және оған қоса біріншіні есепке алып отыру керек. Алынған нүктелер көмегімен деңгей сызығын тұрғызуға болады. Содан кейін функция мәндерін өзгертіп, процедураны қайтадан қайталау қажет. Бұл операция қанша деңгей сызығын тұрғызу керек болса, сонша рет қайталанады.

Деңгей сызығының теңдеуі ашық емес түрде берілген болса, функцияны графикалық кескінде үшін бұдан да қиын әдістерді қолдану қажет.

4. КӨП ӨЛШЕМДІ ІЗДЕУ ӘДІСТЕРІ

Ары қарай айтылатын әдістердің бәрі қадамды сипаттамаға ие. Әдістің бір итерациясында бір қадам немесе бірнеше қадам болуы мүмкін. Егер мақсатты функцияның жаңа нүктедегі мәні ескі нүктедегіден аспайтын болса, қадам «сәтті» болып саналады, яғни егер болса; керісінше жағдайда қадам «сәтсіз» болып саналады.

4.1.Қадымды бір өлшемді оңтайландыруға негізделген әдістер

4.1.1. Гаусс-Зейдель әдісі

Гаусс-Зейдель әдісі айнымалылардың кезектесіп өзгеруінің бұрынғы әдістерінің принципіне негізделген. Оның идеясы келесідей тұжырымдалады: бастапқы нүктеден бірінші айнымалы арқылы қадам жүргізіледі, егер ол «сәтті» болса келесі айнымалыға көшеді. Егер қадам «сәтсіз» болатын болса, қадам қарама-қарсы бағытта жүргізіледі. Бұл

процедура барлық бағытта тек қана «сәтсіз» қадамдар болғанға дейін қайталана береді. Бұл жағдайда қадам мөлшері кішірейеді. Іздеу қадам мөлшерінің абсолютті шамасы берілген дәлдіктен кіші болғанға дейін жалғаса береді.

Гаусс-Зейдель әдісінде әр айнымалы арқылы қадам жасалған кезде мақсатты функцияның өз бағытынтағы минимумын іздейді, оған қоса ол кезде қалған айнымалылардың шамасы тұрақты болып қалады. Бағыт бойынша іздеуді бір өлшемді оңтайландырудың кез келген белгілі әдісі арқылы жүргізуге болады (мысалы, кері айнымалы қадам әдісімен, «алтын қима» әдісімен және т.б.). Осылайша, Гаусс-Зейдель әдісінде көп өлшемді оңтайландыру тапсырмасы бір өлшемді оңтайландыру әдісін көп ретті қолдануға алып келеді. Айнымалыларды түрлендіру кезегі еркін түрде белгіленеді және оңтайландыру процесінде әдетте өзгермейді.

Осылайша, әдістің алгоритмі келесідей болады:

1. тің біршама бастапқы мәні үшін х векторының біреусінен ( ді анықтау үшін) басқа барлық координаталарын белгілейді, содан кейін функциясының минимумын іздеудің бір өлшемді операциясын жүргізеді, нәтижесінде нүктесін алады, мұндағы

2. нүктесінде екіншіден басқа барлық координаттарды белгілей отырып, 1-ді x₂ бойынша қайталайды. Осылай x_n-ға дейін жалғасады. Алгоритм циклі n – әр координат бойымен бір өлшемді оңтайландырудың еселенген операциясынан кейін аяқталады. Әрі қарай мақсатты функциясының мәні алдыңғысынан аз болатын нүктелерін ала отырып, циклді қайталайды.

Есептеу процедурасын тоқтату шарты - берілген дәлдікке жету кезіндегі теңсіздігі болып табылады. Қадамды қозғалыс кезінде, мысалы, айнымалылардың кезекті өзгеру алгоритмінде іздеу нүктесі -мен сәйкес келген нүктеде тоқтатылады, яғни, цикл нәтижесіз болып шығады.

Гаусс-Зейдель әдісінің кемшілігі функция сипаттамасына тәуелсіз, шешімнің әр құраушысының өзгеруінің қатаң бағыты болып табылады. Ол «жыралы» функция кезінде алгоритмнің қисынсыз тоқтатылуына алып келеді.

4.1.2. Хук және Дживс әдісі

Бұл әдісті Гаусс-Зейдель әдісінің модификациясы ретінде қарастыруға болады. Әдістің идеясы келесідей: бастапқы нүктеден Гаусс-Зейдель әдісінің бір итерациясы жүргізіледі; функцияның жөнделген мәні алынған жерде, уақытша бастапқы (негізгі) нүкте орналасады. Осыдан кейін іздеуді екі негізгі нүктені қосатын түзу бойымен жүргізеді. Бұл іздеуді бір өлшемді іздеу әдістерінің кез-келгенімен жүргізеді. Мақсатты функцияның минимал шамасы бар нүктені тауып, ол жерден Гаусс-Зейдель әдісінің тағы бір итерациясын жүргізеді. Ары қарайғы іздеу екі соңғы негізгі нүктелерді қосатын түзу

бойымен іске асады және осылай жалғаса береді.

Хук және Дживс әдісінің қарапайым модификациясын қарастырайық. Процедураға циклды түрде қайталанатын екі этап кіреді: негізгі нүкте айналасындағы зерттеушілік іздеу және үлгі бойынша іздеу.

1. Зерттеушілік іздеу. бастапқы негізгі нүктесі және әр координатасы бойынша өсім беріледі. Негізгі нүктедегі мақсатты функцияның шамасы есептеледі. Ары қарай циклдік тәртіппен әр координата өзгертіледі:

Егер өсім мақсатты функцияны жақсартатын болса, қадам «сәтті» болып саналып, басқа координата бойынша өсім беріледі. Кері жағдайда «сәтсіз» болып саналып, қадам қарсы бағытта жасалады:

Және де қадам «сәтсіз» болғанда, мәнін өзгеріссіз қалдырып, келесі координата бойынша өсім беріледі. Бұл барлық координаталар өзгертілгенше жасалына береді. нүктесі табылды, зерттеушілік іздеу осылайша аяқталады. Егер қадамдар барлық бағыт бойынша «сәтсіз» болып шықса өсімінің кішірейтілуі жүргізіледі (әдетте екі есе) және зерттеушілік іздеу қайталанады. Процедура өсім шамасы берілген дәлдіктен аз болғанда тоқтатылады.

2. Үлгі бойынша іздеу және нүктелерін қосатын бағыт бойымен жүзеге асады. Қадамдар «сәтті» болғанға дейін бір немесе бірнеше қадамдар жасалынады, яғни, мақсатты функцияның жақсартылуына алып келеді. Қадамдардың шамасы әдетте және арасындағы арақашықтыққа тең, яғни:

Егер соңғы «сәтті»қадамнан кейін іздеу соңының шарты орындалмаса, яғни онда бұл нүктені жаңа негізгі нүкте ретінде қабылдап, барлық процедураны қайталайды.

Хук және Дживс әдісінің кемшілігі Гаусс-Зейдель әдісіндегі секілді оның «жыралы» функцияларды оңтайландыру кезіндегі нашар жинақтылығы. Ол зерттеушілік іздеу деңгейінде алгоритмнің қисынсыз тоқтатылуына алып келуі мүмкін.

Поиск по сайту: