Метод штрафов
Методы штрафов (методы штрафных функций) — методы, широко используемые для решения технических и экономических задач оптимизации[1].
Эффективны если штрафная функция естественно вытекает из технического смысла задачи.
Многокритериальные задачи минимизации методы штрафа иногда сводят к однокритериальным. Например, при постановке выделяют один основной критерий как целевую функцию, остальные критерии заменяют ограничениями. При программировании учитываются ограничения при помощи штрафа (их переносят в целевую функцию) — таким образом все критерии заменяются одним.
Довольно часто применяются как в теоретических исследованиях, так и при разработке алгоритмов.
Хорошо подходит для приближённой оценки глобального минимума многоэкстремальных задач в сложной допустимой области.
Этот подход может быть использован не только как вычислительный метод, но и как метод «мягкого» описания систем. Он позволяет заменять задачи со сложными системами ограничений задачами с простыми системами ограничений или вовсе без них, а также решать задачи с несовместными системами ограничений, получая практически приемлемые решения.
В методе штрафных функций значение штрафных коэффициентов, как правило, могут увеличиваться неограниченно. Его вариант — метод точных штрафных функций позволяет находить оптимальные решения уже при конечных значениях штрафных коэффициентов[2][3]. Это значительно ослабляет проблему плохой обусловленности, характерную для метода штрафных функций, который, как правило, используется для получения только приближенных решений. Однако метод точных штрафных функций позволяет получать точные решения исходных задач.
История
[править | править код]Строго математически метод штрафа впервые использовал американский математик Р. Курант в 1943 г. (для изучения движения в ограниченной области)[1].
Методы широко применялись для решения задач локальной минимизации в 60-е годы. Одной из наиболее популярных была программа SUMT (разработчики — американцы Фиакко и Мак Кормик).
Недостатки
[править | править код]Непреодолимый: в рельефе функций штрафов и барьеров образуются глубокие овраги сложной формы, где все методы локального безусловного спуска неэффективны[1].
Существуют более эффективные методы для локальной минимизации с дифференцируемыми функциями цели и ограничений.
См. также
[править | править код]Примечания
[править | править код]- ↑ 1 2 3 Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 79, ISBN 5-02-006737-7
- ↑ Шмелёв В. В. Точные штрафные функции в линейном и целочисленном линейном программировании. Автоматика и телемеханика, . 1992. № 5. С. 106—115.
- ↑ Шмелёв В. В. Метод точных штрафных функций для линейных смешанных целочисленных задач оптимизации. Диссертация на соискание учёной степени доктора физико-математических наук, М.: ИСА РАН, 2000, главы 1-5. Диссертация и её автореферат доступны на сайте Научной электронной библиотеки eLIBRARY.RU в списке публикаций Шмелёва В.В.
Литература
[править | править код]- Ерёмин И. И., Костина М. А. Метод штрафов в линейном программировании и его реализация на ЭВМ // ЖВМиМФ, 1967, том 7, номер 6, 1358—1366
- Смуров С. И., Сокольская Т. В., Бобкова В. А. Методы оптимизации: Методические указания и задания к практическим занятиям и лабораторным работам / Иванов. хим.-технол. ин-т; Иваново, 1990. 72 с.
Ссылки
[править | править код]- Метод штрафных функций
- Потапов М. М. Методы оптимизации. Конспект лекций, МГУ, 2003