Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
!I
4.2]
ОБЩАЯ
:tЮНСТРУI{ЦИЯ
ДВОйСТВЕННЫХ
ЗАДАЧ
201
Если
ввести
обозначение
Inf L
(Х"
л)
=
(inf
L
1
(Х
1
л),
... ,
inf
L
т
(X
t
л»~
" " "
то,
как
легко
заметнть,
множество
Q(x)
можно
предста-
вить
в
следующем
виде:
Q
(х)
=
{q
Е
Е
т
I q -< Inf L
(Х
1
л)}
•.
1eE
h
~
В
соответствии
с
этим
прю.IaЯ
задача
будет
заключаться
в
нахождении
множества
Мах
Inf L
(Х
1
л)
=
l\Iах
{z
Е
Ёт
I z = Inf L
(Х
1
л)
.
при
ХЕЮ
2..eE~
"EE~
...
со
нек?тором
х
Е
D!(
(12)
где
Ёт
=
Ё Х Ё
Х
..
.
ХЁ
и
Ё
-
расширенная
числовая
прямая,
полученная
И3
Е
добавлением
символов
-~
и
+~.
Эта
формулировка
прямой
задачи
эквивалентна
при
веденным
выше
(посколы\y
по
определению
максималь·
ных
э~ементов
они
обязаны
принадлежать
Ет).
Прямой
задаче
сопосташш
следующую
двойстnенную
задачу.
Д
в о
й
с
т в
е
н
н
а
я
з
а
Д
а ч
а.
Найти
множество
Min
Н.
Построенная конструкция
двойственных
много
крите
риальных
задач
была
предложена
в
работе
В.
Д.
Ногина
[67] ;
там
же
было
установлено
равенство
Мах
Q n
n
MinH=QnH.
В
скалярно?tl
случае
(т
=
1)
прямаJi(
задача
1
при
обретает
обычный
вид
(см.
(12»:
найти
шах
illf L
(х, л).
хею
,.
_Eh
,Е
>
...
А
таУ{
кан
при
этом
множество
Н(л)
представимо
в
виде
Н(л)={hЕЕlh>
sup
L(Х1Л)}t
,
хеЮ.
то
двойственную
задачу
можно
сформулировать
следую~
щим
образом:
найти
шiп
sup L
(Х
1
л).
2..EEh
ХЕЮ
>
...
При
изучении
двойственных
?tШОГОI\ритери:альных
за
дач
так
же,
как
и:
для
двой~твенных
сналярных
задач,
202
ДВойСтВЕННЫЕ
МНОГО1{РИТЕРИАльпЫЕ
ЗАДАЧИ
[rл.
,
принципиально
важным
является
случай;
когда
имеет
место
равенство
Мах
Q = Min
Н,
т.
е.
когда
каждое
реше
ние
прямой
задачи
является
решением
двойственной
за
дачи,
и
наоборот.
При
этом
согласно
(10)
и
(11)
каждое
из
множеств
Мах
Q,
Min
П,
Q n
н
и
L(W)
совпадает
со
множеством
эффект~вных
оценок
Р( У)
исходной
много
критериальной
задачи.
Формулированию
условий,
при
которых
указанное
равенство
выполняется,
и
посвящены
следующие
два параграфа.
§ 4.3.
Вогнутый
случай
Здесь
формулируются
условия,
при
ноторых
имеет
ме
сто
равенство
множеств
решений
прямой
и
двойственной
задач
в
предположении,
что
исходная
многокритериаль
ная
задача
-
вогнутая.
:Кроме
тото,
при
дополнительном
предположении
дифференцируемости
мансимизируемой
вентор-функции
и
вентор-фующии
ограничений
приво
дится
.
специальная
формулировка
двойственной
задачи.
Изложение
материала
основано
на
работе
В.
д.
Но
гина
С671.
1.
Будем
рассматривать
многокритериальную
задачу,
в
которой
множество
D s;;
En
выпукло,
а
вектор-фуннции
f
и
g
вогнуты
II
непрерывны
на·
D.
Тогда
множество
до
пустимых
решений
Х
вида
(2.1)
танже
выпукло
(иобя
зательно
замннуто,
если
замннуто
D).
Согласно
(2.7) Q =
=
у
*
и
в
силу
леммы
2.2.2
множество
Q
выпунло.
По
лемме
2.2.1
мнt>жество
собственно
эффективных
точек
множества
Q
совпадает
с
G(Y).
.
Л
е
м м
а
1.
Предnо'//'ожим,
что
выnо.//,нено
ус.//,овие
ре
гу.//,ярности
С.//,ейтера:
существует
та~ая
точ~а
х
е
D,
что
с(х)
>
0(11)'
Если
qO
-
со6ствеlt1tО
эффет;,тивная
точ~а,
то
qOeH.
Д
о
к
а
з
а
т
е
л
ь
с т
в
о.
Пусть
qO
= f(xO)
при
неко
тором
хО
е
G,(X).
Согласно
теореме
2.2.6
существует
такой
. k
вектор
/..0
Е
Е>,
что
пара
(х
О
,
')...0)
образует
седловую
точку
скалярной
фу~кции
.2'(f,t,
х,
л)
при
некотором
f,t
е
М,
т.
е
.
.2'(f,t,
х,
л
О
)
<:.2'
(f,t,
х
О
,
/..0)
:;!
.2'(f,t,
х
О
,
/..)
.
It.
для
всех
х
Е
D,
')...
Е
Е>.
Из
правого
неравенства
при
/..
=
-
О(А)
И
с(х
О
)
е:::;0(1I)
следУет
равенство
</..0,
с(хо»:о:
О.
§ 4.3]
ВОГНУ'l'Ый
СЛУЧАй
203
в
таком
случае
левое
неравенство
принимает
вид
(J.t,
/(хО»
::::,2'(J.t,
х,
1..0)
для
BcexxeD.
(1)
Согласно
представлению
(2.8)
имеем
/
(хО)
=
qO
е
н(,,})
s:
s:H..
.
Т
е
о
р
е
м
а
1.
Л
усть
выnолnе1tо
условие
регулярности
СлеЙтера.
ПредnоложUJrt,
что
справедливо
хотя
бы
одно
из
условий:
. 1)
~аждая
точ~а
qO
Е
Мах
Q
является
собственnо
sф
феnтив1tой
(т.
е.
выnолnяется
равеnство
Р(У)
=
G(Y»;
2)
фуn~ция
/
строго
вогnута;
з)
множества
D,
У
зажnnуты
и
Min Н
s;;;:
н.
Тогда
Мах
Q
s;;;:
Min
Н.
Д
о
к
а
з
а
т е
л
ь
с
т в
о.
Пусть
qO
е
Мах
Q.
Благодаря
(2.Н)
qO
=
/(хО)
при
некотором
хо
е
Р/(Х).
Поскольку,
/(хО)
Е
Q,
то
при
I(хО)
Е
Н,
согласно
теореме
2.2
элемент
/(хО)
будет
принадлежать
множеству
Min
н.
Поэтому
для
доказательства
теоремы
достаточно
установить
включе
ние
/(хО)
Е
Н.
1)
Если
f(xO)
Е
G(Y),
то
согласно
лемме
1
f(xO)
еН.
2)
Иэ
хо
Е
Р/
(Х)
по
теореме
2.2.6
следует
существо-
-
"-
вание
векторов
J.t
0
Е
М
И
1..0
Е
Е>
таЮIХ,
что
пара
(хО,лО)
является
седловой
ТОЧIЮЙ
скалярной
функции
,2'(J.t
0
,
х,
1..).
Поэтому
,2'(J.t
0
,
хО,
лО)
~
,2'(J.t
0
,
х,
лО)
для
всех
х
Е
D.
Следовательно,
функция
,2'(J.t
0
, "
лО)
достигает
максиму
ма
на
множестве
D
в
точке
хО.
А
так
как
эта'
фушщия
строго
.вогнута
(вследствие
строгой
вогнутости
Л,
тохО
единственная
точна
маНСИМУ}18.
Поэтому,
учитывая
ра
венство
(1..0,
с(хО»
=
О,
получаем
(J.t
0
,
/(хО»
>
<J.t
0
,
/(х»
+
(1..0,
с(х»
для
всех
xeD,
x-::/=хО.
Здесь
J.t
0
Е
М.
Но
для
каждого
х
е
D,
х
=#=
х
О
,
всегда
мож
но
подобрать
вектор
J.t
е
М
(который,
разумеется,
будет
зависеть
от
точки
х)
так,
чтобы
написанное
выше
стро
гое
неравевство
выполнялось
после
замены
J.t
0
на
J.t.
Та-
ким
образом,
для
наждого
х
е
D
(для
х
....
х
О
МQЖUО
ввять
любой
вектор
из
М,
так
нак
(1..0,
g(xO»
...
О)
существует
такой
J.t
Е
М,
что
оназывается
справедливым
неравенство
(1).
Поэтому
/(хО)
Е
н(л.
о
).
204
ДВОйСТВЕННЫЕ
МНОГОНРИТЕРИАЛЫIЫЕ
ЗАДАЧИ
[ГЛ.,
з)
Благодаря
теореме
3.1.8
оценна
/(хО)
является
пре
делом
последовательности
собственно
эффентивных
оце-
нон:
f
(х
О
)
=
Нт
f
(x
l
),
где
х'
Е
G/(Ю,
1 =
1,
2,
•••
в
п.
1)
1
....
00
дапного
доназательства
было
устаповлено, что
/(х
'
)
Е
Min
Il
для любого
[.
Используя
условие
Min
Н
s:
Н,
получаем
/(хО)
Е
Н
.•
Нан
ПOIшзывает
нижеследующий
пример,
нание-то
до·
полнительные
предположения
типа
условий
1)
-
3)
тео
ремы
1
вводить
необходимо.
При
м
е
р
1.
Рассмотрим
двухнритериальную
вогну
..
тую
задачу,
в
ноторой
n =
т
=
2,
k = 1, D =
Е2
И
/I(X)
= XI,
мх)
=
х:,
gt(x)
=
-(Хl)2
-
х
2
.
Выпунлое
множество
Х-составляют
ТОЧI{И
плосности
E
Z
,
расположенные
на
параболе
3:2 =
-(хl)\
и
точни,
лежа
щие
ниже
этой
параболы.
Точна
х
О
=
0(2)
эффентивна,
тю.
что
/(хО)
Е
Мах
Q.
Донажем,
что
/(хО)
ф
Н.
а)
Если
"л
=
О,
то
для
х
1
= (1,
1)
справедливо
L(x
l
,
О)
=
(1,
1)
>
(О,
о)
=
/(хО),
т. е.
/(хО)
ф
Н(О).
б)
ЕСJIИ
О
<
"л
<
1,
то
берем
х
2
=
(f
-
л,
1 -
л)
и
по
лучаеу
L(x
Z
,
л)
= «
1-1}),
(1-
л
З
»
>
(о,
О)
=
/(хО)
для
любого
л
Е
(0,1).
Следовательно,
/(хО)
ф
Н(л)
при
0<Л<1.
в)
Если л
~
1,
то
для
х
З
=
(О,
-1)
имеем
L(x
3
,
"Л)
=
(л,
л
-1)
:=::
(О,
О)
=
/(хО),
т.
е.
/(хО)
ф
Н(л)
для л
~
1
.•
В
этом
примере
ии
одно
из
условий
1)
- 3)
не
выпол
няется:
эффентивная
оценна
/(хО)
не
является
собствен
но
вффентивной;
фуннция
/
линейна,
а
значит,
не
яв
...
пяетея
строго
вогнутой.
Далее,
согласно
теореме
3.1.8
/
(х
О
)
=
Нт
/
(x
l
)
И
х
l
Е
G
J
(Х).
По
лемме
1
/(х')
Е
Q n
н,
1
....
00
а
8начит
/(х')
Е
Min
Н,
1 =
1,
2,...
Но,
нан
пона
зано
выше
/(хО)
ф
Н.
Следовательно,
условие
3)
теоре
мы
1
таиже
не
выполнено.
I 4.3]
ВОГНУТЫй
СЛУЧАй
205
2.
Для
дальнейшего
изучения
двойственности
понадо
бятся
дополпительные
понятия
и
факты
выпуклого
ана
лиза.
В
данном
пункте
?tfbl
приведем
эти
дополнительные
сведения,
опираясь
на
[93].
Пусть
Z s
Еn
-
непустое
выпуклое
множество.
Гово
рят,
что
Z
удаляется
в
бесконечность
по
направлению
t
или
что
t
есть
рецессивное
направление
дЛЯ
Z,
если
Z
содержит
все
лучи
с
направлением
t
(где
t *
О(n),
начи
нающиеся
в
любой
точке
из
Z.
Другими
словами,
Z
уда
ляется
в
беСIюнечность
по
направлению
t, t
*О(n),
если
z +
'Лt
Е
Z
для
любых
'А:2::
О,
z
Е
Z.
Множество
всех
векто
ров,
удовлетворяющих
последнему
соотношению,
с
при
соединенным
к
нему
началом
координат
называется
ре
цессивным
конусом
множества
Z
и
обозначается
O+(Z).
Множество
O+(Z)
является
выпуклым
конусом
и
совпа
дает
с
множеством
тех
векторов
t,
для
которых
выполня
ется
Z+
tsZ.
Если
Z
замкнуто,
то
его
рецессивный
конус
замкнут.
Известно,
что
непустое
выпуклое
заМIшутое
множество
ограничено
тогда
и
только
тогда,
когда
его
рецессивный
конус
совпадает
с
началом
координат.
Если
ZT,
"(
е
Г,-
произвольное
семейство
выпуклых
замкнутых
множеств,
пересечение
которых
непусто,
то
справедливо
равенство
0+ ( n Z.,) = n 0+
(Z.,)
.
.,ег
уеГ
Поляра
,выпуклого
Iюнуса
С
определяется
следую
щим
образом:
СО
=
{z
I
<z,
у>
<.::
О
для
всех
у
Е
С}.
Если
С
1
s
С
2
П
C
1
,
С
2
-
выпуклые
конусы,
то
C~
2С;.
Как
известно,
для
выпуклого
заМIШУТОГО
конуса
С
спра
ведливо
равенство
(СО)О
=
С.
л
е
м
1\1
а
2.
Пусть
Z -
Н(7nустое
выnуnлое
аамnнутое
Jltnожество.
Если
JA.
Е
ri (O+(Z))O,
то
.линеЙljая
ФУlmция
<JA.,
.)
достигает
Mancuмy.мa
на
множестве
Z.
Доказательств-о.
Из
УСЛОВИЯ
JA.Eri(O+(Z))O
со
rласно
следствию
11.6.2 [93],
вытекает
неравенство
(у,
JA.)
<
тах
<JA.,
z) =
О
(2)
:e(o+(z))O
для любого
у
такого,
что
линейная
фУНКЦИЯ
<у,
.)
не
206
ДВОйСТВЕННЫЕ
много1\ритЕриАльныE
ЗАДАЧИ
[ГЛ.,
является
тождественно
равной
постоянной
на
множестве
(O+(Z»o.
Обозначим
через
R
максимальное
подпространство,
содержащееся
в
конусе
O+(Z).
ДЛЯ
у
е!
O+(Z)\R
функция
(у,
.)
не
является
тожде
ственно
равной постоянной
на
(O+(Z»O
(8аметим,
что
бла
годаря
О(n)
Е
(O+(Z»O
этой
постоянной
может
быть
лишь
нуль).
В
самом
деле,
если
<у,
z)
....
О
для
всех
z
е
(O+(Z»O,
то
при
каждом
вещественном
а
также
<ау,
z)
=0.
Та
ким
образом,
вся
прямая,
проходящая
через
начало
коор
динат
и
точку
у,
принадлежит
множеству
«O+(Z»O)O
=r
"""
O+(Z),
т. е.
у
Е
R.
Но
это
противоречит
включению
у
е;
O+(Z)\R.
В
соответствии
с
этим
ио
(2)
следует
<у,
J.t)
<
О
для
всех
у
Е
O+(Z)\R, (3)
что
означает
строгое
убывание
линейной
функции
(J.t,.)
вдоль
любого
направления
из
O+(Z)\R.
Рассмотрим
множество
Z'
=- Z n
R.J..,
где
R.J..
-
ортого
нальное
дополнение
R.
Поскольну
для
любого
z е Z
спра
ведливо
R + z
~
Z,
то
Z'
n (R +
z)
=
{z'},
где
z'
-
некото
рая
точка
множества
Z'.
Далее,
очевидно,
что
у
==
z -
-
z'
e;~.
Таким
образом,
для
любого
z
е
Z
существует
такой
z
EiI!
Z',
что
z -=
z'
+
У,
У
Е
R.
Следовательно,
<J.t,
z)
=
(J.t,
z')
+
<J.t,
у).
Но
(J.t,
у)
=
О.
Действительно,
так
как
J.t
Е
(O+(Z»O
и
у
6!
O+(Z),
то
(J.t,
у):;;
О.
А
благодаря
тому,
что
-у
е;
Н,
имеет
место
неравенство
(J.t,
у)
~
О.
Таким
обраЗ0М,
верхняя
грань
линейной
функции
(J.t,
.)
на
множестве
Z
достигается
тогда
и
ТОЛЬ1\О
тогда,
когда
она
достигаеl'СЯ
1lа
Z'.
Рецессивный
конус
множества
Z'
есЧ>
O+(Z')-
-=
O+(Z)
n
R.J...
Далее,
[O+(Z)
n
RЧ\О(n)
g O+(Z)\R.
Поэто
му
из
(3)
следует,
что
линейная
функция
(J.t,
.)
вдоль
любого
направлеJDIЯ
И8
O+(Z')
строго
убывает.
В
соответ
ствии
с
теоремой
27.3
из
[93]
эта
функция
достигает
ма
коимума
на
множестве
Z',
а
значит
и
на
множестве
Z
.•
3.
Важное
свойство
прямого
и
двойственного
мно
жеств
устапавлйвает
следующал
§ 4
З)
ВОГНУТЫй
СЛУЧАй
201
т
е
о
р
е
м
а
2.
Предnо.//,ожим,
что
выnо.//,nеnо
ус.//,овие
регу'//'ярnостu
С.//,ейтера
и
мnожество
Q
вамnnуто.
Тогда
QUH=Em.
(4)
Д
о
R
а
а
а т
е
л
ь
с т
в
о.
Пусть
h
Ф
Q.
ДОRажем,
что
h
а
еЛ.
ТОЧRУ
h
можно
сильно
отделить
от
ВЫПУRЛОГО
aaMH~
нутого
множества
Q,
т.
е.
существует
таRОЙ
ненулевой
вентор
JA.
е
Ет, что
<JA.,
h) >
а.
ДЛЯ
иеRОТОРОГО
а.
Е
Е,
(5)
<JA.,
q)
<
а.
ДЛЯ
всех
q
Е
Q.
ПО
определению
множества
Q
иа
второго
иеравеиства
(5)
т
следует
JA.;;:::
О(т).
Очевидно,
можно
считать,
что
~
JA.i
=
11
i=l
т.
е.
JA.
Е
М.
Более
того,
JA.
Е
(O+(Q»O
n
м,
(6)
где
(O+(Q»O
-
поляра
рецессивного
ROHyca
множества
Q.
Действительnо,
если
J.t
Ф
(O+(Q»O,
т. е.
<JA.,
z)
>
О
для
ие
ROTOPOfO
z
Е
O+(Q),
то
согласно
определению
рецессивно
го
нонуса
для
q'
е
Q
ВRлючеиие
q'
+
лz
е
Q
справедливо
при
RажДОМ
л>
О.
Величину
<J.t,
q' +
лz)
аа
счет
выбора
л
можно
сделать
СRОЛЬ
угодно
большой,
а
это
иесовме
стимо
со
вторым
неравенством
(5).
Если
ri(O+(Q»O
=
{О,
то
O+(Q)
=
Ет,
а
аначит
Q =
Е"'.
Но,
в
соответствии
с
предположением,
h
Ei
Ет
и
h
~
Q.
Поэтому
пусть
J.t
0
Е
ri
(O+(Q»o.
ПОСRОЛЬRУ
-
E~
s;;;
0+
(Q)1
то
(-
E~)O
=
E~;2
(0+
(Q»O.
Следовательно,
JA.
0
Е
E~.
А
тан
нан
Er;.
и
ri
(0+
(Q»O
суть
нонусы,
ТО
можно
счи-
....
тать,
что
(7)
Рассмотрим
вентор
J.t'"
=
(OJA.
0
+
(1-
(O)JA.
при
(о
е
(0,1).
В
силу
(6),
(7)
и
теоремы
6.1
из
[93]
выполняется
JA.'"
Ei
208
ДВОйСТВЕННЫЕ
МНОГОRРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ
~
Е
ri
(O+(Q»O
n
М.
Далее,
очевидно,
что
<J.!"',
h>
=
ro<J.!°,
h>
+
(1-
ro)<J.!,
h>,
<J.!"',
q>
=
ro<J.!°,
q)
+
(1-
ro)(J.!,
q).
Благодаря
(7)
линейная
функция
<J.!O,.)
ограничена
свер
ху
на
множестве
Q
(см.
лемму
2).
А
в
силу
(5)
выпол
няется
<~t,
'~)
> sup <
J.!,q).
qEQ
Поэтому
положительное
ro
можно
выбрать
настолько
ма
лым,
чтобы имело
место
неравенство
<J.!"',
h>
> (/l"', q)
для
всех
q
Е
Q.
(8)
Согласно
лемме
2
фушщпя
<
/l"',
.)
достигает
своего
наибольшего
знач.ения
на
Q.
Пусть
q'"
-
точка
максиму
ма,
т. е.
<J.!"',
q"')::::
<J.!"',
q)
для
всех
q
Е
Q.
(9)
Так
I<aK
q'"
Е
Q,
то
q"'::::;;
j(XO)
при
некотором
хо
Е
Х,
И
по
этому
<J.!"',
q"'>::::;;
<J.!"',
j(XO».
Но
j(XO)
Е
Q,
а
значит
из
(9)
следует
<J.!",
q">::::
<J.!"',
j(XO».
Следовательно,
<J.!"',
qю)
=
=
(J.!"',
j(XO»
и
<J.!"',
j(xO»::::
</l"',
j(x»
для
всех
ХЕХ.
Таким
образом,
вогнутая
скалярная
функция
<J.!",
j(x»
достигает
максимума
на
множестве
Х
в
точке
хО.
Отсю
да
в
соответствии
с
теоремой
2.2.6
(при
т
= 1)
вытекает
существование
такого
вектора
л
Е
E~,
что
<J.!"',
f(xO»::::
<J.!"',
j(x» +
<Л,
с(х»
для
всех
х
Е
D.
Поэтому,
учитывая
неравенство
(8),
получаем
<J.!",
h>
> </l"',
f(x»
+
(Л,
с(х»
для
всех
х
Е
D.
Здесь
J.!
'"
Е
М.
Но
так
как
это
неравенство
строгое,
то
для
каждого
фИI<сированпого
х
Е
D
можно
подобрать
такой
вектор
J.!
Е
М
(зависящий
от
х),
что
</l,
h>
> ;t'(J.!,
х,
л).
Согласно
представлению
(2.8)
это
влечет
h
Е
нел,)
.•
Итак,
о
взаимном
расположении
прямого
и
двойствен
ного
множеств
можно
сказать
следующее:
они
заполняют
все
пространство
Ет
(теорема
2)
11
могут
иметь
общими
§ 4.3]
ВОГНУтЫй
СЛУЧАЙ
лишь
свои
граничные
элементы
(это
вытекает
из
теоре
мы
1.1>.
Т
е
о
р
е
м
а
3.
Пусть
выnо.лJlеnо
ус.ловuе
регу.лярnостu
С.леЙтера
u
мложество
Q
8aм,~nYTO.
Тогда
Min
Н
Е
Мах
Q.
Д
о
к
а
з
а т
е
л
ь
с
т в
о.
Пусть
hO
Е
Min
Н.
Поскольку
hO
-l\пшималъный.
элемент,
то
h°!jE
intH.
Torдa
благода
ря
равенству
(4)
и
замкнутости
Q
имеем
hO
Е
Q.
ТаI\ИМ
образом,
hO
е
Q n
н,
а
значит
в
силу
теоремы
2.2
hO
е
е
MaxQ
.•
4.
Дополнительно
предположив,
что
вектор-функцип
j, g
покомпонентно
дифференцируемы
на
D
Е
Еn,
введем
в
раССl\IOтрение
множество
H
1
= U U U
(hEEffll<~lh»Q'(~lX,
л)}t
'"
Х
j.I
где
объединение
берется
по всем
л
Е
E~, х
Е
D
и
f.t
е
е
М,
для
которых
выполняется
равенство
=
V".2'(J,t,
х,
л)
=
О(n).
(10)
Если
h
е
Н
1
то,
используя
характеристичеСlюе
свой
ство
вогнутой
и
дифференцируемой
функции
!l'(f.t",
л),
а
также
равенство
(10),
п\)лучим
<~t,
h)~
.2'(f.t,
х,
л)
е:
!l'(f.t,
х',
л)
+
,+
<V".2'(J,t,
х,
л),
х
-
х'>
~
!l'(J,t,
х',
л)
для
любого
х'
е
D, (11)
что
согласно
представлению
(2.8)
влечет
h
е
нсл.).
Сле
довательно,
всегда
справедливо
включение
Н
1
Е
Н.
(12)
Л
е
м
м
а
3.
Д.ля
.любых
q
е
Q u lt
е
1I
1
(h:
<J,t,
h>
~
~
P(J,t,
х,
л)
д.ля
ne~OTOpыx
~L
Е
М, х
Е
D,
л
Е
E~)
8Ы-
nо.лnяется
nеравеnство
<J,t,
q>
~
<J,t,
h>.
Доказательство.
Поскольку
qeQ,
то
q:5:
f(xO)
для
некоторого
хО
е
Х.
ДЛЯ
h
Е
H
1
,
используя
свойство
вогнутой
и
дифференцируемой
функции
!l'(J,t, "
л),
полу
Чаеl\1
(11),
откуда
при
х'
=
хО
Е
Х
следует
<J,t,
h>
~
.2'(J,t,
хО,
л)
~
<J,t,
f(xO»
е;:;
<J,t,
q)
.•
Следствие
1.
Ес.лu
qOeQnH
t
,
то
qO-собствеn
по
эффеnтuвnая
точ~а
Q u
qO
Е
Min
H
1
•
14
В.
в
ПОДИНОВСКИЙ,
В.
Д.
НОГИН
21()
ДВОйСТВЕННЫЕ
МНОГОRPИТЕРИАЛЪНЫЕ
ЗАДАЧИ
[ГЛ.
4
д
о
к
а
з
а
т е
п
ь
с
т
в
О.
Поскопьку
qO
е
Н"
ТО
дпя
не
которых
J.l.
0
е
М,
х
О
е
D
и
1..0
Е
E~
верно
<J.l.
0
,
qO)!ii:!E
(J.l.
0
,
х
О
,
лО),
Согпасно
пемме
3
<J.l.
0
,
q):i!
<J.l.
0
,
qO)
дпя
любого
q
е
Q.
Спедоват-епьно,
qO
-
сооотвенно эффеI\тивпая
точ-
ка
множества
Q.
.
Еспи
же
qO
~
Min
Н"
т.
е.
дпя
HeROToporo
h'e
Н
1
вер
но
h~qO,
то
<J.l.
0
,
h)'«J.l.°,
qO),
где
heH"qOeQ,
а
это
противоречит
утверждению
пеммы
3
.•
Т
е
о
р
е
м
а
4.
П
редnо.ложuм,
что
выnодnено
ус.ловuе
регу.лЯР1l0СТU
С.леЙтера,
мnожество
Q
ва.ю.nуrо
u
Н,
=1=
0.
Тогда
Q U
Н
1
=
Е"',
(1З)
д
о
к
а
з
а
тепь
ст
в
о.
Предположим,
что
h
~
Q
и
до
кажем
ВI\пючение
h
е
Н,.
Так
же,
RaK
и
в
ДОI,азатепьстве
теоремы
2,
ТОЧRУ
h
можно
сипьпо
отделить
от
множества
Q,
т. е.
найдется
вектор
J.I.
Е
М
таRОЙ,
что
выпопняется
(5)
и
(6).
Посiюль
RY
Н
1
=1=
0
(т.
е.
найдется
h'"
Е
lI
t
),
то
согласно
лемме
3
при
HeROTopOM
J.I.'"
Е
М
верно
<J.I."',
q):i!
<J.I."',
h"')
для
всех
q
е
Q.
ЛеГRО
понять,
что
J.I.'"
Е
(O+(Q»O n
М.
в
силу
Q
=1=
ЕМ
справедливо
неравепство
ri
(O+(Q»O
.:р
=1=
0,
поэтому
пусть
ji
е
ri
(O+(Q»O.
Апалогично
тому,
RaR
в
ДОRазательстве
теоремы
2
для
J.l.
0
было
установлено
ВRлючепие
(7),
в
данном
случае
можно
ДОI\азать,
что
;:t
Е
ri
(O+(Q»O n
М.
ДЛЯ
БеRтора
J.l.
0
=
лii
+ (1
....
Л)J.I.'"
при
фИI\сированном
л
Е
Е
(О,
1)
согласно
теореме
6.1
из
[93J,
верпо
J.l.
0
Е
ri
(O+(Q)}O
n
М.
Теперь
рассмотрим
вектор
.J.I."'
=
0>J.l.0
+
(1-
O»J.I.
при
о>
е
(О,
1),
для
ROTOPOfO
справедливо
J.I."'
е
ri
(O+(Q»O
n
М.
Аналогично
тому,
как
в
доказательстве
теоремы
2,
мож
по
показать,
что
выполнено
(8)
и
вогнутая
СI\алярная
функция
<J.I."',
/(х»
достигает
максимума
на
множестве
Х
в
точке
хО.
Если
х
-
точка,
для
RОТОРОЙ
вЫПОЛняется
условие
ре
гупярности
Спейтера,
то
для
каждого
i
е
J(XO)
в
силу
ВО-