Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 1.1]
СВЕДЕНИЯ
О
МНОГОНРИТЕРИАЛЬНЫХ
ЗАДА
ЧАХ
11
...
х
у
т.
Иногда
У
получается
из
ух
при
помощи
тех
или
ИНЫХ
ограничений,
направленных
на
удаление
лишен
ных
смысла или
же
заведома
недостижимых
векторов.
Введение
в
рассмотрение
множества
У
дает
ряд
пре
имуществ.
Например,
возникает
возможность
исследова
ния
не
одной,
а
сразу
целого
семейства
задач,
для
каж
дой
из
которых
множество
достижимых
оценок
входит
в У.
В
частности,
становится
возможным
пзучать
харак
тер
зависимости
оптимального
решения
от
тех
или
IIНЫХ
параметров
задачи.
Далее
решения
всегда
будут
обозначаться
буквой
х,
часто
снабжаемой
различными
индексами,
а
соответству
ющие
им
оценки
-
буквой
у
с
теми
же
индексами,
на
пример:
у
=
f(x),
у*
=
f(x*)
и
Т.
П.
Если
данная
вектор
ная
оценка
уО
является
достижимой
и
ей
соответствует
не
сколько
решений,
то
под
х
О
будет
пониматься
(если
нет
специальных
оговорок)
произвольное
из
этих
решений
(т.
е.
любое
решение,
удовлетворяющее
равенству
f(xO) =
=
уО).
3.
В
задачах
принятия
индивидуальных
решений
кри
терии
служат
для
выражения
«интенсивности»
суще
ственных
свойств
(признаков)
решений.
Например,
при
сравпении
неиоторых
изделий
могут
использоваться
та
кие
иритерии,
как
масса,
стоимость,
дата
выпусиа,
внеш-
.
ний
(товарный)
вид
и
Т.
П.
В
задачах
принятия
группо
вых
решений
иритерий
fj
характеризует
«качество»
(или
предпочтительность)
решений
с
точии
зрения
индивида
i,
входящего
в
группу
{1,
2,
...
,
т}.
Например,
если
реше
ний
ионечное
число
и
индивид
i
все
их
проранжировал
.
(упорядочил
по
предпочтительности),
то
можно
принять·
f;{x') = 1
для
наиболее
предпочтительного
решения
х',
/l<х")
= 2 -
для
следующего
по
предпочтительности
ре
шеиия
х",
и
Т.
Д.
ПО
своему характеру
критерии
делятся
на
количе
ственные
и
иачественные.
Грубо
говоря,
[{ритерий
явля
ется
иоличестве:нным,
когда
его
значения
имеет
смысл
сравнивать,
указывая,
на сколько
или
во
сиолько
раз
одно
значение
больше
другого,
и
качественным,
когда
та
кие
сравнения
бессмысленны.
Примером
количественного
критерия
fj
является
масса.
Если
фиксирована
единица
измеренИJI
массы,
то
М,ожно
говорить
О
том,
ВО
сколько
раз
12
ОСНОВНЫЕ
понятия
И
ОПРЕДЕЛЕНИЯ
[ГЛ.
1
(или
же
на
с:коль:ко)
одно
изделие
тяжелее
другого:
отно
шение
весов
изделий
не
изменяется
после
перехода
:к
дру-
.
гой
единице
измерения,
т. е.
'после
преобразования
fj
в
kfi,
где
k >
О.
Понятно,
что
вся:кое
другое
преобразование
(не
являющееся
умножением
на
положительное
число)
может
привести
:к
изменению
исходного
соотношения
зна
чений
fi.
В
разобранном
примере
допустимыми
преобразования
ми
:критерия
fj
являются
все
положительные
линейные
преобраэования,
и
толь:ко
они.
В
общем
случае
фуп:кцшо
q>
называют
допустимым
преобразованием
:критерия
fi,
если
фун:кция
q>(fj)
вновь
о:казывается
:критерием,
изме-
.
ряющим
(задающим)
то
же
свойство.
При
замене
fi
на
f~
=
q>
(fi)
множество
У
;
изменяется
на
Y~
=
q>
(Y
i
).
Та:ким
образом,
с
:каждым
:критерием
связывают
мно
жество
допустимых
преобразований
Ф
и
говорят,
что
этот
:критерий
имеет
шкалу
типа Ф,
или
что
измерение
произ
водится
в
шкале
типа
Ф.
Обычно
множество
Ф
естествен
но вводится
вместе
с
заданием
:критерия,
но
иногда
опре
деление
типа
шкалы
о:казывается
самостоятельной,
до
статочно
сложной
задачей.
В
вышеприведенном
примере
Ф
=
Ф
О
=
{q>Iq>(z)
= kz,
k >
О}.
lli:кала
та:кого
типа
называется
ш:калой
отноше
ний,
та:к
:ка:к
сохраняются
отношения
величин:
kzl/kz
Z
=
= Zl/ZZ
==
е
(е
- const).
РаспространеННЫ1\1
является
и
случай
измерения
в
ш:кале
типа
ФИ
=
{q>1
q>(Z)
= kz +
1,
k>
т.
Здесь
допу
стимыми
преобразованиями
являются
умножение
на
поло
жительное
число
k
и
добавление
произвольного
ЧИСЛа
1.
Та:кая
ш:кала
называется
шпалой
uurервалов.
Это
назва
ние
объясняется
свойством
сохранения
отношений
интер
валов:
:1_
z2
=
(kz
1
+
1)
-
(kz
2
+
1)
=
е
(е
_ const).
:8
_.;:4
(ki
+
1)
- (kz
4
+ l)
Примером
:критерия,
имеющего
ш:калу
интервалов,
слу
жит
«дата
выпус:ка
изделию):
для
измерения
времени
необходимо
фи:ксировать
масштаб и
начало
отсчета.
Шкала
является
тем
более
совершенной,
чем
уже
множество
Ф
допустимых
преобраэованиЙ.
Критерии,
имеющие
ш:калу,
не
менее
совершенную,
чем
интерваль
ная,
называются
,.олuчествеnnЫJtu.
В
большинстве
слу-
§
1.11
СВЕДЕНИЯ
О
МНОГОRРИТЕРИАЛЬНЫХ
ЗАДАЧАХ
13
чаев
количественные
критерии
соответст~уют
объектив
ным
измерениям
объективных
«<физических»)
свойств.
Однако
весьма
широко
распространены
и
критерии
с
ме
нее
совершенными
шкалами,
чем
шкала
интервалов.
Наименее
совершенной
шкалой
нритериев,
встречаю
щейся
в
задачах
оптимизации,
является
порядковая
шка
ла,
для
которой
множество
допустимых
преобразований
Ф
П
состоит
из всех
монотонно
возрастающих
функций:
Ф
П
=
{cplz'
>
Z2
-+
cp{ZI)
>
cp{Z2)}.
:Критерии,
имеющие
по
рядковую
шкалу,
называются
nачествеnnым,u.
Значения
качественного
критерия
име,ет
смысл
сравнивать
только
по
отношениям
«больше»,
«меньше»
и
«равно»
-
они
со
храняются
при
монотонных
преобразованиях.
Но
выяс
нять,
во
сколько
раз
или
на
сколько
одно
значение
боль
ше
другого,
бессмысленно.
:Критерий
с
порядковой
шкалой
естеств.енным
образом
возникает
в
тех
случаях,
когда
решения
ранжируются,
т. е.
располагаются
по
воз
растанию
или
убыванию
интенсивности
некоторого
свой
ства,
а
затем
им
приписываются
числа
таким
образом,
чтобы
большей
интенсивности
соответствовало
большее
(или,
наоборот,
меньшее)
число.
Обычно
такие
ранжиро
вания
получаются
при
субъеI\ТИВНЫХ
(<Измерениях»,
на
пример
отражают
мнение
индивида
i
о
предпочтительно
сти
решений.
Весьма
часто
субъективные
измерения
выполняются
и
в
балльных
шналах.
Например,
эксперты
могут
оцени
вать
в
баллах
внешний
вид
изделия.
:Критерии
с
балльны
ми
шкалами
занимают
«промежуточное»
положение
меж
ду
количественными
и
качественными
критериями.
Утверждение
о
значениях
критериев
с
заданными
ти
пами
шкал
называется
осмысленным, или
адекватным,
ес
ли
его
истинность
не
изменяется
после
применения
к
критеРИЯ1\{
любых
допустимых
преобразовапий,
опреде
ляемых
типами
шкал.
Поэтому
для
анализа
и
репrения
практической
многокритериальной
задачи
оптимизаЦИIl
следует
применять
только
те
определения
11
понятия,
ме
тоды
и
процедуры,
ноторые
приводят
к
получению
адек
ватных
J!ЫВОДОВ
и
рекомендаций.
Например,
широко
известным
является
метод
решения
многопритеР11альных
задач,
основанный
на
«свертывавию)
векторного
критерия
f
в
одну
фУНIщию
-
обобщенный
(или
агрегированный)
нрптерий
р{!!,
!z,
... ,
!т).
Нетрудно
14
ОСНОВНЫЕ
понятия
И
ОПРЕДЕЛЕНИЯ
[ГЛ.
1
убедиться
в том,
что
этот
метод
не
пригоден
для
ре
шения
задач
с
:качественными
:критериями.
Возьмем
наи
более
распространенный
обобщенный
:критерий
-
линей-
т
ную
«сверт:ку»
F1:,
=
~
f1i/i,
где
J,.t/
-
не:которые
поло-
i=l
жительные
числа,
хара:ктеризующие
относительную
важ
ность
:критериев
(:коэффициенты
важности).
Пусть,
напри
мер,
т=-
2,
J,.tl
=
f12
=
1,
I(x')
=z
(2,8),
'(х")
= (1, 27).
Тогда
Fx
у:казывает,
что
х"
лучше,
чем
х',
та:к
:кю,
2 + 8 < 1 + 27.
Одна:ко
если
:к
первому
:критерию
приме
нить
допустимое
преобразование
<p\(Z)
=
Z~,
а
:ко
второму
<Pa(Z)
=
Z\/З
(т.
е.
1\
заменить
Ha/~,
а
12-
на
'~!3),
то
вывод
о:кажется
противоположным,
ибо
32 + 2 > 1 + 3.
Для
более
подробного
озна:комления
с
вопросами
из
мерений
в
ш:калах
различных
типов
можно
обра
титься
:н
иниге
[56].
Строгое
и
полное
изложение
математичеСIЮЙ
теории
измерений
имеется
в
монографиях
[75, 89].
4.
На:к
уже
у:казывалось,
выделение
оптимального
ре
шения
из
множества
Х
должно
быть
произведено
на
осно
ве
предпочтений
лица,
принимающего
решение.
Эти
пред
почтения
должны
быть
описаны
формализован
но
при
по
мощи
:критериев
11' 12'
...
,
1т.
В
теории
принятия
реше
ний
разработаны
специальные
общие
способы
описания
предпочтений.
Для
удобства
читателя
в
следующем
пара
графе
приводятся
все
используемые
в
дальнейшем
сведе
ния,
:касающиеся
описания
предпочтений
и
определения
оптимальных
решений.
Более
подробно
эти
вопросы
ос
вещены,
например,
в
:книгах
[56, 103].
5.
В
последующих
главах
основное
внимание
будет
уделено
:конечномерным
многоиритериальным
задачам,
т.
е.
задачам,
в
которых
Х -
подмножество
пространства
Еn.
В
таиих
задачах
множество
Х
обычно
выделяется
из
не:которого
более
широ:кого
множества
D 5
Еn
при
помо
щи
специальных
ограничений,
:ноторые
чаще
всего
пред
ставляются
в
виде
неравенств:
Х
=
{х
е:
Dlg\(x)
!Е;
О,
...
,
сл(х)
$:;
О},
(1)
где
g/,
f =
1,
2,
...
,
k,-
числовые
фуниции,
определенные
на
D
и
составляющие
ве:ктор-фун:кцию
ограничений
g = (gl,
gz,
...
, gk)'
При
этом
считается,
что
и
11, 12,
'"
... ,
1т
та:кже
определены
на
D.
§
1.2]
ОТНОШЕНИЯ
ПРЕДПОЧТЕНИЯ
И
ФУНIЩИИ
ЦЕННОСТИ
{5
В
роли
множества
D
обычно
выступает
либо
все
про
странство
ЕП,
либо
некоторое
его
специфичесное
подмно-
жество,
например
неотрицательный
ортант
E~,
образуе
мый
всеми
векторами
с
неотрицательными
компонентами:
E~
=
(Х
Е
Е
n
I
Xl
>-
О,
••..
,
Х
n
2::
01.
п
рантически
множе
c~o
D
выделяется
из
Еп
при
помощи
самых
простых
и
очевидных
ограничений
на
переменные
Х;.
Так,
если
Х;
потребное
количество
ресурса
i-ro
типа,
то
Xj;;;;;;
О
и
мож-
но
принять
D =
Е:;".
6.
В
зависимос;и
от
струнтуры
множества
Х
(или
же
D)
и
свойств
функций
f/
(а
также
gj)
для
удобства
иссле
дования
выделяют
различные
нлассы
многокритериаль
ных
задач.
Так,
если
множество
Х
(D)
содержит
нонечное
число
элементов,
то
задача
называется
конечной,
а
если
X(D)
исчислимо,
т.
е.
конечно
или
же
счетно,
то
-
дис
кретной.
В
частности,
если
у
каждого
вектора
Х
из
Х
(D)
все
компоненты
Х/
-
целые
числа,
то
задача
называется
целочисленной.
А
если
венторы,
образующие
Х
(D),
буле
вы
(т.
е.
состоят
из
нулей и
единиц),
то
и
сама
задача
называется
булевой.
Если
Х
(или
D)
выпукло,
а
все
f,
(и
gj)
-
вогнутые
функции,
то
задача
называется
вогнутой.
В
частности,
~c
ли
Х
-полиэдральное
множество
(т.
е.
«вырезано»
из
Ел
нонечной
системой
линейных
неравенств
и
равенств),
а
все
f/
линейны,
то
многонритериальная
задача
является
линейной.
В
специальный
класс
выделяются
танже
задачи,
в
ко
торых
все
функции
f/
(и
g)
дифференцируемы
(иногда
требуется
непрерывная
дифференцируемость).
При
этом
обычно
предполагается,
что
множество
D -
отнрытое
(на
пример,
в
его
роли
выступает
само
пространство
Еп
или
положительный
ортант
Е:;"
=
int
Е];
=
(Х
Е
Е
n
I Xi>
01
i=
=
1,2,
...
,
n})
или
же
что
Х
s;;;
intD.
§ 1.2.
Отношения
предпочтения,
функции
ценности
и
выбора
1.
Достаточно
общим
и
хорошо
разработанным
являет
ся
способ
описания
предпочтений
на
«язьше»
бинарных
отношений.
Вообще
бинарные
отношения
могут
быть
16
ОСНОВНЫЕ
ПОНЯТШI
И
ОПРЕДЕЛЕНИЛ
(ГЛ.
1
использованы
и
практически
применяются
для описания
не
только
предпочтений,
но и
попарных
свявей
самого
различного
характера
между
объектами
произвольной
природы.
Нак
извеетно,
бuнарnым
отношением
р
на
(или
во)
множестве
А
называется
подмножество
множества
А
2 =
=
А
ХА,
т.
е.
совокупность
упорядоченных
пар
Са,
Ь),
где
а,
Ь
Е
А.
Если
(а,
Ь)
Е
р,
то
говорят,
что
а
и
Ь
на
ходятся
в
отношении
р,
и
этот
факт
записывают
тю,:
арЬ.
Можно
вводить
в
рассмотрение
и
n-арные
отношения
как
подмножества
множества
А
n.
Однако
мы
будем
иметь
дело
только
с
бинарными
отношениями,
и
поэтому
для
краткости прилагательное
«бинарное})
часто
будем
опу
скать.
Н
бипарным
отношениям
как
ко
множествам
приме
нимы
все
теоретико-множественные
операции,
в
том
чис
ле
операции
пересечения
N,
объединения
U,
образования
разности
\
и
другие.
Для
отношений
вводятся
и
специфи
ческие
операции.
Таи,
под
р-I
понимается
отношение,
об
ратное
к
р,
которое
определяется
следующим
образом:
т.
е.
пара
Са,
Ь)
ВIшючается
в
р-I
тогда
и
толы{о
тогда,
lюгда
пара
(Ь,
а)
входит
в
р.
Пусть
В
с:
А.
Отношение
Рв
=
{(а,
ь)
Е
pla,
Ь
6
в}
на
зывается
сужением
р
на
В.
Отношение
р
называется
реф.деl'>сивным,
если
(а,
а)
Е
Е
Р
ДЛЯ
всякого
а
Е
А,
и
uрреф.деl'>сивnым,
если
(а,
а)
Ф
Ф
р,
т. е.
ара
не
верно
ни
для
одного
а
е
А.
Отношение
р
называется
симметричным,
если
из
(а,
Ь)Е
реледует
(Ь,
а)Е
р,
аСUJtметричnым,
если
Са,
Ь)Е
Е
Р
влечет
(Ь,
а)
Ф
р,
и
аnтисu.м.метричным,
если
из
(а,
Ь)
Е
Р
и
(Ь,
а)
Е
р
вытекает
а
=
Ь.
Асимметричное
отношение
является,
очевидно,
и
иррефлексивным.
Отношение
р
называется
транзитивным,
если из
арЬ
и
Ьрс
следует
арс.
Элементы
а
и
Ь
из
А
называются
сравnимьши
по
р,
сели
справедливо
арЬ
или
Ьра,
и
несравнимыми
по
р
в
противном
случае
(когда
неверно
ни
арЬ,
ни
Ьра).
Отно
шение
р
называется
nо.дllЫ.~
(или
связн,ъUt),
если
любые
а,
Ь
Е
А
сравнимы
(в
том
числе
при
а
=
Ь).
Отношеющ
§ 1.2]
ОТНОШЕНИfI
ПРЕДПОЧТЕНИЯ
И
фунtщии
nERHOCTlt
17
не
являющееся
полным,
называется
частичн,ЫJlt
(ИЛИ
не
СШ13ным).
Например,
отношение
~
(<<не
меньше»)
на
множестве
действительных
чисел
рефлексивно,
антисимметрично,
транзитивно
и
полно,
а
отношенне
>
(<<больше»)
ирреф
лексивно,
асимметричпо,
транзитивно,
но
пе
является
полным
(так
кан
а>
а
иеверно).
Рефлексивное,
симметричное
и
транзитивное
отноше
иие
называется
эnвива.леnтnостъю.
Примером
эквивалент
ности
служит
отношение
равенства
=
векторов
нв
Ет.
Эк
вивалентности
играют
большую
роль
в
математике.
Это
объясняется
тем,
что
они
тесно
связаны
с
равбиениями
множеств.
Совокупность
{A
j
}
непустых
подмноmеств
мно
а:ества
А
навывается
его
равбиением,
если
они
попарно
не
пересекаются
(A
s
n
А
l
=
l2J
прн
j
*-
[)
и
в
совокупносТJI
составляют
все
А
(т. е.
U A
j
=А).
Сами
А
;
называroтся
j
1>лаССaJItи
разбиеnия.
Если
р
-
эквивалентность,
то
она
порождает
разбие
ние
А
следующим
образом:
а
1I
Ь
относятся
к
одному
Iшассу
(навываемому
n.лассом
эnвива.леnтnости)
в
том
1I
толыю
том
случае,
если
(а,
Ь)
е
р.
Обратно,
если
дано
разбиение
{A
j
}
множества
А,
то
отношение
р,
определяе
мое
так:
(а,
Ь)
е
р
тогда
и
только
тогда,
когда
а
II
Ь
от
носятся
1\
одному
И
тому
же
классу
разбиения,
оказыва
ется
Э1\ви:аалентностью.
Иррефле1\сивное
транзитивное
(а
потому
и
асиммет
ричное)
отношение
называется
СТ
рогим
(частичн,ым)
nо
ряд1>ОJlt,
а,рефлексивное
и
транзитивное
отношение
-
(час
ТUЧnЫJlt)
nвазиnорядnом
(или
предпорядком)
.
Антисим
метричный
I\В8.ЗИПОРЯДОН
называется
(частиЧllЪL.1t)
nо
рядJ;ОJ.t:
Расс:мотрим
отношения
~,
> > n
>,
определяе:мые
на
Еm
следующим
образом:
а
Е;:
Ь
++
а/
~
Ь(,
t =
1,
2,
...
, m;
,
а
>
Ь
++
а
~
Ь
и
а*-
Ь
(т.
е.
справедливы
т
нера
венств
а/
~
b
i
,
причем
хотя
бы
одно
ив
них
-
строгое);
а>
Ь
++
а;
>
Ь
Е
,
i =
1,
2,
...
, m;
а,>
Ь
++
а
=
Ь
ИЛИ
аl>
Ь(
хотя
бы
для
одного
ie
"е{1,
2,
...
,
т}.
Легко
видеть,
что
отношение
;;;;
является
частичным
ПОРЯДКОl\{,
>
И
> -
строгие
частичные
порядки,
а
:>
2
в. В.
ПОДИНО8сltиl1.
В.
Д.
Ногин
18
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
[ГЛ.
i
рефлексивно
(НО
не
явлнется
ни
симметричным,
ни
тран
зитивным).
Взаимосвязь
этих
четырех
отношений
и
отношения
ра
венства
представлена
схемой
на
рис.
1.
Согласно
этой
схеме,
например,
из
а>
Ь
следует,
что
верно
таюке
а
>
;;?:
Ь,
a~
Ь
и
а
>=
Ь,
таи
что
>
с
>
с
~
с
>.
Заметим
==
Рис.
1.
еще,
что
~
есть
объединение
>
и
=.
Полезно
иметь
в
виду
таК
же, что
а;>
Ь
верно
тогда
и
толь
н:о
тогда,
когда
Ь
>
а
неверно.
В
дальнейшем
/
используется
следующее
утверждение
[67].
Л
е
м м
а
1.
а
/"
Ь
тогда
и
толь
'Но
тогда,
nогда
</l,
а>
~
<(..t,b>
для
nenоторого
веnтора
/l
из
IIшожества
Для
доказательства
леммы
предположим
вначэле,
что
а:>
Ь.
Если
а
=
Ь,
то
</l,
а>
=
</l,
Ь>
при
любом
(..t
ЕМ.
Пусть
а!
> b
j
•
Определим
число
t =
шах{р,
q}
~
О,
где
р
=
~
1
ai
1,
q =
~
I b
i
1·
.
i~j
i+j
Если
t =
О,
то
</l,
а>
>
</l,
Ь>
при
всяком
(..t
е
М.
Ес
ли
t >
О,
то
пусть
Имеем
а;
-
Ь
;
= 2tr
;;;:;;
r(p + q),
откуда'
aj-rp>-bj+rq,
а]
+ r
~
ai
>-
Ь]
+ r
~
b
i
,·
i7'-j
i*j
таи что
</l,
а»
</l,
Ь>
при
/lj
= 1![ 1 + r(m -
1)],
и
(..ti
=
=
r([
1 + r(m - 1)]
при
остальных
i
=1=
j.
Пусть
теперь
а;>
Ь
неверно,
таи что
справедливо
Ь
>
а.
Но
тогда,
очевидно,
<(..t,
Ь>
>
<(..t,
а>
для
любого
I1
ЕМ
.•
§
1.2]
ОТНОШЕНИЯ
ПРЕДПОЧТЕНИЯ
И
ФVНlЩИИ
ЦЕННОСТИ
19
Пусть
\jJ
-
функция,
отображающая
А
во
множе
ство
и,
на
котором
задано
отношение
б.
Это
отношение
индуцирует
на
А
отношение
р
следующим
образом:
(а,
Ь)
Ер
++
('ф(а),
",(ь»
Е
б.
Нетрудно
проверить,
что
если
б
рефлеI{СИВНО
(иррефщшсивно,
симметрично,.
транзитивно),
ТО
таким
же
будет
и
р.
Следователь
но,
если
б
-
эквивалентность
(квазипорядок,
строгий
порядон)
,
то
и
р
будет
отношением
такого
же
типа.
2.
Для
описания
предпочтений
широко
используются
следующие
бинарные
отношения,
вводимые
на
множе~
стве
А
сравниваемых
объентов
(в
многокритериальных
задачах
ТaI\ИМИ
множествами,
кан
уназывалось
в
§ 1.1,
являются
множество
решений
Х
и
множество
всех
оце
нон
у).
Отношеnие
(строгого)
nре8nочтеnия
Р:
аРЬ
означа~
ет,
что
объект
а
(строго)
предпочтительнее,
чем
Ь.
Отnошеnие
безразличия
1:
alb
означает,
что
объенты
а
и
Ь
одинаковы
по
предпочтительности
(если
выбор
ог
раничить
двумя
этими
объеюами,
то
безразлично,
накой
из
них
взять)
*).
Отnошеuие
пестрогого
предпочтепия
R:
aRb
означает,
что
объеI{Т
а
не
менее
предпочтителен,
чем
Ь,
т.
е.
имеет
место
аРЬ
или
же
alb;
формально
R
есть
объединение
Р
и
1:
R =
Р
U
1.
ОТНОШЮj]Ш
предпочтения
всегда
должны
обладать
сле
дующими
свойствами:
Р
асимметрично
(и
иррефленсив
но);
1
рефлексивно
и
симметрично,
R
рефлеIl:СИВНО;
Р
и
1
не
пересенаются
(не
может
быть
одновременно
аРЬ
и
alb).
Полезно
иметь
в
виду,
что
Р
и
1
восстанавливаются
по
R:
alb,
когда
одновременно
aRb
и
bRa,
т. е.
1 = R n
R-I;
аРЬ,
когда
aRb
верно,
но
bRa
неверно:
Р
=
R\R-
1
=
=R~
.
Таким
образом,
1
есть
«симметричная
часты>,
а
Р
«асимметричная
часты>
R.
В
общем
случае
отношения
R,
Р
и
1
нетранзитивны.
Если
же
R
оказывается
транзитивным,
то
транзитйвными
будут
Р
и
1;
в
этом
случае
R -
нвазипорядон,
Р
-
СТРО-
*)
Введение
обозпачепий
р
и
1
связапо
с
апглийскими
словаJlIИ
латинского
происхождения
preference
(предпочтение)
и
indifferen-
се
(безразличие).
2*
20
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
[ГЛ.
1
гий
порядон,
1 -
энвивалентность,
причем
Р
транзитив
но по
1:
из
аРЬ
и
Ыс,
а
танже
из
alb
и ЬРс
следу
ет аРс.
3.
Пусть
в
А
задано
отношение
нестрогого
предпоч
тения
R
(порождающее,
нан уназывалось
выше,
отноше
ния
Р
и Л,
и
пусть
В
-
подмножество
А.
Объент
(эле
мент)
а*
е В
называется
uаи,л,учшuм
(оптимальным)
по
R
(в
В),
осли
ОН
не
менее
предпочтителен,
чем
любой
дру
гой
из
В,
т. е.
если
a*Ra
справедливо
для
любого
а
Е
В.
Наилучший
объент единствен
с
точностью
до
энвивалент
ности
1,
.т.
е.
если
Ь*
-
танже
наилучший
в В, то
a*Ib*.
Если
необходимо
произвести
выбор
одного
объента
из
В,
то
можно
взять
любой
из
наилучших
объентов
(если
они
в
В
есть).
Если
R -
порядон,
то
наилучший
объент
един
ствен.
К
сожалению,
если
отношение
R
не
является
связным
нвазипорядном,
то
наилучших
элементов
может
не
она
заться
даже
в
нонечном
множестве
В.
Например,
если
В
=
{а,
Ь,
с}
и
R =
{(а,
а),
(Ь, Ь),
(С, С),
(Ь,
сН,
то
в
В
наилучшего
элемента
нет
(а
и
Ь
не
сравнимы
по
R).
По
этому
приходится
использовать
более
слабое
понл.тие
ман
симального
объента.
Для
дальнейшего
это
определение
удобно
ввести
применительно
!{
общему
случаю:
не
пред
полагая,
что
объент входит
в
В.
Объент
а
О
е
А
называется
маnсима,л,ьuым
по
Р
отuоси
те,л,ьuо
В,
если
в
В
не
существует
объента
а,
строго
бо
лее
предпочтительного,
чем
а
О
,
т. е.
если
аРа
О
не
имеет
места
ни
при
наном
а
е
В
*).
Если
объент
а
О
принадлежит
В,
то
его
называют
мансимальным
по
Р
в
В.
В
разобран
ном
тольно
что
примере
мансимальными
(в
В)
являются
объекты
а
и
Ь.
Легко
проверить,
что
наилучший
в.
В
объент
является
и
маНСIIмальным.
Обратное
утверждение,
разумеется,
неверно.
Обозначим
множество
максима:IЬНЫХ
по
Р
объеI\ТОВ
из
В
через
Мах,в.
Это
множество
вuутреuuе
устойчиво
в
том
смысле,
что
если
а,
Ь
Е
МахрВ,
то
не
!южет
быть
ни
аРЬ,
ни
ЬРа.
Это
множество
называется
вuеuше
устойчивым
*)
Используются
ТlШже
наименования
«неподчинеиныЙ.,
(шедомииируемый»
и
др.
Если
объект
(элемент)
а
е
В
ие
яВЛя
ется
максимальным
(т.
е.
существует
Ь
е
В
такой,
что
ЬРа),
то
он
вааывается
подчиненным
(объекту
Ь)
или
доминируемыM
(объектом
Ь).