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

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

§

2.2]

:ВОГНУТЫЕ

:и

ЛИНЕЙНЫЕ

ЗАДА

q:и

111

Д

о

с т а т

о ч

Н

о

с т

ь.

Если

пара

(хО,

1..0)

есть

седловая

точка,

то

И3

правого

неравенства

(14)

при

1..=

Ощ

имеем

<'),0,

g(X

O

»

<:

О.

Но

').,0

~

O(h)

И

g(XO)

;Е;

Ощ,

поэтому

<').,0,

g(X

O

» =

О.

(15)

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

левое

неравенство

(14)

влечет

<!L,

f(x» +

(')

..

,0,

g(x»::::

<!L,

f(xO»

для

всех

xeD.

Отсюда

следует

<!L,

f(x»

::;;

<!L,

f(xO»

для

всех

х

е

Х.

Так

как

!L

>

О(т),

то

хО

е

s(x).

Н

е

о б

х

о

д

и

м

о

с

т

Ь.

И3

слабой

эффективности

х

8

вы

текает

несовместность

на

D

следующей

системы

BOГHY~

тых

неравенств:

f(x)

-

f(xO)

>

О(тН

к(х)

;е:

O(h)'

По

теореме

Фана

-

ГЛИl<сберга

-

Гоффмана

об

альтер

нативе

существуют

неотрицателыIеe

числа

/11!

/121'

•

'l

11т./!

т

k

"'~'

л~\

.

"1

').,х,

~!Li

+

~

"'J

= 1

!

такие,

что

i=l

j=

1

<!L,

f(x)-f(хО»+<').,О,

g(x»::;;O

для

всех

xeD.

(16)

Отсюда

следует

левое

неравенство

(14).

Дa.тree,

если

в

(16)

положить

х

=

хО,

то

получим

<1..0,

g(XO»

~

О.

Но

<Л,

g(XO»

~O

дЛЯ

любого

"л

Е

E~\

поэтому

<1..0,

g(xO»::;;

~

<"л,

g(xO»,

т. е.

правое

неравенство

(14)

также

вы

полняется.

Для

того

чтобы

доказать

включение

!L

е

М,

достаточно

убедиться,

что

!L

>

О(т),

поскольку

В

этом

случае

неравен

т

ства

(14)

всегда

можно

поделить

на

~

~ti.

Действительно,

i=l

если

бы

было

~t

=

О(т),

то

И3

(16)

при

х

=

х

следовало

бы

неравенство

<').,0,

g(x»

<:

О,

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

условию

ре

k

гулярности

и

равенству

~

').,1

= 1.

'Условия

слабой

эф-

&=1

фективнос'.Си

доказаны.

112

УСЛОВИЯ

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

[ГЛ.

2

Условия

собственной

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

получаются

ИЗ

дo~

назанных

условий

слабой

эффеНТИВlIОСТИ

при

помощи

Teo~

ремы

1.13

(аналогично

тому,

нан

это

было

сделано

в

дo~

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

теоремы

3).

Эти

условия

будут

отличаться

от

условий

слабой

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

ЛИШЬ

тем,

что

в

них

вентор

I-t,

участвующий

в

фупнции

Лагранжа,

будет

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

ВIшючению

I-t

Е

М,

а

не

I-t

Е

М

.•

7.

Рассмотрим

линейную

многонритериальную

задачу.

Пусть

линейная

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

j

имеет вид

j(x)=«c\

х>,

<с

2

,

х>,

...

,

<с

m

,

х»,

а

множество

Х

иолиэдрально,

т.

е.

задано

нонечной

сис~

темой

линейных

неравенств

Х

=

{х

Е

Еnl

<a

J

,

х)

::о;;

Ь

j

,

j =

1,

2,

...

, k},

(17).

где

а

!

Е

Еп,

Ь

}

Е

Е,

j =

1,

2,

...

, k.

В

линейной

многонритериалыIйй

задаче

множество

оценон

У

не

тольно

выпунло,

но

таюне

и полиэдрально.

Рпс.

5.

Рис.

5

наводит

на

мысль

о

том,

что

здесь

для

l{аждой

эффентив~

ной оцепни

уО

можно

подобрать

вентор

I-t

Е

М

таной,

чтобы

ТОЧ[\а

уО

была

точной

мансимума

на

У

фушщии

<I-t,

у).

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

вспомпив

теорему

3,

можно

пред~

положить,

что

множества

Р(

У)

И

а(

У)

(а

таЮI\е

Pj(X)

и

Gj(X»

в

липейных

задачах

совпадают.

Это

предположение

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

OHa~

зывается

верным.

Вначале

донажем

следующую

теорему,

Прllведенную

в

[208]

для

эффективных

решений.

т

е

о

р

е

м

а

7.

Для

того

чтобы

в

линеunоu

задаче

ТОЧ1>а

х

О

Е

Х

была

эффективной

(слабо

эффе"тивnоu),

необходи

жо

*),

чтобы

для

не"оторых

векторов

I-t

Е

М

(I-t

Е

М)

и

л

Е

E~

выnолнялuсь

равенства

7n

h

~

~ici

=

~

Лjа

j

(

18)

i=1

З=1

*)

Как

показывает

Т\ОRазательство

леммы

4,

условия

теоремы

7

являются

п

достаТОЧНЬШII.

§

2.2)

ВОГНУТЫЕ

И

ЛИНЕйНЫЕ

ЗАДАЧИ

k

.~

Лj

(bj -

<a

i

1

хО»)

=

О.

6=1

113

(19)

Д

О

R

а

з

а т

е

л

ь

с

т

в

о.

Через

J(XO)

обозначим

множест

во

индексов

Ю,ТIIВНЫХ

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

т. е.

j

Е

J(XO)

тогда

и

ТОJIЫ\О

тогда,

когда

<a

1

,

ХО)

= b

1

•

ЭффеIПИDIЮСТЬ

хО

влечет

несовместность

следующей

системы

линейных

неравенств:

<ci,

х)

>

О,

i = 1,21

..

'.'

m~

(20)

-<аj,х)>О

для

всех

jEJ(XO).

Действительно,

если х

-

решение

системы

(20),

то

для

достаточно

малого

в

>

О

II

точки

х'

=

ХО

+

вх

будем иметь

<с\

х')

:::::

<с\

хО),

i =

1,

2,

...

,

т,

<a

J

,

х')

:;;

<a

1

,

хО)

=

Ь

;

дЛЯ

всех

j

Е

](хО),

<a

1

,

х')

<

Ь

;

дЛЯ

всех

остальных

j,

что

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

эффективности

ХО.

ИЗ

несовместности

неравенств

(20)

по теореме Тю.

кера

об

альтернативе

следует

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

векторов

ft

Е

Е

М

1

Л

Е

E~

таЮIХ,

что

выполняется

равенство

(21)

!юторое,

очевидно,

эквивалентно

равенствам

(18), (19).

Если

же

хо

слабо

эффективна,

то

несовместной

будет

система

<с\

х)

>

О,

i =

1,

2,

...

,

т,

_<a

1

,

х)

б;

О

для

всех

j

Е

J(XO),

и

применение

теоремы

:МОЦЮIНCI.

приведет

к

равенству

(21)

- k

С~Е:МИЛЕЕ-~:

•

Л

е

м

м

а

4.

jj

линейной

задаче

точка

хО

эффективна

тогда

и

только

тогда,

когда

существует

вектор

~t

Е

М,

длл

которого

выnолнлется

т т

~

< i

О)

,-, < i )

~

fti

с,

Х

= max."-i

~Ч

с

1

Х

•

(22)

i=l

хЕХ

i=l

8

в. в.

ПОДИНОБСRИЙ,

в.

Д.

Ногин

Н4

УСЛОВИЯ

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

(ГЛ

2

Для

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

кеобходимости возьмем

произволь

ное

х

Е

Х.

"Умножая

равенство

(21)

скаллрно

на

х

-

хО,

получим

m • .

~

f1i

(с

.,

х

-

х

О

)

= .

~

Лj

(а

З

1

х

-

хО).

(23)

i=l

JEJ(""O)

НО

<a

i

,

хО)

=

Ь,

для

j

Е

J(XO)

И

<a

J

,

х)

~

Ь"

поэтому

правая

часть

равенства

(2З)

неположительна

для

любого'

х

Е

Х.

НеПОЛОiIштельность

левой

части

(23)

влечет

(22).

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

имеет

место

в

силу

f1

>

О(т)

(см.

пример

1.2).

11

При

м

е

ч

а

н и

е

6.

Лемма

4

для

линейных

задач

спе

циального

вида

впервые

была

получена

Т.

Купмансом

[184];

затем

А.

Чарнс

и

"У.

Купер

[130]

доказали

ее

при

помощи

теоремы

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

линейного

программиро

вания

на

основе

теоремы

1.6.

Аналогичным

путем

П.

Бод

[121]

показал

ее

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

для

общего

случая.

Позднее

она

была

установлена

в

[149, '172].

в

[77]

она

получена

при

помощи

теоремы

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

линейного

программирования

на

основе

теоремы

1.5.

Согласно

доказанной

л-емме,

в

линейной

задаче

всегда

1Зыполняются

равенства Р(

У)

=

У>

и

Pj(X)

==

Х>.

Сравнивая

лемму

4

с

теоремой

4,

получаем

С

л

е

Д

с т

в

и

е

3.

В

линейной

задаче

справедливы

ра

венства

Р(У)

=

G(Y),

Pj(X}

==

Gj(X}.

8.

Равенства

из

последнего

следствия

получены

для

ли

нейной

многокритериальной

задачи,

т.

е.

в

предположении

линейности

всех

функций

fi

и

аффинности

*)

всех

функ

ций

g"

участвующих

в

определении

множества

Х

(1.1.1).

Здесь

мы

покажем,

что

указанные

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

вы

и для

определенного

класса

нелинейных

функций,

а

именно

для

полиэдральных

вогнутых

фушщий.

Напомним

(см.

[93]),

что

полиэдральной

вогnутой

на

зывают

числовую

фУНIщию

h:

Еn

-+

Е

вида

h

(х)

=.

min

(c

j

,

х)

+

а;}"

JE{1.2

.....

s}

*)

Числовая

функция

h

аффultltа.

если

она

одновременно

во

гнута

и

выпукла

на

Еn.

Аффинная

функция

представляет

собой

сумму

линейной

функции

и

некоторого

числа,

т. е.

h

(х)

.=

<С,

.х)

+

+

Ь,

где

с

Е

Еn,

Ь

ЕЕ,

§

22)

ВО,ГНУТЫЕ

И

ЛИНЕйНЫЕ

ЗАДАЧИ

115

где

d

Е

Е",

а}

Е

Е

для

всех

j.

Понятно,

что

всякая

аффин

пая

(в

частности,

линейпая)

функция

является

полиэд

ра.JIЬНОЙ

вогпутой,

но

не

наоборот.

Полиэдральная

вогпу

тая

функция

вогнута

на

ЕЛ.

В

соответствии

с

этим

будем

считать,

что

критерии

имеют

вид

/i(X)=~i~i

(с

;

(i),

х)

+

а}),

i =

1,

2,

...

,

m1J

где

M

i

= {1,2,

""Si}

и

c;(i)E

Е

n

,

(Х~ЕЕо;ля

всех

i

и

j.

Л

е

м

м

а

5.

Если

множество

Х

nолuэдральн,о,

все фунr.

ЦUU

/,

являются

nолиэдральн,ы.~tU

вогнутыми

и

Р(У)

=1=

О,

то

М1tожество

У

*

nолиэдральн,о.

Д

о

к

а

з

а

т

е

л

ь

С т

в

о.

Пусть

В

-

это

матрица,

первую

строку

ноторой

составляют

компонепты

пекоторого

векто-

ра

из

с

1

(

1)}

с

2

(1)t

..

'.i

/1

(1),

вторую

строну

-

I\омпоненты

неноторого

вентора

из

с

1

(2),

с

2

(2),

...

,

с"

(2),

и

Т. д.;

пос

леднюю

CTpOI\Y

-

компоненты

неноторого

вентора

из

с

1

(т),

с

2

(т),

..

"

с'т

(т).

Пусть

Ь

-

это

соответствую

щий

матрице

В

Bel,Top,

первой

номпонентой

которо-

1 1 1 u

го

служит

одно

из

чисел

а

1

,

(Х2,

...

,

(Хо,

,второи

-

одно

из

чисел

ai,

(X~,

•••

а

(Х;.

и

т. д.;

последней

номпонентой

-

од-

т

т т

т

по

из

чисел

(Х

1,

(Х2

,

..

"

(Х'т'

ан

что,

например,

матрице,

у

I{ОТОРОЙ

первая

cTpoI\a

есть

вентор

с!

(1),

вторая

строка

-

вектор

с!(2)

и

т.

д.,

последняя

cTpoI,a -

вентор

с!(m),

со-

Ь

12т

О

ответствует

вектор

с

компонентами

(Xl,

(Хl,

•••

,

(Xl

•

че-

видно,

число таних

матриц

равно

числу

соответствующих

векторов

и

является

нонечным.

Иснлючим

из

введенного

набора

матриц

ивенторов

«ЛИШШlе»,

т.

е.

тание,

для

но

торых

не

существует

х

Е

Х,

при

НО

тором

имеет

место

ра

венство

/(х)

=

Вх

+

Ь.

Оставшийся

набор

матриц

обозна

ЧIIМ

через

В\

В

2

,

•••

,

ВТ, а

соответствующие

им

венто

ры

-

через

Ь\

Ь

2

,

•••

,

Ь

Т

•

Введем

в

рассмотрение

множества

ХJ={ХЕХlj(х)=ВJх+И,

j=1,

2,

...

, r,

п

услов~мся

i-ю.

номпоненту

вектора

BJ

x +

Ь

'

обозначать

через

(Щ,

х)

+

b~,

i =

1,

2..,

...

,т.

Из

определения

мно

жества

Х

;

следует,

что

если

х

Е

X

J

,

то

Х

Е

Х

И,

кроме

то

го,

х

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

следующей

конечной

системе

линеiiных

8'"

Ц6

УСЛОВИЯ

ОПТИМАЛьности

[ГЛ.

2

неравенств:

<В{,

х)

+

bi

<:

<c

k

(i),

х)

+

al~

k = 1,

2,

..

'.'

Si,

i =

1,

2,

...

, m.

Обратно,

если

х

Е

Х

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

этой

системе

Лlшейных

неравенств,

то

<BI

I

х)

+

Ь{

=

min

«c

k

(i)t

х)

+

a~)~

t =

1~

21

••

"

т,;

kEMi

•

т.

е.

BJ

x

+

Ь

!

=

j(x).

Поэтому

с

учетом

полиэдральпости

Х

получаем,

что

каждое

Х

}

представляет

собой

мпошсство

решений

некоторой

конечной

системы

линейных

Ilера

венств,

т.

е.

полиэдрально.

Проверим

равенство

'

,.

Х

= U Xj.

:i=1

Пусть

Х

Е

Х.

В

силу

определения

матриц

Bt,

В\

...

,

В'

и

соответствующих

им

векторов

bt,

Ь

2

,

•••

,

Ь

Т

найдутся

В}

и

Ь

}

такие,

что

BJ

x

+

Ь

!

=

j(x).

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

Х

S;;;;

U X

j

•

j

Обратное

включение

выполняется

по

определению

мно

жеств

X

j

•

Таким

образом,

можНо

записать

у

= j

(Х)

= j

(.U

X

j

)

=

.U

j

(X

j

).

)=1

з=1

Для

любого

х

Е

Х

}

справедливо

равенство

j(x)

=

BJ

x

+

+ b

i

•

Это

означает,

что

на

множестве

Х

!

полиэдральпая

во

гнутая

(покомпонентно)

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

j

совпадает

с

не

которым

аффинным

отображением

(т.

е.

с

суммой

некото

рого

линейного

отображения

и

постоянного

вектора).

От

сюда

благодаря

полиэдральности

Х

!

следует

(см.

теорему

19.3

из

[93]),

что

j(X;) -

полиэдральвое

множество,

j-

=

1,

2,

...

, r.

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

У

-

это

объединение

конеч

ного

числа

полиэдральных

множеств

(в

частности,

явля

ется

8амкнутым).

С

самого

начала

мы

предполагали,

что

Р(

У)

=F

!о,

поэтому

из

замкнутости

У

согласно

лемме

1,

которая

доказана

в

§ 3.1,

следует

замкнутость

множества

у

*.

Опираясь

на

выпуклость

Х

и

вогнутость

функций

j;,

легко

установить

(см.

лемму

2.2),

что

У

I\C,

кроме

того,

lIвляется

выпуклым

множеством.

§ 2.3]

двvx.НРИТЕРИАЛЬНЫЕ

ЗАДАЧИ

117

Для

мпожества

У:I<

можно

записат.ъ

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

r r

У.

=

У

-

E~

=

i~J(Xj)

-

E~

=

j~JI

(X

j

)

-

E~}

Заметим,

что

благодаря

полиэдральности

/(X

j

)

все

мно,

жества

t

(Xj)

-

E~l

j =

112"

"'1

r"

полиэдральны

(см.

следствие

19.3.2

из

[93]).

Далее,

пос.коль.ку

У

* -

выпу.клое

зам.кпутое

множест

ПО,

то

у

* =

co(~y

У.

=

ё<mV

{jQl

[1

(X

j

)

-

E~]}.

Справа

здесь

стоит.

замыюшие

ВЫПУКЛОЙ

оБОЛОЧI\И

I\онеч

ного

числа

пошшдральных

множеств.

Опо

само

является

полиэдральпым

множеством

(см.

теорему

19.6

из

[93]).

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

У.

-

полиэдральное

множество

.•

т

е

о

р

е

м

а

8.

Пусть

aOnYCTU.AlOe

.мnожество

Х

имеет

вид

(1.1.1), D =

Еn

U

все

фУН1>ЦUU

/i,

gj

яв.ляются

nолuэд

ральnымu

вoгnYTЫMи.

Тогда

Р(

У)

=

G(

У)

(а

значuт,

Pf(X)

=

Gj(X».

Д

о

к

а

з

а

т е

л

ь с т

в

о.

Благодаря

тому,

что

gj -

поли

эдральные

вогнутые

фушщии,

множество

Х

полиэдрально.

Если

Р(У)

=

0,

то

равенство

Р(У)

=

G(Л

выполняет

оя.

Поэтому

пусть

Р(

У)

=1=

0.

в

этом

случае,

согласно

лемме

5,

полиэдралъным

является

множество

У..

Поэто

му

в

силу

следствия

3

справедливо

равенство

Р

(У

*)

=

=

G

(У

*).

Отсюда,

учитывая

лемму

1,

получаем

Р(

У)

=

=

G(Y).

[1

Заметим,

что

отличные

от

приведенных

выше

условия

па

функции

/!

и

gj,

обеспечивающие

совпадение

эффек

тивных

и

собственно

эффе.ктивных

точе.к,

можно

найти

в

[68].

§

2.3.

У

словил

оптимальности

для

дпухкритериальных

задач

1.

В

данном

параграфе

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

условия

оп

тимальности

по

Парето

для

задач

с

векторным

критерием

/ =

(/1'

/2).

При

формулировке

этих

условий

используют

ся

сведения

о

наибольших

и

наименьших

значениях

крн

териев

на

множестве

эффеI\ТИВНЫХ

решений.

118

УСЛОВИЯ

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

(ГЛ.

2

Предположим,

что

Р,(Х)

'*

0.

Тогда

Sup /i

(х)

<:: Sup /i

(Х),

i =

1"

2.

'(

1)

!l:EPf.X)

хеХ

Если

же

множество

Р,(Х)

еще

и

внешне

устойчиво,

то

согласно

следствию

1.4

это

нестрогое

неравенство

обраща

ется

в

равенство.

Л

е

м

м

а

1.

Есди

уО

Е

Р(

У)

и

y~

=

шах

Уl',

то

y~

=

УЕР(У)

=

шiп

У2'

,

II

ЕР

(У)

Д

о

I\

а

з

а

т е

л

ь

с

т

в

о.

Допустим,

что

y~

> inf

У2'

уЕР(У)

Тогда

найдется

у*

Е

р(

У)

такой,

что

y~

>

у;.

В

СИЛУ

эф

8

РI!С.

6.

фективности

у*

должно

быть

о

*

У2

<

YI,

а

это

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

условию

леммы

.•

Заметим,

что

на

случай

т

> 2

лемма

1

не

обобщается

(см.

рис.

6,

где

У

=

р(у)

шеСТИУГОЛЬНИI\,

вписанный

в

треуголыпш

Аве).

!/.г

2.

Обратимся

к

рассмот-

рению

ДВУХI\ритериальной

за

дачи,

в

которой

вектор-функ

ция

/ = (/1' /2)

задана

на

не

пустом

множестве

Х s;;

Еn.

Введси

следующие

обозначения:

b

i

= SUP/i(X), i =

1,

2;

ХЕХ

Х;

=

{Х

Е

Х

1/1

(Х)

=

Ь

1

};

а

=

{Stl

P

(/2

(Х)

I

Х

Е

Х;\,

если

X~

=1=

0,-

2

inf

{!

2

(Х)

I

Х

Е

Х}

-

В

противном

случае.

'У'СЛОВIшся

считать,

что

[а2,

Ь

2

]

означает

соответствую

щий

отрезок

в

случае

конечных

а2

и

Ь

2

,

а

в

случае,

если

одно

из

них

Сили

оба)

есть

бесконечность,

то

-

соответст

вующий

луч

(или

всю

числовую

прямую).

Например,

ес

ли

а2

==

-

00,

то

[а2'

Ь

2

]

есть

(-

00,

b

2

J.

Если

Р,(Х)

'*

0,

то

согласно

(1)

мх)

~

Ь

а

для

любого

х

Е

Р/(Х).

Если

Х;

=1=

01

'то

благодаря

лемме

1

!а(х)

G;

аа

§

~.Зl

ДВУХКРИТЕРИАЛЪНЫЕ

3АДАчtt

119

для

всех

х

6

Pt(X).

Если

Х;

= ef,

то

для

каждого

х

е

Е

Pj(X)

также

имеем

мх)

iE:

аа.

Таким

образом,

мх)

Е3

Е! [аа,

Ь

а

]

при

х

Е

Pt(X).

Длл

а

е

[аа,

Ь

а

]

введем

в

рассмотрение

задачу:

найти

max{/I(x)lxeX,

/а(х)Е;;а}.

(2)

Если

хо

Е

Pj(X),

то

согласно

теореме

1.5

хо

-

единст

венное

(с

точностью

до

эквивалентности

~t)

решение

М

дачи

(2)

при

а

=

/2(ХО),

причем,

как

выяснено

выше,

CG

е

е

[аа,

Ь

а

].

Наоборот,

если

хо

-

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

(с

точностыо

до

эквивалентности

~

j)

решение

задачи

(2),

то

иа

теоремы

1.8

(при

fPo(/(X»=/I(X),

fPl(/(X»=

мх),

t

l

=

=

а)

следует

эффективность

хО.

Все

это

означает,

что

хО

Е

Pj(X)

тогда

и

только

тогда,

когда

точ

ка

х

8

является

единственным

(е

точностью

до

эквивалентности

~

j)

решением

скалярной

задачи

(2)

при

а

6i

[аа,

Ь

а

]

(см.

рис.

7).

При

м

е

'1

а

н И

е

1.

Легко

по

нять,

что

наименьший

интервал

изменения

параметра

а,

при

кото-

Рис.

7.

ром

остается

справедливым

сфор-

мулированное

выше

взаимнооднозначное

соответствие

между

эффективными

точками

и

решениями

аадачи

(2),

есть

~2'

o~],

где

a'.l=

iпf

/'.1

(х),;

Ь

2

==='

вир

/2

(х).

-

XEPfX)

XEPf

X )

Но

дело

в

том,

что

в

общем

случае

вычислить

эти

величи

ны

практически

сложно.

Поэтому

вместо

них

берутся

другие

границы

(<<с

запасою»,

как,

например,

аа

и

Ь

а

,

оп-

ределенные

ранее.

Заметим

также,

что

в

случае

X~

=

ef

и

Ь

1

< +

00

в

качестве

нижнеii

границы

иптервала

изме

нения

а

можно

брать,

например,

sup

{Уаl

У

е

У,

УI

= b

l

},

что

явллется

более

точным,

чем

аа

(последнее

видно

на

рис.

7,

если

из

множества

У,

изображенного

на

нем,

ис

ключить

все

точки,

первая

координата

которых

есть

b

j

).

В

§

2.1

было

отмечено,

что

требуемое

условие

един

ственности

выполняется,

если

Х

выпукло,

t.=.

(/\,

/2)

ква

зивогнута,

причем

/1

строго

КВ<lзивогнута.

Другие,

спецц-

120

Условия

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

tl'Л.

2

физические для

двухкритериальпого

случая

достаточные

условия

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

УI{азьшает

т

е

о

р

е

м

а

1.

д.rtя

того

чтобы

каждое

решеТ·tuе

задачи

(2)

при

а

Е

[а2'

Ь

2

]

бы.rtо

едиnствеnnы,м

с

точnостью

до

э;;,

вивадеnтnости

-f

(а

зnачит,

и

эффеnтивnЫ.J>t),

достаточтю

выnо.rtnеnия

одтюго

из

следующих

усдовий:

1)

Х

выnу;;,до,

/!

CLl.rtbllO

;;,вазuвогnута,

а

/2

вогnута;

2)

.J>tnожество

У

* =

у

-

E~

выnу;;,до;

3)

Х

=

Еn

и

фуn;;,ция

/!

Ta1ioea,

что

;;,аждый

ее

до;;,адь-

1lЫЙ

Jrtа;;'СUNУ.и,

яв.rtяется

гл

оба.rtbТibLJft,

а

/2

nодуnеnрерыв

на

снизу

па

Еn.

Заметим,

что

вогнутая

функция

СIIЛЬНО

I{вазивогнута

(см.

§ 2.2),

поэтому

условие

1)

выполнепо,

если

Х

ВЫПУI,

ло,

а

/

вогнута

(в

<Этом

случае

УДОВJ1створяется

и

усло

вие

2».

д

оI{

а

з

а

т

е

л

ь

с

т

в

о.

Допустим,

что

решение

хО

зада

чи

(2)

не

является

единственным

с

точностью

до

ЭIШIIва

лептпости

-/,

т. е.

найдется

х'

Е

Х,

дЛЯ

которого

/1(Х')

=

/1(ХО)'

Мх')

>

МхО).

(3)

Если

/Jx') =

Ь!,

то

В

силу

определения

числа

а2

при

ходим

I{

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

а2

~

Мх')

>

МхО)

::::

GG

::::

а2.

Пусть

/1

(х')

<

Ь

1

•

Рассматривая

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

пред

положения

теоремы,

придем

I{

противоречиям:

1)

Из

неравенства

/!(х')

<

Ь!

следует

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

такой ТОЧЮI

х*

Е

Х, что

/!(х*)

>

/!(х').

(4)

Для

любого

Л

Е

(О,

1)

благодаря

вогнутости

/2

и

выпукло

сти

Х

имеем

/2(ЛХ'

+

(1-

л)х*)

~

лfz{х')

+

(1-

Л)/z(х*).

В

силу

неравенства

из

(3)

при

Л

о

,

достаточно

БЛИЗI{ОМ

R

единице,

получаем

Лоfz{х')

>

МхО)

-

(1-

Ло)fz{х*).

Поэтому

/z(лох'

+

(1-

ло)х*)

>

/z(XO)

~

а.

А

благодаря

сильной

Rвазивогнутости

/!

имеем

I1

(лох'

+ (1 -

ло)х*)

>

I1

(х

О

),