ВУЗ:
Составители:
()
==−=
λ∂
∂
==
∂
∂
λ−
∂
∂
=
∂
∂
∑
=
.,1,0...,,,
;,1,0
21
1
mixxxgb
F
nj
x
g
x
f
x
F
nii
j
m
i
j
i
i
jj
(9)
с n + m неизвестными x
1
, x
2
, …, x
n
, λ
1
, λ
2
, …, λ
n
. Решив систему уравнений (9), получают все точки, в которых функция
может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безус-
ловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (9), как правило,
имеет несколько решений.
Выпуклое программирование. Функция f (x
1
, x
2
, …, x
n
), заданная на выпуклом множестве X, называется выпуклой,
если для любых двух точек
X
(1)
и X
(2)
из X и любого 0 ≤ λ ≤ 1 выполняется соотношение:
(
)
()
(
)
[
]
()
(
)
()
(
)
()
1212
11 XfXfXXf λ−+λ≤λ−+λ
. (10)
Функция f (x
1
, x
2
, …, x
n
), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X
(1)
и
X
(2)
из X и любого 0 ≤ λ ≤ 1 выполняется соотношение:
(
)
(
)
(
)
[
]
()
(
)
()
(
)
(
)
1212
11 XfXfXXf λ−+λ≥λ−+λ
. (11)
Если неравенства (10) и (11) считать строгими и они выполняются при 0 ≤ λ ≤ 1, то функция
f (x
1
, x
2
, …, x
n
) является
строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых
множеств.
Если
() ()
∑
=
=
k
j
j
xfxf
1
, где
()
xf
j
– выпуклые (вогнутые) функции на некотором выпуклом множестве X ⊂ E, то
функция
f(x) – также выпуклая (вогнутая) на X.
Рассмотрим задачу нелинейного программирования:
f (x
1
, x
2
, …, x
n
) → max (12)
при ограничениях
(
)
mibxxxg
inj
,1,...,,,
21
=
≤
, (13)
njx
j
,,0≥
. (14)
Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако
для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций
f(x) и g(x),
разработаны эффективные методы их решения.
Говорят, что множество допустимых решений задачи (12) – (14) удовлетворяет условию регулярности, или условию
Слейтера, если существует, по крайней мере, одна точка
X
(0)
, принадлежащая области допустимых решений такая, что
()
mibXg
ij
,1,
0
=<
. Задача (12) – (14) называется задачей выпуклого программирования, если функция f (x
1
, x
2
, …, x
n
)
является вогнутой (выпуклой), а функции
()
(
)
mixxxg
nj
,1...,,,
21
=
– выпуклыми. Функцией Лагранжа задачи выпук-
лого программирования (12) – (14) называется функция
(
)( )
()
[]
,...,,,
...,,,...,,,,...,,,
1
21
212121
∑
=
−+
+
=
m
i
nii
nmn
xxxgb
xxxfyyyxxxL
(15)
где y
1
, y
2
, …, y
m
– множители Лагранжа.
Точка
() ()
()( )
00
2
0
1
00
2
0
1
00
...,,,,...,,,,
mn
yyyxxxYX =
называется cедловой точкой функции Лагранжа, если
()
≤
00
2
0
121
...,,,,...,,,
mn
yyyxxxL
()
≤≤
00
2
0
1
00
2
0
1
...,,,,...,,,
mn
yyyxxxL
(
)
mn
yyyxxxL ...,,,,...,,,
21
00
2
0
1
для всех
() ()
mjynjx
jj
,10и,10 =≥=≥
.
Теорема Куна–Таккера. Для задачи выпуклого программирования (12) – (14) множество допустимых решений ко-
торой обладает свойством регулярности,
()
(
)
00
2
0
1
0
...,,,
n
xxxX =
является оптимальным решением тогда и только тогда,
когда существует такой вектор
()
(
)
miyyyyY
in
,1,0,...,,,
000
2
0
1
0
=≥=
, что
(
)
(
)
(
)
00
, YX
– седловая точка функции Ла-
гранжа.
Если предположить, что функции f и g непрерывно дифференцируемы, то теорема Куна–Таккера может быть допол-
нена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка
(
)
(
)
(
)
00
, YX
была седловой точкой функции Лагранжа, т.е. являлась решением задачи выпуклого программирования:
