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

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

Пусть имеем задачу

Формируется новый критерий, например с квадратичным "штрафом" для ограничений типа равенств:

с модульным "штрафом":

с комбинированным "штрафом":

(индексы суммирования для простоты опущены), где a — коэффициент "штрафа". Он характеризует вклад в общий критерий оптимальности. Rp — новый критерий, F_(x) — срез функции F(x); он определяется по следующему правилу:

Отклонения от ограничений увеличивают критерий Rp, т.е. как бы накладывают "штраф" Н на Rp. Уменьшение Rp происходит как за счет уменьшения R(x}, так и за счет уменьшения величины нарушения ограничения.

В точке минимума ограничения будут справедливы, т.е. равны нулю, и поэтому R * = R_p*. Однако это соотношение будет справедливо только при коэффициенте "штрафа", стремящемся к бесконечности.

Увеличение a, с одной стороны, не допускает больших откло­нений в "запретные" стороны от ограничений (это хорошо), а с другой — увеличивает "овражность" Rp (овраг размерности m имеет место вдоль ограничений), что резко усложняет поиск оп­тимума Rp (это плохо).

Поэтому целесообразно решать задачу сначала с маленьким значением a, потом его увеличивать. Это будет способствовать более быстрому выходу в область условного оптимума и точному его определению.

Существуют и другие структуры Rp, в частности учитываю­щие сравнительную важность отдельных ограничений. При этом каждое ограничение может иметь свой коэффициент штрафа.

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

Дата добавления: 2014-01-13