Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач

Подождите немного. Документ загружается.

OJjIТ!H!:

~'Сi1О'ВIIЯ:

ОПТЮIАЛЫЮr,тп

71

рот,

-если

(8)

Dыполпепо,

то

IфеДIIо.1JожеПIJе

уО

Ф

Р(},}

ведет

к

ПРОТI1воречпю:

113

существования

у

Е

У

такого,

'"

что

у

>уО,

следует

е

О

=о

у

-

уО

>

0(»1)

П

~

e~

>

О

••

~=1

Из

леммы

1.2.2

вытекает

Те

о

р

е

м

а

7.

Пусть

фующuя

ер(у)

не

уб~Iвает

по

>

на

У,

а

уО

-

ее

точка

.ilеакси.lItУ.ilса

па

У.

ДЛЯ

эффе1>тuвnо

СТU

уО

достаточnо

выnолnеnия

одnого

из

следующих

условий:

ер

возрастает

по

>

па

У;

уО

_

едunствеltnая

точnа

маКСU.,су.на

ер

па

У.

В

пижеследу:ющпх

примерах

рассматрпваются

некото

рые

I\OHKpeTHble

тппы

ФУНIЩIlU,

максимпзацпя

(пли

мини

МlIзация)

которых

ведет

к

получсщпо

эффективных

точек.

т

При

1\1

е

р

2.

ФУШЩИЯ

ер

(у)

=

~

~t1Y1'

где

~I

>

О,

ЯВля-

i=l

стся

возрастающеu

по

каждой

переменной

У.

па числовой

IIРЯМОЙ,

И

потому

возрастает

по

>

на

Ет

(см.

лемму

1.8.4).

Поэтому

любая

ее

точка

манспмума

па

У

эффен

'[нвна.

При

м

е

р

З.

Фупнция

ер

(у}

=

[i~

~Ш:]

1/3,

где

s >

О Ц

~t,

>

О,

является

возрастающей

по

каждой

переменноii

УI

на

множестве

неотрiщательпых

чпсел,

а

потому

возрастает

110

>

па

Е:?

Следовательно,

если

уО

-

ТОЧltа

мансимума

фупнцпи

(jJ<Y)

на

У

с

E~

то

уО

Е

Р

(У).

Эта

же

ФУlIIЩIIЯ

(r

при

s <

О,

~I

>

О,

i

Е

Лl

является

возрастающей

по

каж·

дой

перемеПIIОЙ

УI

па

мпожестве

положптельпых

чисел,

п

поэтому

возрас'rает

по

>

па

E~.

Следовательно,

если

уО

_

точна

мансимума

(jJ

на

У

с

Е;\

то

она

эффентивна.

Пр

п

м

е

р

4.

Пусть

y~>-

sup

Yi

для

Dcex

i

Е

М,

а

Функ-

уеУ

ция

(jJ{y)

возр'астает

по

>

па

Е;;.

Тогда,

1\8I,

ЛОГI\О

про

верить,

ФУНIЩllЯ

(jJ(y* -

у)

убывает

но

>

па

У.

В

силу

теоремы

7

любая

ее

ТО'1I,а

МИI'шмума

па

мпожестве

У

::нрфентивпа.

В

роли

фушщии

(jJ(Y*

-

у),

согласпо

преды-

дущему

примеру.

может

выступать

[i~l

f11

(y~

-

Yi)"]

1/8

72

}'С.'10ВИJ'l

ОПТИМАЛЬНОСТИ

[Pl.

2

*

при

s >

О

и

I-ti>

О,

i

е

111.

Еслп

а,е

У;

>Sup

Yi,

i

Е

М,

то

уЕУ

В

этой

фУНlЩИП

может

быть

И

s <

О.

ФУНlЩИЯ

шах

~ti

(у7

-

Yi),

где

у7

-пропзвольные

фИI{~

iEM

спровапные

qПСJra,

а

I-ti

б

О,

явдяется

невозрастающеii

по

>

на

Ет.

Если

ее

точка

МIIНIIмума

па

У

единственна,

то

опа

эффектпвна.

т

Пр

II

М

е

р

5.

Фушщпя

ер

(У)

=

П

y~li

прн

подожитель-

;=1

ных

I-ti

возрастает

по

I\юrщоii

переменной

У;

па

(О,

+(0),

II

поэтому

является

возрастающей

по

>

на

Er;.

Следова

тельно,

есдп

уО

-

ТОЧI<а

маl{симума

ер(у)

на

У

с

Er;,

то

уО

е

р(у).

При

у7

>

Sup

Yi,

i

Е

М,

фушщпя

ер

(у*

-

У)

=

УЕУ

т

= n

(у7

-

Yi(i

убывает

по

.2:

на

у;

поэтому

ВСЯl\ая

ее

i=1

ТОЧI{а

МИПI!мума

па

У

эффеКТIIВН3.

Отметим,

что

утверждеппя,

сформулпровапные

в

при

мерах

2-5

кат{

следствия

из

теоремы

7,

можно

прямо

проверить

рассуждением

«от

ПРОТИВНОГО».

Таи,

еСШI

ДШI

неl(ОТОРЫХ

у, У'

Е

У,

У

с

ЕТ;

сираведлпво

У

2:

у',

то,

на

пример,

при

s >

О

и

I-ti>

О,

ie

111,

П,

стало быть,

у'

не

моа,ет

являться

точ!юй

МaI{симума

фуниции

ер

(у)

=

[i~

~iyi

J1/

8

на

У.

Анадогом

теоремы

4

для

эффеIПИВНЫХ

оценок

яв

ляется

Т

е

о

р

е

м

а

8.

Пусть

epi,

j =

О,

1,

"',

р

(р

б

О,-nе

убывающие

по

>

па

У

фующии.

Если

точnа

уО

Е

Z,

где

Z

оnределеnо

согласnо

(4J,

удовлетворлет

условию

(5),

то

длл

ее

эффеnтивн,ости

достаточnо

выnолн,еnил

одnого

иа

следующих

условий:

гро

возрастает

по

>

на

Z;

у"

-

едunственлал

ТО'lnа

lftanCllJ1ty.lla

<ро

па

Z.

§

~11

ОБЩПЕ

УСЛОВИЯ

ОПТII:\1.\ПЫIOСТИ

73

Доказательство

этой

теоремы

аналогпчно

доказателт,

ству

теоремы

4

с

той

лишь

разницей,

что

здесь

вместо

теоремы

3

следует

сослаться

на

теорему

7.

При

м

е

р

6.

Если

в

нримере

1

уО

-

единственная

точка,

удовлетворяющая

всем

указанным

там

уеловюш,

то

она

эффективна.

Отсюда,

в

частности,

следует

еЩJa

ведливость

утверждения

о

задаче

(1.5.1),

ефОР:'.1улирован

ного

в

п.

6

из

§ 1.5.

Следствие

3.

Пусть

уОеУ,

Zo={yeYly~y"},

а

фУН't;,цuя

<р

возрастает

по

.2:

па

Zo.

Оценка

уО

эффектив

на

тогда

и

ТОЛЬКоо

тогда,

когда

Ч'

(уО)

=

тах

<р

(у).

lI

e

Z

O

Достаточность

следствия

вытенает

П3

теоремы

8.

Д.rтrr

проверки

необходимости

нужно

лпшь

заметить,

'!То

П

pll

уО

Е

Р(

У)

оказывается,

что

zo =

{уО}.

Пр

п

м

ер

7.

Пусть

f!i>

О,

i

еМ.

ОцеIша

уО

Е

У

эф

феI;ТIIвпа

тогда

II

то.1IЫЮ

тогда,

,\огда

Те

о

р

е

1\1

а

9.

Предnоложи.1t,

что

!/

Е

у

и

у?

>

о,

i = 1, 2,

...

,

m.

OlfeUKa

уО

эффективна

тогда

и

ТОЛЫiО

тог

да,

-погда

существует

веnтор

f.1

Е

1\1

такой, что

уО

есть

1n

TO'lf>a

.1taKCU.1ty.lta

функции

~

у!

fta

.lt1южестве

i=1

Z =

{у

Е

У

I min

~L;Yi

>

тах

min

!liY:}

*).

iellI

II'ЕУ

iE1I1

*)

Иначе

говоря,

уО

есть

точка

Лel{сикографического

максюrу

ыа

па

У

всктор-фующии

('

,min

f!iYi I

~

Yi)'

Заметим,

'по

ю!е-

1ЕМ

;=1

т

сто

~

У; В

этой

теореме

можно

взять

любую

функцию

<Р(У),

воз

i=1

растаюцую

по

~

на

У

(и

даже

лишь

на

S(Y)).

Идея

введения

т

второй

фушщпи

~

У;

длн

выделения

эффеIПИВНЫХ

точек

впер

i=1

вы"

БЫ,lа

использована

А.

Д;тюФФрпоном

rНЮl

прп

доказатt.'.1ьстве

~'твера;деНlIЯ,

обобщением

которого

яВЛяется

reUpe)Ia

10.

i4

Условия

ОПТИМАЛЬНОСТИ

[ГЛ.

2

д

о

к

а

з

а

т

е

л

ь

с т

n

о.

Пусть

уО

эффе1\тпвна.

Так

каи

уЙ

Е

S(Y),

то

по теореме

1

при

IЧ

=flY,

определяемых

ра

венством

(2),

функция

шiп

fliYi

достигает

в ТОЧI,е уО

наи

;Е1I1

большего

на

У

зпа:еПJJЯ,

равного

')..0.

Поэтому

Z =

{У

Е

У

I

шiп

":

Yi:>

'1-0

l =

ieM

Yj J

=[YEYIYi:>Y?,

i=1,2,

...

,mj=Zo.

Следовательно,

1\а1\

уназано

в

примере

7,

уО

есть

точна

т

манспмума

фушщии

~

У;

на

zo

=

Z.

i=l

Пусть,

паоборот,

прп

пеJ\ОТОРОМ

fl

Е

М

оцею,а

уО

яв-

т

ляется

ТОЧJ\ОЙ

мат:спмума

фушщип

~

У;

на

Z.

Приняв

i-1

fJ\

Ч'о

(у)

=

~

Yi,

ffl

(у)

=

шil1

~tiYi,

t

l

=

шах

шiп

fliY~1

на

ос-

i=1

ieM

U'ЕУ

iE1I1

повании

теоремы

8

(при

р

= 1)

можно

утверждать,

что

уО

Е

Р(У)

••

При

м

е

ч

а

н

и

е.

Аналоги

теоремы

9

можно

получать

при

помощп

теоремы

2.

Например,

учитывая

следствие

1

II

теорему

8,'

моашо

утверждать,

что

уО

Е

У

эффеJ\ТИВ

на

тогда

11

толы<о

тогда,

Iюгда

сущестпует

ве1\ТОР

ZO

Е

Ет,

т

при

нотором

уО

есть

то'ша

мансимума

фуннцпи

~

Yi

(илп

i=1

любой

другой

ФУIШ!lIlИ,

возрастающеii

по

>

на

SCY»

на

множестве

{

У

Е

У

I

шiп

(У;

-

z~)

=

шах

шiп

(Zi

-

zy)}.

{ЕМ

ХЕУ

ieM

Если

фуннцпя

ч'

-

неубывающая

по

>

на

У,

то

ТОЧI<а

ее

мансимума

на

У

может

не

быть

эффентивной

Спример:

постоянная

на

У

фующия).

Однано

верно

следующее

утве

ращение:

Т

е

о

р

е

м

а

10.

Если

;.4tн,ожество

У

nеnусто,

8aJrt1,ЛУТО

1.l

ограnичен,о,

а

<р

-

nеубывающая

по

>

па

У

и

nолун,еnре-

рывnая

сверху

фуnкция,

то

.Atnожество

У:

ее

точек

.Ma~

си.МУоltа

па

У

со'8ерж:ит

по

крайней

мере

одuу

эффектив

ную

точку.

§

~.11

ОБЩИЕ

~'с.лОDИП

оптим.ШЫIOСТИ

75

Эаметим,

что

еслп

в

условиях

этой

теоремы

<р

возрастает

по

>

на

У,

то

У;

s;

s

(У)

(см.

теорему

3).

Д

о

и

а

з

а

т

е

л

ь

с

т в

о.

Каи

известно

из

анаЛlIза,

мно-

* .

а;ество

У

<1"

для

которого

можно

записать

равенство

У:

=

{У

Е

У

I

<р

(У)

:>

тах

<р

(Y)},j

.

IIЕУ

т

непусто,

замкнуто

и

огранпчено.

Фующия

~

Yi

возрастает

i=l

* *

по

>

на

У

<1"

Существует

точка

ее

МaI,симума

па

У

(j)'

ко-

торая,

по

теореме

8,

эффеКТIIвна.

•

Таи

r,aI{

при

ПРОИЗВОJIЬНОМ·

фIшспрованном

j

Е

1II

фуш~

ЦIШ

<р(У)

=

У;

непрерывна

на

Е'"

и

является

неубывающей

по

:>,

то

из

теоремы

10

вытеIшет

следующий

извеСТIIЫЙ

рсзультат

(см.,

например,

[77)):

С

л

е

Д

с

т

в

и

е

4.

Если

У

'tenYCTO,

за.ш,.нуто

и

ограни

чеnо,

то

У;

ПР

(У)

=1=

5Z5,

j

=--=

1,

2,

..

"

111,

где

у}'

= r Y*EY.I

у;

=

шах

Y.i}'

так

что

для

любого

f

Е

JJ

\.

,,"'У

тах

У)

=

тах

У)

=

шах

Yj.

IIЕУ

lIЕ:l'(У)

IIES(Y)

Справедливо

таюr;е

тю,ое

общее

УТllсржденпс:

Т

е

о

р

е

м

а

11.

Если

.множество

Р(

У)

внешне

устойчи

ао,

а

функция

<р

является

неубывающей

по

>

на

У,

то

Бl1р

<Р

(У)

=

БПР

ер

(у).

IIЕl'(У)

lIеУ

Д

О

1{

а

3

а

т е

л

ь

с т

в

о.

В

случае

У

=!2J

равенство

оче

RПДНО.

Разберем

слу.чаЙ,

Iюгда

У

=1=

!2J.

При

этом

Р(

У)

=1=

rf=

!2J

I

так

что

Бl1

Р

<Р

(У)

<

Бll

р

<р

(у).

РЕР(У)

IIЕУ

Остается

док«зать

справедливость

обратного

неравенства.

Пусть

{y

k

}

s:

У

-

маI\симизирующая

последовательность:

lim

<р

(у")

=

БllР

<р

(у).

k-'>..,

IIЕУ

В

силу

внешней

устойчивости

множества

Р(

У)

дЛЯ

каж

дого·

yk

.

найдется

Zh

Е

Р( У)

такой,·

что

zh;:';;;

yk.

Отсюда

75

1'С.'ОЕИFl

ОПППI_~.'1,НОСТИ

[Г".

2

ep(Z~)

б

ep(yk),

тат,

что

ер

(у")::;;;

sпр

ер

(у).

Поэтоыу

II

у""Р(У)

511

Р

ер

(у)

~

51]

Р

(р

(у).

•

иЕ:У

уЕР(У)

Отметим

еще

одно

CBoiicTBO

зффеюпвных

оценон

[85]:

Если

выnолnеnы

условия

Teope.~tbl

2

и

уО

Е

Р(У),

то

уО

_

едиnствеnllая

точка

'мШiСll.tlулtа

Фун,кциu

min

~i

(Yi)

ieM

па

У.

действптелыI,'

пусть

у

Е

У

II

У

=1=

уО.

В

СИJIУ

уО

Е

Р(

У)

дЛЯ

некоторого

i

Е

М

будет

уУ

>

Yi,

отнуда,

учитыван

~l

(y~)

=

~2

(y~)

=

...

=

~т

(y':r,)

,

получаем

min

~!

(У?)

>

> min

~;

(у;).

•

ielll

ieM

Пр

п

11

е

р

8.

ЕСШI

уО

Е

Р(

У),

то

функция

min

(Yi

-

y~)

iEM

па

слеДСТВIIЯ

1

достигает

своего

наибольшего

значения

на

У

в

единственноii

точке

уО.

Аналогично,

если

уО

Е

Р( У)

и

у

О

>

0(",,,

то

ыаь:синуна

на

У

фующия

шiп

[.t?Yi,

где

[.t~

iElIl

назначены

согласно

(2),

достигает

в

единственной

точ

ке

уа.

В

§

1.2

было

введено

бинарное

отношение

:>

:у'

>-

У'!

верно

тогда

и

ТОЛЬКО

тогда,

когда

неверно

У"

>

у'.

При

помощи

этого

отношеНI!Н

определеНП8

эффективной

оцен

fШ

можно

перефразировать

следующим

обраЗ0М:

оценка

уО

Е

У

эффвь:тивна

в

том

и

ТОЛЬКО

том

случае,

если

для

любой

оцен:ки

у

Е

У

вьшолняетея

соотношение

уО

>-у.

Используя

;'IеШIУ

1.2.1,

отсюда

получаем

такую

фор

НУЛИРОВI\У

(СМ.

[70]):

оценна

уО

Е

У

эффеI\ТIIвна

тогда

и

толыи

тогда,

когда

для

нее

найдется

вентор-функция

j.t(y)

со

значениями

пз

М,

и

таная,

что

неравенство

<р./у),

уО)

~ <j.t(y),

у)

справедливо

для

IШiНДОГО

у

Е

У.

Если

на

вид

веиор-фующип

j.t(y)

нало,юIТЬ

опреде

:тенное

ДОПЩIНIIтельное

огранпченпс,

то

из

последнего

опроделсrшя

получаем

следующее

достаточное

условио

эффеНТИВНОСТII.

Л

е

м

м

а

1.

Если

существует

r;Оliечnыu

nабор

векто

ров

{~t\

~t\

...

,

~tP}

с

М,

обладающий

тел

свойствО/Jl,

что

для

r;аждого

у

Е

У

найдется

свой

НО.нер

iE

{1,

2,

...

,

р},

ОБЩИЕ

УС.'IОЕИЯ

ОПТlПIАПЬНОСТII

при

/'iОТОРОЛI

выполняется

1lеравеltство

<~Ii,

у")

~

<f(i,

у>,

то

оцеm,а

уО

эффентuвllа.

77

(9)

3.

В

обще:\!

случае

условне

ле~fМЫ

1

не

является

необ

ХОДИМЫМ

условием

эффеюпвпости.

Так,

в

прш.rере

1.6.1

(см.

рис.

1.12)

для

эффеКТПВIIоii

оцешш

уО

не

существу

ет,

очевидпо,

IIСIЮМОГО IюпеЧIIОГО

набора

венторов

~;

(за

~fетпм,

что

уО

песоБСТВСПIIО

эффеrtтивпа).

Однако,

если

ограничпться

рассмотреlIпе~l

собственно

эффективных

оце

HOI"

то

это

условпе

будет

1,31,

достаточпьш,

так

II

необхо

ДШIЫМ.

т

е

о р

е

1\1

а

12

(lIопш).

Olfenr-a

уО

Е

У

собствеllНО

.7ффеnтивна

в

ТО.1Е

и

тольnо

ТОЛl

случае,

если

существует

ltабор

eer.Topoe

~!,

~2,

•••

,

~p

Е

М,

р::;;;

т,

обладающий

теu

свойстволt,

что

для

r.аждоЙ

оценr.u

у

Е

У

найдется

Но.мер

i

Е

{1,

2,

...

,

р},

при

поторо.1!

выполняется

uеравенство

(9).

Д

о

l>

а

3

а

т

е

л

ь

с т в

о.

Не

умаляя

общностп,

ПОЛОiЮШ

y~

=

О(т).

Отметим

С.'IедующнЙ

факт,

непосредственно

вы

'I

скэющпiI

па

определеНIIЯ

собственно

эффеЮIIвпоiJ

оцен

ЕЛ.

Включение

y~

Е

С(

у)

пмеет

иесто

в

том

и

TO,1JbHO

TO~!

с:туча9,

еспи

существует

число

N >

О

тююе,

что

дпя

на,!>

;:1;ОГО

i

Е

М

система

неравенств

у,>О,

у,

+ NYj >

О,

j =

1,

2,

...

,

т;

•

..t..

•

] ..,-

1,

(

10)

не

Iп!еет

решения

на

MHOrнeCTB€

У.

Д

о

с

т

а т

о

'1

Н

О

С Т

ь.

Согласно

лемме

1,

оценнз

0(",)

2ффеЮИБна.

ДOKa;'Ee~1

ВRлючсние

О(т)

Е

С(

У).

ПУС!'{,

(

mfli

I

N =

шах

\_.2..

j, k

Е

11,1,

l

'1'

• k .

i=

1,

2,

"',

Р}>О.

(11

)

Ссди

О(т)

Ф

С(

Л,

то

для

этого

чисда

N

существует

ИН

,:т,екс

k

Е

М

П

точка

у'

Е

У

такие,

что

y~>O,

y~

-+

ЛТу~

>

О,

j =

1,

2,

..

"

7n;

j

=1=

k.

(

12)

Об~значюиVJо=[jЕМlу~<О).

В

сиду

О(m)=Р(У),

78

~'СЛОВИfI

ОПТИМАЛЬНОСТИ

(ГЛ

2

выполняется

М

О

=1=

0.

Из

(12)

следует

my~

+ N

~

у;

>

О.

(

13)

jEM

u

С

другой

стороны,

по

условию

теоремы,

для

'[ОЧКИ

у'

существует

вектор

Jli

Е

М

такой,

что

<JlI,

у'):$

О.

Отсюда

f'

~

i'

JlhYk

+

.(.j

Jl

jY

j :::;;

О.

jE1I1

~

П,

учитывая

(11),

получаем

неравенство

,

",'

ту"

+ N ~

Yj

s

О"

jEM

o

ноторое

противоречпт

(1З).

Н

е

о

б

х о

Д

и

м

о

с

т

Ь.

Пусть

у

О

Е

С(

У),

т. е.

сущест·

вует

таное

N>

О,

что

для

любого

i

Е

М

система

нера·

венств

(10)

несовместпа

на

У.

Возьмем

пропзвольную

ОЦefШУ

у

Е

У.

ДЛЯ

I\аждого

i

Е

М

выполняется

либо

У.:::;;;

~

О,

либо

У;

+

NYi

~

О

при

Hel\OTopOM

j

Е

М\Ы.

Просум.

мировав

по

i

Е

М

все

подобного

рода

неравенства,

по·

лучим

где

N/

>

О

для

люБOI'О

i

Е

М. Отсюда

следует

неравенство

(9)

при

уО

=

О(т)

И

,Очевидно,

~/

Е

М.

ТаюlМ

образом,

для

I,аiRДОГО

у

Е

У

существует

BeI{TOp

Jl!

=~,

при

котором

имеет

место

не·

равенство

(9).

Причем,

благодаря

конечности

множества

lIндексов

М

число

таких

векторов,

обладающих

необхо

димыми

свойствами,

I\Онечно.

То

есть

существует

Rонеч·

пый

набор

векторов

'~1,

ii"2,

.. "

~plcM

с

тем

свойством,

'что

для

каждого

у

Е

У

найдется

i

Е

{1,

2,

...

,

р},

при

1\0·

тором

имеет

место

(9)

(с

Jl! =

i'>.

Укажем

набор

не

более,

чем

нз

т

векторов,

обладаю·

.щих

неоБХОДИ~fЫМИ

свойствами.

Пусть

8 =

min

I~j

I i

еМУ!

§ z

t)

ОБЩИЕ

УСЛОВИЯ

ОПТИМАJiЬНОСТИ

79

i =

1,

2,

...

,

р}.

Рассмотрим

векторы

следующего

вида:

L~={E,

1=1,2,

...

,т;

l=1=i;

~

J 1 -

(т

-

1)

Е,

j =

i;

t = 1,

2!

.

",

т.

(14)

Очевидно,

~Lf

Е

М

для

любого

i

Е

М.

Докажем

включение

{J.L\

J.L2,

...

,

~p}

s;:;

conv

{J.L\

J.L2,

...

,

J.Lm}.

Для

этого

возьмем

произвольпый

вы\тор

"jil

«старого»

на-

-1

.

бора.

Если

е

=

11т,

то,

очеВIIДНО,J.Li=1/m,

l

=1,2,

"'1

т.

В

этом

случае

для

"1

=

"2

=

...

=

"т

=

11т

имеем

j =

1,

2,

.

",

т,

(15)

т.

е.

J.Ll

Е

conv

{~tt,

~t2,

•••

,

~Lm}.

Если

е

<

11т,

то

берем

i!i

-8

Лi

= 1

,i

=

1,

2,

.

'"

т,

--

тЕ

1n

где

~

Iч

=

1.

Для

этих

"1

равенства

(15)

также

имеют

i=l

место.

Вr:лючепие

ДОl>аззпо.

ПреДПОЛОiЮШ,

что

<шовыii»

набор

векторов

(14)

не

обладает

необходимыми

свойстваМII,

т.

е.

найдется

оценка

у

Е

У

тю.ая,

что

<~tJ,

у)

>

О,

j =

1,

2,

...

,

т.

Для

пропзвольного

l

Е

{1,

2,

...

,

р}

при

некоторых

"!

$;

О,

,

т

j =

1,

2,

"

.,

т,

~

,),;

=

1,

имеет

место

представление

(15).

j=l

Поэтому

ИЗ

(16)

получаем

неравенства

т

~

Лj

<J.L

j

,

у)

=

<~/,

у)

>

О,

j=l

1 =

1,2,

...

,

р.;

ноторые

означают,

что

и

«старый»

набор

векторов

также

пе

обладает

необходимыми

свойствами.

Это

противоречит

полученному

рапее

.•

При

1\1

е

ч

а

II

и

е

1.

Если

множество

У

состоит

из

ко

нечного

числа

:)Лемептов,

то

условие

доказанной

теоре

мы

является

необходимым

и

достаточным

для

того,

чтобы

уО

Е

РО').

Это

вытекает

из

того,

ЧТО

в

слvчае

ко-

80

УС.10ВШI

ОПТИ~1А.1ЫlOСТII

ttЛ.2

нечного

множества

У

пмеет

место

равенство

ССУ)

=

=

р(

У)

(c~1.

прпмер

1.6.3).

ПРИ

М

е

ч

а

н п

е

2.

Аналпз

доназательства

теоремы

12

поназывает,

'ITO

при

неоБХОДНМОСТII

в

фОРМУЛИРОВl\е

этой

теоремы

веI,ТОры

~ti

моа\Но

С'IIIтать

ве[{торами

вида

(14)

и р

=

m.

Непосредственно

из

теоремы

12

(часть

«достаТО'I

носты)

при

р

= 1

выте"ает

С

л

е

Д

с т

в

и

е

5

(Джоффрион).

Если

все

111>

О,

то

т

.ll.юбая

ТОЧNа

.лtaNСИ.~IУ.ltа.

фУ1iNции

~

f!iYi

иа

Jlmожестве

У

i=1

является

собствеюiO

эффеNтив1iОЙ.

Обобщением

этого

результата

является

т

е

о

р

е

м

а

13.

ПУСТЬ

фУ1iNЦИЯ

ер

при

любых

у',

у"

Е

Е

У

удовлетворяет

условию

т

ер

(у')

-

ер

(у"):>

~

Лj

(у',

у")

(y~

-

y~)1

(17)

i=1

причеjJ.t

для

фУ1iNций

l\i(Y',

у"),

определеnnых

па

У

Х

У,

справедливы

не

равеиства

Ь

;

б

'J..Jy',

y")~

а;

>

О,

i =

1,

2,

...

,

т,

(18)

где

ai, b

i

(i

Е

111)

-

Ilекоторые

числа.

Каждая

ТОЧNа

lf/Ш'

симу.лtа

фУnNЦИU

ер

/la

У

является

собствеn1iО

эффеNТllа-

1iОЙ

оцеНNОЙ.

Доназательстпо.

Еслп

у'

>у",

то,

согласно

(17)

и

(18),

ер(у')

>

ер(у").

Следовательно,

ер

возрастает

по

>

на

У.

Поэтому,

если

уО

Е

У

-

точна

мансимума

ер

на

У,

то у

О

Е

р(у)

(теорема

7).

Понажем,

что

уО

собственно

ь

эффеНТIIвна,

прпчем

можно

взять

е

=

(т

-1)а'

где

1)=

=

шах

b

i

,

а

= min

а;

(рассматривается

случай

т

~

2).

iEM

iElIl

ПреДПОЛОЖIШ,

наПРОТIIВ,

что

уО

несобственно

эффентпв

на,

тан

что

найдутся

тание

i

Е

М,

У

Е

У,

удовлетворяю

щие

(1.6.1),

что

для

ВСЯIюго

j

Е

М,

дЛЯ

ноторого

спра

ведлпво

(1.6.2),

выполннется

неравенство

Сдедоватедьно,

для

дюбого

j

Е

М,

j

9=-

i,

верно

у;

-

y~

>