Метод штрафів

Ме́тоди штра́фів (ме́тоди штрафни́х фу́нкцій) — методи, що широко використовуються для розв'язування технічних та економічних задач оптимізації.

Ефективні якщо штрафна функція природно випливає із технічного сенсу задачі.

Багатокритеріальні задачі мінімізації методи штрафів іноді зводять до однокритеріальних. Наприклад, під час постановки виділяють один основний критерій як цільову функцію, інші критерії замінюють обмеженнями. При програмуванні враховують обмеження за допомогою штрафу (їх переносять на цільову функцію) — завдяки цьому всі критерії замінюються одним.

Досить часто застосовують як у теоретичних дослідженнях, так і під час розробки алгоритмів.

Добре підходить для наближеної оцінки глобального мінімуму багатоекстремальних задач у складній допустимій ділянці.

Цей підхід можна використати не тільки як обчислювальний метод, але й як метод «м'якого» опису систем. Він дозволяє замінювати задачі зі складними системами обмежень задачами з простими системами обмежень або зовсім без них, а також розв'язувати задачі з несумісними системами обмежень, отримуючи практично прийнятні рішення.

У методі штрафних функцій значення штрафних коефіцієнтів, зазвичай, можуть збільшуватися необмежено. Його варіант — метод точних штрафних функцій дозволяє знаходити оптимальні розв'язки вже при скінченних значеннях штрафних коефіцієнтів. Це значно послаблює проблему поганої обумовленості, характерну для методу штрафних функцій, який зазвичай використовують для отримання лише наближених розв'язків. Однак метод точних штрафних функцій дає змогу отримувати точні розв'язки початових задач.

Історія

Строго математично метод штрафу вперше використав американський математик Р. Курант 1943 року (для вивчення руху в обмеженій ділянці).

Методи широко застосовувалися в 1960-ті роки для розв'язування задач локальної мінімізації. Однією з найпопулярніших була програма SUMT (розробники — американці Фіакко та Мак Кормік).

Приклад

Нехай потрібно розв'язати таку задачу з обмеженнями:

${\displaystyle \min f(\mathbf {x} )}$

де

${\displaystyle c_{i}(\mathbf {x} )\leq 0~\forall i\in I.}$

Цю задачу можна розв'язати як серію задач мінімізації без обмежень

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\sigma _{k}~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))}$

де

${\displaystyle g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}.}$

У попередніх рівняннях, ${\displaystyle g(c_{i}(\mathbf {x} ))}$ — зовнішня штрафна функція, а ${\displaystyle \sigma _{k}}$ — штрафні коефіцієнти. На кожній ітерації k методу, збільшуємо штрафний коефіцієнт ${\displaystyle \sigma _{k}}$ (наприклад, у 10 разів), розв'язуємо необмежену задачу та використовуємо розв'язок як початкове припущення для наступної ітерації. Розв'язки послідовних задач без обмежень збігатимуться до розв'язку початкової задачі з обмеженнями.

Недоліки

Непереборний: у рельєфі функцій штрафів і бар'єрів утворюються глибокі яри складної форми, де методи локального безумовного спуску неефективні.

Існують ефективніші методи для локальної мінімізації з диференційовними функціями цілі та обмежень.

Див. також

• Дослідження операцій

Примітки

1. Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 79,
2. Точные штрафные функции в линейном и целочисленном линейном программировании. , . 1992. № 5. С. 106—115.
3. Метод точных штрафных функций для линейных смешанных целочисленных задач оптимизации. Диссертация на соискание учёной степени доктора физико-математических наук, М.: ИСА РАН, 2000, главы 1-5. Диссертация и её автореферат доступны на сайте Научной электронной библиотеки eLIBRARY.RU в списке публикаций Шмелёва В. В.

Література

• , Костина М. А. Метод штрафов в линейном программировании и его реализация на ЭВМ, Ж. вычисл. матем. и матем. физ., 1967, том 7, номер 6, 1358—1366
• Смуров С. И., Сокольская Т. В., Бобкова В. А. Методы оптимизации: Методические указания и задания к практическим занятиям и лабораторным работам / Иванов. хим.-технол. ин-т; Иваново, 1990. 72 с.

Посилання

• Метод штрафних функцій (рос.)
• Потапов М. М. , МДУ, 2003 (рос.)