Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
ог,ЩИЕ
УСЛОВИЙ
ОПТИl\I.\.1ЫIOСТП
>
о
(yJ
-
у;).
А
таl,
юш
всегда
то
О
~
(т
-
1)
~i
(у,
У:)
t
Л
j
(у,
у
)
81
Просуммировав
последние
т
-1
неравенств,
соответ
ствующих
разпым
j
=F
i,
после
песложных
преобраЗ0ва
ниi:i
получим
m
~
Лi
(у,
уО)
(У!
-
yr)
>
OJ
i=1
Б
силу
(17)
отсюда
следует
ер(у)
>
ер(уО),
а
это
противоре
чит
условию,
что
уО
-
ТОЧI{а
МaI{симума
ер
на
У.
•
При
м
е
р
9.
Пусть
в
УХ
=
У
1
Х
У
2
Х
...
Х
У
т
все
У,
Jlнтервалы
(конечные
или
бесконечные).
ПреДПОЛОЖЮI,
что
фУНКЦИЯ
ер
определена
II
непрерывна
на
УХ
II
длн
ЕЮI\ДОГО
i
Е
111
имеет
на
УП)
= Y
1
Х
•••
Х
Y
i
-
1
Х
int
Y
i
Х
Y
i
+1
Х
•..
Х
У
т
Drp
(у)
непрерывную
частпую
ПРОIl3ВОДIТУЮ
-{)_о
-,
удовлетворяю
У;
щую
условию
Ь
;
~
д(р(у)/ду;
~
а;
>
О.
По
известноi:i
из
анаШJза
формуле
конечных
прпра
щений
при
у'
=F
у"
ер
(у')
_
ер
(у")
=
~
D~~:i)
(у:
_
у;)'
, "
где
суммирование
ведется
по
тем
i,
для
!{оторых
Yi
=1=
Yi,·
о
Х
И
z'
Е
Ут.
ТаЮIМ
образом,
ФУШЩIlЯ
ер
удовлетворяет
условию
(17),
где
j
tI(P
(z/)
-.
-
при
У'
-=F
у""
'.;
(у',
у")
=
ау
i
о
i =
1,
2,
..
" m.
а;
при
у'
=
у",
Следовательно,
все
ее
ТОЧТ\IJ
ЫaJ,СЮIУ~Iа
на
У
s::;
ух
вхо
ДЯТ
в
С(
У).
6
в. В.
ПО;j;шовсюrЙ.
В.
Д.
Ногин
82
Условия
ОПТИМ.\ЛЫlOСТИ
[гл.
2
в
чаСТНОСТlI,
если
т
ух
=
II(ci,
d
i
),
где
+00
> d
i
>
С;
>
О,
i=l
i
Е
М,
то
любая
точна
мансимума
фуннции
ер
(у)
=
= (
~
~tiY:)
1/8,
где
s
=1=
О
и
!li>
О,
собственно
эффентивна.
1=1
!Сроме
того,
еСЛII
у*
>
(d
1
,
•••
,
d
т
),
то
любая
точна
мини-
мума
на
У
фупнции
ер
(у*
-
у)
= [
I~!li
(у:
-
Yi)8
т/а
яв
ляется
собственно
эффентивной
[158].
Заметим,
что
требование
(18)
в
теореме
13
и
анало
гичное
требование
в
примере
9
существенны.
Пример
10.
Пусть
ух=
[О,
1)2,
У
=
{у
Е
ЕЧ
Yi
+
y~~
11.
ТОЧI\И
у*
=
(О,
1)
и
уО
=
(1,
О)
эффеI{тивны:;iо
являются
несобственно
эффентивными.
Нетрудно
прове'
у
v--
рпть,
что
фующия
ер
(у)
= 2 1 - 1 -
y~
непрерывна
на
ух,
имеет
непрерывную
частную
пропзводную
arpa
(у)
=
2
У1
Х
У!
Х
ln
2
на
Уа)
=
(О,
1)
х
[О,
1],
непрерывную
частную
НРОIIЗВОДНУЮ
arpa
(у)
=
У2
(1-
y~)-1/2
на
YG>
=
[О,
1]
х
(О,
1)
У2
И
достигает
на
У
наибольшего
значения,
равного
1,
в
двух
ТОЧI{ах
-
несобственно
эффеНТIIВНЫХ
ТОЧI{ах
у*
и
уО.
'Га
Iюе
положение
объясняется
тем,
что
частная
производная
дср(у)/аУ2
не
удовлетворяет
соответствующпм
неравенст
I1ам,
тан
нан
1
·
и2
О
l'
У2
+
1т
=,
1т
=
00.
112->+0
V 1 -
Y~
1/2->1-0
V 1 -
Y~
'У'читывая
примечание
2,
а
таюне
тот
фант,
что
уО
Е
Е
S(
у)
тогда
и
толыш
тогда,
I1:0гда
для
любого
у
Е
У
существует
номер
i
Е
М
ТaIЮЙ,
что
уУ
>
Yi
(этот
факт
вытенает
из
определения
слабой
Эффel{ТИВНОСТИ),
из
тео
ремы
12
ПОJIучаем
следующий
результат.
Т
е
о
р
е
м
а
14.
Для
того
чтобы
оце1lnа
уО
Е
У
была
собствеllnО
эффеnтивnой,
llеобхоаи
..
,1,О
и
достаТОЧ1l0,
чтобы
существовало
е>
О,
при
nотором
точка
уО
слабо
аффеn
тивnа
по
веКТОР-фУllnции
«!l\
у>,
<~tz,
у),
...
,
<!lm,
у»
(гае
веnто
ры
~ti
Е
М
U.~tеют
ви{)
(14»
ОТIlоситеЛЬ1l0
.},t1tо
жества
У.
§ 2.IJ
ОБЩИЕ
УСЛОВИiI
ОПТИМЛЛЬНОСТП
83
Имея
в
распоряжении
условия
слабой
эффeItТНВНОСТИ,
при
помощи
теоремы
14
можно
легко
получить
условия
собственной
эффективности.
Это
соображение
будет
ис·
lIользоваться
в
последующих
параграфах
при
выводе
ус·
ловий
собственной
эффективности
для
различных
RJIaCCOB
МНОГОRритериальных
задач.
Первым
результатом
TaRoro
использования
теоремы
14
(и
теоремы
1)
является
С
л
е
Д
с т в
и
е
6.
Пусть
уО
>
О(т).
В,.,л,юченuе
уО
Е
G(
У)
Zl.1leeT
.место
тогда
и
то.лы;,о
тогда,
1>огда
существует
е
>
О
та1>ое,
что
равенство
(в
"оторолt
J.Li
и.меет
вид
(14»
выполняется
при
llе1>ОТОРО.1!
л
=
(ЛI,
Л2,
••.
,
Л
m
)
Е
М.
Теорема
14
позволяет
таюке
переформулпровать
опре
деление
собственно
эффеl\ТИВIIОЙ
оценки
так,
что
оно
становится
геомотричеСIШ
наглядным.
Введем
для
этого
1I0лиэдральный
:конус
Л.={ZЕЕml<f..t\
z);;;::O,
i=1,
2,
"',
т},
Здесь
nекторы
f..t{
имеют
вид
(14'>
11
О
<
е
::;;;
11т
(если
е
=
=
11т,
то
J.Lt
=
J.L2
=
...
=
f..tm),
тю{
что
f..tl
ЕМ.
Нетрудно
про
верить,
что
при
умеПLшеНIIИ
е
:конус
А.
«сужаетсЯ»,
т.
е.
если
11т
>е>
е,
то
Аё::::>
Ав
(более
того,
int
Аё::::>
:=J
[Ae,\{O(m)}J).
В
самом
деле,
пусть
f..tl
-
векторы
вида
(14),
а
~c
-
таIш\е
векторы
впда
(14),
где
вместо
е
фигу.
рирует
8.
Возьмем
ПРОIlЗВОЛЬНУЮ
точ:ку
Z
Е
А.
и
дона·
тем,
что
z
Е
А
•.
Включение
Z
Е
А.
означает,
что
Z
удов·
лстворяет
системе
линейных
нераnепств
(f..t
f
,
z>
~
О,
i =
1,
2,
••
"
т.
ЕСЛII
ё
=
11т,
то,
суммируя
выписанные
неравенства
n
умножая
результат
на
11т,
получим
т
f
~
-'
т
~
Zj
=
(f..tl.f
z)
>
O~
;'=1
i =
1,
2"
..
','
m~
что
означает
z
Е
Л
е
.
Если
ё
<
11т,
то
введем
некто·
ры
л',
л
3,
•••
,
л
т,
номионепты
I\OTOPЬYX
положительны
6*
УС."'Iовия
оптш.[
;':1ЬНОСТИ
[Г.'1
Z
и
опреде:rяются
следующиы
образоы:
~
'=12
...
,т;
j
=1=
i,
f
-
I 1
--
те'
1
.,
''л
J
= ( -
i =
1,
2,
"',
m.
1.-(m-l)e-g
l-т/:'
,
j = i,
ЛеГI\О
провериТI,
справемшIВОСТЬ
равенств
i =
1,2,
"',
m.
ПОЭТОМУ,
умноя,ая
неравепство
<1-1/,
z)
б;
о
на
полоil'\И
тельное
число
л~
II
суммпруя
ПО
j =
1,
2,
...
,
т,
получим
т
~
1'~<[1i,
z)
=
<~i,
z»O.
э=1
Это неравенство верно
д:ш
любого
i =
1,
2,
...
,
m.
Следо
вательно,
z
ЕЛЕ'
В
тон
с"'учас,
J.Oгда
:;6
С\,\{О(",,}]
И
11m>ё>е,
по
нрапней
~fepe
оп~о
пз
перавенсгв
<[1',
z>
б;
О,
i =
=
1,
2,
...
,
т,
будет
страгЮI
n Yl\a;;aHHOe
выше
су~.ши
рованпе
будет
приводпть
к
строт
ШI
неравенстваи
<~',
z)
>
О,
i =
1,2,
..
" m
t
которые
означают,
чго
z
Е
int
.\:.
11
Ответим
таЮI·е
еще
O!JHO
СВОЙС1ВО
BBeneHForo
I\оиуса
.\.:
в
преде.lе
при
е
->-
О
БОНУС
Л
О
будет
представ.:JЯТЬ
собой
неотрицатсльный
ОР1аПГ
E~
(сы.
рпс.
2).
Т
е
о
р
е
и
а
13.
Оценка
y~
Е
JГ
собственно
эффе,;ruвна
в
ТО.Ч
и
ТОЛЬКО
ТОЛ
случае,
сели
существуеr
е>
О,
при
liOTOpO."It
(20)
д
о
R
а
а
а
т е
л
ь
с
т
в
о.
Не
ограничивая
общности,
бу
дем
считать,
что
уО
=
О(т).
Пусть
О(m)
Е
С(
у).
Согдасно
теореме
14
существует
с
>
О,
прп
I\ОТОРОЫ
систс~rа
не
равенств
<11',
у>
>
О,
~=1,
2,
...
,
т,
(21)
§ 2 ! ]
ОБЩИЕ
УСПОЕIН
ОПТИ'I
~
'1ЫIOСТП
1'5
где
Lt
l
вида
(14),
не
имеет
решенип
на
мноа;естве
У,
т.
е.
у
n int
А.
=
!О.
Тогда
ДЛЯ
с'
<
е
будет
выполнено
равен
ство
(20)
(при
е
=
е'
>
О).
Обратио, пусть
выполнено
(20).
Тогда
CRCTe7lIa
не
р[шспств
(21)
песовместна
на
У,
оп,уда
согласно
теореме
14
Быт('кает
О(ln)
Е
С(
У)
.•
ГеометрпчеСJ{ая
пптернрет,щпя
теореыы
15
в
случае
т
= 2
прпведепа
:на
рис.
2.
В
равенстве
(20)
хо
ронlO
просма
трпваетсн
слязь
понятпlI
эффек
тпвности
и
собствепной
:JффСЮIIВНОСТИ:
в
пре
деле
при
е
-+
О
это
ра
венство
будет
опреде
.'1ять
эффеюивную
ОЦeIШУ
уО.
При
м
е
ч а
п
и
е
3.
IJ
работе
[58]
(см.
тю;
;1<е
[96])
бьшо
введено
понятпе
М-регулярно-
Рие.
2.
сти.
Последняя
теорема
показывает,
что
это
понятие
равносильно
понятию
собственной
эффектив
НОСТII.
При
М
е
ч
а
н п
е
4.
Еще
о!!ну
перефорнулпроы;у
соб
ственно
эффентпвного
решения,
ноторая
отличается
от
прпведенной
в
теореме
15,
МОiБНО
найти
в
[112].
С
помощью
теоремы
15
МОiБНО
установить,
прп
каких
условиях
IIIноа;ества
подлинно
эффективных
и
собствен
rro
эффеRТИВНЫХ
оценон
совпадают.
т
е
о
р
е
м
а
16.
Предnоложu.ч,
что
.Шlожество
У
аа.""-"'
I-/УТО
и
существует
вектор
~t
Е
1\Т,
длл
которого
справедли
во
1lераве1lство
<r-t,
у>
~ const
алл
всех
у
Е
У.
Тогда
С(У)
=В(У).
Д
о
R
а
з
а
т
е
л
ь
с т в
о.
В!.люченпе
С(
У)
!:
В(
У)
было
донааано
в
теореме
1.6.1.
Докажем
обратное
ВRлючеНIIе.
Пусть
уО
Е
В(
У).
Не
ограничивая
общности,
положим
у
О
=
О(m).
86
ус:ювия
ОПТИМ.\ЛЬНОСТII
(ГЛ
3
Предположим,
что
оценн:а
О(т)
не
является
собствен
по
эффективной
(заметим,
что
в
силу
О(m)
Е
В(У)
эта
оценка
эффективна).
В
этом
случае
согласно
теореме
15
найдутся
последовательности
чисел
{8
в
}
и
точек
{yk}
та
кие,
что
8"
-+-
+0
и
(22)
IIачиная
с
неноторого
номера
k
(его
всегда
можно
считать
равпым
едипице),
стапет
справедливым
равеп
ство
т
/-1
=
~
Л
1
/-1i
при
некоторых
1..1>
О,
i =
1,2,
...
,
т,
1=1
где
/-1'
вида
(14)
с
8 = 8,
И
8, >
еА
для
всех
k =
2,
3,
...
Отсюда
следует,
что
система
линейных
неравенств
Ау
>
>
O(ffi+l)
(где
А
-
матрица
размера
(т
+
1)
х
т,
СТРОI{Ю\Ш
которой
являются
векторы
p,l,
p,z,
... ,
р,"',
-р,)
не
имеет
решения
(это
легко
проверить
рассуждением
«от
против
ного»).
Следовательно
(см.
теорему
8.4
из
[93),
мно-
жество
Ар!
n
{У
I
(/-1,
у)
< const} =
Аl
RО1\шаюно.
Поэтому
последовательность
{yk}
огранпчена
и
ее
можпо
считать
сходящейся:
liш
у"
=
у*.
БЛaIодаря
замкнутости
множества
У
имеем
у*
Е
У.
Вспоминая
оиределение
конуса
Ав",
УСJIовие
yk
Е
Aeh
можно
записать
подробно:
(1
-
(т
-
1)
8п)
y~
+
ekY~
+ ... +
ekY~
>
О,
eпY~
+
(1
-
(т
-
1)
8п)
y~
+ ... +
8"y~
>
О,
(23)
e"y~
+
eпY~
+ ... +
(1
-
(т
-
1)
8/,)
y~
>
О.
Так
как
ПОСJIедовательность
{у"}
ограппчена,
то
огранп
ченными
ЯВЛЯЮтся
и
все
последовательности
{y~I;'=
1,
t =
1,
2,
•..
, m.
Поэтому,
переходя
в
нсравепствах
(23)
1\
пределу
при
k -+-
00,
получим
у*
~
О(т).
Неравенство
у*
>
О(т)
противоречит
ВJ{лючению
О(т)
е
Е
jJ(
У),
по;)тому
пусть
у*
=
О(т).
Возьмем
послеДQватель-
§
~
11
ОБЩИЕ
Условия
ОПТИМАЛЬНОСТИ
87
НОСТЬ
7.
-=
1,
2,
..
, (24)
в
сплу
(22)
I!ykll>
О
для
любого
k,
и
поэтому
определе
ппе
последовательности
{w
k
}
Rорреитно.
Члепы
этой
по
следовательности
принадлеiI\ат
еДIIНИЧНОМУ
заМIШУТОМУ
шару,
следовательно,
ее
можно
считать
сходящейся:
Нт
(lj"
=
ы.
COfJIaCHO
определению
Rасательного
нонуса,
Я-Н'"
прпведенного
в
§ 1.6,
(Ij
Е
Т
(У
-
Е:;,
О(m)).
Поделив
все
неравенства
снстемы
(23)
па
11y
k
ll
II
принав
во
внимание
оцеПRИ
1
y~
/~
у"
111<
1,
i =
1,
2,
...
,
т;
k =
1,
2,
,
..
,
при
дем
R
неравенству
(t)
>
О(т).
Это
вместе
с
равепством
Ilwll
= 1
влечет
(j)
>
О(т),
что
ПРОТlIворечпт
начальному
предположению
О(т)
Е
в(у)
.•
Следствие
7.
Если
Y-nОJtnаnr,
ТО
с(у)=в(у).
4.
Выше
был
установлеп
целый
ряд
свойств
эффек
ГПВ
ных
оценон.
При
этом
к
струнтуре
множества
У
не
предъявлялось
КaIшх-либо
существенных
требованпй
(кро
ме
:замипутости
и
ограниченностп
в
теореме
10
и
заМКlIУ
~
ости
в
теореме
16),
а
на
уО
иногда
полагалось
условие
принадлешать
положительпому
ортанту
ишr
же
быт},
еДIIпственной
точкой
мансимума
на
У
для
соответствую
щей
фуннцпи.
Поэтому
все
полученные
условия
эффеRТИВ
пости
оценон
леГRО
переформулировать
в
соответствую
щпе
условия
эффективности
решений.
Например,
теорема
1
принимает
вид:
если
/.(хо)
>
О,
i =
1,
2,
' ,
.,
т,
то
решение
х
О
Е Х
слабо
эффентивно
тогда
n
ТОЛЬRО
тогда,
ногда
существует
вентор
~!
Е
М,
при
нотором
min 'tttft
(х
О
)
=
тах
min 'ttl/t
(х).
tE1Il
ХЕХ
tEM
11
словие
единственности
ТОЧЮI
маI<симума
фУНIЩИII
«:р(у)
на
множестве
У
обеспечивается,
например,
единст
венностью
тОЧI<И
манснмума
<p(j(x»
на
Х.
ПраюпчеСI<II
последнее
условне
гарантируется
чаще
всего
в
тех
слу
чаях,
ногда
Х
ВЫНУI<ЛО,
<р(/(х»
строго
I<вазивогнута
(в
частности,
строго
вогнута)
на
Х:
кан.
известно,
строго
}\вазивогнутая
фУНIщия
может
достигать
маКСП'vIума
лпшь
в
еДJIпственноlJ
ТОЧI,е
(см.
§
2),
88
~'словия
ОПТlВIАЛЫIOСТИ
[ГЛ.
2
т
Например,
строго
вогнута
фушщия
~
11;/;
(х),
где
все
i=l
~ti
~
О,
все
фУНКЦИИ
/;
вогнуты,
по
крайпей
мере одно
/!i>
О И
соответствующая
функция
/;
строго
вогнута.
Строго
квазивогнутой
является
функция
mil1
~tJ;
(х),
где
iEM
все
/!!
~
О и хотя
бы
одно
I1J>
О,
причем
все
функции
/;
строго
квазивогнуты.
В
теореме
8
точна
максимума
<р
на
Z
(см.
(4)) 01\3-
зывается
единственной,
если
множество
Х
ВЫПУI\ЛО,
все
фУНКЦИИ
<pj(f(x))
I\ВаЗIШОГНУТЫ
(11
1'''
этом
множество
{xEXI<pj(f(x))~tj,
j=1,
2,
...
,
р}
выпукло),
а
<ро(/(х))
строго
Iшазпвогнута.
Аналогпчно
в
задаче
(1.5.1)
решение
х
О
будет
единствеНIIЫИ,
еСJlИ
Х
ВЫПУI\ЛО,
все
/;
I\ваЗIl
вогнуты,
нрнчем
/!
строго
Jшазивогпута.
При
м
е
р
11.
Рассмотрпм
многонрптерпалыIIo
зада
чу
с
векторным
критерием
/ =
Ц1,
/2'
...
,
Iщ),
в
Iютороir
все
критерИII
/!
ПОJlOiRптельны
па
Х,
причем
/1,
...
,
J,
желательно
максимпзировать,
а
//+1,
...
,
/,~
-
МИНИМИЗII
ровать.
Эту
задачу,
ню,
отмечалось
в
§
1.3,
можно
пред
ставить
в
виде
зада'IИ
маКСIIмизации
с
векторныи
крн
терием
(/1,
...
,
//,
-/1+1'
...
,
-/т).
Так
нан
ФУННЦИЯ
-11t
возрастает
на
(-00,
0),
то
этот
векторный
критерий
Эlшивалентен
(см.
§ 1.8)
венторному
критерию
(fl,
'"
••.
,
//,
1///+1,
...
,
111т).
Поэтому,
ссылаясь
па
пример
5,
можно
утверждать,
что
при
~ti
>
О,
i =
1,
2,
"'.
т,
любо[)
решение
х
О
Е
Х,
доставляющее
папбольшее
на
Х
значе
ние
фУНIЩШI
является
эффектпвным,
5.
Теорема
1
и
пример
8
ПОЮ1зывают,
что
еСЛII
все
I\ритерии
/!
положительны
на
Х,
то
любое
эффективное
решение
х
О
может
быть выделено
максимпзацией
на
Х
фУНI\ЦИИ
mil1
~;/i
(х)
при
надлеlIШЩIНl
образом
подобран-
iEM
ных
положительных
ноэффицпентах
[.tl.
Этот
фаI{Т
позво
ляет
ИСПОЛЫlOвать
такую
Фунrщию
ДЛЯ
построешIЯ
мно
жества
(слабо)
эффеКТНВIIЫХ
решенпй
(см.
§ 3.5).
С
дру
ГОЙ
стороны,
он
говорпт
О
TO~I,
что
задачу
выбора
§
~.1]
ОБЩИЕ
условия
ОПТИМА.;IЬНОСТП
89
оптимального
решеIШЯ
при
палпчпи
ве!{ТОРIЮГО
"рптерип
/ =
(/"
/2,
...
,
/т)
формаJIЫIO
~lОашо
свести
к
задаче
опти
мизации
по
одпому
I{ритерию
min
f!i!i,
в
котором
параметр
i6M
~l
=
(/ll'
/l2,
••.
, /lm)
является
неопреде.ленным.
А
для
решения
последней
задачи
можно
использовать,
напри
~tep,
принцип
маКСlIмина.
Уrшзанное
положение было
сформулировано
и
широко
использовано
Ю.
Б.
Гермейе
ром
при
построении
оригинальной
методологии
исследо
ваНIIЯ
операций
[19, 21].
Следуя
работе
В.
В.
Подиновсиого
[80],
разберем
под
j10бнее
этот
подход
I\
МНОГОI\ритериальным
задачам
для
с.1учая,
когда
НИИaI\ОЙ
дополнительной
информации
для
выбора оптимального
решения
во
множестве
Р/Х)
нет.
Пусть
все
нритерии
fi
положительны
на
Х.
Тогда,
согласно
теореме
1
и
примеру
8,
выбор
единственного
(с
точностью
до
эквивалентности
- f)
решения
из
мно
;1;ecTвa
Pj(X)
равносилен
уиазаниIO
вектора
/l
пз
МНО
а;ества
~lO=
{~EE;I~i=1/!i(X),
i=1,2,
...
,m;
XEPj(X)},
(25)
r;оторыи
следует
использовать
при
мar;СПМIIзацип
на
Х
функции
'ф
(.х,
~)
= min
f!ifi
(х).
(26)
iEM
I{
задаче
оптимизации
с
нритерием
'Ij;(Х,
/l),
в
котором
значение
параметра
/l
Е
МО
считается
неизвестным,
фор
мально
можно
применить
тот
или
ипой
припцrш
приня
тия
решений
в
условиях
пеопределеШIOСТII.
Крптичесииii
обзор
основных
ТalШХ
ПРНIIЦИПОВ
имеется
в
юrиге
[53].
Т
е
о
р
е
м
а
17.
Пусть
Х
-
1/еnустой
ко],tnаnт,
а
все
fj
положительны
и
непрерывны
на
Х. Тогда,
соглаС1Ю
nрин
/{иnам
],юксшtИн,а
(Вальда)
,
],tИнимаксного
сожаления
(Сэвuджа)
u
nесси.ltu3Nа-оnти.мU3.Лlа
(Гурвича),
оnтu],tаль
nое
ПО
критерию
(26)
решение
х* удовлетворяет
условию
. t;
(х*)
.
/;
(х)
тlll
--.-
=
шах
тll1
--*-,
(27)
iEM
/;
ХЕХ
iEM
f
i
где
17
=
шах
fi
(.1'),
ХЕ.\
iEM.
90
УСJЮВИЯ
ОПТШIАЛЬНОСТП
(ГЛ
2
д
о
к
а
з
а
т
е
JI
ь
с Т
в
о.
3амеТllМ вначале,
что
в
усло
ВIIЯХ
теоремы
множество
У
непусто,
замкнуто
и
ограни-
чено,
а
функция
min
У:
непрерывна
и
не
убывает
по
;
1ЕМ
li
на
У.
Поэтому,
согласно
теореме
10,
во
множестве
точек
максимума
этой
фующии
на
У
имеются
эффективные
оценки,
и
оптимальными
следует
считать
решения,
имею
щие
эти
оценки.
Кроме
того,
по
следствию
4
справедливы
равенства
17
=
тах
11
(х)
=
тах
/1
(х).
хЕХ
XEPj(X)
(28)
Согласно
ПРИUЦИllУ
максимина
оптимальным
счита
ется
решецие,
максимизирующее
функцию
inf
'Ф
(Х,
~t).
J.1E,MO
ДЛЯ
ПРОИЗВОЛЬНОl
О
фUl{сироваIIНОГО
х
Е
Х
можно
заIIIl
сать
inf
min
[~1!
,(х)]
=
min
[11
(х)
inf
~t]
=
min
11
(Х)
(
')
l-tеМо
1ЕМ
'ЕМ
J.1EMo
1ЕМ
шах
1
и
•
uepf
x
)
(29)
Поэтому,
в
силу
(28),
ОUТЮ.lальное
решение
х*
удовлет
воряет
(27).
Принцип
минимаксного
сожаления
рекомендует
в
ка
nестве
оптимального
припнть
решение,
минимизирующее
на
Х
фующшо
Sl!p
[шах
Ф
(и,
~)
-
ф
(х,
~)].
(ЗО)
J.1EMo
UЕХ
СоглаСIIО
теореме
1
для
любого
фШ{СIIровашlOГО
J..t
Е
:М
О
тах
Ф
(n,
~)
=
1.
(31)
иЕ:Х
С
учетом
(З1)
и
(29)
для
минимума
функции
(ЗО)
по
лучаем
mш
sup
[1
"-ЕХ
I1ЕМ°
-
ф
(х,
~t)]=
шiп
11
- iIlf
'Ф
(х,
~t)]
=
;хЕХ
J.1E:MU
.
[1
.
1,
(Х)
J 1 . f,
(Х)
=Шlll
-ШIIl-
..
- = -ТJ1f\ХffiIП--,
ХЕХ
1ЕМ
1,
;хЕХ
,ЕЫ
f;
Тю{им
образом,
оптимальное
решение
х*
удовлетворяет
равенству
(27),