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

Методы штрафов (методы штрафных функций) — методы, широко используемые для решения технических и экономических задач оптимизации.

Эффективны если штрафная функция естественно вытекает из технического смысла задачи.

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

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

Хорошо подходит для приближённой оценки глобального минимума многоэкстремальных задач в сложной допустимой области.

Этот подход может быть использован не только как вычислительный метод, но и как метод «мягкого» описания систем. Он позволяет заменять задачи со сложными системами ограничений задачами с простыми системами ограничений или вовсе без них, а также решать задачи с несовместными системами ограничений, получая практически приемлемые решения.

В методе штрафных функций значение штрафных коэффициентов, как правило, могут увеличиваться неограниченно. Его вариант — метод точных штрафных функций позволяет находить оптимальные решения уже при конечных значениях штрафных коэффициентов. Это значительно ослабляет проблему плохой обусловленности, характерную для метода штрафных функций, который, как правило, используется для получения только приближенных решений. Однако метод точных штрафных функций позволяет получать точные решения исходных задач.

ИсторияПравить

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

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

НедостаткиПравить

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

Существуют более эффективные методы для локальной минимизации с дифференцируемыми функциями цели и ограничений.

См. такжеПравить

• Исследование операций
• Список алгоритмов

ЛитератураПравить

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

СсылкиПравить

• Метод штрафных функций
• Потапов М. М. Методы оптимизации. Конспект лекций, МГУ, 2003