Ме́тоди штра́фів (ме́тоди штрафни́х фу́нкцій) — методи, що широко використовуються для розв'язування технічних та економічних задач оптимізації.
Ефективні якщо штрафна функція природно випливає із технічного сенсу задачі.
Багатокритеріальні задачі мінімізації методи штрафів іноді зводять до однокритеріальних. Наприклад, під час постановки виділяють один основний критерій як цільову функцію, інші критерії замінюють обмеженнями. При програмуванні враховують обмеження за допомогою штрафу (їх переносять на цільову функцію) — завдяки цьому всі критерії замінюються одним.
Досить часто застосовують як у теоретичних дослідженнях, так і під час розробки алгоритмів.
Добре підходить для наближеної оцінки глобального мінімуму багатоекстремальних задач у складній допустимій ділянці.
Цей підхід можна використати не тільки як обчислювальний метод, але й як метод «м'якого» опису систем. Він дозволяє замінювати задачі зі складними системами обмежень задачами з простими системами обмежень або зовсім без них, а також розв'язувати задачі з несумісними системами обмежень, отримуючи практично прийнятні рішення.
У методі штрафних функцій значення штрафних коефіцієнтів, зазвичай, можуть збільшуватися необмежено. Його варіант — метод точних штрафних функцій дозволяє знаходити оптимальні розв'язки вже при скінченних значеннях штрафних коефіцієнтів. Це значно послаблює проблему поганої обумовленості, характерну для методу штрафних функцій, який зазвичай використовують для отримання лише наближених розв'язків. Однак метод точних штрафних функцій дає змогу отримувати точні розв'язки початових задач.
Історія
Строго математично метод штрафу вперше використав американський математик Р. Курант 1943 року (для вивчення руху в обмеженій ділянці).
Методи широко застосовувалися в 1960-ті роки для розв'язування задач локальної мінімізації. Однією з найпопулярніших була програма SUMT (розробники — американці Фіакко та Мак Кормік).
Приклад
Нехай потрібно розв'язати таку задачу з обмеженнями:
де
Цю задачу можна розв'язати як серію задач мінімізації без обмежень
де
У попередніх рівняннях, — зовнішня штрафна функція, а
— штрафні коефіцієнти. На кожній ітерації k методу, збільшуємо штрафний коефіцієнт
(наприклад, у 10 разів), розв'язуємо необмежену задачу та використовуємо розв'язок як початкове припущення для наступної ітерації. Розв'язки послідовних задач без обмежень збігатимуться до розв'язку початкової задачі з обмеженнями.
Недоліки
Непереборний: у рельєфі функцій штрафів і бар'єрів утворюються глибокі яри складної форми, де методи локального безумовного спуску неефективні.
Існують ефективніші методи для локальної мінімізації з диференційовними функціями цілі та обмежень.
Див. також
Примітки
- Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 79,
- Точные штрафные функции в линейном и целочисленном линейном программировании. , . 1992. № 5. С. 106—115.
- Метод точных штрафных функций для линейных смешанных целочисленных задач оптимизации. Диссертация на соискание учёной степени доктора физико-математических наук, М.: ИСА РАН, 2000, главы 1-5. Диссертация и её автореферат доступны на сайте Научной электронной библиотеки eLIBRARY.RU в списке публикаций Шмелёва В. В.
Література
- , Костина М. А. Метод штрафов в линейном программировании и его реализация на ЭВМ, Ж. вычисл. матем. и матем. физ., 1967, том 7, номер 6, 1358—1366
- Смуров С. И., Сокольская Т. В., Бобкова В. А. Методы оптимизации: Методические указания и задания к практическим занятиям и лабораторным работам / Иванов. хим.-технол. ин-т; Иваново, 1990. 72 с.
Посилання
- Метод штрафних функцій (рос.)
- Потапов М. М. , МДУ, 2003 (рос.)
В іншому мовному розділі є повніша стаття Pénalisation (optimisation)(фр.). Ви можете допомогти, розширивши поточну статтю за допомогою з французької.
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Me todi shtra fiv me todi shtrafni h fu nkcij metodi sho shiroko vikoristovuyutsya dlya rozv yazuvannya tehnichnih ta ekonomichnih zadach optimizaciyi Efektivni yaksho shtrafna funkciya prirodno viplivaye iz tehnichnogo sensu zadachi Bagatokriterialni zadachi minimizaciyi metodi shtrafiv inodi zvodyat do odnokriterialnih Napriklad pid chas postanovki vidilyayut odin osnovnij kriterij yak cilovu funkciyu inshi kriteriyi zaminyuyut obmezhennyami Pri programuvanni vrahovuyut obmezhennya za dopomogoyu shtrafu yih perenosyat na cilovu funkciyu zavdyaki comu vsi kriteriyi zaminyuyutsya odnim Dosit chasto zastosovuyut yak u teoretichnih doslidzhennyah tak i pid chas rozrobki algoritmiv Dobre pidhodit dlya nablizhenoyi ocinki globalnogo minimumu bagatoekstremalnih zadach u skladnij dopustimij dilyanci Cej pidhid mozhna vikoristati ne tilki yak obchislyuvalnij metod ale j yak metod m yakogo opisu sistem Vin dozvolyaye zaminyuvati zadachi zi skladnimi sistemami obmezhen zadachami z prostimi sistemami obmezhen abo zovsim bez nih a takozh rozv yazuvati zadachi z nesumisnimi sistemami obmezhen otrimuyuchi praktichno prijnyatni rishennya U metodi shtrafnih funkcij znachennya shtrafnih koeficiyentiv zazvichaj mozhut zbilshuvatisya neobmezheno Jogo variant metod tochnih shtrafnih funkcij dozvolyaye znahoditi optimalni rozv yazki vzhe pri skinchennih znachennyah shtrafnih koeficiyentiv Ce znachno poslablyuye problemu poganoyi obumovlenosti harakternu dlya metodu shtrafnih funkcij yakij zazvichaj vikoristovuyut dlya otrimannya lishe nablizhenih rozv yazkiv Odnak metod tochnih shtrafnih funkcij daye zmogu otrimuvati tochni rozv yazki pochatovih zadach IstoriyaStrogo matematichno metod shtrafu vpershe vikoristav amerikanskij matematik R Kurant 1943 roku dlya vivchennya ruhu v obmezhenij dilyanci Metodi shiroko zastosovuvalisya v 1960 ti roki dlya rozv yazuvannya zadach lokalnoyi minimizaciyi Odniyeyu z najpopulyarnishih bula programa SUMT rozrobniki amerikanci Fiakko ta Mak Kormik PrikladNehaj potribno rozv yazati taku zadachu z obmezhennyami minf x displaystyle min f mathbf x de ci x 0 i I displaystyle c i mathbf x leq 0 forall i in I Cyu zadachu mozhna rozv yazati yak seriyu zadach minimizaciyi bez obmezhen minFk x f x sk i I g ci x displaystyle min Phi k mathbf x f mathbf x sigma k sum i in I g c i mathbf x de g ci x max 0 ci x 2 displaystyle g c i mathbf x max 0 c i mathbf x 2 U poperednih rivnyannyah g ci x displaystyle g c i mathbf x zovnishnya shtrafna funkciya a sk displaystyle sigma k shtrafni koeficiyenti Na kozhnij iteraciyi k metodu zbilshuyemo shtrafnij koeficiyent sk displaystyle sigma k napriklad u 10 raziv rozv yazuyemo neobmezhenu zadachu ta vikoristovuyemo rozv yazok yak pochatkove pripushennya dlya nastupnoyi iteraciyi Rozv yazki poslidovnih zadach bez obmezhen zbigatimutsya do rozv yazku pochatkovoyi zadachi z obmezhennyami NedolikiNeperebornij u relyefi funkcij shtrafiv i bar yeriv utvoryuyutsya gliboki yari skladnoyi formi de metodi lokalnogo bezumovnogo spusku neefektivni Isnuyut efektivnishi metodi dlya lokalnoyi minimizaciyi z diferencijovnimi funkciyami cili ta obmezhen Div takozhDoslidzhennya operacijPrimitkiZhiliniskas A Shatlyanis V Poisk optimuma kompyuter rasshiryaet vozmozhnosti M Nauka 1989 s 79 ISBN 5 02 006737 7 Tochnye shtrafnye funkcii v linejnom i celochislennom linejnom programmirovanii 1992 5 S 106 115 Metod tochnyh shtrafnyh funkcij dlya linejnyh smeshannyh celochislennyh zadach optimizacii Dissertaciya na soiskanie uchyonoj stepeni doktora fiziko matematicheskih nauk M ISA RAN 2000 glavy 1 5 Dissertaciya i eyo avtoreferat dostupny na sajte Nauchnoj elektronnoj biblioteki eLIBRARY RU v spiske publikacij Shmelyova V V Literatura Kostina M A Metod shtrafov v linejnom programmirovanii i ego realizaciya na EVM Zh vychisl matem i matem fiz 1967 tom 7 nomer 6 1358 1366 Smurov S I Sokolskaya T V Bobkova V A Metody optimizacii Metodicheskie ukazaniya i zadaniya k prakticheskim zanyatiyam i laboratornym rabotam Ivanov him tehnol in t Ivanovo 1990 72 s PosilannyaMetod shtrafnih funkcij ros Potapov M M MDU 2003 ros V inshomu movnomu rozdili ye povnisha stattya Penalisation optimisation fr Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z francuzkoyi Divitis avtoperekladenu versiyu statti z movi francuzka Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad