Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Условная многомерная минимизация решения задач НЛП. Метод штрафных функций.

Преобразовать задачу поиска минимума выпуклой функции f(x) с наложенными на нее ограничениями в виде неравенств, в котором все g_i(x_i)<=b_i также выпуклые и x_j>=0.

F(x)=f(x)+H(x)

Функция H(x) определяется заданной системой ограничений и называется штрафной функцией поскольку ее роль сводится к штрафованию функции F при нарушении заданных ограничений. Вид штрафной функции не единственный, но обычно принимается, что штрафная функция вычисляется H(x) = sum(i=1…m)(a_i(x)*g_i(x)), где

a_i = 0 if g_i(x)<=b_i, ai if gi(x) > bi. Ai — веса штрафной функции. Используя штрафную функцию последовательно переходят от одной точки решения к другой до необходимого значения. Координаты точек на следующем шаге находятся:

x_j^k+1=min(0; x_j^k +(∂f(x_j^k)/ ∂x_j +∑альфа_i; ∂g^{(x^-k)}/ ∂x_i))

Из этой формулы видно, что если предыдущая точка в направлении j находится в области допустимых значений, то второе слагаемое в квадратных скобках будет нулевым и переход к новой точке или новой координате определяется только градиентом целевой функции. В том случае, если точка не принадлежит области допустимых значений, то за счет ненулевого второго слагаемого на нескольких последующих итерациях достигается возвращение точки в область допустимых значений. Чем меньше ai, тем быстрее находится решение. Но при этом точность снижается. Поэтому в данном методе поступают так: начальные ai сравнительно малы, а в процессе вычисления их значение увеличивают.

Алгоритм:

1. Определяется исходное допустимое решение.

2. Выбирается шаг вычисления.

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

4. Находится новое решение (новые координаты точек).

5. Проверяется удовлетворяет ли найденное решение заданной системе ограничений. Если да, то происходит проверка на окончание процесса, если условия окончания удовлетворяются, то задача решена и стоп. Если нет, то переход к пункту 2. Если найденные решения не удовлетворяют заданной системе ограничений, то переходим к этапу 6.

6. Устанавливаются новые значения весовых коэффициентов и происходит переход к этапу 4.

В данном методе самой плохой стороной является произвольный выбор весовых коэффициентов ai, поэтому получаются значительные колебания точек. Это существенно замедляет сходимость процесса, данный недостаток отсутствует в методе Эрроу-Гурвица, который является разновидностью метода штрафных функций. В данном методе ai задаются только в начале, далее они рассчитываются по формуле:

Альфаi^k=max(0;альфаi^k-лямбдаg(x^-k))

Благодаря этому происходит целенаправленное изменение весовых коэффициентов и скорость сходимости увеличивается.