Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 3,1]
~опоnоrйЧЕсRиЕ
СВОЙСТВА
151
3.
Напомним,
что
множество
Z
>=
Ет
называется
(см.
[50] ):
дугообразно
связным,
если
любые
две
его
точки
мож
но
соединить
дугой
*),
целиком
лежащей
в
Zj
стягuваемым
в
себе,
если
суще<;твует
точка
z*
Е
Zи
непрерывное
отображение
h:
Z
Х
[О,
1]
-+- Z
такие,
что
h(z,
О)
=
Z,
h(z,
1)
=
z*
для
любого
z
Е
Z.
Если
ltIНожество
стягиваемо
В
себе,
то
оно
является
дугообразно
связным.
Рассмотрим
свойства
непустого
множества
р(у),
предполагая,
что
У
замкнуто
и
ВЫПУRЛО.
ПОСRОЛЬRУ
всег
да
Р(У)
=
р(у.)
(лемма
2.2.1),
а
при
сделанных
пред
положениях
У.
заМRНУТО
(следствие
4),
то
далее
в
тео
ремах
9-11,
принадлежащих
Б.
Пелегу
[207],
будем
считать,
что
У
=
У
*.
Т
е
о
р
е
м
а
9.
Множество
р(
У)
стягuваемо
в
себе.
Д
о
R
а
з
а
т
е
л
ь
с
т в
О.
ПОСRОЛЬКУ
Р(
У)
=1=
{О,
то
в
силу
теоррмы
7
существует
вектор
!А
Е
М
И
число
а
такие,
что
для
всех
у
Е
У
выполняется
неравенство
(4).
Пусть
w =
min
!Ai.
Введем
на
Ет
beRTOP-фУНКЦИЮ
iEM
•
т
1
~
,
F
(у)
=
у
+
-w
[а
-
<f!,
У»)
~
е{,;
i=l
где
е!
-
i-й
орт
(е1
=
11
ej
=
О
при
j
=F
i).
Эта
функция
непрерывна
по
у.
Для
у
Е
У
определим
множество
R(y)
=
{:
Е
Ylz 6
у}.
Для
кsащого
j
Е
М
И
всякого
z
Е
R(y)
справедливы
не
равенства
F
j
(у)
~
Yj
+ +
[~f!iZj
- i
~tiYi]
>
1=1
i=l
БZj+(~
-1)(Zj-Yj)+'
~
~f!i(Zi-Уi»Zj.
i+j
Таким
образом,
beRTOP-фУНIЩИЯ
F
обладает
тем
свой-
СТВОМ,
что
F(y)
~:
для любого
Z
Е
ЯСу).
(15)
------
*)
Дугой
вазывается
rомеоморфиый
образ
ОТРСЗRа
[О,
1].
152
СТРУКТУРА
МНОЖЕСТВА
ЭФФЕКТИВНЫХ
РЕШЕНИй
[ГЛ,
3
Определим
фУПIщию
r:
У
-+
Р(
У)
из
условии
11
r
(у)
- F
(у)
11
=
min
11
z - F
(у)
11.
'ЕЩу)
в
силу
справедливости
(4)
множество
R(y)
-
выпуклый
компакт.
Функция
Ilz
-
Р(у
)11
строго
выпукла
по
z,
и
по
этому
достигает
на
R(y)
минимума
в
единственноii
точке
r(
у).
Кроме
того,
г(у)
Е
Р(
У)
(см.
пример
2.1.4).
Поэто-
му
функция
r
определена
корректно.
'
Ранее
было
принято
У
=
У
*.
Поэтому
в
У
существу
ют
точки
а,
Ь
такие,
что
Ь
>
а.
Определим
на
Р(
У)
Х
х
[О,
1]
вектор-функцию:
h(p,
t)
=
r«1-
пр
+ ta).
Очевидно,
что
h(p,
О)
=
р,
h(p,
1) =
r(a)
Е
Р(
У)
дЛЯ
лю
бого
РЕ
Р(У).
Остается
показать
непрерывность
функции
h.
Пусть
t =
Нт
t/t,
р
=
lim
р\
где
р,
р\, р2,
...
-
точки
из
Р(У),
а
t,
t\, t
2
,
•••
-
числа
из
[О,
1].
Если
t =
О,
то
Нт
[(1-
t
ll
)
pll
+
tha]
=
р"
11
...
""
а
благодаря
тому,
что
r(y)
Е
R(y),
h(p\
t/t)
6
(1-
t
k
)
pk
+ tka. (16)
Последовательность
{h(p\
t
k
)}
ограничена,
и
поэтому
в
силу
(16)
и
рЕР(У)
имеем
limh(plll
t
h
)
=
р.
lI~oo
Если
t >
О,
то
'у
=
(1
-
t)
Р
+ tb >
(1-
t)
Р
+ ta =
=
Нт[(1-
tk)pk
+ tka] =
у.
(17)
k ...
oo
Покажем,
что
beRTOP-фУНКЦИЯ
r
непрерывна
в
ТОЧRе
у
=
==
(1-
t)p
+
ta.
Для
этого
предположим,
напроТllВ,
что
у
=
lim
у\
Нт
r
(у")
= z
=1=
r
(у).
(18)
k ...
oo
11->00
Тогда
IIr(y)
- F(y)1i <
IIz
- F(y)I!.
(
19)
Существует
последовательность
{z/'},
Zk
Е
R(yk),
k =
==
1,
2,
...
такая,
что
lim
Zll = r
(у)'
11
....
00
(20)
§ 3.1]
ТОПОЛОГИЧЕСКИЕ
СВОйСТВА
153
Действительно,
пусть
z(-r)
=
т'{
+
(1-
тИу)
>
у,
't
Е
(О,
1),
где
"(
-
вектор
из
(17).
Найдется
натуральное
число
k(T)
такое,
что
Z(T)ER(yk)
для
любого
k;?:k(T).
Но
Нт
Z
(т)
= r
(у).
Поэтому
найдутся
такие
точки
Zk
Е
R(y-),
ЧТО
имеет
ме
сто
(20).
И3
(18) - (20)
следует
существование
таного
номера
k,
что
Ilzk
- F(yk)II <
IIr(y1<)
- F(y-)II.
Но
это
противоречит
определению
вектор-функции
r.
Итак,
r
непрерывна
в
точне
(1-
t)p
+ ta.
Непрерыв
ность
h
в
(р,
t)
следует
из
непрерывности
r
в
(1-
t)p
+
+
ta
.•
е
л
е
Д
с
т
в
и
е
6.
Множество
р(у)
дугообразно
связно.
е
л
е
Д
с
т
в
и
е
7.
Если
р(
у)
=F
)25,
то
S(
у)
дугообразно
связно.
Д
о
н
а
з
а
т
е
л
ь
с т в
о.
Возынем
произвольные
ТОЧЮI
у\
у2
Е
S(
У).
Множество
р(
у)
дугообразно
связно,
по
этому
точки
r(yt),
r(y2),
где
r -
функция,
введенная
при
доказательстве
теоремы
9,
можно
соединить
дугой
L
s;
s;
р(у).
Отрезок
L\,
соединяющпй
точни
у!
И
r(yl),
вхо
дит
в
S(Y).
Аналогичным
свойством
обладает
отреЗ0Н
L
z
,
соединяющий
у2
и
r(y
2
).
Таким
образом,
дуга
L
,
U L U L
z
лежит
в
S(
у)
и
соединяет
у\
и
у2.
•
Множество
Z
s;
Ет
называется
ретра,;,то,м
множества
vV
s;
Е'n,
Z
s;;;
W,
если
найдется
непрерывное
отображение
Ф
: W
-+
Z,
называемое
ретранцпей,
такое,
ЧТО
'IjJ(Z) = Z
для
любого
Z
Е
Z [50].
Те
о
р
е
м
а
10.
Если
множество
р(у)
за.~шнуто,
то
оно
является
ретра,;,том
JМtoжества
У.
Д
о
к
а
3
а
т е
л
ь
с т
в
о.
ОпредеЛIlМ расстояние
меilЩУ
у
Е
У
и
р(
у)
по
формуле
d
(У!
Р
(У))
= inf
Ily
-
zll.
ZEP(Y)
.
Введем
на
У
функцию
t(
) =
а(у,
Р(У»
у
1
+d(y,
Р(У»·
(21)
Очевидно,
О
~
t(y)
<
1,
и
эта
фушщия
непрерывна
по
!/.
Кроме
того,
у
Е
Р(
у)
тогда
1I
только
тогда,
когда
Ну)
=
О.
154
СТРУНТУРА
МНОЖЕСТВА
ЭФФЕКТИВНЫХ
РЕШЕНИЙ
[ГЛ.
Э
Используя
обозначения
из
доказательства
предыду
щей
теоремы,
определим
на
У
функцию
'Ф(У)
=
г«(1-
t(y»y
+
t(y)a).
Для
нее
'Ф(у)еР(У)
прп
уе
у
и
ф(у)=у
при
уеР(У).
Аналогпчно
ТОМУ,
кю,
было
сделано
в
доказательстве
тео
ремы
9,
используя
непрерывность
НУ),
можно
установить
непрерывность
'Ф.
Таким
образом,
'Ф
-
ретракция
У
на
Р(У)
.•
Те
о
р
е
м
а
11.
Если
.множество
Р(У)
-
комnакт,
то
оно
является
peTpaKTO~'
некоторого
компактного
выnу,.
лого
nоf)~tн,ожества
У.
Д
о
1\
а
з
а
т е
л
ь
с
т
в
о.
Выберем
точку
а
е
Ет,
для
ко
ТОРОЙ
существует
точка
У
е
Р(У)
такая,
что
у>
а.
Пусть
У
I
= conv
{Р(У),
а}.
Очевидно,
У
1
-
ВЫПУI\ЛЫЙ
компакт
и
P(Y
1
)
=р(у).
Пусть
q
Е
Еm
удовлетворяет
неравеНС1ВУ
q
~
у
для
всех у
е
Y
1
•
На
У
1
определим
фУНКЦIIЮ
r
l
:
rl(y)
е
Н
1
(у)
=
{z
е
Y1lz
~
у}
пз
условия
IIr~(y)
-
qll
=
min
Ilz
-
qll·
ZER
1
(y)
Ироме
того,
пусть
t(y)
-
функция
(21).
Функция
'Ф(У)
=
г
1
«1-
t(y»y
+
t(y)a)
представляет
собой
ретрющию
множества
У
1
на
РО1
.•
При
помощи
леммы
1
теоремы
9-11
можно
распро
странить
на
случай
BOГlIYTЫX
многокритерпальных
задач.
Например,
лемма
1
и
TeOpel\1q
9
приводят
К
следующему
утверждению.
т
е
о
р
е
м
а
12.
Пусть
~tножество
Х
выпукло,
вептор
функция
f
вогн,ута
и
непрерывна
на
He~t,
~tножество
У
замкнуто
и
р(у)
-1=
$О.
Тогда
множество
Р(У)
стягивае~tО
в
себе.
Из
этой
теоремы,
в
частности,
СJrедует,
что
если
х
ВЫПУКЛЫЙ
Rомпакт,
а
f
вогнута
п
непрерывна
на
х,
то
множество
эффективных
оцеНОI\
Р(
У)
стягиваемо
в
себе.
В
этом
пупкте
разбираЛIIСЬ
свойства
множества
эф
фентивных
точек.
Искшочение
составляет
следствие
7,
11
котором
даны
достаТQtIПые
условия
дугообразной
CB~3-
§
3.2]
условия
СУЩЕСТВОВАНИЯ
ЭФФЕНТИВНЫХ
РЕШЕНИй
155
НОСТИ
множества
S(Y).
Более
подробно
с
тополоrnчеС1\И~
ми
свойствами
множества
слабо
эффективных
точе1\
MO"'~
по
озпаRОМIIТЬСЯ,
обратившись
1\
статье
В.
В.
Морозо
ва
[59].
§
3.2.
У
словив
существования
эффективных
решений
ЛеГ1\О
попять,
что
еслн
существует
(в
том
или
IIНО~1
смысле)
эффеRтивное
решение,
то
существует
(в
том
же
смысле)
эффеRтивлая
оценка.
И
наоборот,
из
существо
вания
эффективной
оцешш
всегда
следует
существование
эффентивного
решепия.
Аналогично,
множество
эффеI{
тивпых
решений
внешне
устойчиво
(см.
§
1.4,)
тогда
и
толыю
тогда,
когда
внешне
устойчивым
является
мно
жество
эффективных
оцеНОR.
Поэтому
при
изучеНПIl
B()~
просов
существования
пет
надобности
пршщиппально
различать
результаты,
относящиеся
к
оцеШ\аМ,
и
резуль
таты,
относящпеся
к
решениям.
1.
Общие
условия
существования
эффентивных
точек
содержатся
в
следующем
утверждении.
т
е
о
р
е
м
а
1
*).
Пусть
У
"1=
0.
Достаточным
условuе.1rt
существованuя
эффектuвных
точе,.
и
внеШllей
устойчи
вости
М1tожества Р(
У)
является
KOJ.tnaY>THOCTb
J.t1ижества
R(y)
= {z
Е
Ylz
б;
у}
для
любого
у
Е
У.
Если,
KpOJ.te
того,
У
выпукло
и
вамкнуто,
то
укаЗа/тое
условие
является
необходUJ.tЫJ.t
условиеJ}f,
существованuя.
Напомним,
что
из
внеШНeI'i
устойчивости
множества
Р(
У)
следует
внешняя
устойчивость
множества
S(
У)
(теорема
1.4.1).
Д
о
1\
а
з
а т е
л
ь с
т
В
о.
Д
о
с т
а т о
ч
н
о
с
т
Ь.
Возьмсм
произвольпую
точну
у*
Е
У
и
вентор
!L
Е
М.
Через
уО
обозначим
ТОЧIСУ
мансимума
линейной
фУН1\ЦИИ
(~t,
у)
на
множестве
R(y*)
(вследствие
номпантности
R(y*)
та
кая
точна
найдется).
В
силу
теоремы
2.1.8
точна
уО
эф
фективпа
(в
этом
таЮI\е
легко
убеДИТI,СЯ,
предположив
противное).
А
та!\
I,aI,
yOeR(y*},
то
уО:?::у*,
т.
е.
МНО
жестt!O
Р(
У)
внешпе
устойчиво.
II
е
о
б
х
о
д
и
м
о
с
т
Ь.
Пусть
уО
Е
Р(
У).
ПреДПОЛОiIШМ
напротив,
что
для
HeI\OToporO
у*
Е
У
множество
R(y*)
не
.)
Эта
и
следующая
теорема
являются
частными
случаями
теорем,
доказанных
Р.
Хартли
[168,
169].
156
Сl'РУНТУРА
МНОШЕСТВА
ЭФФЕНТИВНЫХ
РJ::ШЕНИй
[ГЛ.
3
является
l{омпактом.
ПосколЫ\у
У
заМI{НУТО,
то
R(y*)
ДОJШШО
быть
псограниченным.
Отсюда
следует,
что
бо·
лее
ШIlрокое
множество
Н*
=
У
* n
(у*
+
E~)
таюне
не·
ограничено.
Множество
R*
выпукло
н,
в
силу
следствия
1.4,
замкнуто.
Его
пеограПИ'1еНlIOСТЬ
влечеr
существова·
нне
рецессивного
направления
(направления
удаления
8
бесконечность),
т.
е.
найдется
ненулевой
вектор
z
Е
Е2-.
ТaIiОЙ,
что у
+
лz
Е
У
*
для
всех
у
Е
У
*
и л
6;
о
(c~f.
§ 3
в
[931).
При
у
=
уО
И
л>
О
отсюда
следует,
что
yU
Ф
р
(У
*).
НО
это
противоречит
начальному
условию
уО
Е
Р(
У),
так
как
согласно
лемме
2.2.1
р
(У
*) =
р
(У)
.•
У
слов не
существования
эффективных
точе«
в
этоii
теореме не
является
достаточпым
для
существования
соб·
ственно
эффеюивных
точек.
Пример
1
..
Пусть
m=2,
Y=(YEE
2
IY2=e-
V1
j.
Здесь
R(y)
=
{у}
-
l{омпактное
мiюшество
для
любого
у
Е
У.
Тем
пе
менее
собственно
эффективных
ТОЧeI\
по
существует.
I\pOMe
того,
прпмер
множества
У,
изображенпого
па
рис.
4,
показывает,
что
при
:щмкнутом
и
эффектпвно
вы·
пуклом
У
из
Р(
У)
=1=
0
не
обязательно
следует
компаю·
.
пость
R(y)
для
I\аЖДОГО
у
Е
У.
Таким
образом,
требование
выпуклости
У
в
теореме
1
нельзя
заМСНIIТЬ
на
требова·
lIие
эффективной
выllюIости
•.
Условие
замкнутости
множества
R(y)
прп
каЖДО:ll
у
Е
У
проверять
довольпо
трудно.
Если
же
в
условиях
теоремы
1
дополнительно
потребовать
заМlШУТОСТЬ
У,
то
можно
получить
болсе
простые
условия
существованшт.
Т
е
о
р
е
м
а
2.
Пусть
,м1l0жество
У
llenycTO
и
за.икnуто.
ДостаТОЧ1-lы.tt
условие.м
существоваnuя
всех
видов
эффек·
тuвnых
точек
и
вnеШllей
устойчивости
Jltltожества
Р(
У)
является
существование
вектора
J.t
Е
М
и
числа
ct
тапllХ,
что
справедливо
llepaeellCTBO
(1.4).
Если
к
ТОJl/У
же
У
выпукло,
то
указаnnое
условие
является
llеобходиJlIЫ,м
д.lЯ
существоваll11Я
эффективТ-tЫХ
точек.
Д
о
к
а
з
а т
е
л
ь с т в
о.
Д
о
с т
а
т о
ч
н
о
с
т
ь.
Возьмем
произвольную
точr,у
у
Е
У.
Нетрудно
убедиться
в
том,
что
замкнутость
У
и
выполнение
перавенства
(1.4)
для
J.t
>
О(т)
влечет
компактность
множества
R(y),
определен·
ного
в
теореме
1.
Согласно
этоii
теореме
множество
Р(
У)
непусто
и
внешне
устойчиво.
В
силу
следствия
1.3
II3
§ 3.2]
УСЛОВИЯ
СУЩЕСТВОВАНИЯ
ЭФФЕRТИвных
РЕШЕНИЙ
157
Р(
У)
=F
f2J
следует
С(
У)
=F
f2J,
поэтому
все
виды
эффе.ктив.
lIЫХ
ТОЧeI,
существуют.
Н
е
о б
х
о
д
11
М
О
С
Т
ь.
В
предположениях
теоремы
име·
ет
место
прапое
из
В!,JlIOЧОШIЙ
(.1.7)
(теорема
1.7).
Сле·
довательно,
если Р(
У)
=F
f2J,
то
найдутся
ве.ктор
Il
Е
1\1
и
то'ша
уО
Е
У
тан:пе,
что
<Il,
у)::::;;
<Il,
уО)
=
а
для
всех
уЕУ
.•
Пример
множества
У
=
{у
Е
EZI
У2
~
О}
показывает,
что
n
теореме
2
условие
существования
соответствующих
Il
и
а
не
будет
необходимьш
условием
существования
сла·
бо
эффективных
точе1\.
Вопрос
существования
слабо
эффеl'ТИВНЫХ
точе1\
ока·
зывается
тесно
связанным
с
наличием
граничных
точек
множества
У
*.
Т
е о
р
е
м
а
3.
Н
еравенство
S(
У)
=F
f2J
U.~teeT
:место
тог·
да и
толь~о
тогда,
nогда
Joщожество
У
*
UЛlеет
хотя
бы
одщj
граНUЧllУЮ
точr.у,
т. е.
Fr
(У
*)
=1=)2).
д
о
к
а
з
а
т
е
л
ь
с т
в
о.
Необходимость
сразу
следует
n
силу
равенства
из
леммы
2.2.1.
Для
ДОI\азательства
достаточности
13031>·
мем
уО
Е
F r
(У
*).
по
определению
мноа,ества
У
*
для
llекоторого
у
Е
У
справеДЛИI30
у
~
уО.
Если
допустить,
что
YnFI'(Y*)=)2),
то
(тю,кю{
УЕУ*)
YEilltY*.
Отсюда
следует
неравенство
у'
>
у
прп
некотороы
у'
Е
У
*.
В
итоге
получаем
у'
>
уО,
а
это
противоречит
ВI\Лючению
уО
Е
Fr
(У
*).
•.
Следует
отметить,'
что
в
условиях
теоремы
3
множе·
СТВО
S(
У)
не
обязательно
внешне
устойчиво.
Пример
2.
Для
множества
Y=0(2)U{YEE
2
Iyz<0}
множество
S(Y)
непусто
(0(2)
Е
S(Y»,
но
пе
является
внешне
устойчивым.
2.
В
теоремах
1-3
были
сформулированы
условия
существования
в
теРМIшах
множества
оценок
У.
Неред·
ко
при
исследовании
многокритериальных
задач
более
удобными
ОI<азываются
условия,
выраженные
втерми·
нах
множества
решений
Х
и
ве.кторноЙ
функции
j.
Одним
из
наиболее
общих
подобного
рода
достаточ·
ных
условий
существования
псех
видов
эффективных
точек
является
услопие
компа.ктности
Х
1I
иолунепрерыв
ности
сверху
компонент
вектор-фующпи
j.
158
СТРУ:!ПV1'А
МНОЖЕСТВА
ЭФФЕ!\ТИВНЪrХ
РЕШЕНИЙ
[ГЛ.
3
Т
е
о
р
е
м
а
4
(ПОДIIНОВСКИй)
*).
Если
Х
-
nеnустой
KOJtnanT,
а
t -
nОЛУllеnрерывnая
сверху
(no1>OJtnOlleltTUO)
lla
Х
веnТОР-фУ1l1щия,
ТО
все
виды
эффеnтивllЫХ
точеn
существуют,
причем
М1l0жество
Р,(Х)
вnеШllе
устойчиво.
Д
о
к
а
в
а т
е
л
ь
с
'r
в
о.
Возьмем
произвольпую
точку
а-*
Е
Х,
зафиксируем
некоторый
вектор
~
Е
М
И
рассмот
рим
полунепрерывную
сверху
скалярную
фуНIЩИЮ
< Il,
t(x».
Она
достигает
(см.
[42])
своего
наибольшего
значения
на
IЮМПaI\те
{х
Е
Xlj(x)
~
f(x*)}.
Точка
макси
мума
хО,
как
легко
убедиться,
рассуждая
«от
протпвно~
го»,
принадлежит
множеству
Р,(Х).
I\роме
того,
j(xO)::::
~
j(X*),
т. е.
Р,(Х)
-
внешне
устойчивое множество.
Мансимизируя
указанную
функцию
<~L,
j(x»
на
KOM~
паI\те
Х,
получим
точку
Х,
ноторая
согласно
следствию
2.1.5
собственно
эффективна.
11
Теорема
4
представляет
собой
многокритерпальный
аналог
известной
из
анализа
теоремы
Вейерштрасса.
Обобщение
теоремы
4
можно
получить
при
помощи
по~
пятия
Ет;.
~полунепрерывной
фушщпи
['136].
П
р
П~l
е
'1
а
п и
е.
Утверждения
о
внешней
устойчиво
сти из
теорем
1,
2
и
4
являются
по-существу
следствия
ми
одного
из
фундаментальных
положений
теории
мно
теств,
называемого
леммой
Цорна,
а
также
теоремой
I\уратовсного
-
Цорна
(см.
[42, 50]):
еслп ВСЯIШЯ
цепь
частично
упорядоченного
множества
обладает
верхней
гранью,
.
то
каждый
не
максимальный
элемент
этого
мно
жества
подчинен
некоторому
мансималыIOМУ
элементу.
Действительно,
допустим,
например,
что
выполнены
достаточные
условия
пз
теоремы
1:
У
=/=
eJ
и
при
любом
У
Е
У
мпожество
R(y)
=
{z
Е
Ylz
~
у}
компактно.
Пусть
Q -
произвольная
цепь
из
У,
.Т.
е.
любые
две
ТОЧIШ
из
Q
сравнимы
по
~.
Проверим,
что
для
Q
существует
Bepx~
пяя
грань,
т.
е.
ТОЧl(а
уО
Е
У
такап,
что
уО
~ Z
для
вся
l\ОГО
Z
Е
Q.
Возьмем
произвольную
точку
ZO
Е
Q
и
рас
смотрим
совокупность
8°
множеств
R(z)
для
всех
z
Е
Q
таких,
что
z;;=::
ZO.
Поскольку
во
ВСЯI\ОМ
Rонечном
наборе
точек
{zt,
Z2,
•••
, Zn}
из
цепи
Q
имеется
наибольшая,
то
n
пере
сечение
n R
(Zl)
непусто,
тан
ЧТQ
система
множеств
i=l
.)
Существование
эффективных
решений
в
предположении,
что
Х
-
неп~'стой
Rомпакт
и
I
непрерывна,
дО!,азано
в
[121.
§ 3.2]
УСЛОВИЯ
СУЩЕСТВОВАНИЯ
ЭФФЕRТИВНЫХ
РЕШЕНИй
159
So
-
центрированная.
Следовательно,
в
силу
Rомпантно
стп
R(zO)
пересечение
всех
множеств
R(z)
из
SO
пепусто
([42J, § 2.6,
теорема
1).
Лешо
понять,
что
веяная
ТОЧI,а
па
этого
пересечепия
-
верхняя
грань
Q.
Следовательно,
согласпо
лемме
Цорна
Р(
У)
внешне
устойчиво.
ДЛЯ
вогнутых
многонритериальных
задач
с
неогранп
ченным
мпожеством
Х
представляет
интерес
следующпu
критерий
существования.
т
е
о
р
е
м
а
5.
Предnоложи.м,
что
;М/1,ожество
Х
/1,еnусто
и
вЫnУ1>ЛО,
ве~тор-фу/Uщия
1
вогнута
и
Jo//1,ожество
У
аа,и1'>/1,УТО.
Для
существования
эффе1'>тивnых
и
собствеЮ-lО
эффе1'>тив/1,ЫХ
ТОЧе1~
и
в/1,ешней
устойчивости
Joшожества
Pj(X)
nеобходи,:мо
и
достаточ/1,О,
чтобы
н.ашлись
ве1'>ТОР
р
Е
М
и число
а,
для
1'>оторых
верн.о
нераве/1,ство
(1.4),
<:Ое
у
=
I(x).
Д
о
н
а
3
а
т
е
л
ь
с
т
в
о.
Достаточность
обеспечивается
теоремой
2.
Если
же
Р
,(Х)
=1=
!21,
то
согласно
лемме
1.1
ВЬШУIшое
множество
У.
замннуто;
В
этом
случае
след
ствие
1.3
гарантирует
выполнение
перавенства
G
(У
*)
*
=i=0.HoG(Y.)=G(Y)
(см.
лемму
2.2.1>,
а
вначит
п
G j
(Х)
=I=!21.
Отсюда
в
силу
теоремы
2.2.4
вытенает
су
ществование
требуемых
р.
и
сх
.•
Из
этой
теоремы
очевидным
образом
вытенает
слепу
lOщее
обобщение
следствия
1.3
(с
условием
2»
[711:
в
предположешшх
теоремы
5
Pj(X)
=I=!21
тогда
и
только
тогда,
ногда
а,(Х)
=1=
!21.
Если
р.
Е
М,
ТО
пусть
М
о
=
{i
Е
MI!li >
О},
а
10
озна
чает
beI\TOP-фУШЩИЮ,
образованную
из
тех
Rомпонеuт
fi,
для
которых
i
Е
М
о
•
С
л
е
Д
с
т
в
и
е
1.
Пусть
вектор-фуmщия
1
вотута
на
lIеnустом
вЫnУ1'>ЛОJot
множестве
Х.
Н
еобходшtым
услови
еон
существования
слабо
эффе1'>тив/1,ЫХ
реше/1,ий
являетс.q,
вЫnОЛ/1,еnие
неравеnства
(1.4)
для
nеroоторого
!l
Е
М.
Ес
.ли,
roроме
того,
I~(X)
8aJot~nYTo,
то
yr.aaallHoe
условuе
:tвляется
достаТОЧ/-lЫ.ч.
Д
о
к
а
з
а
т е
л
ь
с
l'
В
о.
НеоБХОДIIМОСТЬ
следует
из
тео
ремы
2.2.2.
Донажем
достаточность.
Из
(1.4)
имеем
<!l0,
fo{х»
s
ct
для
всех
х
Е
Х,
где
!tY
=
!li
>
О
для
наждого
i
Е
М
о
•
Мuожестпо
fo{Х)
по
Условию
заМIШУТО.
Согласпо
теореме
5
эффентиnные
точ
Ю!
цо
beh1'OP-фУННЦИИ
t~
ОТlIосптель~о
Х
с~'ществуют.
160
CTPYRTYPA
МНОЖЕСТВА
ЭФФЕНТИВНblХ
РЕШЕНИЙ
[ГЛ.
3
Нетрудно
понять,
что
каждая
таиая точка
слабо
эффек
тивна
по
вентор-функции
f
.•
Нижеследующий
пример
показывает,
что
условие
замкнутости
мнощ:ества
fo(X)
в
следствии
1
существенно.
Пример
3.
Пусть
m=n=2,
Х={хЕЕ2Iх2~-1/хl,
х
!
>
О},
f(x)
= (x
j
,
х
2
).
Существует
ве!\тор
J.L
=
(О,
1),
для
которого
справедливо
неравенство
(1.4):
<J.L,
f(x»
=
Х2
~
-1/Х
1
<
О
для
всех
х
Е
Х.
Одна!\о
слабо
эффе!\тивных
точек
не
существует,
так
ка!\
множество
f2(X) =
{х
Е
Elx
<
О}
незаМIШУТО.
3.
Пусть
вентор-функция
f
линейна:
лх)
=
«с\
х),
<с\
х),
.•.
,
<с
т
,
х»,
(1)
где
с/:=/=
О(n),
i =
1,
2,
...
, m.
Через
Х"
обозначим
проеJЩIIЮ
ВЫПУI\ЛОГО
заМI\НУТОГО
множества
Х
на
аффинную
оболочку
*)
L
множества
{О(n),
с\
с
2
,
•••
,
с
1n
}.
Для
любого
х
Е
Х
имеет
место
пред
ставлеНие
х
=
х'
+
х",
где
х'
Е
Х
N
•
х"
Е
L.!..
(LJ.
-
орто
гональное
дополнение
Ы.
посI\олы\y
!(х")
=
О(т)
дЛЯ
ВСЯI\ОГО
х"
Е
L.!..,
то
j(x)
=
j(x').
Следовательно,
У
=
=
j(X)
= j(X,,).
ТОЧI\И
Z,
дЛЯ
ноторых
f(z)
=
О(m),
лежат
в
множестве
LJ..,
имеющем
с
L,
в
котором
находится
Х",
единственную
общую
точку
О(n).
В
ЭТИХ
условиях
тооре
ма
9.1
из
[93]
гарантирует
замкнутость
множества
j(X,,),
если
Х"
зам!\нуто.
Таким
образом,
когда
Х"
заМIШУТО,
то
заl\ШНУТЫМ
является
и
множество
У.
БЛЮ'одаря
этому
факту
из
теоремы
5
получаем
следующее
утвершденпе.
С
л
е
Д
с т
в
и
е
2.
Пусть
Х
-
nеnустое
выnуnлое
ааМ1>
nутое
множество,
веnтор-фунnция
j
лиnеunа
и
Nноже
ство
Х"
аа:Atю-tуто.
Собствеn1l0
аффективные
и
аффеnТllв
ные
ТОЧnll
существуют
в
1'0.%
и
тольnо
то.м
случае,
если
llаuдутся
веnтор
J.L
Е
М
и
число
а
Та1ще,
что
выполняет
ся
(1.4),
где у
=
j(x).
в
том
что
требование
замкнутости
Х"
в
следствии
2
является
существенным,
убеждает
следующий
При
м
е
р
4.
Множество
Х
с Е
З
представляет
собой
неограниченный
I\РУГОВОЙ
конус
с
вершиной
в
начале
координат,
!\асающийся
ПЛОСI\оСТИ
х2Охз
ПО
ОСИ
Охз
*)
Минимальное
аффинное
множество,
содержащее
данное
мно
жестно
Z s:;
Ет,
называется
аффинной
оБОЛОЧI{ОЙ
множества
Z
(см.
[93]).