Кіріспе

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

Шектілік қанағаттандыру проблемаларымен байланысы

Шектелген оңтайландыру мәселесі (ШОП) – классикалық шектеулерді қанағаттандыру мәселесінің (ШҚМ) маңызды жалпылауы болып табылады. ШОП – бұл оптимизациялануға тиіс мақсаттық функцияны қамтитын ШҚМ. Оптимизация бөлігін шешу үшін көптеген алгоритмдер қолданылады.

Ерітінді әдістері

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

Ауыстыру әдісі

Өте қарапайым проблемалар үшін, мысалы, бір теңдік шектеуіне бағынған екі айнымалы функциясы үшін, алмастыру әдісін қолдану ең ыңғайлы. Идеясы – шектеуді мақсатты функцияға қойып, шектеудің әсерін қамтитын күрделі функция жасау. Мысалы, мақсатты функцияны максимумға жеткізуді қарастырайық, шарты бойынша . Шектеуден , оны мақсатты функцияға қойып, мынаны аламыз. Бірінші реттік қажетті шартынан , оны шешіп және нәтижесінде аламыз.

Лагранж көбейтушісі

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

Теңсіздік шектеулері

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

Сызықтық бағдарламалау

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

Сызықтық емес бағдарламалау

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

Квадраттық бағдарламалау

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

KKT шарттары

Теңсіздік шектеулерін ескере отырып, KKT әдісі сызықтық емес бағдарламалауда Лагранж көбейтушілері әдісін кеңейтеді. Ол туындылану және дөңгелек жағдайларда қолданылуы мүмкін.

Бұтақталған және байланған

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

Бірінші таңдау шектеу функциялары

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

Орысша қуыршақ іздеу

Бұл әдіс тармақталған және байланысты алгоритмді қолданады, мұнда – айнымалылардың саны. Әрбір мұндай мәселе – бастапқы мәселеден айнымалылардың тізбегін және оларды қамтитын шектеулерді шығару арқылы алынған қосалқы мәселе болып табылады. – айнымалылар бойынша мәселе шешілгеннен кейін, оның оңтайлы құны басқа мәселелерді шешу кезінде жоғарғы шек ретінде пайдаланылуы мүмкін. Атап айтқанда, тағайындалмаған – айнымалылары бар шешімнің құнына бағалау, бағаланған айнымалылардан алынған құнға қосылады. Іс жүзінде, бұл бағаланған айнымалыларды ескермеу және тағайындалмаған айнымалылар бойынша мәселені шешумен бірдей, бірақ соңғы мәселе бұрыннан шешілген. Нақтырақ айтқанда, тағайындалған және тағайындалмаған айнымалыларды қамтитын жұмсақ шектеулердің құны жоғарыда көрсетілгендей (немесе кез келген басқа әдіс арқылы) бағаланады; тек тағайындалмаған айнымалыларды қамтитын жұмсақ шектеулердің құны осы кезде белгілі болған тиісті мәселенің оңтайлы шешімін пайдалану арқылы бағаланады. Орыс қуыршағы іздеу әдісі мен динамикалық бағдарламалау арасында ұқсастық бар. Динамикалық бағдарламалау сияқты, Орыс қуыршағы іздеу де бүкіл мәселені шешу үшін кіші мәселелерді шешеді. Бірақ, динамикалық бағдарламалау кіші мәселелерде алынған нәтижелерді тікелей біріктіре отырып, бүкіл мәселенің нәтижесін алады, ал Орыс қуыршағы іздеу оларды іздеу кезінде тек шек ретінде пайдаланады.

Құраны жою

Қиындықтарды жою алгоритмін шектеулерді оңтайландыру үшін бейімдеуге болады. Белгілі бір айнымалыны проблемадан оны қамтитын барлық жұмсақ шектеулерді жаңа жұмсақ шектеумен алмастыру арқылы жоюға болады. Бұл жаңа шектеудің құны, жойылған айнымалының әрбір мәні үшін максималды мән деп есептелінеді. Формальды түрде, егер жойылмайтын айнымалы болса, оны қамтитын жұмсақ шектеулер болса және олардың айнымалылары болмаса, жаңа жұмсақ шектеу былай анықталады:

Қиындықтарды жою алгоритмі айнымалылардың (кәдімгі) ретімен жұмыс істейді. Әрбір айнымалыға шектеулер жиынтығы сәйкес келеді; айнымалының жиынтығында рет бойынша ең жоғары айнымалыны қамтитын барлық шектеулер болады. Сауыттан шығару соңғы айнымалыдан бастап бірінші айнымалыға дейін жүзеге асырылады. Әрбір айнымалы үшін, айнымалыны жою үшін, сауыттың барлық шектеулері жоғарыда көрсетілгендей алмастырылады. Алынған шектеу тиісті сауытқа орналастырылады.