6.3 Лагранж көбейткішінің жалпыланған әдісі

Шартты оңтайландырудың (5.3), (5.6) есебін келесі түрде қарастырайық. нүктесі шектеулер-теңсіздіктерді

, , (6.11)

және шектеулер-теңдіктерді

, (6.12)

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

, (6.13)

яғни , мұндағы

, (6.14)

және .

Есептің осылай қойылуында (6.11) шектеулер жүйесі қажет болса , айнымалыларының теріс еместік шарты енгізіледі. Қосымша (әлсіз) теріс емес айнымалыларын енгізе отырып, және олардың квадраттарын (теріс еместік шартын қамтитын) пайдаланып шектеулер-теңсіздіктерді шектеулер-теңдіктер арқылы беруге болады. Сонда

,

және Лагранж функциясы мына түрде жазылады:

.

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

(6.11)-(6.13) есебінің экстремальдық нүктесін табайық. Лагранждың жалпыланған әдісінің идеясы осыған дейін қойылған мәселеге тіреледі: егер функциясының шартсыз экстремум нүктесі қойылған шектеулерді қанағаттандырмаса, онда шартты экстремум нүктесі жарамды мәндер облысының шекарасында жатуы керек. Шектеулер-теңсіздіктері жоқ (6.12), (6.14) есептер үшін көмекші Лагранж функциясын жазайық:

, .

Егер функциясының экстремум нүктесі (6.11) шектеулер-теңсіздіктерін қанағаттандырмаса, онда осы шектеулер-теңсіздіктерінің біреуі немесе бірнешеуі тура теңдіктер ретінде орындалуы керек. Сондықтан, Лагранждың жалпыланған әдісінің есептеу алгоритмін бірнеше кезең түрінде жазуға болады:

1-кезең. Лагранж функциясының шартты экстремумының (6.12), (6.13) қосымша есептерін шығару керек. Егер алынған экстремум нүктесі (6.11) шектеулер-теңсіздігін қанағаттандырса, онда есеп шығарылған, және осы шектеулер артық болып табылады. Әйтпесе деп алып екінші кезеңге көшеміз.

2-кезең. (6.11) кез келген шектеулер-теңсіздігін белсенді шектеулер ретінде, яғни шектеулер-теңдіктер түрінде жазамыз. Оларды Лагранждың көмекші функциясына қосамыз. функциясының экстремум нүктесін табу керек. Егер алынған нүктесі қалған шектеулер-теңсіздіктерді қанағаттандырса, онда шешім алынды. Кері жағдайда басқа шектеулер-теңсіздіктерін белсенді ету керек. Егер іріктеп алған белсенді шектеулер ретіндегі барлық мүмкін шектеулер-теңсіздіктер жарамды шешімді табуға мүмкіндік туғызбаса, онда үшінші кезеңге көшу керек.

3-кезең. Егер болса, онда деп ұйғарып, екінші кезеңге қайта оралу керек. Егер болса, жарамды шешім жоқ.

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

7-лекция. Итеративті есептеу әдістері

7.1 Итеративті әдістер ұғымы

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

, ,

мұндағы векторы нүктесіндегі бағыт деп аталады, ал саны – қадам ұзындығы деп аталады. Әр түрлі итеративті әдістер бір бірінен мен мәндерін есептеу тәсілдерімен ерекшеленеді.

Итеративті әдістердің тиімділігі келесі факторлармен бағаланады:

1) әмбебаптылығымен;

2) дәлділігімен;

3) бастапқы мәліметтер мен параметрлерге сезімталдылығымен;

4) есептеулерге кететін шығындармен;

5) жинақтылығымен және жинақтылық жылдамдығымен.

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

, , ,

мұндағы бастапқы есептің шешімінің дәлдігі деп аталады. Бұл жерде тиімді шешімнің жуықтауы ретінде мәні алынады. Итеративті үрдістердің маңызды қасиеті мына түрде беріледі:

.

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

Тек қана жарамды нүктелер ( шартынан шарты алынады) тізбегін құратын әдістер мүмкін болатын бағыттар әдісі деп аталады.

Бірөлшемді оңтайландыру әдістері, яғни , ал – итеративті әдістердің ең қарапайымы болып табылады.