Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 3.2]
УСЛОВIIЯ
СУЩЕСТВОВ.\ншr
ЭФФЕЮ'ПВНЫХ
РЕШЕНИЙ
161
(см.
рис.
5).
Для
линейной
вектор-функции
!(Х)
= (X
1
,
Х2)
лешо
убедиться
в
справедливости
равенств
у
=
Х"
=
0(21
u
{Х
е
Е
2
lx
l
<
О}.
Эффективными
здесь
являются
все
ТОЧI\И
вида
Х!
=
Х2
"""
=
О,
Х.
~
О.
Однако
не
существует
Jt
е
М
и
а,
для
ко
торых
выполняется
(1.4)
(заметим,
что
отсюда,
в част
ности,
следует
а,(Х)
=
0).
4.
Рассмотрим
линеiiную
задачу,
в
НОТОРОЙ
!
имеет
вид
(1)
II
Х
=
{Х
е
Еnl
(a
J
,
х>
:::;;
b
j
,
j =
1,
2,
...
,
k},
где
а
'
е
Еn,
Ь;
Е
Е,
j =
1,
2,
...
,
k.
В
линейной
задаче,
нан
указывает
следствие
2.2.3,
Pt(X)
=
а/(Х).
Поэтому
условия
существования
соб
ственио
эффективных
точек
будут
иметь
таIЮЙ
же
вид,
нан
и
условия
существова
ния
эффективных
точен.
Рис.
5.
о
В
нижеследующем
у
'г-
.
першдении
формулируется
простой
нритерий
существо
вания
эффентивных
(а,
зна
чит,
И
собственно
эффентив
ных)
и
слабо
эффентивных
точен.
Этот
J<,ритерий
для
эф
фентивных
точеI{
впервые
был
получен
Д.
Геiiлом,
Х.
l\уном
и
А.
Таннером
[154],
а
позднее
-
С.
Н.
Чер
ниновым
[101].
т
е
о
р
е
м
а
6.
В
лunеЙIiОЙ
задаче
эффе1i,ТU8ltые
(слабо
эффе1i,тuвuые)
ТО'l11,и
существуют
тогда
u
"!!ЛЬ1i,О
тогда,
когда
liаuдутся
та11,ие
8е1'>70ры
Jt
Е
М
(j,t
е
М)
и л
Е
E~J.
что
m h
~
~liCi
=
~
j>ja'.
(2)
1='1
j=1
Д
О
I{
а
з
а
т е
л
ъ
с т
в
о.
Д
о
с
т
а
т
с
ч
н
о
с
т
Ь.
ДЛЯ
лю-
бого
Х
Е
Х
из
(2)
получаем
m
11
It
~
~li
(c
i
,
Х)
=
~
Лj
(a
J
,
x)~
~
ЛjЬj
=
а.
(3)
1-1
"
J-l
j-l
В
линейной
задаче
множество
У
полиздрально,
а
значит,
11
в.
в.
Подиновений.
в.
д.
Ногии
162
СТРУКТУРА
МНОШГ;СТВА
;)ФФЕНТИВНЫХ
РЕШЕНИЙ
[ГЛ
3
замкнуто.
Поэтому
последнее
неравенство
согласНD
тео
реме
5
(следствию
1)
влечет
существование
эффектив
ных
(слабо
эффектпвных)
точек
Н
е
о б
х
о
д
и
м
о
с
т
ь.
Если
существует
эффективная
(слабо
эффективная)
ТОЧII:а,
то
благодаря
теореме
2.2.7
- h
равенство
(2)
при
!-t
Е
М
(!.!
Е
М)
и
л
Е
Е>
выполня-
-
ется
.•
ПодчеРlшем,
что
теорема
6
поЛучена
в
предположе
нии
Х
=F
rZJ.
Rритерий
существования
эффективных
точен
в
линейной
задаче,
где
заранее
не
предполагается
нали~
чие
допустимых
решений,
будет
сформулирован
в
§
4.4
(Н.
2).
Если
в
линейной
задаче
множество
Х
задано
ограни~
чениями
<a
i
,
х)
:::;:;
b
j
,
j =
1,
2,
...
,
k;
х
~
О(n)'
то,
как
легко
проверить,
необходимое
и
достаточное
ус
ловие
(2)
принимает
вид
неравенства
,
т
k
~
~tici:::;;
~
Лjа
i
.
i=l
j=l
Если
же
Х
является
решением
системы
<a
i
,
х>
= b
i
,
j = 1,
2,
...
,
k;
х
~
О(n)'
то
условие
существования
будет
иметь
тот
же
вид
Be~
равенства,
однако
на
Bel{TOp
')..,
не
будет
налагаться
ни
каких
ограничений
(т.
е.
л
Е
E~).
В
заключение
заметим,
что
из
(2)
для
всякого
х
Е
Х
следует
неравенство
(3).
Поэтому
в
линейных
задачах
согласно
теореме
5
непустое
множество
Р,(Х)
(а
тю,же
и
S
,(Х»
всегда
внешне
-устойчиво
[71J.
§ 3.3.
Структура
множеств
эффективных
решений
в
линейIlыl:
задачах
Учитывал
тот
факт,
что
в
линейных
задачах
множе~
ство
оцеНОI,
У
всегда
полиэдрально
(см.
теорему
19.3
из
[93]),
а
значит
выпукло
и
замкнуто,
результаты,
по~
лученпые
в
§
3.1
для
вогнутых
задач,
можно
без
труда
переформулировать
применительно
к
линейной
вадаче.
§ 3.3]
ЛИНЕйНЫЕ
ЗАДАЧИ
{63
В
даННО~1
параграфе
мы
рассмотрим
ТaIше
свойства
мно
жеств
эффентпвных
решений,
!,оторые
имеют
MQCTO
толь
КО
для
линейных
задач
и
отражают
СJIецифпну
послед
них.
На
протяжении
параграфа
предполагается,
что
линей
ная
веюор-фуНIЩИЯ
!
имеет
вид
!(х)
=
«ct,
х),
(с
2
,
х>,
...
о
••
,
<с"',
х»,
где
сi=FО(п),
i=
1,2,
...
,
m.
1.
Вначале
установим
одно
полезное
свойство
множе
cтna
эффективных
решений,
I1:0Topoe
справедллво
благо
даря
лицейности
j.
т
е о
р
е
м
а
1.
Еслu
существует
вe~TOp
~t
е
М
(f1
Е
?vf),
оля
nоторого
въznолняется
равен,ство
т
~
f1iCi
=
О(n)})
i=l
(1)
то
Gj(X)
=
Х
(Sj(X)
=
Х>.
В
nротивн,о.м
случав
эффеn
TUeltblJllU
(слабо
эффе~тuвны.мu)
решен,uя.мu
.i'rtoeyr
я.в
ляться
лишь
гран,uчнъzе
ТОЧ1Щ
.множества
Х.
Сформулированное
утверждение
для
эффективных
ре
шений
было
доказапо
С.
Н.
ЧернИI\ОВЫМ
[101],
а
позднее
1I
в
[115,
126].
Д
о
н
а
з
а т е
л
ь
с
т в
о.
Возьмем
произвольную
точку
х
О
Е
Х.
Из
равенства
(1)
вытекает
неравенство
т т
~
f1i
(ciJ.
хО)
>-
~
~!
(c
i
.1
x).iJ
i=l
i=l
справедливое
для
всех
х
Е
Х.
Поэтому,
согласно
следст
ВIIЮ
2.1.5
(теореме
2.1.3),
если
J.t
Е
М
(J.t
==
М),
то
х
О
_
собственно
эффективная
<Слабо
эффеюивная)
точна.
Докажем
вторую
часть
теоремы.
Предположим,
на
против,
что
х
О
Е
int
Х
является
эффективной
(слабо
эф
фективной)
'!ОЧI\ОЙ.
ОчеВIJДНО,
найдется
такое
8 >
О,
ЧТО
Х
е
=
{х
Е
~"X;
-
х11
~
8$ 1=
11,
21,
..
';!,
n}
с:
Х.
Легко
понять,
что
Х
О
Е
Р/(Х.)
(соответственно
х
О
Е
St(X.»,
причем
IIшожестnо
Х.
полиэдральпо.
На
оспованпи
тео
ремы
2.2.7
мошно
утверждать,
что
в
ллнейноu
задаче
с
beKTOP-фУННЦllей
«ct,
х>,
(с
а
,
х>,
...
,
(с
т
,
х»
и
мно
жеством
Х.
дЛЯ
точки
х
О
существуют
векторы
f1
Е
.м
11'
164
СТРУНТУРА
МНОЖЕСТВА
ЭФФЕКТИВНЫХ
РЕШЕНИй
[ГЛ.
3
-
~n
(J.t
е
М)
и
л
Е
Е;;
таl\ие,
что
т
n
2n
~
/1ici
=
~
Лj
-
~
Лj,
(=1
;=1
;=п+1
n
2n
~
Лj (е
+
х1-
x~)
+
~
Лj
(е
-
х1
+
x~)
=
О.
§=1
;=n+1
Из
второго
равенства
благодаря
е>
О
следует
л
=
O(zn).
ПОЭТОМУ
первое
равенство
принимает
вид
(1).
Получен~
ное
противоречие
говорит
о
том,
что
эффеI,тивные
(слабо
эффеl\тивные)
решения
могут
быть
лишь
граничными
ТОЧI\8.МИ
.•
Итак,
в
случае
линейной
beI\TOP-фУИI\ЦИИ
f
незаВИ
1
симо
от
строения
ДОПУСТИМОГО
мноmества
Х
эффеl\ТИВ
ные,
собственно
эффективные
11
слабо
эффеюивные
ре
шения
МОГУТ
либо
составлять
все
множество
Х,
Лllбо
располагаться
лишь
на
границе
этого
мноа.ества.
2.
До
I\онца
параграфа
считается,
что
Х,..
{х
Е
Еn!
<a
j
,
х>
~
b
j
,
j =
1,
2,
...
, k}.
В
линейных
задачах
Pj(X)
"""
Gj(X)
(см.
следствие
2.2.3);
поэтому
в
ФОР1[УЛИРОВl\ах
приводимых
ниже
утвершде
пий
участвуют
лишь
эффеКfивиые
точки.
Отличительной
особенностью
линейных
многокрите
риальных
задач
является
то,
что
для
этих
задач
множе
ства
Р/Х)
и
Sj(X)
всегда
можно
представить
в
виде
ко
нечного
объединения
решений
скалярных
задач
линей
ного
программирования
вида
</1,
!(х»
-+
тах.
Введем
множество
V =
{и
Е
Е
n
I v =
(;
/1iCi
для
HeKoToporo~t
Е
М}.
Т
е
о
ре}[
а
2
(Эрроу
-
Баранкии
-
Блекуэлл).
Су
ществует
Ta1tou
1tон,еЧl-tЫй
н,абор
векторов
v\
v
2
,
•••
, v
r
е
е
V,
что
,
Р/(Х)
= U
X(v
i
).
i=-l
(2)
где
Х
(v
i
)
=
{х
о
е
Х
I
<и\
х
О
)=
тах
<vi~
х)}.
~_ж
§ 3.3]
ЛИНЕ1ШЫЕ
ЗАДАЧИ
165
r
ДоназатеЛLСТВО.
Включение
P
j
(X}2,
U
X(v
f
)
i=1
очевидно
(см.
пример
2.1.2).
Докажем
обратное.
Поли
эдральное
множество
Х
представим
в
виде
выпуклой
обо
лочки
конечного
числа
точек
и
направлений
(см.
[9ЗJ):
Х
=
{Х
I
х
= ±
ffiiXi
+
~
ffijX
j
для
неIЮТОРЫХ
,
i=l
j=l+l
ffii>O, i =
1,
2,
...
,
Nj
.±
ffii
=
t}.
(3)
1=1
Подмножество
U
множества
точе]\
{х"
ха,
••. , x
1
}
на
зовем
подходящим,
если
найдется
v
Е
V
такое,
что
U
s=
5
Х(I).
В
силу
нонечности
l
число
подходящих
мнон,еств
Rонечно.
Обозначим
их
через
U
1
,
и
2
,
•••
, U
r
,
а
соответ
ствующие
им
v -
через
v"
1)2,
.,.,
и'.
Возъмем
произвольную
ТОЧI\У
х
О
Е
Р,(Х).
Существует
таrюй
вектор
v
Е
V,
ЧТО
х
О
Е
Х(и)
(см.
лемму
2.2.4),
С
дру
гой
стороны,
в
силу
(3)
ВЫПОЛIIяется
1 N
х
О
=
~
(J)iXi
+
~
ffijX'
(4)
i=l
;=1+1
1
при
неI\ОТОрых
ffii
>
О!
~
=
11
21
.•
'1
N;
.~
(O)j
=;=
1.
И
по-
1=1
1
скольну
~
ffiiXi
Е
Х
ж
то
i=1
(v
1
Х
О
)
>
<v,
i~
ffiiXi)j
а
значит,
<
и,
.
~
ffijX
j
)
~
О.
}~l-rl
1 N
А
так
как
~
ffijX!
+
~
2ffijXj
Е
Х,
то
(=1
1=1+1
(v,
х
О
)
>
(и
1
Х
О
)
+
<v,
.
~
ffiJXi).
з=1+1
•
Поэтому
(5)
1б6
СТРУКТУРА
МНОЖЕСТВА
ЭФФЕКТИВНЫХ
РЕШЕНИй
[Г.'!
3
Пусть
и
-
множество
тех
x
f
,
для
которых
COOTBeT~
ствующие
ю,
в
представлении
(4)
положительны,
И
М
о
-
множество
соотвеТСТВУЮЩIIХ
индеI,СОВ
i.
Справедливо
в.ключение
и!:
Х(и).
В
самом
деле,
если
это
не
так
и,
например,
(v
1
х
8
)
<
ша'{
(v,
х),
ТО
используя
(5)
получаем
ХЕХ
I
<v,
х
О
)<
~
ю,
та'{
(v
,
х)
=
тах
(и,
Х)1
i=l
хЕХ ХЕХ
что
противоречит
условию
х
О
Е
Х(и).
Следовательно,
множество
и
-
подходящее.
Пусть
для
определенности
и
= U
1
•
V = u
l
•
Тогда
из
равенства
(v\xi)=max(v\x)
для
всех
iE.M
Q
,
ХЕХ
учитывая
(4)
и
(5),
получим
(иl,
х
о
)
=
тах
(u1,
х),
хеХ
т. е.
х
О
Е
X(v
l
)
.•
Анализ
доказательства
теоремы
2
показывает,
что
по~
добного
рода
утверждение
будет
справедливо
и
дЛЯ
MHO~
жества
слабо
эффективных
точек;
при
этом
роль
l\IНO~
жества
У
будет
выполнять
замыl.нпеe
V =
{v
Е
Е
n
I v =
{~
~t1Ci
для
некоторого
Il
Е
м}.
Т
е
о
р
е
м
а
З.
Существует
такой набор
векторов
r
1)1,
и
l
,
••.
, v
T
Е
V,
что
Sj
(Х)
= U
х
(v
l
).
{-1
Поскольку
множество
решений
Х(и')
обычной
задачи
линейного
программирования
представляет
собой
Hel,o-
торую
грань
множества
Х,
то
согласно
ДОI\азанному
MHO~
жества
Р/Х)
и
SJ(X)
являются
объединением
некоторых
граней
множества
Х.
Возможен
и
случай,
когда
все
мно
жество
Х
выступает
в
роли
подобной
грани.
3.
Здесь
мы
будем
дополнительно
предполагать,
что
полиэдральное
множество
Х
содержит
по
крайней
мере
одну
вершину
(!<райнюю
точну)*)
.
• )
Множество
Х
заведомо
будет
содерщать
вершину,
если,
на.
пример,
l\Омпоненты
допустимых
векторов
еще
ц
в:еотрицательны,
т.
е.
;r
~
О(п)
(см.
[105]),
~
3 3]
ЛИНЕйНЫЕ
ЗАДАЧИ
{57
Напомним,
что
точка
х
О
е
Х
называется
вершиной
мно
жества
Х,
если
из
соотношений
х
О
=Лх'+(1-Л.)х"j
х',х"еХ;
ЛЕ(0,1)
следует
х'
...
х"
"'"
хО.
При
сделанном
предположении
о
существовании
вер
шины
множества
Х,
если
Р,(Х)
=1=
0,
то
существует
по
крайней
мере
одна
эффективная
вершина,
т.
е.
эффек
тивная
точка,
являющаяся
вершиной.
Действительно,
если
х
О
Е
Р,(Х),
то
согласно
лемме
2.2.4
точка
х
О
является
рсшение:и
задачи
линейного
программирования
т
~
~i
<c
l
l
х)
-*
шах
для
неноторого
~
Е
М.
(=1
Х
Как
известно
из
курса
линейного
программирования
(теорема
3.2
из
[105]),
среди
решений
этой
задачи име
ется
хотя
бы
одно
опорное
решение,
т. е.
вершина.
В
си
лу
~
>
О(т)
эта
вершина
будет
~ффективноЙ.
Введем
множество
V*
векторов
v
из
Е",
удовлетво
ряющих
следующим
двум
условиям:
1)
v=лv',
где
v'e
V
и
л~О;
2)
задача
линейного
программировапияшах
<v,
х) име
Х
ет
решение
(это
решение
эффективно!).
Нетрудно
понять,
что
v*
-
выпуклый
конус.
Обозначим
вершины
полиэдральноl'О
множества
Х
че
рез
х\
xz,
... ,
хН,
N ~
1,
и
введем
множества
v*
(;)
=
(v
Е
Е
n
I
<v
1
x
i
)
=
шах
<v,
х)},
j =
1,2,
..
. , N.
ХЕХ
Непосредственной
провеРRОЙ
легко
установить,
что
каж
дое
из
введенных
множеств
представляет
собой
выпуклый
замкнутый
конус
*).
Л
е
м
м
а
1.
Пусть
v*
=1=
0.
Тогда
N
v*
С
U
v*
(j).
j=1
д
о
R
а
3
а
т е
л
ь
с т
в
о.
Возьме]\[
ПРОП3ВОJlЬНЫЙ
вектор
v
е
V*.
Среди
решений
задачи
линейного
програ?rIМирова-
*)
Более
того,
r:аждое
пз
этих
множеств
является
полиздраль
пым
конусом.
168
СТРУНТУГА
МНОiIШСТВА
ЭФФЕКПШНЫХ
ГЕШЕПИЙ
[ГЛ.
3
ния
тах
<V
1
х)
имеется
вершина
множества
Х.
Обозначим
хеХ
ее
через
х1.
Таким
образом,
<v,
x
j
)
=
тах
<v,
х),
и
по
ХЕХ
этому
V
е
V*
(j)
при
не
котором
j
е
{1,
2,
...
,
N}
.•
Говорят,
что две
вершины
х!
и
х!
множества
Х
яв
ляются
смежными
(соединены
ребром),
если
для
ЛЮООlI
внутренней
точки
хотрезка
[х\
xi],
соединяющего
дан
ные
вершины,
из
соотношений
х=л,х'+(1-J..)х";
х',х"еХ;
л,е:(0,1)
следует
х',
х
11
е
[х\
х!].
Множество
(подмножество)
вершин
мнощества
Х
на
зывается
реберт-lO
свЯ3flЫJt в
том
случае,
если оно
состоит
лишь
из
одной
вершины,
либо
если
для
любой
пары
вер
шин
х\
х!
ЭТОГО
множества
(подмножества)
найдется
та-
кая
конечная
последовательность
вершин
x
ii
,
Xi2,
•••
,xt1e
Е
{х!,
х
2
,
•••
, x
N
},
что
X
i
! =
х!,
х!!
= x
j
И
любые
две
соседние
вершины
этой
последовательности
являются
смежными.
Л
е
м м
а
2.
Справедливы
утверждет-tUя:
1)
Мflожество
вершиfl
nо.лиэдра.лЫ-lOго
Х
ребеРflО
связ
по;
2)
nод.}f,ножество
всех
в
ер
ш
U1-t
,
доставляющих
JlaItCU-
Jly.ilt
.лUflейflОй
фУЮЩUU
fla
Х,
реберт-lO
связно.
Д
о
к
а
з
а
т
е
л
ь
с т
в
о.
1)
Если
Х
содержит
всего
одну
вершину,
утверждение
справедливо.
Пусть
х"
х!
-
про
извольная
пара
вершин
множества
Х.
Из
курса
линейно
го
программирования
известно
(см.
[105]),
что
для
вер
шины
х!
должны
выполняться
равенства
<a
ip
xj)
=
ь·
р
- 1 2 n· {;
Е'
i }
r-
, I
p
'
-"
•••
"
'1'
2"'"
n =
причем
Bel\TopbI
а\
ai~,
...
, a
in
s;
{1,
2,
"',
k},
линейно
независимы.
n n
Пусть
i.i
=
~
а
1р
,
Ь
=
~
b
ip
'
Ясно,
что
неравенство
<а,
p~1
р=l
x):i!o
выполняется
для
всякого
х
Е!!!
Х,
причем
<а, х;)
=
о.
:Кроме
того,
если
х'
е
Х
и
<а,
х')
=
Б,
то
х'
=
х;
(в
Против
ВОМ
случае
нарушается
условие
линейной
независимости
i
С
. )
векторов
а!,
а
2,
•••
,
а
'n
.
Все
это
означает,
что
линей~
ная
функция
<а,
х>
достигает
своего
максимального
зна
'1ения
на
Х
в
единственной
точке
х!.
,
§ 3,3]
ЛИНЕйНЫЕ
ЗАДА
'111
169
Теперь,
если
вершину
х
;
принять
за
начальное
опор
ное
решение
в
задаче
линейного
программирования
тах
(а,
х),
то
примененuе
СIIмплеI{с-метода
даст
исномую
хЕХ
последовательность
смежных
вершин,
в
ноторой
первым
элементом
является
х\
а
последним
x
J
•
2)
Множество
Х'
всех
точен,
доставляющих
мансимум
данной
линейной
функции,
является,
нан
известно,
поли
эдральным
множеством.
Согласно
ДОJ\азанному
пуннту
1),
множество
всех
вершин
из
Х'
реберно
связно.
Лешо
по
нять,
что
вершина
в
множестве
Х'
будет
вершиной
и
в
множестве
Х
и,
нроме
того,
любые
две
смежные
верши
I1Ы
в
Х'
смешны
и
в
Х
.•
Т
е
о
р
е
м
а
4.
Если
р/х)
*"
!2J,
то
JotНожество
эффе,.
тuвllЫХ
вершuн
реберно
связно.
Д
о
н
а
з
а
т е
л
ь
с
т
в
о.
В
начале
данного
пуннта
было
НОI,азано,
что
из
перавенства
Pj(X)
*"!2J
следует
сущест
вование
зффеI,ТIIВНЫХ
вершин.
Если
имеется
лишь
одна
эффеНТIIвная
вершина,
то
УТВ\:Jржденпе
справедливо.
Пусть
х
;
И х
;
-
две
НРОIIзвольные
эффеНТlIвные
вер
шины
и
пм
соответствуют
множества
У*Ш
и:
У*Ц).
Со
гласно
лемме
2.2.4
У*
n
{Т*
(i)
*"!2J
11
1'* n
ТТ*
(;)
.р.
!2J.
Возь
мем
и
1
Е
~'*
n V*(O JI
и
2
Е
V* n
ТТ*(Л
JI
расс:'.IOТРИМ
отре
зон
[и\
и
2
],
соеДИНЯЮЩПII
ТОЧIШ
и
1
II
и
2
•
Поскольку
У*
выпунлый
НОНУС,
то [и\
и
2
]
s;
У*.
Согласно
лемме
1
N
[и!,
и
2
]
s=
U
у*
и),
причем
наn;дое
У*(п
есть
выпуклый
j=l
замкнутыii
нонус.
Тюшм
образом,
отрезо!>
[v\
V
Z
]
ПОRРЫ
вается
конечным
числом
отрез
нов
T
i
,
T
i
,
•••
, T
11
,
где
1 2
{i
1
,
i
2
,
•••
, i/}
с
{1,
2,
...
, N}
и
T
is
=
[и!,
и
2
]
n
у*
(t,),
8:::::0
-==
1,
2,
...
,
[.
Благодаря
замкнутости
у*u.)
отрезки
T
1
,
замкнуты.
А
тан
нан
они
понрывают
весь
отрезок
[и\
и
2
],
то
моашо
считать,
что
s =
1,
2,
...
,
1-1.
Множество
вершин,
являющихся
решению,ш
каждой
из
'задач
шах
(и\
х),
s =
1,
2,
...
,
l-
1,
представляет
собой
под
'ЕХ
множество
IIЗ
Fj(X)
II,
кроме
того,
согласно
лемме
2
ре
бс-рно
связно.
IJолее
того,
ЯСllО,
что
объединение
по
s =
{70 CTP}'l\TYPA
МНОЖЕСТВА
ЭФФЕl\ТI!ВНЫХ
РЕШЕНий
[ГЛ.
Э
-=1,
2,
...
,
l-
1
всех
подобного
рода
вершин
также
ребер
но
связно.
Но
х
;
-
точка
максимума
функции
<и\
х),
а
r -
точка
максимума
фующии
<V
il
-
1
;
х) на
Х.
Следо
вательно,
вершнны
x
i
,
х1
входят
В
указанное
объедине
ние,
и поэтому их
можно
соединить
последовательностью
ребер,
каждое
из
которых
соединяет
пару
эффективных
вершин
.•
Анализ
приведенных
рассуждений
ПОl\азывает,
что
по
добным
образом
можно
установить
реберную
связность
множества
слабо
эффективных
вершин.
Для
этого
вместо
множеств
V
и
у*
следует
использовать
их
замыкания
V
и
У*,
а
вместо
леммы
2.2.4 -
теорему
2.2.2.
§
3.4.
Оценка
числа
эффективных
точек
в
дискретных
задачах
Когда
мноа;:ество
У
с
Еm
конечно
(состоит
из
N
эле
ментов),
то
множество
эффеI\ТИВНЫХ
точек
Р(
У)
всегда
непусто
и,
более
того,
внешне
устойчиво.
Хотя
-в
каждой
Rонкретной
задаче
все
эффективные
точки
можно
пере
числить,
несомненный
интерес
представляет
вопрос
о
получении
«априорной»
оценки
числа
таЮIХ
точек
По
добного
рода
оценки
могут
ОI,азаться
полезными
при
анализе
трудоемкости
различных
алгоритмов построения
множества
эффективных
решений,
а
также
процедур
вы
деления
наиболее
приемлемого
решения
среди
всех эф
фективных.
Количество
эффективных
точек
I
Р(
У)
I
в
зависимости
от
конфигурации
множества
У,
очевидно,
может
изме
няться
в
пределах
от
1
дО
N.
Поэтому
в
общем
случае
N -
точная
верхняя,
а
1 -
точная
нижняя
оценни
чис
ла
IP(Y)I
(а
также
и
IS(Y)I).
Однако,
если
I{аким-либо
образом
учитывать
особенности
конфигурации
множест':
ва
У,
то
указанную
верхнюю
оценку
МОiIШО
уточнить.
Наиболее
просто
это
сделать
в
том
случае,
когда
мно
жество
У
!
значений
i-ro
нритерия
(§
1.1)
нонечно
при
наждом
i
-1,
2,
"',
m.
Поскольку
числа
IP(Y)I
и
IS(Y)I
инвариантны
относительно
монотонных
преобразований
нритериев
(§ 1.8),
то
удобно
полагать,
что
каждое
мно
жество
У
!
состоит из
целых
чисел,
так
что
множество
оценок
}'"
=
У
!
Х
У
2
Х
...
Х
У
т
-
это
множество
точек
m-
мерного
гиперпараллелепипеда
с
цеЛОЧIIсленными
коор-