Кудрявтсев Методы оптимизатсии 2015
.pdf2.3Условная оптимизация функций многих переменных
2.3.1 Основные понятия и определения
Постановка задачи |
|
|
|
, |
, , … , |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Пусть задана функция n |
действительных переменных |
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
, |
|
|
|
(2.14) |
|||||
определенная на множестве |
|
|
|
|
|
которая представляет из себя |
||||||||||||||
|
|
|
|
|
||||||||||||||||
функцию цели (функцию |
качества). Требуется найти |
|
|
дос- |
||||||||||||||||
|
j k |
|
|
|
|
|
|
|
при ограниче- |
|||||||||||
тавляющий максимум (минимум) данной функции |
|
|
j, |
|
||||||||||||||||
ниях вида: |
|
@ |
|
0, @ |
|
0, … , @ |
|
0, |
|
|
|
|
|
|||||||
т.е. имеется |
|
|
0, |
|
|
0, … , |
|
0, |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
p ограничений заданных в виде равенств и m-p огра- |
|||||||||||||||||||
его легко переписать в виде |
|
|
|
|
|
. |
|
|
|
0, то |
||||||||||
ничений, заданных в виде неравенств. Как было отмечено ранее, |
||||||||||||||||||||
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
||||||
если какое-либо ограничение представлено в виде |
|
|
|
|
|
|||||||||||||||
в |
|
|
, , … , |
, @ , , … , |
, , , … , , |
|||||||||||||||
1, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Функции |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
общем случае нелинейны. В отличие от задач линейного программирования для задач нелинейного программирования не существует универсального метода решения.
В методах оптимизации с ограничениями используются понятия
выпуклых и вогнутых функций. |
|
|
|
|
|
|
|
|
назы- |
|||||||||||
Функция |
|
|
определенная на выпуклом множестве |
|
||||||||||||||||
вается выпуклой вверх, если для любой пары точек |
|
|
|
|
|
|
|
и |
||||||||||||
|
|
, |
|
|
|
|
|
|
|
|
|
|
|
|
k |
, |
|
|
|
|
произвольного |
0 |
| 1 |
выполняется неравенство |
|
, |
k |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
||
Если |
| |
A 1 | |
|
| A 1 | |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
называется вогнутой (выпуклой вниз). |
|
|
|
|
|
|
|
|
||||||||||
то функция| |
A 1 | |
|
|
| A 1 | , |
|
|
|
|
|
|
||||||||||
Нетрудно установить, |
что если |
|
функции |
|
|
|
|
|
|
|
|
|||||||||
выпуклы (вогнуты) на множестве |
|
, то |
функция |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
k |
|
, , … , |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
61 |
|
|
|
|
|
|
|
|
|
|
|
|
также выпукла (вогнута), если | 0, 1, Š .
Обобщенный алгоритм поиска условного экстремума
1.Поиск всехkстационарных точек функции на выпуклом множестве .
2.Исследование точек границы, с отысканием тех из них, где достигает максимума.
3.Непосредственным сравнением точек, найденных в п. 1 и 2, определяют точку абсолютного максимума.
Следует отметить, что такой подход может применяться только в простых случаях, при небольшом числе ограничений.
2.3.2 Метод множителей Лагранжа
|
|
|
Метод неопределенных множителей Лагранжа позволяет оты- |
|||||||||||||||||||||||||||||||
|
скивать максимум (минимум) функции при ограничениях равенст- |
|||||||||||||||||||||||||||||||||
|
вах. Основная идея метода заключается в переходе от задачи ус- |
|||||||||||||||||||||||||||||||||
|
ловной оптимизации к задаче поиска безусловного экстремума |
|||||||||||||||||||||||||||||||||
|
специально построенной функции Лагранжа. |
|
|
|
||||||||||||||||||||||||||||||
|
|
|
Рассмотрим задачу поиска минимума функции цели при огра- |
|||||||||||||||||||||||||||||||
|
ничениях равенствах: |
|
|
, , … , |
|
|
‹ min |
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ , , … , |
0 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
0 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Œ |
|
|
, , … , |
|
|
|
(2.15) |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
цию |
|
|
|
λ , λ |
, … , λ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
Предположим, что |
|
все функции дифференцируемы. Введем m |
|||||||||||||||||||||||||||||
|
|
|
|
|
@ |
|
|
, , … , |
|
|
0. |
|
|
|
|
|||||||||||||||||||
|
переменных |
|
|
|
|
|
F |
|
|
(множителей Лагранжа) и составим функ- |
||||||||||||||||||||||||
|
|
|
|
Лагранжа: |
|
|
|
|
, , … , , λ , λ , … , λ |
|
|
|
|
|||||||||||||||||||||
|
|
|
или в |
|
|
|
|
, , … , |
A ∑ |
|
λ |
|
@ |
, , … , |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.16) |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F , Λ |
! A |
Λ · y!, |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
векторной форме |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
Λ λ , λ , … , λ |
|
|
|
|
|
|
y @ , @ , … , @ |
|
|
|
|
|||||||||||||||||||||
|
( |
|
( |
|
∑ |
|
|
λ @ |
|
|
|
( |
|
|
|
|
|
|
|
|
( ( 9 |
|
|
|
||||||||||
|
Λ |
· y! |
|
|
и |
|
|
|
|
|
|
|
|
|
|
– векторы, |
|
|||||||||||||||||
где |
( |
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
а |
|
|
|
|
|
|
|
|
|
|
|
|
|
—(скалярное |
|
произведение. |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
62 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, , … , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
Покажем, что для решения задачи (2.15) т.е. для отыскания точ- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ки |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, обеспечивающей минимум функции |
|
, |
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
, , … , |
|
|
|
|
|
|
λ |
|
, λ , … , λ |
, |
|
|
|
|
|
|
|
|
|
|
(2.17) |
||||||||||||||||||||||||||||
необходимо решить систему нелинейных уравнений относительно |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
неизвестных |
|
|
|
|
|
|
|
|
|
|
|
|
8(+ > ,DE> - |
0, |
|
|
|
1, |
|
: |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8(+ > |
E |
> |
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
,D |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.18) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8C |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Для доказательства |
предположим, что функции |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
0, 1, . |
|
|
|
|
x@ |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
x@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
градиенты |
|
|||||
имеют непрерывные производные первого порядка, а , @ |
, @ , … , @ |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Žx@ |
Ž |
|
; p@ |
|
|
|
|
Žx@ |
Ž |
|
|
|
|
|
|
|
|
|
Ž |
x@ |
|
|
Ž |
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
p@ |
|
|
|
|
x |
|
|
|
|
|
|
|
|
x |
|
|
|
|
; P ; p@ |
|
x |
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
• |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
• |
|
|
|
|
|
|
|
|
|
|
|
|
|
• |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Žx@ |
Ž |
|
|
|
|
|
|
|
|
|
|
|
Žx@ |
Ž |
|
|
|
|
|
|
|
|
|
|
Ž |
x@ |
|
|
Ž |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
||||||||
линейно независимы. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
, , … , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
Представим, что из уравнений ограничений можно явно выра- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
• |
|
|
, |
|
• , … , • |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||
зить переменные |
|
|
|
|
|
|
|
! |
|
|
|
|
|
через |
|
|
, т.е. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
! |
|
|
|
|
|
|
! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
В этом случае задачу условной минимизации можно свести к |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Для |
|
|
|
|
|
|
, • |
|
|
, • |
|
, … , • |
|
|
‹ min. |
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||
безусловной: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
нять ее нулю и решить |
|
|
|
|
|
|
|
|
, • |
|
|
|
, • |
|
, … , • , |
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
нахождения стационарных точек необходимо найти произ- |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
водную сложной функции |
|
|
|
|
|
|
|
|
|
|
|
|
! |
|
|
|
x |
|
|
|
|
|
прирав- |
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
‘ |
|
|
|
x |
|
|
|
|
x |
‘• |
|
|
|
|
x ! |
|
‘• |
|
|
|
|
|
‘• |
0. |
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
‘ |
|
|
x |
|
|
A x |
‘ |
|
|
A x |
|
|
|
|
‘ |
|
|
A P A x |
|
‘ |
|
|
|
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
уравнение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для ограничений можно записать |
|
|
|
x@ |
‘• |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
‘@ |
|
|
x@ |
|
|
x@ |
‘• |
|
|
|
x@! |
|
‘• |
|
|
|
|
|
|
|
|
|
|
0, |
|
|
|
1, . |
|
||||||||||||||||||||||||||||||||
‘ |
|
x |
|
A x |
|
‘ |
|
A x |
|
|
‘ |
! |
A P A x |
|
‘ |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
63 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Данные уравнения могут]быть· T записаны0, в матричной форме (2.19)
где |
|
|
|
|
|
|
|
|
P |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
8 |
|
|
8 |
|
|
8 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
] |
|
|
8 |
|
8 |
|
8 |
|
; |
T |
FG |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
8$ |
|
8$ |
|
8$ |
|
|
|
|
FG |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
Ž |
|
|
|
|
|
|
’ |
|
|
|
Ž |
|
|
|
F |
|
|
|
|
|
• |
|
• |
|
• |
|
|
|
|
. |
|||||||
|
|
Ž |
|
8 |
|
8 |
P |
|
8 |
Ž |
|
|
|
F |
Ž |
||||
|
|
|
8$ |
8$ |
P |
8$ |
|
|
|
Ž • |
|
||||||||
|
|
|
|
8 |
|
8 |
8 |
|
|
| . |
|
|
|
|
|||||
Поскольку |
|
] |
|p , p@ |
, p@ , … p@ |
|
|
|
|
|||||||||||
Матрицу A можно записать в векторной форме: |
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|||
|
вектор |
не нулевой, то для получения ненулевого |
|||||||||||||||||
|
|
|
|
уравнения (2.19) требуется, чтобы определи- |
|||||||||||||||
решения матричного T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
тель матрицы был равен нулю, т.е. строки матрицы должны быть |
|||||||||||||||||
|
|
|
/ |
|
p A / p@ A / p@ A P A / p@ 0, |
|
|
||||||||||
линейно зависимы, а именно должно выполняться соотношение: |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
причем коэффициенты |
|
|
|
|
не должны быть равны ну- |
||||||||||||
лю одновременно. |
|
|
/ , / , / , … , / |
|
|
|
|
|
|
||||||||
Так как по условию |
|
|
|
|
линейно независимые, то |
||||||||||||
коэффициент |
|
не |
|
может равняться нулю (так как в противном |
|||||||||||||
|
|
|
|
p@ |
, p@ , … , p@ |
|
|
должны бы быть |
|||||||||
|
|
|
остальные коэффициенты |
|
|
|
|||||||||||
случае все |
|
/ |
|
|
|
|
|
|
|
|
|
|
|
|
|||
равными нулю, а это противоречит |
требованию линейной зависи- |
||||||||||||||||
|
/ , / , … , / |
|
|
/ |
, полу- |
||||||||||||
мости |
строк матрицы A). Разделив данное уравнение на |
||||||||||||||||
чим: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p A λ p@ A λ p@ A P A λ p@ 0, |
(2.20) |
||||||||||||||||
λ |
|
|
, 1, |
— |
|
|
|
|
|
|
|
|
|||||
где |
|
|
|
|
|
, |
|
|
точка решения системы (2.19). |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом, для решения задачи минимизации с ограниче- |
||||||||||
1, |
|
|
|
|
|
|
|
|
|
|
ниями (2.15) должны существовать такие коэффициенты |
|
|
|
|
||||||
|
, которые одновременно не обращаются в нуль, и |
выполня- |
||||||||
|
|
“ |
, |
|||||||
ется соотношение (2.20). |
F , Λ! A Λ · y |
|
|
( |
||||||
Если теперь ввести функцию |
|
|
|
|
|
|
|
и Λ |
||
|
|
|
|
|
|
, то, вы- |
||||
числяя частные производные этой |
функции от ее аргументов |
|
|
|||||||
|
( |
( |
( |
|
|
|
|
|||
|
|
64 |
|
|
|
|
|
|
|
и приравнивая их нулю, получим уравнения (2.20) и (2.15). В самом деле
|
E> |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
HI+J> |
, Λ - |
|
HM)J> |
* |
|
|
|
|
HP )J> |
* |
|
|
|
HP )J> |
|
* |
|
|
|
|
|
|
HP )J> |
* |
|
|
|
|
|
|
||||||||
|
L |
N O |
N O |
|
|
N Q N O |
L 0, |
S L 1, U, |
|||||||||||||||||||||||||||||||
|
HJ |
|
HJ |
|
|
HJ |
|
|
HJ |
|
|
|
|
HJ |
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
HI |
L P )J> * L 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
V L 1, W. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
HO |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
Из всего вышесказанного следует теорема Лагранжа. |
|
|
|
|
|
||||||||||||||||||||||||||||||||||
имеют непрерывные частные |
|
|
|
|
|
|
|
, @ |
|
, @ , … , @ |
|||||||||||||||||||||||||||||
Задана задача (2.15) нахождения минимума функции при огра- |
|||||||||||||||||||||||||||||||||||||||
ничениях |
равенствах. |
Все |
|
функции |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
производные на множестве |
|
. Пусть |
||||||||||||||||||||
существует точка |
|
|
в которой достигается |
относительный экстре- |
|||||||||||||||||||||||||||||||||||
|
|
, |
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
Если ранг матрицы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
мум задачи (2.15). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, … , λ |
|
|
|
|
|
||||||||||
|
|
равен m, то существуют m |
|
|
|
|
λ , λ |
|
|
|
|
|
|
||||||||||||||||||||||||||
в точке |
|
чисел |
|
|
|
|
|
|
, не все од- |
новременно равные нулю, для которых справедливо соотношение |
|||||||||||
|
|
|
p A ∑ λ @ 0. |
|
(2.21) |
||||||
Алгоритм метода неопределенных множителей Лагранжа: |
|||||||||||
|
|
|
( |
|
(8(+( |
|
|
|
|||
|
|
|
|
F , Λ! A |
Λ · y!. |
|
|
|
|||
1. Составление функции Лагранжа |
|
|
0, |
1, |
|
||||||
8(+ >,DE>- |
|
|
|
|
|
8 |
|
||||
|
|
|
|
|
|
|
|
E> |
|
|
|
2. Нахождение частных производных |
>,D- |
|
|
и |
|||||||
|
|
|
0, 1, . |
|
|
|
|
|
|
|
|
3. |
|
|
|
|
|
|
|
|
|
||
8C |
|
|
|
xF , |
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
Λ! |
|
|
|
|
|
|
|
|
Решение системы уравнений |
|
|
|
|
|
|||||
|
|
|
|
x |
|
0, |
|
1, , |
|
|
|
|
|
|
|
|
|
65 |
|
|
|
|
|
|
|
xF , |
( |
|
|
|
|
|
|
Λ! |
|
|
|
||
|
|
|
|
0, |
1, . |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
4. Исследование |
решения системы точек |
|
на минимум. |
||||
|
xλ |
|
|
|
|
2.3.3Пример использования метода неопределенных множителей Лагранжа
Найти минимум целевой функции |
|
|
|
|||||||
при ограничениях , |
|
A ! ” min |
|
|||||||
|
|
|
|
|
|
|
|
2 0, |
|
|
|
|
|
|
, |
|
|
|
|||
Составим |
функцию Лагранжа |
|
|
2 0. |
|
|||||
|
|
|
, |
|
|
|||||
, , , λ , λ |
λ |
2 λ 2 . |
||||||||
Дифференцируя |
функцию |
, , , λ , λ |
по переменным |
, , !, λ , λ и приравнивая полученные выражения нулю, полу-
|
|
|
|
|
λ |
0 |
|
|
|||
чим следующую систему уравнений: |
|
|
|||||||||
|
$ |
|
λ λ 0 |
||||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
# |
|
|
|
|
λ |
|
|
|||
|
|
|
|
2 0 |
|
||||||
|
|
! 1; |
|||||||||
Из первого и третьего |
уравнения следует |
|
|
||||||||
! |
|
|
|
|
|
2 0. |
|
||||
данную систему, находим |
|
|
|
|
|
|
|
|
λ |
λ 2 . Решая
.
2.3.4Поиск условного экстремума при ограничениях– неравенствах. Теорема Куна-Такера
Рассмотрим задачу поиска минимума функции цели при огра- ничениях–неравенствах: , , … , ‹ min
66
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& , , … , |
( 0 |
|
|
|
|
|
|
|
|
|
|
|
(2.22) |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
, , … , |
|
( 0 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
% |
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
, , … , ( 0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
||||||||||||||||||
если оно |
|
|
|
|
|
|
|
, , … , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0. |
|
|
|
|||||||||||||||||||
|
Ограничение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
называется активным в точке |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
выполняется как строгое равенство, т.е. |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
Рассмотрим случай линейных ограничений, т.е. |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||
|
Здесь |
|
|
– |
|
|
|
|
& |
|
|
*µ + |
|
( 0, |
- 1, . |
|
|
|
|
, , … , |
|
|
|||||||||||||||||||||||||||||
можно представить как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
µ( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
вектор постоянных коэффициентов размерности n, а |
|||||||||||||||||||||||||||||||||||||||||||
|
обозначает скалярное произведение векторов |
|
|
|
и . |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
µ( Представляя приведенное выражение в |
другом виде, нетрудно |
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
µ( |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||
заметить, что ограничения задаются неравенствами вида |
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
|
|
|
|
|
|
|
|
|
|
. Допус- |
|||||
и каждое ограничение |
определяет полупространство в |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
*µ / + , |
|
- 1, . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
µ( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m полупространств, причем |
|||||||||||||||||||
тимая область задается пересечением |
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
Заметим, что |
|
0, . |
|
|
|
|
|
|
к |
|
|
гиперплоскости, определяемой |
|||||||||||||||||||||||||||||||||||||||
вектор |
|
|
|
|
является |
|
нормалью |
|
|
||||||||||||||||||||||||||||||||||||||||||
|
Пусть |
|
|
|
|
|
µ( |
|
p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
внутрь |
допустимой |
области. |
|||||||||||||||||||||||
уравнением |
|
|
|
|
|
|
|
и направлен |
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
является точкой минимума задачи (2.22). Обозначим |
|||||||||||||||||||||||||||||||||||||||||||||
|
Для любой точки |
|
|
– |
|
\: |
|
|
|
|
0&. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
множество индексов активных ограничений как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
так как |
|
|
|
|
|
|
*µ |
|
|
|
|
находящейся внутри допустимой области |
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
/ 0 |
|
|
|
|
|
|
0& |
|
|
|
|
|
|
|
|
( 0; |
|
|
- 2 3, |
|
|
|
|
|
|
|
||||||||||||||||||
ограничений, |
справедливо выражение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
Если |
|
|
– |
|
|
|
µ( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
векторы |
|
и |
|
|
|
|
|
|
|
|
являются однонаправленными. |
|
|
|
|
|
|||||||||||||||||||||||||||||||||
в силу того, что |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
/ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
точка минимума функции, то |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
однонаправленными. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
градиент направлен в сторону максимального воз- |
|||||||||||||||||||||||||||||||||||||||||
растания функции, и, следовательно, |
|
|
|
|
|
и |
|
|
|
|
|
|
|
являются |
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
*µ |
|
|
|
|
|
|
|
|
/ 0, |
- 1, ., |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
Таким образом, имеем очень важные неравентства: |
|
|
|
|
|
|
|
. |
||||||||||||||||||||||||||||||||||||||||||
|
Для дальнейших |
|
|
|
0 |
|
|
|
|
|
|
|
/ 0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.23) |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
преобразований воспользуемся леммой Фаркаша
67
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
λ |
|
|
|
|
|
A – матрица размерности m x n, |
|
|
|
– вектор размерности |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
m, |
Пусть |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
– |
вектор размерности |
n. |
Тогда имеет |
|
решение только одна из |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
систем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4λ +, |
|
|
|
|
λ / 0, λ 2 5 , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 ( 0, |
|
|
|
, + / 0 |
|
|
2 5 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1)T * |
* |
|
|
|
|
|
* |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.24) |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
(2.25) |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 ] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a ] 0 a, 0 |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
Доказательство. Пусть система* |
(1) имеет решение, т.е. сущест- |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
вует |
|
|
|
|
, а |
|
|
|
|
|
|
|
|
|
|
|
, то |
|
|
|
|
]λ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a, ]λ! a ], λ! |
|
. Под- |
|||||||||||||||||||||||||||||
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
. Предположим, что |
|
|
|
T |
|
|
|
|
|
|
и |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
λ 0 a ] 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a, 0, |
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
ставим вместо |
|
выражение |
|
|
|
, получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. Но так |
|||||||||||||||||||||||||||||||||||||||||||||||||
как |
|
|
|
y( , 0 |
|
|
|
|
|
|
|
|
|
получим( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
т.е.( |
противоречие( |
с ус- |
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
T |
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
ловием |
|
|
|
|
|
|
|
|
|
|
|
. Следовательно, |
|
если система (1) имеет решение, |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
то система ((2) его не имеет. |
i |
˜с: с ]λ, λ 0š |
|
|
|
|
|
|
]λ › |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
. По теореме об |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Пусть теперь система (1) не имеет решения. Рассмотрим замк- |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
f i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Так как |
|
и( |
|
|
|
, |
|||||||||
нутое выпуклое множество |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
то |
|
|
|
|
|
|
|
|
|
Š, ! G α |
|
|
|
|
|
|
отделимости выпуклого( ( |
множества. |
точ(- |
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Š, с |
α |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 i |
||||||||||||||||||||||||
ки,( которая ему не принадлежит, существуют вектор |
|
|
и число |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
такие, что |
α 0 |
|
. |
|
|
|
|
Š, ! G α G 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
α |
Š, с |
||||||||||||||||||||||||||||||||||||||
Š, ]λ! Š ], λ! |
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
|
. По условию нулевой |
Š |
|
|
|
( |
|
α |
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
λ 0 |
|
. С другой стороны, |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
и |
|
значит |
|
|
|
|
|
|
( |
|
и |
|
|
Так(как |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Š |
|
], λ! α |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
Š |
|
] 0 |
|
|
выполнение( |
|
|
|
Š |
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
обеспечивается |
|
при |
||||||||||||||||||||||||||||||||
шим,( |
то |
|
|
|
условия( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
T |
|
|
|
|
|
. Следовательно, |
|
T – решение |
(системы |
(2). |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Вернемся к |
анализу неравенств (2.23). Первые |
m неравенств |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
*µ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
можно представить в матрично-векторной форме: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
*µ |
|
|
|
|
|
|
|
|
|
/ 0 или |
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
*µ , *µ , … , *µ |
|
/ 0. |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
, |
перепишем ] |µ( , µ( , … , µ( |
|
|
|
|
|, |
|
|
a |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, а |
|
также |
|||||||||||||||
|
|
Вводя |
|
|
обозначения |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
*µ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
] 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
неравенства (2.21) в виде |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a 0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
В соответствии с леммой |
Фаркаша система (2.25) не выполняет- |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ся и, следовательно, должна иметь решение система (2.24), т.е.
68
|
|
|
|
|µ( |
|
|
|
]λ , |
|
| |
|
λ 0 |
. |
|
, |
|
||||||||||||||
|
|
|
|
, µ( |
|
, … , µ( |
|
|
|
|
· λ |
p |
|
|
||||||||||||||||
Используя введенные |
|
обозначения, получим |
|
|||||||||||||||||||||||||||
|
|
|
( |
|
( |
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|||||||||||
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
||||
|
|
|
p |
|
∑Y |
λ |
|
µ |
∑Y λ p . |
(2.26) |
||||||||||||||||||||
шется в виде |
|
|
|
λ |
|
0 при |
|
f – |
, то выражение (2.26) запи- |
|||||||||||||||||||||
Если принять, что |
|
|
|
|
|
∑ |
|
|
λ |
|
|
|
|
|
||||||||||||||||
Кроме того, |
p |
|
A |
|
|
|
p |
0. |
|
|||||||||||||||||||||
|
|
аналогичном (2.21): |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.27) |
так как |
|
|
|
при |
∑ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
||||||
|
|
|
|
|
|
|
,λа |
|
|
|
|
0, |
|
|
|
|||||||||||||||
|
|
|
справедливо соотношение |
0 |
|
|
||||||||||||||||||||||||
0 |
|
|
– |
|
|
|
|
|
|
|
|
|
|
f – λ |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.28) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
при |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Таким образом, если ввести целевую функцию, аналогичную |
||||||||||||||||||||||||||||||
функции Лагранжа, то можно записать |
|
|
|
, |
|
|||||||||||||||||||||||||
|
|
|
|
ž |
|
|
|
|
A λ |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и решение задачи (2.22) сводится к решению системы уравнений:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
pž |
|
|
|
0, |
||
p A λ p |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, |
|
|
|||
λ |
λ 0, |
1, . |
||||
При решении данной системы может случиться так, что в случае |
λ 0, 1,
произвольных функций в задаче (2.22) не будет существовать таких
, для которых были бы справедливы полученные
уравнения (2.27) и (2.28). Поэтому на функции необходимо наложить определенные ограничения, которые называют условиями регулярности ограничений.
Требования к условиям регулярности ограничений сформулиро- |
|||||||
производные на |
|
|
, 1, |
|
|
|
|
ваны в теореме Куна-Такера. |
|
k |
|
|
|||
Пусть функции |
|
69 |
|
||||
|
|
имеют |
непрерывные частные |
||||
|
открытом множестве |
|
, содержащем точку . |
Если является решением задачи (2.22), где , 1, удов-
летворяют условию регулярности в виде линейной независимости |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
λ |
|
, λ |
, … , λ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
векторов-градиентов |
|
|
|
|
|
|
|
|
|
, то существуют такие неотрицатель- |
||||||||||||||||||||||||||||||||||||||||||||
ные множители |
Лагранжа |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0, |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
9 λ |
|
0& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
9 λ |
|
|
& |
|
|
|
|
|
|
|
|
|
|
λ |
|
|
|
|
|
|
|
|
- 1, .. |
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
0, |
|
|
|
|
|
/ 0, |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Если определить функцию Лагранжа как |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
F , Λ! A λ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
p |
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F , Λ! 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
то теорему Куна-Такера можно записать в виде |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
(9 |
|
|
p F , Λ! |
0, |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
p |
C |
|
|
|
|
|
( |
|
|
|
|
|
|
|
|
|
|
|
|
0, |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
Λ |
|
|
F , Λ! λ |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
Доказательство. |
|
|
|
|
|
|
|
|
|
λ |
0, |
|
|
1, . |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
ности точки |
|
: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A ŸT |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Разложим целевую функцию |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
в ряд Тейлора в окрест- |
|||||||||||||||||||||||||||||||||||||
|
Пусть |
|
|
– |
|
A |
|
ŸT |
|
|
|
|
A Ÿp |
|
|
T A Ÿ |
|
. |
|
|
|
|
|
|||||||||||||||||||||||||||||||
0 при – |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
что |
||||||||||||||
|
|
I |
|
|
множество |
активных |
|
ограничений, |
|
учитывая, |
|
|||||||||||||||||||||||||||||||||||||||||||
|
A ŸT |
|
|
|
|
|
A Ÿp |
|
|
T A |
|
|
Ÿ |
|
|
|
Ÿp |
|
T A |
|
Ÿ |
|
. |
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
, получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
T ? 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
¡p |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
Нетрудно видеть, что система неравенств |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.29) |
|||
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
для не- |
||||||
несовместна, так как в |
|
противном случае при малом |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
p |
|
|
T |
0 |
|
|
, |
|
|
|
|
|
|
|
|
Ÿ G 0 |
|
|
|
|
|||||||||||||||||||||||||||||
которого |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A ŸT ? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
получили бы |
|
|
|
A ŸT 0, |
|
|
|
|
|
|
|
–, |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
что противоречит |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
70 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
предположению об оптимальности точки |
|
|
|