Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 1.8]
вRвивАлЕнтныE
ВЕНТОРНЫЕ
RРИТЕРиИ
61
тогда
и
ТОЛЬRО
тогда,
ногда
f2(x)
ё"i;;
/2(х')
(соответственно
/2(х)
>
/2(х')).
Из
этого
определения
следует,
что
ЭRвивалентные
по
!-
(по:::)
Rритери'и
по
рождают
в
Х
одни
и
те
же
отно-
;ения
строгого
предпочтения
!:::.!
(!-
f)
и
безразличия
'"",.
Поэтому,
в
ч,астности,
им
соответствует
одно
и
то
же
множество
эффеRТИВНЫХ
(слабо
эффеRТИВНЫХ)
ре
шений.
Предположим,
что
критерий
/'
получен
из
j
переста
НОВRОЙ
частных
критериев.
Очевидно,
/
и
/'
ЭRвивалентны
11
по
!-,
И
по
;::.
Следовательно,
множества
Fj(X)
и
S,(X)
~
инвариантны
относительно
пере
нумерации
частных
RРИ
териев.
ПодчеРlшем,
что
речь идет
об
инваРИtlНТНОСТИ
этих
множеств
именно
в
целом:
выбираемое
по
неноторым
соображениям
эффеRтивное
или
слабо
эффеRтивное
ре
шение
таRИМ
свойством,
вообще
говоря,
не
обладает
(на
пример,
лексикографически
оптимальное
решение
всегда
эффеRТИВНО,
однано
после
перенумераЦИII
Rритериев,
оста
ваясь
эффеRТИВНЫМ,
оно
может
не
быть
леКСИRографиче
ски
оптимальным).
Заметим,
что
надлежащим
образом
сформулированные
свойства
независимости
или
же
зав'И
СIlМОСТИ
выбора
решений
от
нумерации
I\ритериев
лежат
в
основе
аI\сиоматичеСRОЙ
теории
важности
Rритериеn
[82, 96].
Приведем
неСRОЛЬRО
известных
простых
утверждений
(см.,
например,
[77]),
позволяющих
в
ряде
случаев
ре
шать
вопрос
об
эквивалентности
векторных
Rритериев,
а
также
строить
новые
I{ритерии,
эквивалентные
данному.
Л
е
м
м
а
1.
Если
-притерии
Р
и
/2
э-пвивалентны
ПО
;:
- -
или
!-.'
ТО
э-пвивалеnтnы
в
TOJt
же
СJtысле
и
-притерии
/' =
и~,
/~,
"',
/~,
"')
и
/"
=
(Л,
/~,
"',
/~,
ЧJ),
где",-
nроuавольnая
числовая
фуn-пцuя,
оnределеюия
па
Х.
Л
е
м
м
а
2.
Пусть
~
-
воарастающая
па
У
;
числовая
ФУllщия;
тогда
-притерии
/ =
(/1'
/2,
...
,
/т)
и
/'
=
(/1,
/2,
...
...
,
/;-1'
~(/;),
/i+I,
...
,
1т)
э-пвивалеnтnы
no.t.
и
ПО
;::.
Л
е
м: м:
а
3.
Если
СР(УI,
У2,
••• ,
Ут)
-
nii;бывающая
по
~
(воарастающая
ПО
»
па
У
числовая
фУll-пция,
то
-при
терии
1=(/1,
/2,
...
,
1т)
и
f'
=
(/1,
...
,
/т,
CP(/l,
...
,
1т))
эnвивалеnтnы
ПО
::.
(по
;:::').
62
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
(ГЛ.
1
в
справедливости
этих
лемм
легко
убедиться,
исходя
непосредственно
из
определений
отношений
';::.1
и
:::
j'
До
кажем,
например,
лемму
3.
Пусть
/(х)
;;;:::
/(х').
Если
<р
-
неубывающая
по
>
функ
ция,
то
при
этом
<р(/(х»
~
<р(/(х'»,
так
что
(х);;;:::
/'(х').
Если
же
/(х)
>
/(х')
и
<р
возрастает
по
>,
то
<р(/(х»
>
>
<р(/(х'»,
и
поэтому
также
(х)
>
/'(х').
Пусть
теперь
j'(x);;;:::
(х').
Тогда
/(х)
~
/(х').
А
если
j'(x)
>
/'(х'),
то
/(х)
>
/(х'),
•
Лемма
1
показывает,
что
если
была
устаповлена
экви
валентность
критериев
/1
1I
/2,
а
затем
оказалось,
что
мно
гокритериальная
модель
принятия
решенпй
неадеIшатна
реальной
проблемной
ситуации
и
необходимо
добавить
еще
один
или
неСIЮЛЬRО
частных
иритериев,
Iюторые
так
же
желательно
маь:симизировать,
то
«расширенпые»
вы,
торпые
иритерии
вновь
окажутся
эквивалентными.
Лемма
2
говорит
о
том,
что
отношения
::1
и
-;:1
не
из
меняются
при
произвольных
монотонных
преобразованиях
частных
критериев,
ПраI\тически
это
означает,
что
отно-
шения
~/!
::'1
и
~I
(а
потому
и
множества
Р/Х)
и
S/X»
можно
вводить
в
любых
многонритериальпых
задачах
максимизации
ка"
с
количественными,
та"
и
с
качествен
ными
критериями
(т.
е.
допустимо,
чтобы
ШI\аЛЫ
частных
иритериев
были
всего
лишь
порядновыми).
Монотонные
преобразования
можно
использовать
и
для
приведения
частных
I\ритериев
I\
БОJIее
удобному
виду,
облегчающему
анализ
задачи и
построение
множеств
Р/Х),
Sj(X).
Например,
I\ритерпй
/;
(х)
=ех
р
[
-
i~1(Xj)2]
не
является
вогпутым
на
ЕП,
'по
его
можно
заменить на
n
вогнутую
фУНIщию
-
~(xj)2~TaK
нак
функция
ln t
возра~
;=1
стает
на
(О,
+(0»,
Критерий
/i(X)
=
-ls(x)l,
где
~
-
диф.
ференцируемая
функция,
терпит
(шзлою>
при
s(x)
=
О,
но
вместо
него
можно
использовать
глаДI\УЮ
функцию
_~2(x)
(ибо
_t
2
возрастает
па
(-00,
О]).
Отметим
еще,
что
любой
I\ритерпй
/;
можно
замеППТlJ
на
k/i+l
(где
k>O),
a
l
;
(а>
1),
b-
t
,
(О<Ь<
1)
или
па
ft.
(с
-
нечетное
положительпое
число).
Если
критерий
§ 1.8]
ЭНВИВАЛЕНТНЫЕ
ВЕНТОРНЫЕ
НРИТЕРИИ
GЗ
11
положителен
на
Х,
то
вместо
него
можно
взять
П(а.>
>
О),
-1/11
или
log~I!(~
>
1),
а
неотрицательный
критерий
11
можно
преобразовать
в
tr
(f1
>
О).
'Указанные
преобра
зования
плодотворно
применяются
к
критериям
в
обыч
ных
экстремальных
задачах,
Для
практичеСI\ОГО
использования
леммы
3
(и
других
утверждений,
в
которых
говорится
о
неубывающих
и
ВО3-
растающих
по
;;::;:
или
>
фушщиях
*»
полезной
оказы
вается
Л
е
м
м
а
4.
Если
фУluщия
ер(у"
У2,
""
Ут)
оnределеnа
па
z.....:..
Z,
Х
.,
,
Х
Zт
s;;
Ет
и
является
nеубывающей
по
каждой
nере,м,еnной
У;
(возрастающей
по
каждой
nере,м,еn
пай
YI;
nеубыва1Ощей
по
каждой
и
возрастающей
хотя
бы
по
одnой
nере,м,еnн.оЙ
У/)
при
любых
фиксироваnnых
зnа
чеnиях
остальnых
nере,м,еnн.ых
У}
Е
Zj,
то
оnа
является
nеубывающей
по
>
и
>
(возрастающей
по
~;
возраста
ющей
по
».
Действительно,
если
У
б;
у'
и
ер
не
убывает
по
каждой
переменной
Yi,
то
ер
(у)
>
ер
(y~,
У2'
• , "
Ym»ep(y~,
y~,
...
,
Уm»
..
,
>ер
(у'),.
откуда
ер(у)
б;
ер(у'),
Если
У
>у',
а
ер
возрастает
по
каж
дой
перемешlOЙ
У/,
то
в
цепочке
перавенств
для
ер
хотя
бы
один
раз
встретится
>,
и
в
итоге
будет
ер(у)
>
ер(у'),
Нан:онец,
если
у>
у',
а
ер
не
убывает
по
I,аждой
перемен
ной
у;
и
возрастает
хотя
бы
по
одной
Yi,
то В
этой
цепоч
ке
опять
хотя
бы
один
раз
встретится
>,
и
по;этому
ер(у)
>
ер(у').
•
Например,
лемма
4
показывает,
что
фушщия
ер
(У)=
т
=
~
~tiYi,
где
все
f11
б;
О,
НО хотя
бы
одпо
f1i>
О
(и,
в
част-
i=l
ности,
функция
ер(у)
=
у),
является
неубывающей
по
>
и
возрастающей
по
>
на
Еm.
Следовательно,
учитывая
лемму
3,
при
построепии
множеств
Р,(Х)
и
Sj(X)
можно
из
нескольких
повторяющихся
частных
критериев
оста
вить
лишь
один,
и
можно
отбросить
частный
критерий,
являющийся
линейной
комбинацией
с
положительными
*)
Так
как
у
>
у'
влечет
у>
у',
то
функция,
неубывающая
(возрастающая)
по
~,является
неубывающей
(возрастающей)
11
по
>,
64
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
[ГЛ.
t
ноэффпциентами
всех
или
несколы\Их
остаJIЬНЫХ
крите
риев.
При
м
е
ч
а
н и
е.
Интересным
является
вопрос
о
том,
в
какой
мере
достаточные
условия,
указанные
в
лемме
4,
ЯВЛЯЮТСЯ
и
необходимыми.
Легко
видеть,
что
если
ер(у)
-
неубывающая
по
:>
фупнция
на
Z =
ZI
Х.,.
Х
Zm,
ТО
она
не
убывает и
по
каждой
переменной.
Обладает
ли
апаJ[О
ГИЧН~IМ
свойством
ФУНIщпя
ер,
возрастающая
по
>?
Рассмотрим
простой
пример:
т
=
2,
ZI =
Z2
=
{О,
1},
ер(О,
0)=0,
ер(О,
l)=ер(l,
0)=-1,
ер(1,1)
=
1.
Здесь
qI
возрастает
по
>
на
{О,
1}
Х
{О,
Н,
тем
не
менее
по
кащ
дой
переменной
не
является
даже
неубывающеЙ.
Справедливо,
однако,
утверждение
(см.
(77]):
ФУШЩIIЯ
ср,
непрерывная
и
возрастающая
по
>
на
открытом
мно
жестве
Z =
ZI
Х
...
Х
Zm
~
Ет,
является
неубывающей
по
каждой
переменной.
Для
доказательства
допустим,
что
утверждение
невер-
,
"Z
I
11
,
11
но,
так
что
найдутся
тзкиеу,
у
Е
,ЧТОУi>Уj,
Yi
=
Ур
i =
1,
2,
"',
т;
i
=t=
j,
однаI\О
8 =
ер(у")
-
ер(У'»
о.
Возь-
мем
такое
достаточно
малое
б>
о,
чтобы
у
6
=
(У:
+
б
t
••
,
... ,
y~+
б)
Е
z
и
ер
(у
6
)
-
ер
(yl) <
8.
Тогда
ер(у6)
_
ер(у")
~
:::
I
ер(у6)
-
ер(у')
I +
<р(У')
-
ер(у")
< 8 - 8 =
О.
Следовательно,
ер(у6)
<
ер(у"),
хотя
уб
>
у",
а
это
протпво
речит
предположению
о
том,
что
ер
возрастает
по
>.
•
2.
Легко
убедиться
в
том,
что
определение
эффектив
пой
последовательности
адекватно
при
возрастающих
не
прерывных
преобраЗОilаниях
нритериев.
Это
объяспяетсл:
I
тем,
что
в
указанном
определении
по
существу
пспользу-
ется
топологическое
попятие
онрестности
ТОЧI<И
в
I<рите
риальном
пространстве.
3.
Определения
собственно
и
подлинно
эффентивных
решений
связаны
с
конфигурацией
множества
ДОПУСТИМЫХ
оцеНОI<.
Поэтому
эти
определения,
нан
нетрудно
прове
рить,
аденватны
при
аффинных
положительных
преобра
зованиях
нритериев
(при
умножении
на
положительное
число
и
прибавленни
нонстанты).
Следовательно,
понятнл:
собственно
и
подлинно
эффективных
решений
имеет
смысл
использовать
лишь
в
тех
задачах,
в
I<ОТОРЫХ
все
критерии
являются
количественными,
ГЛАВА
2
УСЛОВИЯ
ОПТИМАЛЬНОСТИ
в
этой
главе
в
Зlшпсrшостп
от
CBoiicTB
1\рптерпев
и
структуры
мпожества
допустпмых
решений
формулиру
ются
различпоrо
рода
пеоБХОДЮIЫО
и
достаточные
условиа
того,
чтобы
данное
решение
или
данная
оцеlша
были
6
ТОМ
ПЛИ
ином
смысле
ОПТIПlаЛЫIЫМП
(зффектпвнымп).
I\ю{
и
В
обычных
;)J\стрс~IaлыIхx
задачах,
знанпе
условий
ОLIтпмальности
позволяет
разрабатывать
методы
отысна
ШIЯ
ЭффСI\ТПВНЫХ
решеппй
и
способы
проверн:и
эффек
Тlшностп
выделенного
РСIПенпя.
I\poMe
того,
ЭТИ
УСЛОВШI
ПОЗВОЛЯЮТ
глубже
ПОIIНТЬ
нрнроду
II
взапмосвязъ
различ
ного
тппа
эффеНТИВlIЫХ
решений,
а
также
IIсследовать
СТРУI\ТУРУ
и
свойства
множеств
эффеитивных
решений
II
оценок.
Учптывая
взапмосвязь
различных
ПОlIятпil:
эффентпв
ПОСТII,
схематпчесни
представлеппую
па
рис.
1.14,
следует
IHIC1'},
в
виду,
что
условия,
являющпеся
достаточными
ДШI
зффеIПИВНОСТП
в
пеI,ОТОРОМ
уr,аааппом
смысле, оказыва
lOтся
достаточными
н
для
ЭффСИТНВПОСТIl
В
более
широ
J\OM
смысле.
И
наоборот,
УСЛОВIIЯ,
явлшощиеся
необходп
~[ымп
для
эффеНТlIВIIОСТII
в
установленном
смысле,
оказы
ваются
необходпмымп
для
эффеRТПВПОСТП
в
более
узном
смысле.
IIапрпмер,
условне,
достаточное
д:ш
собственной
зффеКТIIВНОСТII,
будет
достаточным
для
всех
трех
другпх
ТIIПОВ
эффеI\ТПВНОСТII,
включая
слабую.
А
условие,
пеоб
ХО;:(IIМОС
дЛЯ
слабой
эффеНТIIВПОСТII,
будет
пеоБХОДIIМЫМ
и
;~JIЯ
всех
остаJIЬПЫХ
трех
ТIIПОВ
эффеКТIIВIIОСТIТ,
в
том
чис
Jle
п
для
собственной.
В
первом
параграфе
Г.'Iавы
устапаВJIIIВаlOТСЯ
услоВIШ
оптпыалыIOСТП
ДJIЯ
общего
случая,
т.
е.
без
I.юшх-либо
ограППЧIlтельпых
предно.'Iо;r,еlшii
о
CTPYI,Type
множества
J\ОПУСПIЫЫХ
решенпi1
Il
свойствах
венторпого
ирптерия.
В
JJослеДУЮЩIIХ
пяти
параграфах
рассматрпваются
МlIО
гонрптерпальпые
задачп
разлпчпых
I\лассов
(вогнутые,
.1"lIнеЙные
и
т.
д.),
II
для
НИХ при
водятся
более
содержа-
5
в.
В.
Подиновсниi!,
В.
д.
lIогиц
66
~'СЛОВИЯ
ОПТИМАЛЬНОСТИ
(ГЛ
2
тельные
условия
ОПТIlмаЛLНQСТII.
Прп
до}~азательстве
этпх
условий
оптимальности
широко
ИСПОJIЬЗУЮТСЯ
теоремы
об
альтернативе
ДJIЯ
систем
шшейных
и
вогпутых
нера
венств.
Последний,
седьмой,
параграф
посвящен
обсуждо
нию
свойств
эффеИТJIВНЫХ
последовательностей.
Посиольиу
в
этой
и
всех
последующих
главах
прово
дится
чисто
анаЛlIтическое
исследование
МНОГОI\ритерп
альных
задач,
формальпая
постановиа
и
содержательный
смЫсл
иоторых
были
иодробно
разобраны
в
главе
1,
то
далее
ШИРОI\Q
используется
11
общематематичеСI\ая
тер
мииология:
решения
11
их
оцеиии
часто
называются
точ
камй
соответствующих
множеств
(Х·
и
У),
иритерии
!,
~
функциями
и
т.
11,
§ 2.1.
Общие
УCJI"ОВИII
оптимальности
Здесь
J'стаиавли'Ваются
условшг
оптималь:ности
без
кг:
ких·либо
существепных
предположений
-относительно
струитуры
множества
допустимых
решений
Х
и
свойств
заданной
па
нем
вектор-функции
/ =
(/\,
/2,
...
,
1т).
Мно
гие
из
этих
условий
оптимальности
являются
переформу
лировкаМII
или
(<почти
переформулировиамш>
введенных
в'
главе
1
различных
определений
эффеитивности.
Для
простоты
и
наглядности
изложения
вначале
рассматрива
ются
условия
эффективности
применительно
и
оценкам,
а
затем
показывается,
что
полученные
результаты
легко
trереносятся
и на
решения.
1.
Начнем
с
рассмотрепия
свойств
слабо
эффеI\ТИВНЫХ
оценок.
т
е
о
р
е
м
а
1
(Гермейер).
Предположим,
что
уО
Е
У
u
все
уУ
>
О.
Оценуm
уО
слабо
эффе~тuв1tа
тогда
u
ТОЛЪ~О
тогда,
"огда
существует
вe~TOp
f..t
Е:М
Ta~oй,
ЧТО
(1)
Для
слабо
эффе"Тllвnой
oцeH~lI,
уО
Е
У
JotoЖnО
nрu1tять
f..t
=
f..t
0
,
где
f..t
0
Е
:м
-
вe~TOp
с
,.олmо1tента.'Щ
(2)
§
21)
11
тогда
ОБЩИЕ
УСЛОВИЯ
ОПТИМАЛЬНОСТИ
тах
min
f1fYi
=
'),0,.
IIЕУ
{ЕМ
67
Напомним,
что
М
-
это
множество
векторов
из
Ет
с
положительными
компонентами,
в
сумме
равными
единице.
Доказательство.
Из
равенства
(1)
следует,
что
для
любого
у
е
У
существует
номер
i
е
М
такой,
что
y~
> Yi.
Поэтому
условия
(1)
достаточно
для
слабой
эффеи
тивности
уО.
Доиажем
необходимость.
Для
этого
возьмем
веитор
f1
0
е
М
с
иомпопентами,
определяемыми
формула
ми
(2).
Из
yOeS(Y)
следует,
что
для
каждого
уеУ
су
ществует
j
е
М,
при
I\OTOPOM
выполняется
неравенство
у']
>%
а
значит,
и
неравенство
f11y~
>
f1~Yi'
Поэтому
f1~y1
=
1,0
= min
f1Yyf
> min
f1~Yi
••
{ЕМ
iell1
Геометрически
совершенпо
очевидно, что
уО
е
S(Y)
тогда
и
толыю
тогда,
Iюгда
во
внутрепность
ортанта
E~
,
транслированного
(сдвппутого)
в
точку
уО,
не
попадмт
,
РИС.
1.
ни
одна
точка
из
У
(см.
рис.
1).
ПОСI{ОЛЬКУ
гиперповерх
ность
min
!1Ш!
=
'),
:при
А
'=
Ой'
п(\ложите~ь'ПыХ
f1'
пред-
ie!l'
"
'.
,
ставляет
собой
границу
этого
же
ортанта,
трансляцию
Иоторого
в
уО
можно
осуществить
назначением
подходя
щих
значений
параметров
Jt,
>
о
и
')"
то
появляется
воз
МОжность
сформулированный
геометричесиий
фаит
выра-
5"
(j8
~'С:IOВПfI
UПТИМ.ШЫIOспI
[1';1.
2
ЗIIТЬ
В
терминах
фУШЩПIJ
min
~t,y,.
Эта
возможность
II
iElIl
реаШI30вана
в
Teope~fe
1.
Полезным
обобщеппе~1
теоремы
1
является
т
е
о
р
еы
а
2.
Пусть
у"
Е
У,
а
~i,
i =
1,
2,
...
,
m,-
во.3-
растающuе
фующиu
одной
nepellleHHou,
nричеJt
~1
(y~)
==
=
~2
(y~)
= . " =
~7JI
(y~).
ОцеН1>а
уО
слабо
эффективна
тогда
и
только
тогда,
1>огда
~l(Y~)
=
тах
min
~,
(у.).
(3)
уЕУ
iEM
ДOl~азательство
апаЛОГlIЧIIО
данному
выше
для
теоре
мы
1.
Иа
(3)
для
JIlобого
у
Е
У
I10Jlучаем,
что
при
некото-
ром
i
Е
111
верпо
~;
(у?):?:
~;
(Yi),
а
потому
и
y~>
Yi,
так
что
yOES(Y).
Наоборот,
еСiIП
yOES(Y),
то
для
I\аЖДОГО
уЕ
У
найдется
~
Е
л1
тшшii,
что!/?
> !/i,
oТl,yдa
~;
(rЛ)
>~;
(у,).
ПОЭТО~IУ
С
учеТО~1
равепстu
~1
(у7)
"'"-'
~2
(y~)
=
...
=
~m
(y~~,)
мо;rаю
заппсать
Подбнрая
фушщпн
~,
ТОГО
илп
иного
подходящего
BrI-
да,
МОJIШО
получат!"
соответствующие
r,ОIшретизацпп
ра-
венства
(3).
Напрнмер,
еслп
уО
Е
Е';,
то,
ПОЛО'hИВ
~;
(Yi)=-~
=
~?Yi,
где
f.t~
определяются
формулой
(2),
приходим
"
теореме
1.
Если
же
принять
~;
(Yi) =
У;
-
У?,
то
получим
С
л
е
Д
с т
в
и
е
1.
Оцеnка
у"
Е
У
слабо
эффективна
10';-
да
и тол
Ь1>О
тогда,
когда
тах
min (Yi -
у?)
=
о.
уЕ
У
'ЕМ
Непосредствешю
нз
леммы
1.2.2
вытеI\ает
следующее
утверждение.
т
е
о
р
е
м
а
3.
Если
фуnкция
ср(у)
во.3растает
по
>
на
У,
то
любая
ее
точка
.наКСН.ну.1Ш
на
У
слабо
эффен
тивн.а.
Прпмерами
функций,
возрастающих
по
>
на
Еm,
слу
жат
miп
~,(y.)
и
тах
~,(Y,),
где все
~,-
возрастаЮЩllе
iEM
iE1I1
на
Е
фушщии
(напрпмер,
упомшraвшиеся
выше
~;
=
У,-
-
y~;
~.
=
f.t.Yi
прн
~t.
>
О).
Возрастающей
по
>
па
Е'"
является
фУШЩIIЯ
ср(у)=
YJ'
где
j -
ПРОil3ВОЛЬПЫЙ
фш~сп-
~
2 1 J
ОБЩИЕ
~'СJIOJШН
ОПТИ:\I"\;IЫIOСПl
6()
ропаПlIЫЙ
номер
из
М.
По
теореме
3
все
точип
мar,СШlуыа
на
У
указанных
фушщш!
слабо
эффеIПИВНЫ.
ОВIетим
еще, что
фушщпп
miп
~t,
(У:
-
У,)
и
тах
~i
(у7
-
Yi)1
где
iElI1
;
Е
111
У*
Е
Еm,
~t,
>
О,
являются
убывающимп
по
>
на
Е"',
11
поэтому
точии
их
минимума
па
У
слабо
эффективны.
Используя
полученные
пыше
результаты
II
строя
ПО;J:
множества
множества
У,
замкнутые
сверху
по
>
ОТНОСII
телыro
У
(например,
нрп
помощи
лемм
1.2.3
и
1.2.4,),
можно
rroЛУ'IiJ.ТЬ
новые
условия
слабой
эффеитивностп.
Приведем
здесь
лпшь
одно
IIЗ
оБЩIIХ
утверждений
подоб
ного
рода.
т
е о
р
е
м
а
4.
Пусть
еро
-
возрастающая
по
>,
а
ер]!
j =
'1,
2,
...
,
р,-
неу6ывающuе
по
>
на
У
фующиu.
ЕСЛ'l
OI/eHna
уО
Е
Z,
где
Z =
{у
Е
YlepJ(Y)
;:::::
t
J
,
j =
1,
2,
...
,
р},
(4.)
а
t
J
-
nроuзвольные
ФllnСllроваnные
числа,
удовлетворяет
условию
(5)
то
она
слабо
эффеnтuвна.
Д
о
и
а
з
а т
е
л
ь
с т
в
о.
По
теореме
3
точиа
уО
слабо
эффеюпппа
отпосительно
Z.
Согдасно
леммам
1.2.3
и
1.2.4
МIIOFI,естпо
Z
ЗЮШIIУТО
сперху по
>
относительно
У.
Jlоэтому,
I\aK
пон:азывает
лемма
1.2.5,
уО
Е
S(Y).
•
При
м
е
р
1.
Пусть
j
Е
М,
N
~
111
и
ТОЧI{а
уО
Е
У
удоплетворяет
перавенствам
У?
> t
i
,
i Е
N.
Если
о
Yj
= maxYj,
yEZ
где
Z =
{у
Е
У
1
у,
;:::::
t,
для
всех
i
Е
N},
то,
согласно
тео
pe:\Ie
4,
уО
Е
S(
У).
Заметим,
что
еслп
N =
rz;,
то
Z =
У.
Прппедем
еще
однн
результат,
харан:теризующпй:
c:ra-
бо
эффеl{тивные
точки.
Если
фующuя
ер(у)
возрастает
по
>
на
l>t1l0жестве
Z'={YEYly=yO
ила
у>уО},
то
оценnа
уОЕ}'
слабо
эффеl'iТllвна
тогда
n
толъnо
тогда,
Nогда
(Г
(уО)
=
тах
(р
(у).
UE.Z'
70
УСЛОDШI
ОПТИМАЛЬНОСТИ
[ГЛ
2
в
самом
доле,
если
уО
~
S(Y),
Тат,
ЧТО
дЛЯ
нен.ОТОРОГО
у*
Е
У
справедливо
неравенство
у*
>
уО,
то
у*
Е
Z'
и,
I,pOMe
того,
<Р(У*)
>
<р(уО).
Поэтому
уО
не
может
быть
точ.
коп
макспыума
фушщпи
<р
на
множестве
Z'.
Если
а,е
уО
Е
S(Y),
то
Z'
=
{уО}.
•
2.
Перейдем
1,
рассмотрению
свойств
эффеитивных
оцепок
т
е
о'
р
е
м
а
5
(ПодиноnснпЙ).
Оценnа
уО
Е
У
эффе~
тuвна
тогда
и
тольr.о
тогда,
nогда
для
nаждого
i
Е
И
где
у?
=
maXYi}
IIEyi
(G)
yi=[YEYIYJ>y~,
j=1,2,
...
,m;
j*i}.
(7)
Если
уО
Е
У
эффеnТU6nа,
ТО
оuа
является
едunствеН1l0Й
в
У
точnой,
удовлетворяющей
(6)
при
паждом
i
Е
М.
Д
о
и
а
з
а т е
л
ь
с
т в
о.
Если
для
некоторого
i
е
JJ1
нап
дется
такая
точиа
уЕ
У',
ЧТОУi>УУ'
то,
согласно
(7),
у
>
уО,
тан
что
у
О
~
Р(У).
Ilаоборот,
если
оценка
уО
пе
эффективна,
то
наlЩУТСЛ
номер
i
е
М
и
ТОЧI,а
У
Е
у'
ТaIше,
что
у,
>
у?,
и
тогда
(6)
не
будет
выlIлнлтьсл
•.
Пусть
У
Е
Р(У).
Тогда
для
любой
точки
у'
е
У,
отлич-
ной
от у
О
,
найдется
помер
i
Е
М,
при
котором
у?>
y~.
По
этому'
у'
неЛЬЗiI
подста'Вить
в
(6)
вместо
уО,
•
Для
уО
Е
У
введем
в
рассмотрение
мпожестnIl
У
<О
I
У
I
о.
1 2 .
-L
.}
=
у.
Е
У!
= Yi, 1 = !
t""
т;
J f
~
•
ПОСI\ОЛЬRУ
у(')
s;;
Г,
то
113
теоремы
5
вытеltает
С
л
е
Д
с
т в
и
е
2.
Если
уО
эффеliтuвnа,
ТО
y~
=
тах
Yi
IIЕУ
(i)
для
nаждого
i
ЕМ.
Т
е
о
р
е
м
а
6.
Oцe1l~a
уО
е
У
эффеr.тuвnа
в
ТО.Н
II
ТОJlЫ'О
в
ТО,.,!
случае,
ес.ли
т
тах
~
е!
=
О,
(8)
(у,Е)ЕТ
i=l
где
т
= r
(у,
Е)
Е
У
х
E~
I
у
-
е
=
уО}.
д
о н
а
з
а
т
е
л
ь
с т
в
о.
Если
уО
Е
Р(
У),
то
для
у
Е
У
па
у
~
уО
CJleAyer
у
=
уО,
11
поэтому
Т
=
{(уО,
О,т)}.
Наобо~