30 Постановка знлп с огран-ми - рав-ми

Решается задача: f(x)max(min) (1)

g₁(x)=b₁

g₂(x)=b₂

… (2)

g_m(x)=b_m

В более компактной форме имеет вид:

f(x)max(min) (3)

g(x)=b (4)

Где b^т=(b₁,b₂,…,b_m) - заданный вектор правой части ограничений .

g^т(х)=(g₁(x),g₂(x),…,g_m(x))- вектор-ф-ия задач (3)-(4).

Решить приведенные задачи означает: найти точку локального экстремума х^*Д целевой ф-ии f(x), где область Д- это множество точек х, являющ-ся решением сис-мы огр-ний (2).

Огр-ния (2)или (4) - это и есть условие, выполнение которого обяз-но при поиске экстремума целевой ф-ии.

31 Назначение и обоснование метода множителей Лагранжа

Метод предназначен для решения задач

f(x)max(min) (1)

g₁(x)=b₁

g₂(x)=b₂

… (2)

g_m(x)=b_m

или

f(x)max(min) (3)

g(x)=b (4)

В основе метода лежит тот факт..., что в точке условного экстремума х^*Д градиент f(х*) целевой ф-ии д.б. ортогонален касательной гиперплоскости к области ограничений Д, определенной в (2) или (4).

Это означает, что должны существовать такие числа ₁,₂,…,_m, для которых f(х*)=_j=1^m_jg_j(x^*), (5), т.е. градиент представим в виде линейной комбинации градиентом ф-ии ограничений, которые в свою очередь ортогональны мн-вам ур-ня Мj={x:g_j(z)=b_j}, j=1,m.

Соотношение (5) и дает основу методу множителей Лагранжа.

32 Схема реализации метода множителей Лагранжа

1) В рассмотрение вводится ф-ия Лагранжа: L(x, )=f(x)+ ^т(b-g(x))=f(x)+ +_j=1^m_j(b_i-g_i(x)) (1),

где х^т=(х₁,х₂,…,х_n)-вектор инструментальных пер-ных ф-ии Лагранжа;

^т=(₁,₂,…,_m)-вектор мн-лей Л.

2) Опр-ся стационарные точки (х^*,^*) ф-ии Л.Для этого решается след-щая сис-ма Ур-ний, представ-щая собой необходимые условия существования экстремумов ф-ии Л.

Сис-ма Ур-ний (2) представима в более компактной форме:

где

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

R_g(x)-м-ца Якоби вектор-ф-ии огр-ний g(x).

3) Опр-ся тип условного экстремума целевой ф-ии f(x) в найденных стац-ных точках х^*, удовл-щих сис-мам (2) и (3).Для этого в рассмотрение вводится т.н. окаймленная м-ца Гессе, имеющая след-щую блочную стр-ру:

где R_g(x^*,^*)-м-ца Якоби,

-м-ца Гессе ф-ии Лагранжа, эл-ты кот-ой опр-ся знач-ми частныз пр-ных вторго порядка ф-ии Л. по инстр-ным пер-ным.

Тип экстремума стац-ной точки x^*следует из приведенных ниже достаточных усл-ий: 1)Точка x^*-точка макс-ма ф-ии f(x), если, начиная с главного минора порядка 2m+1 окаймленной м-цы Гессе, все посл-щие n-m главных миноров этой м-цы образуют знакопеременный числовой ряд, причем знак первого члена этого рядаопр-ся знаком (-1)^m+1.

2) Точка x^{* -} точка мин-ма ф-ии f(x), если, начиная с главного минора порядка 2m+1 окаймленной м-цы Гессе, все последующие n-m главных миноров этой м-цы имеют одинаковые знаки, определяемые мн-лем (-1)^m, (m-число огр-ний исходной з-чи; n-число пер-ных аргументов цел-ой ф-ии исходной з-чи).