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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

Например, на практике поставщик продукции платит штрафы за срыв сроков поставки, а исполнитель платит неустойку в случае нарушения условий договора.

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

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

История[править | править вики-текст]

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

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

Недостатки[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 79, ISBN 5-02-006737-7
  2. Шмелев В.В. Точные штрафные функции в линейном и целочисленном линейном программировании. Автоматика и телемеханика. 1992. № 5. С. 106—115.

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]