Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 2.3)
ДВУХRРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
121
Два
последних
неравенства
противоречат
тому,
что
х
О
._
решение
задачи
(2).
2)
Здесь
ТaIш,е
имеет
место
пераnепство
(4)
тrри
не.ко
тором
х*
Е
Х.
Возьмем
л
Е
(О,
1)
Il
у
(л)
=
лl
(х')
+
(1
-
л)
f
(х*)
Е
У
*.
Вследствие
(3)
II
(4)
прп
ЛI,
достаточно
близ.ком
.к
едини
це,
будет
выполняться
неравенство
l(хО)
<
у(л!!.
Но
у
(л
1
)
Е
Е
У
*,
поэтому
существует
х
Е
Х,
при
.котором
У(ЛI)
~
~
l(х).
Следовательпо,
ЛХО)
<
l(х),
что
противоречит
то
му,
что
хО
-
решение
задачи
(2).
3)
В
этом
случае,
IIОС.коль.ку
хО
-
решение
задачи
(2)
и
12(ХО):>
а,
из
(3)
следует,
что
х'
-
точ.ка
ма.ксимума
фун.кции
11
на
от.крытом
множестве
{xEEnlfzCx)
>а}.
Значит,
х'
-
точ.ка
ло.кального
ма.ксимума
11.
В
соответст
nпи
с
предположением
3),
х'
является
точ.кой
глобального
ма.ксимума,
т. е.
II(Х')
=
Ь!.
Это
противоречит
начальному
допущению
II(Х')
< b
l
••
3.
Разобранные
выше
условпя
оптимальности
пред
ставляют
интерес
не
только
в
рам.ках
много.критериаль
пой
оптимизации.
Их
моnшо
использовать
и
при
реше
пип
одпокрптериальных
задач
специального
вида.
Для
иллюстрации
этого
ПОJIожения
рассмотрим
СJIедую
щую
задачу
ма.ксимизации
ЧИСJIОnОЙ
фун.кции:
найти
шах
h
[/1
(х),
12
(х)]"
(5)
ХЕХ
где
<11(Х)'
f2(X)) =
лх)
-
двумерная
ве.ктор-фун.кция,
определенная
на
множестве
Х
s
Еп,
а
Ы·,
.]
-
число
вая
фун.кция
двух
переменных,
являющаяся
неубываю
щей
на
своей
области
задания
!(Х)
по
.каждой
пере
менной.
Согласно
теореме
1.10,
если
Хнепусто
и
.компа.ктно,
а
фун.кции
11, 12,
l~
непрерывны
на
своих
множествах
задания,
то
среди
решений
задачи
(5)
имеется
по
.краЙ
ней
мере
одна
эффе.ктивная
точ.ка
по
ве.ктор-фун.кции
1
относительно
множества
Х.
Следовательно,
можно
за-
писать
равенство
тах
'~
[/
(х)]
=
тах
h
(у).
(6)
ХЕХ
уЕ:Р(У)
Продположим,
ЧТО
11,
12
И
Х
удовлетворяют
одному
1J3
трех
предположений
теоремы
1.
В
этом
случае
I\аЩ-
122
УСЛОВИЯ
ОПТИМАЛЬНОСТИ
[ГЛ.
2
дое
решение
задачи
(2)
является
единственным
с
точ
ностью
до
эквиващштности
-f.
Для
сх
Е
(а2,
Ь
2
]
введем
множество
Х*(.сх)
=
{х*
Е
Xlx*
-
решение
задачи
(2)}.
Пусть
х*(.сх)
-
произвольная
функция,
определенная
на
мноЖестве
[а2,
Ь
2
]
и
обладающая
свойством
х*(.сх)еХ*(сх)
для
любого
ae[az,
ь
z
].
(7)
При
сделанных
предположениях,
если
х
1
и х
2
-
два
различных
решения
задачи
(2)
при
одном
и
том
же
сх,
то
j(x
1
)
=
j(x
2
).
Поэтому
для
произвольной
функции
х*(сх),
удовлетворяющей
(7),
верно
равенство
ЩХ*(сх)]
Icx
е
[а2'
Ь
z
]}
=
{/[х*(сх)]
'а
е
[az,
Ь
2
]}.
Согласно
рассуждениям
предыдущего
пункта
множество,
стоящее
в
этом
равенстве
слева,
совпадает
с
р(
У).
Сле
довательно,
р(у)
=
{у
е
YI
у
= j[x*(cx)]
при
Hel\OTopoM
сх
е
[az,
bzj}.
В
этом
случае
равенство
(6)
можно
переписать
таи:
тах
h
[f
(х)]
=
тах
h
[f
(х*
(сх))].
X~X
СХЕ;[а
2
,Ь
2
]
(8)
ИтаI\,
имеет
место
следующее
утверждепие.
Если
х
непустой
I\омпакт,
функции
/1. /2,
h
непрерывны
и
выпол
няется
одпо
из
трех
предположений
теоремы
1,
то
для
любой
функции
х*(сх),
удовлетворяющей
(7),
справедливо
равенство
(8).
На
основании
равенства
(8)
можп'о
предложить
сле
дующий
путь
решения
исходпой
задачи
(5):
а)
решив
параметричеСI\УЮ
заДi1(IУ
(2),
найтп
ФУНI\
цИЮ
х*(а)
для
всех
а
Е
[az,
Ь
2
];
б)
максимизировать
функцию
h[j(x*(cx»]
одной
пере~
менной
на
промежутке
[а2,
b
z
];
если
ао
-
точка макси
мума,
то
х*(схо)
-
решение
задачи
(5).
В
тех
случаях
ногда
аналитичеСIШll
вид
фУЮЩИЙ
/1./з
сравнительно
прост.
реализаЦlIЯ
изложенного
способа
ре
wеНИlI
задачи
(5)
МQЖ~Т
Оl\азаrЪСlI
неСЛQiIШ()Й,
§ 2.3)
ДВУХRРИТЕРИА.1iЫIЫ11:
зл,nл
ЧI1
123
При
м
е
р
1.
Пусть
требуется
решить
эадачу
(5),
в
ко
торой
V
-
h =
11'
12';
1,
(Х)
= -
Х
1
-
Ха
+
Ха
+ 11,
МХ)
=
Х,
+
2Ха
+
5х.,
а
множество
Х
задано
ограничениями
Х,
+
Ха
+
2x~
= 3,
X
z
+
2Х
а
+
Х,
= 7,
Х"
•••
,
Х,
~
о.
Здесь
!,(Х),
'2(Х)
>
О
для
всех
Х
Е
х,
поэтому
функция
у-
-
h
[У1'
У2]
=
У1
У2
строго
воэрастает
по
каждой
переменной
на
Е;.
Во-первых,
находим,
что
решение
х
'
=
(о,
1,
3,
о)
мак
симиэирует
функцию
'~
на
множестве
х.
Так
как
шах
{мх)
Ix
=
Х,
мх)
= !Ilx
l
)}
=
6,
то
полагаем
а2
=
6.
Да
лее,
максимиэируя
12
на
Х,
находим
решение
х
2
=(0,
11/2,
о,
3/2).
Следовательно,
Ь
2
=
15/2
п
задача
(2)
при
а
Е
Е
[6, 15/2]
принимает
следующий
вид:
максимизировать
[,
при
условиях
ХI
+
хз
+
2х.
= 3,
Х2
+
2х
з
+
х.
=
7,
Х
1
+
2х
з
+
5х,
::::
а,
XI,
•••
,
X,~
о.
Решая
эту
задачу
линейного
параметрического
програм
мирования,
находим
х*(а)
=
(о,
3а
-17,
15
-
2а,
а
-
6).
В
соответствии
с
этим
h
[f
(х*
(а))]
= (43 -
5а)
}/а.
Эта
функция
на
промежутке
. [6, 15/2]
достигает
макси
мума
при
ct
=
6.
Следовательно,
(0,1,3,
о)
-
решение
ис-
ходной
задачи,
и
шах
h =
13V6."
124
vсловия
ОПТИМАЛЬНОСТИ
(гп.
2
При
м
е
ч
а
п и
е
2.
Подобным
образом
задачу
(5)
мож
но
решать,
беря
за
основу
не
(2),
а
задачу
отыскания
шах
[~ttl
(х)
+
(1-
~)
/2
(х)).
хЕХ
Принципиальпая
возможность
такого
подхода
заложена
в
теореме
2.4.
Реализацпю
этой
возможности
заинтересо
ванный
читатель
может
наiiти
в
работе
[160).
§
2.4.
У
словил
оптимальности
для
дифференцируемых
фушщпй
Условия
оптимаЛЬНОСТII,
которые
здесь
формулируют
ся,
фактически
являются
дальнейшим
обобщением
клас
сической
теоремы
Ферма:
производная
в
точке
экстре
мума
обращается
в
нуль.
Для
вывода
необходимых
условий
используется
в
ос
новном
только
свойство
дифференцпруемости
функции,
причем
посколы\y
эти
условия
носят
локальный
хары\тер,
то
дифференцируемость
требуется
лишь
в
рассматривае
мой
ТОЧI\е.
Для
того
чтобы
достаточпые
условия
опти
мальности
сформулировать
в
паиболее
общей
форме,
при
влекаются
понятия
псевдо-
и
квазивогнутой
функций
(см.
§ 2.2).
В
этом
параграфе векторные
функции
/ =
(/"
/2,
....
• •• ,
/т)
И
g =
(g"
g2,
•••
, gk)
будем
считать
заданными
на
множестве
D
s;
Еn.
При
этом
донустпмое
множество
Х
будет
представлять
собой
множество
решений
системы
неравенств
(1.1.1).
1.
Введем
множество
J(XO)
номеров
аI\ТИВНЫХ
ограни
чений:
j
Е
J(XO)
тогда
и
толы\o
тогда,
ногда
g/XO) =
О.
Будем
считать,
что
хО
Е
intD.
Необходимое
условие
оптимальности
формулируется
в
следующей
теореме,
где
'\1/i(XO)
означает
градиент
функции
/i,
вычисленный
в
точке
хО.
т
е
о
р
е
м
а
1
(Да
Канха
-
ПолаI\
-
Джоффрион).
Пусть
ве,;,торные
Фун,;,ции
/, g
дифферет-щируем.ы
(no,;,ollt-
nонентно)
в
точ,;,е
хО
Е
Х
и
выполнено
условие
регуляр
ности:
существует
та,;,ая
точ,;,а
х
Е
Еп,
что
для любого
j
Е
J(XO)
справедливо
T-tераеенстео
('\1 g/XO),
х>
>
О.
ДЛЯ
того
чтобы
точ,;,а
хО
была
слабо
эффе,;,тивной
(собственно
§ 2.4]
ЗАДАЧИ
С
ДИФФЕРЕНЦИРУЕМЫМИ
ФУНIЩИЯ:МИ
~25
эффе-птив1-l0U)
,
1-lеобходимо,
чтобы
сущестSовалu
веnтор
- . h
lt
Е
М
(lt
Е
М)
и
вектор
л
Е
Е;;;
такие,
что
т
~
ltN!i
(Х
О
)
+
~
лj'vgj
(Х
О
)
=
О(n).
(1)
i=l
JEJ(X
O
)
Д
о
к
а
з'а
т
е
л
ь
с
т
в
о.
Вначале
докажем
условие
сла
бой
эффективности.
Пусть
ХО
Е
Sj(X).
Тогда
система
ли
нейных
неравенств
(V/J<XO),
х>
>
О,
i =
1,
2,
...
,
т,
для
всех
j
Е
J(X
U
)
(2)
(3)
несовместна.
Действительно,
если
это
не
так, то
для
точ
ки
х,
удовлетворяющей
этой
системе,
можно
УI{азать
8 >
>
О
такое,
что
хо
+
8Х
Е
D
и
j;(XO
+
8Х)
-
!i(XO)
= 8(Vj;(XO),
Х>
+
0(8)
>
О,
i=
1,2,
...
,
т,
gj(XO
+
8Х)
=
8(ОУ
gi(XO),
х>
+
0(8)
>
О
gj(XO
+
8Х)
=
g;(XO)
+
0(8)
>
О
для
всех
j
Е
J(x
Q
),
для
всех
j
Ф
J(XO).
Здесь
первое
неравенство
будет
иметь
место
в
силу
диф
ференцируемости
!I
инеравенства
(2);
второе
-
БJIагода
ря
дифференцируемости
gi
инеравенству
(3);
третье
гследствие
непреРЫВНОСТlI
gJ
инеравенства
gj(XO)
>
О
ПрII
j
Ф
J(XO).
Выписанные
три
неравенства
противоречат
сла
бой
эффективности
хО.
СJIедовательно,
система
перапенств
(2)-
(3)
несовместна.
В
этом
СJIучае
по теореме
Моцкина
об
адьтерна
тиве
(§
2.2)
существуют
векторы
lt,
л
вида
(~t,
Л);;;'
О(тН)
И
такие,
что
имеет
место
равенство
(1).
Проверим
ВКJIючение
lt
Е
М.
Если
lt
=
О(т),
то
Л
>
>
Ощ
и
из
(1)
сдедует
равенство
~
Лj
(V gj
(х
О
),
;>
=
О,"
jEJ(XO)
противоречащее
неравепству
л
>Ощ
и
УСЛОВIIЮ
регуляр
ности.
Поэтому
lt
>
О(m),
а
значит,
можно
считать,
что
т
~
lti
=
1.
'Условие
слабой
эффеRТIШПОСТИ
ДОI,азано.
i=l
Теперь
пусть
ХО
Е
Gt(X).
Согдасно
теореме
1.14
ТОЧI{а
хО
является
слабо
эффы{тивпой
по
вентор-фунrщии
«lt\!(X»,
<lt
2
,j(x»,
...
,
<ltт,j(x»),
где
веI{ТОры
ltiEM
f26
vсnовия
ОПТИМАЛЬRОСТИ
(ГЛ.
2
имеют
вид
(1.14),
относительно
Х.
При
меняя
R
ТОЧRе
х
О
доказанное
необходимое
условие
слабой
эффективности,
- - k
получаем
существование
векторов
J,I.
е
М
и
л
Е
E~
таких,
что
1:
~;V
[
1:
J,I.;/r
(Х
О
)]
+
~
'}.,/V
gj
(х
О
)
=
О(n).
i=l
r=l
jEJ(~O)
Отсюда,
учитьшая
вид
(1.14)
векторов
J,l.f
и
условие
т
~
~i
=
11
после
несложных
преобразований
получим
(=1
т
.
1:
[~i
(1-
те)
+В]
V/
i
(х
О
)
+ }J
лjVg
j
(х
О
)
=
О(n).
i=1
jEJ(x
O
)
Вводя
вектор
!-1
с
l\омпонентами
J.tj
=
~j(
1 -
те)
+
е,
i =
=
1,
2,
...
,
т,
приходим
к
равенству
(1).
Jlешо
uроверить,
что
!-1
Е
М
.•
Из
ДОI\азательства
теоремы
видно,
что
в
случае,
когда
условие
регулярности
не
предполагается
выполпенным,
необходимое
условие
слабой
эффективности
будет
иметь
прежний
вид
(1),
однако
относительно
векторов
J.t
и л
будет
известно
только
то,
что
(J.t,
'}.,)
>
О(т+l<)
(так
что
MO~
жет
быть
J.t
=
О(т).
2.
Исследуем
вопрос
о
том,
когда
выполнение
равен
ства
(1)
влечет
слабую
эффективность,
эффективность,
и
собственную
эффентивность
решения
хО.
т
е
о
р
е
м
а
2.
Предположим,
что
MT-tOжество
D
вЫnУ1>
ло,
ве1>ТОР-фУli1>ция
/
'nсевдовогнута,
а
ве1>тор-фУН1>ция
g
n01>omnonehtt-tO
дифференцируема,
и
для
nаждого
j
Е
Е
J(XO)
фУН1>ция
gj
nвазивоmута.
Тогда
из
равенства
(1)
а
веnтором
J.t
е
М
следует
слабая
эффе1>тивность
ХО.
Д
о
к
а
з
а
т е
л
ь
с
т
в
о.
Предположим,
напротив,
что
найдется
такая
точка
х
l
е
Х,
что
/(х
1
)
>
/(хО).
(4)
Для
любого
j
е
J(XO)
выполняется
неравенство
(Vgj(XO),
х
l
-
х
О
)
~
о.
в
самом
деле,
если
это
не
тан,
то
благодаря
неравенству
(У'
gj(XO),
х
l
-
хО)
<
О
при
некотором
j
е
J(XO)
дЛЯ
всех
достаточно
малых
е
>
О
будем
иметь
gj(XO
+
е(х
l
-
х
О
»
= e(Vgj(xO),
х
1
-
хО)
+
о(е)
<
О.
с
другой
стороны,
посколь:ку
х\
е
Х,
то
gj(xll
~
о
= gj(XO),
§ 2,4]
ЗАДАЧИ
С
ДИФФЕРЕНЦИРУЕМЫМИ
Фуmщиями
127
а
так
как
функция
gj
квазивогпута,
то
для
любого
е
е:
е:
(О,
1)
справедливо
противоположное
неравенство
gj(X
O
+
е(х!-
хО»)
=
g;(1-
В)ХО
+
вх!);;:::
gj(XO)
=
О.
в
силу
ДОI\азаnного
ИЗ
(1)
следует
неравенство
т
~
Ili
(V/
i
(х
О
)"
х
1
-
х
О
)
<::
О.
{=l
Поскольку
Il
>
О(т),
то
ИЗ
этого
неравенства
вытекает
существование
такого
номера
t,
что
("V/I(xO),
х!
-
хО)
~
О.
Отсюда,
исполь~уя
псевдовогнутость
функции
ji,
получа
ем
неравенство
jj(X!) ::; NxO),
противоречащее
(4)
.•
Согласно
теореме
1.6.2
в
случае
выпуклого
множества
Х
И
строго
квазивогнутой
вектор-функции
j
слабо
эф
фективная
точка
всегда
является
эффективной.
Поэтому
ссли
к
предположениям
теоремы
2
добавить
строгую
ква
ЗIIВОГНУТОСТЬ
j
и
выпуклость
множества
Х,
то
равенство
(1)
при
1-1
е:
М
будет
гарантировать
эффективность
ХО.
Перейдем
к
собственно
эффективным
решениям
и
рас
С~IOтрим
следующий
При
М
е
р
1.
n =
1,
т =
2,
/1
(х)
=
х,
МХ)
=
е-Ж,
Х
=
=
(-
00, + 00).
Здесь
обе
функции
псевдовогнуты.
Для
эф
ФеI\ТИВНОЙ
ТОЧIl:И
хО
=
О
равенство
(1)
выполняется
при
1-11
=
1-12=
1/2:
I-1l
v
fl(хО)
+
I-1z
V
МхО)
= 1/2 . 1 + 1/2 .
(-1)
=
О.
Однако
она
не
является
собственно
эффективной,
так
как
при
x
h
= k, k =
1,
2
...
,
имеем
11
(x
ll
) -
11
(х
О
)
12
(х
О
)
-
12
(х")
k
---,я,..-
-+
+
00.
1 -
е-
Я~ОО
Пример
покаЗЫВRет,
что
в
предположении
псевдовог
нутости
необходимое
условие
собственной
эффективно
СТИ
теоремы
1
при
1-1
е:
М
не
будет
достаточным.
Поэтому
от
функции
I
нужно
потребовать большее,
чем
псевдо
вогнутость.
т
е
о
р
е
м
а
3.
П
редnоложuм,
что
век.тор-фуnrщuя
f
nOl>O.~monenTп0
дuффереllцuруе,м,а
в
точк.е
хО
Е
Х U
вог
нута, а
век.тор-фуnк.цuя
g
nок.о,млонеnтно
дuфференцuру
е.ма
и
для
любого
t
е:
J(XO)
к.вазuвОг1ч;та.
Тогда
eblnO/lflC-
128
условия
ОПТИМАЛЬНОСТИ
[гл.
2;
llue
paeellCTea
(1)
при
J.t
Е:М
обеспечивает
собствеllllУЮ.
эффектив1l0СТЬ
хО.
Д
о
1\
а
з
а
т
е
л
ь С
т в
о.
Рассмотрим
С1\алярную
фунrщию
F(x)
=
<J.t,
/(х).
Условие
(1)
можно
переписать
так:
V F
(х
О
)
+
~
лjV
gj
(х
О
)
=
О(n).
jEJ(XO)
Благодаря
вогнутости
f
фунrЩИЯ
F
та1\же
вогнута,
э
ЗИЭ·
чит,
псевдовогнута.
Поэтому
по
теореме
2
при
т
= 1
по
..
лучаем,
что
фУН1\ЦИЯ
F
достигает
своего
МЭI,симального
значения
на
множестве
Х
J3
ТОЧl,е
ХО.
В
этом
случае
сог
ласно
следствию
1.5
ТОЧ1\а
хО
собственно
эффентивпа
.•
При
м
е
'1
а
н
и
е.
Впервые
условие
оптимальности
ти~
па
(1)
встречается
еще
у
Х.
Куна
и
А.
Таккера
[187].
Оно
было
получено
применительно
к
понятшо
собствен
ной
эффективности,
введенного
ими
и
использующего
свойство
дифференцируемости
/
и
g.
Достаточное
УСЛ0
4
вие
Куна
и
Таннера
требовало
вогнутости
f
и
g.
У
словия
оптимальности,
не
предполагающие
выполне
ния
условий
регулярности,
получены
в
[110].
§
2.5.
У
словин
оптимальности
второго
ПОРЯД1\а
Рассмотрение
этого
параграфа
ограничивается
задачей
многонритериальной
оптимизации
без
ограничений,
т. е.
считается,
что
Х
= D =
Еn.
BeKTOP-фУН1\ЦИЯ
/
предполага
ется
пономпонентно
дважды
дифференцируемой
в
рас
сматриваемой
точне
хО
Е
Еn.
Через
\12/;(хО)
обозначается
гессиан
функции
/;,
вычисленный
в
ТОЧ1\е
хО:
V
2
/i
(х
О
)
=
11
a:~h~::)
11"
k,
j =
1,
21
..
" n.
В
формулировках
необходимых
И достаточных
УСЛОВИЙ
оптимальности
будет
участвовать
множество
К(хО)
= {z
Е
Еn
I
<У'
!i(XO),
z>
S;;
О,
i =
1,
2,
...
,
т}.
Очевидно,
К(хО)
-
выпуклый
заМ1\НУТЫЙ
1\ОНУС
С
верши
ной
в
начале
ноординат.
1.
Необходимые
условия
второго
порядка
слабой
эф
фентивности
в
многокритериальной
задаче
без
ограниче
ний
представлены
в
следующей
теореме.
§ 2.5]
УСЛОВИЯ
ВТОРОГО
ПОРЯДНА
129
Т
е
о
р
е
м
а
1.
Для
того
чтобы
решение
х
О
было
слабо
эффеnтивным
по
веnтор-фуnnции
!
относительно
Еn,
не-
06ходи.мо
выполнение
следующих
соотношений:
т
~
f1i'V!i
(хО)
=
О(n)
для
неnоmорого
f1
Е
М.!)
(1)
i=l
min
ZV2!i
(XO)z
<::
О
iellI
для
всех
z
Е
К
(хО).
(2)
д
о
к
а
3
а
т е
л
ь
с т
в
о.
Равенство
(1)
следует
ИЗ
тео
ремы
4.1.
Для
ДОI,азательства
неравенства
(2)
возьмем
произвольный
вектор
z
Е
К(х
О
).
Если
ДЛЯ
него
неравен
ство
(2)
не
выполняется,
то
ZV
2
/
i
(X
O
)z
>
О
для
всех
i
ЕМ.
Так
как
Z
Е
К(х
9
),
то
для
любого
(J)
Е
(О,
1)
справедшlВО
2
(J)
(V!i
(х
О
)l
z)
+
~
zV
2
fi
(хО)
Z >
О
для
всех
i
Е
111.
Положим
х'
=
х
О
+
(J)Z,
(J)
Е
(О,
1).
Тогда
для
достаточно
малого
положительного
(J)
будет
выполнено
1
fi
(х')
- !;
(хО)
= (V!i
(х
О
),
х'
-
хО)
+ 2
(х'
-
хО)
Х
Х
V2/
i
(х
О
)
(х'
-
хО)
+
0i
«(U2)
>
о
для
всех
i
Е
111,
где
величина
о;(т2)
такова,
что
о;(ф2)/т2
-+
о
при
(J)
-+
о.
Полученные
неравенства
противоречат
слабой
эффекПIВ
IJОСТИ
решения
хО
••
2.
Решение
х
о
Е
Х
называется
лоnально
эффеnтивНЫN,
ссли
существует
такая
онрестность
В(х
О
)
ТОЧRИ
хО,
что
х
о
эффеRТИВНО
по
f
относительно
множества
Х
n
В(х
О
).
Решение
х
о
Е
Х
называется
[223]
строго
эффеnти8Нbl.ч
по
!
относительно
Х,
если
из
соотношений
f(x)
~
!(хО),
х
Е
Х,
следует
равенство
х
=
хО.
т
е
о
р
е
м
а
2.
Пусть
для
неnоторого
f1
Е
М
выnолн:~
еrся
(1).
Если
К(х
О
)
=
{О(n)}
или
minzV2!i(XO)Z<O
для
всех
zEK(xU)""-{О(n)},
(3)
iElIf
o
где
Mo={iEMIf1;>O},
то
х
О
является
локальным
строго
эффективным
решеТ-tUе.~t
по
!
относительно
Еn.
Д
о
R
а
з
а
т
е
л
ь
с т
в
о.
Предположим,
напротив,
что
х
О
Не
является
ЛОRальпым
строго
эффеRТИВНЫМ
решением.
1)
Б. Б.
ПОДIlНОВСНIIit,
в.
д.
Ногин
130
УСЛОВИЯ
ОПТИМАЛЬНОСТИ
[ГЛ.
2
Тогда
существует
такая
последовательность
точек
{x
1
}
с:
c:E",x1+-хО,
1-1,
2,
..
"
что
!
(x
l
)
:>
f
(ха),
Нт,х'
=
х
О
,
(4)
1-.""
Рассмотрим
последовательность
1 _
x1_xO
Z -
11
%1
_
ха
11
t 1 =
11
2}
, , •
Из
этой
последовательности
всегда
можно
выделить
схо
дящуlOСЯ
подпоследовательностъ,
Поэтому
будем
СЧlIТать,
что
сходится
саыа
эта
последовательность;
Нт
Zl
=
Z01
11
ZO
11
=
1,
1 ... ""
Обозначим
Ю/
=
IIх'
-
xOll,
Тогда
Ф,
-+
О и
х
1
=
х
О
+
CJ)/z',
В
силу
дифферепцируемости
f.<x/)
- f;{xO) +
CJ),<Vj.(XO),
z/)
+
о.(ю,)
для
всех
i
е
М,
Отсюда
благодаря
(4)
для
достатс,чно
большого
N
,
сле
дует
< V
МхО),
z/)
~
О,
1
0=
N
t
,
N
,
+
1,
,."
длп
всех
i
Е
111,
т. е.
z/
е
К(хО),
t = N
"
N
,
+
1".,
Следовательно,
ZO
е
К(хО).
Равепство
К(х
О
)
=
{Ор)
противоречит
тому,
ЧТО
ZO
е
Е
К(хО)
И
OzOIl
=
1.
Пусть
К(хО)
+-
(О'n)}
и
имеет
место
(3),
Для
любого
t
е
М
О
и
каждого
z
е
К(х
О
)
справедливо
ра
венство
<V!,(XO),
z) =
о.
Действи-гельно,
если
<Vf,(xO),
z')
>
,)t
>
О
при
некоторых
i
е
М
О,
z'
Е
К(х
О
},
то
~
~ti
(У'
fi
(ха),
;=
1
z')
>
О,
что
ПРОТlIворечит
(1),
Поэтому
имеет
место
пред
стаВJlение
для
всех
i
е
М
о
,
1 = N
t
,
N
t
+
1,
,.,
Отсюда
благодаря
(4)
для
достаточного
большого
N%
имеем
z
Iоу
2f,(xO)ZI
:=:::_
о,
1 N
11.1
+ 1
=
2,
На
I
...