Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§
4.4]
ЛИНЕйНЫй
СЛУЧАй
221
Выше
в
примере
2
было
показано,
что из
существова·
ния
допустимых
решений
в
прямой
задаче
А
и
в
двой
ственной
задаче
А,
вообще
говоря,
не
следует
существова
ние
оптимальных
решений
в
этих
задачах
(т. е.
из
Q::f=
fZJ
и
H::f=
0
не
следует
неравенство
Мах
Q
::f=
0
или
Min
Н
::f=
::f=
0).
В
этом
смысле
двойственная
задача
А
1
обладает
тем
преимуществом,
что
из
наличия
допустимых
решеннй
в
прямой
задаче
А
и
в
двойственной
задаче
А
1
всегда
сле
дует
Мах
Q = Min Н
1
::f=
0.
Рассмотрим
ПРIIмер,
иллюстрирующий
результаты
тео·
ремы
3.
При
1>1
е
р
3.
Пусть
в
линейной
задаче
А
n =
6,
т
= 4,
k=3и
('
о о
о
-1
-~)
С=
о
1
О
О
О
О
О
-1
О
О
О
'
О О
1 1
1
О
С
о о
-1
О
-
2)
Ь
=
(~).
А=010
202,
О О
1 2 5
О
Здесь
прямая
задача
будет
IIметь
следующий
вид:
-
най
ти
множество
максимальпых
векторов
среди
всех
векто
ров
q = (ql'
qz,
qз,
q.),
удовлетворяющих
условиям
ql
~
Х\
-
Хб,
qz
~
Х2
-
Х"
qз
~
-Х3,
ql.~X8+X~+XS,
Х
1
-
Х.
-
2Ха
~
5,
Х2
+
2х.
+ 2x
s
~
3,
Ха
+
2х.
+
5Х
б
::::
5,
XI,
X
z
,
•••
,
Ха
~
О.
(9)
В
этой
задаче
10
переменных
и
7
ограничений
в
фор~[е
неравенств
(не
считая
неравенств
ХI
~
О).
Двойственная
задача
А
1
принимает
вид:
найти
мно
жество
минимальных
векторов
среди
всех
векторов
lt
=
222
ДВОйСТВЕННЫЕ
мноtО1<РйТЕРПАЛЬНЫЕ
ЗАДА
ЧП
[ГЛ.
4
....
(h",
h
z
,
h
з
,
h~),
удовлетворяющих
условиям
J,tl
h
l +
J,t
2
h
2
+
J,t.h.
+
J,t.h,
е;
5ЛI
+
ЗЛz
+ 5}v.,
Лl
;;::::
J,tt,
Л2
s1:;
J,tz,
л.
ii;: -
J,t.
+ J,t.,
-1..1
+
2Л2
+
2Л.
е;
J,t.!
5
л
s
е;
-
J,t1
+ J,t.,
-
2Лt
+
21.2
е;
-
J,t2,
J,tl
+
J,tz
+
J,ts
+
J,t.
=
1,
J,tl'
J,t2,
J,ts,
J,t.
>
О;
1..1,1.2,
Лз
е;
О.
(10)
в
этой
задаче
11
переменных
h
"
•..
, h.,
J,tt,
•••
,J,t.,
Лl,
•••
. . "
Л
•.
Но
так
как
переменпые
/-1-1,
/-1-2,
/-1-.,
/-1-.
связаны
ра-
4&
венством
~
JLi
-=
1,
то
независимых
переменных
10.
i-l
Нетрудно
проверить,
что
значения
/-1-"
-
JLa
-/-1-.-/-1-.
==
1/4,
ЛI
=
ЛZ
= 1/4,
ЛЗ
=
О
удовлетворяют
всем
условиям
(10),
не считая
первого
неравенства.
Следовательно,
Н
1
=1=
>О.
А
так
как
Q
=1=
>О,
то
согласно
теореме
3
Мах
Q = Min
Н
•
= Q n
Н
•.
Таким
образом,
множество
эффеI{ТИВНЫХ
оценок
исход
ной
задачи
в
точности
совпадает
с
мношеством
венторов
q,
удовлетворяющих
одновременно
неравенствам
(9)
и
соотношениям
(10),
где
в
первом
перавенстве вместо
h.
стоит
q"
i
"'"
1,
2,
.•.
, 4.
Рассмотрим
решение
хО
= (5, 3, 5,
О, О,
О),
qO
=
-
(5,
3,
-5,
5).
Оно
является
допустимым
в
прямой
зада
че,
т. е.
qO
е
Q.
Нроме
того,
видно,
что
для
упомянутых
выше
значений
/-1-1,
••• ,
/-1-.,
Лl,
Л2,
Л.
выполняется
и
пер
вое
неравенство
в
(10):
1 1 1 1 1 1
-,,5
+
,.8
- "4'5 +
4·5
s;::
5'4
+
8'4'
Следовательно,
qO E!i Q n H
1
•
Поэтому
рассмотренное
реше
ние
является
эффективным.
Пусть
Х
....
0(8)'
q -
0(6)'
Это
решение
является
допу
стимым
в
прямой
задаче,
но
для
него
первое
неравенство
в
(10)
может
иметь
место
лишь
при
1..1'"
л2
....
ла
....
О.
Тогда,
например,
второе
неравенство
в
(10)
примет
вид
О
iiE:
/-1-1,
чего
быть
не
должно.
Следовательно,
q =
0(6)
Ф
H
1
,
Т.
е.
оценка
q
не
является
эффективной.
§
Н]
ЛИНЕйНЫй
OJIучла
223
4.
В
этом
пункте
будем
рассматривать
прямую
задачу
В
(т. е.
задачу
с
ограничениями
в
форме
равенств).
На
помним
ее
формулировку:
найти
множество
Мах
Q,
где
Q
вида
(1),
а
Х
определяется
равенством
(3).
Двойственная
задача
В
I
в
этом случае
заключается
в
нахождении
множества
Min Н
1
при
Н
1
= u u
{h
е
cn
I «(1, h)">
('А,
Ь)},
А
j.L
где
объединение
берется
по
всем
векторам л
Е
Е
"
И
(1
Е
М,
дЛЯ
которых
выполняется
неравенство
л.А
~
(1С.
Если
для
некоторого
j =
1,
2,
.•
" k
выполняется
b
J
<
О,
то
умножением
j-ro
равенства
в
системе
Ах
=
Ь
на
-1,
придем
к
системе
с ь;
= - b
j
>
О.
Поэтому,
не
уменьшая
общности,
далее
будем
считать,
что
Ь
6;
Ощ.
Введем
множество
H
2
=U U
{heEmlh">Ub},
-и
11
где
U -
числовая
матрица
размера
т
Х
k
и
объединение
берется
по
всем
U
и
(1
Е
М,
дЛЯ
которых
выполняется
пе
равенство
(1ИА:<?:: (1С.
Покажем,
что
при
незначительных
предположениях
введенное
множество
H
z
совпадает
с
H
1
•
Если
h
Е
lI
з
,
то
по
определению
множества
Нз
имеем
(11)
для
не
которой
матрицы
U
и
некоторого вектора
(1
Е
М.
Положим
(1и
=
л.
Е
Е".
Тогда
(12)
т.
е.
h
Е
Н!.
Включение
Н
2
s=;
Н
I
доказано.
Пусть
h
Е
Н!,
т.
е.
имеет
место
(12).
Покажем,
что
найдется
матрица
и,
для
которой
справедливо
(11).
Сна
чала
рассмотрим
случай,
когда
</t,
h>
=
<1..,
Ь>.
Вектор
л
всегда
можно
представить
в
виде
- -
1../
=
1..0
+
б
i
,
i =
1,
2,
...
,
kj
б
l
==
О,
где
ба,
15з,
••
I
б
ll
-
некоторые
числа.
Предположим,
что
224
ДВОйСТВЕННЫЕ
МНОГОНРИТЕРIЦЛЫIЫЕ
ЗАДАЧИ
[ГЛ.
4
k
~
bj
=F
О
п
введем
матрицу
j=1
где
k
k
i
-
~
бjЬj
j=2
Ui
=
---"'k--"---
~
Ь
;
0=1
i = 1,2,
.•.
,
т.
Нетрудно
убедиться
в том,
что
ДЛЯ
9ТОЙ
матрицы
ира.
венство
h =
ИЬ
выполняется.
Остается
проперить
спра
ведливость
равенства')..
=
JtU.
Дойствительно,
для
каждого
j =
1,
2,
.•.
, k
имеем
т
k
т
,.,
't.ll.
-
~
б
Ь·
-'.1'11
-'.11]
')..j
= I
JtiUi
+
бj
=
i=1
k
i=2
t=1
~
Ь
-'.1 ,j
j=1
h k
~
ЛiЬi
-
~
бjЬi
i=1
j=2
-
1,
~
Ь
;
j=1
В
соответствии
с
доказанным
для
данной
матрицы
U
в
случае
<Jt,
h>
=
<')..,
Ь>
из
(12)
следует
(11),
т. е.
I1
1
5
НЗ'
Теперь
пусть
<Jt.
h>
>
<')..,
Ь>.
В
силу
/.1.
>
О(т)
суще
ствует
такой
вектор
h'
Е
Ет,
что
(/.1.,
h')
=
<')..,
Ь)
и
h'
<
h.
Согласно
доказанному
выше
h'
Е
Н
2
•
Поэтому
И
h
Е
Н
2
•
Сформулируем
полученные
результаты
в
следующей
лемме.
Л
е
м м
а
4.
Справедливы
утверждeuия:
1)
Н
2
5 H
1
;
2)
если
ь;;:;::=
О(л)!
ТО
Н
2
= H
1
•
:Как
показывает
нижеследующий
прпмер
условие
Ь
>
O(~)
в
ле}lме
4
является
существенным.
I
Н)
ЛИНЕйНЫй
сmтЧАй
При
м
е
р
4.
n =
2,
т
=
2,
k = 1
И
С
=
(:
_
~),
А
=
(1
О),
Ь
=
О.
в
силу
Ь
=
О
имеем
Н
2
=
Е;
так
как,
например,
для
l1
=
=(1/2,
1/2)
и
U =
(~)
,Вьшо;няется
равенство
I1UA
...
f.1C.
Однако
Н
1
:::/=Е;.
В
самом
деле,
например,
(1,
-1)еН
1
,
так как
для
;t:
=
f.12
=
1/2,
л.
= 1
справедливо
(~
~)(_~»1.0,
1·(1
O)~(;
~)C
_~).
Таким
образом,
прямой
задаче
В
можно
сопоставить
следующую
двойственную
задачу.
Д
в
о
й
с
т
в
е
н
Н
а
я
з
а
Д
а ч а
В
2
•
Найти
множество
blin
Н
2
•
Связь
между
прямой
задачей
В
и
двойственной
зада
чей
В
2
устанавливает
следующая
теорема,
которая
следу
ет
непосредственно
из
теоремы
3
и
леммы
4.
Т
е
о
р
е
м
а
4.
Пусть
Ь
>Ощ.
Следующие
утвержде-
ния
эnвивалентны:
1)
Q
=1-
f2J,
Н
2
'=1=
f2Jj
2}
Мах
Q
'=1=
f2J;
3)
Min
Н
2
'=1=
f2J
j
4)
Мах
Q = Min
Н
2
= Q n
Н
2
'=1=
f2J.
Докажем
вспомогательное
утверждение.
Л
е
м м
а
5.
Следующие
два
условия
эnвивалентны:
1}
f.1UA
6;
f.1C
для
He1i,OTOpOeO
Il
е
М;
2)
ИАШ5СШ
для
всех
ШЕЕ~.
Д
о
к
а
з
а
т
е
л
ь
с т
в
о.
Услов;е
2)
означает
несовме
стностъ
системы
линейных
неравенств
(С
- U
А)
ш;;;; О(т).
w >
О(n).
По
теореме
Таю,ера
об
алыернатиue
(§
2.2)
это
имеет
место
тогда
и
только
тогда,
котда
существует
такой
BeK~
тор
f.1
е
1\1,
что
ПРИ
ПСI\ОТОРОМ
z
БОРНО
J.tC
-
f.1U
А
+ z =
О(n"
Z G
0(1))-
Последнее
эквивалентно
условию
1)
.•
15
в. в.
ПОДИНОВСНliJ!,
в.
д
Нотаи
226
ДВОЙСТВЕННЫЕ
МНОГОRРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ
&
в
соответствии
с
этой
леммой
множество
На
допуска·
ет
представление
Н
2
=
~
{l~
>
ИЬ
I
ИАШ5
Сш
для
всех
шЕ
E~}.
Оказывается,
мпожество
минимальных
элементов
мно
жества
На
совпадает
с
множеством
минимальных
элемен
тов
следующего
мпожества:
НЗ
= U
{h
Е
Ет
I h =
иь},
и
где
объединение
берется
по
всем
U
ТaIШМ,
ЧТО
и
Аш
>-
5СШ
дЛЯ
всех
w
Е
E~,
т. е.
имеет
место
равенство
Min
Н!
...,
Min
Нз.
(13)
Проверим
это
равенство.
Согласно
лемме
5 MHOiI,e-
ство
НЗ
МОrIШО
пгедставить
в
виде
Нз
= U U {h
Е
Ет
I h =
иь},
и
11
(14)
где
объединенпе
берется
по
всем
и
II
~t
Е
М,
дЛЯ
которых
выполняется
неравенство
~ИА
~
~C.
Если
h
Е
Min
Па.
то
в
силу
минимальности
элемента
h
имеем
h =
иь,
~tUA
> /lC
дЛЯ
некоторой
матрицы
U
и
не
которого
вектора
~t
Е
М.
Следовательно,
h
Е
П
З
•
Но
Нз!;;
Н
2
,
И
поэтому
h
Е
Min
П
З
•
Если
h
Е
Min
Нз.
то
h
Е
Н
2
•
Пусть,
например,
суще
ствует
такой
элемент
h'
Е
Н
2
,
что
h'
<5
h.
Тогда
U'b~h'
<h
для
такой
матрицы
И',
что
~И'А
~
~C
при
некотором
~
ЕМ.
и'ь
Е
П
з
,
а
значит
элемент
h
не является
мини
мальным
элементом
множества
Нз.
Равенство
(1З)
дока
зано.
Введем
следующую
двойственную
задачу,
эквиналент
ную
двойственной
задаче
Е
2
•
Эту двойственную
задачу
ввел
Г.
Изерман
[173,
175,
176].
Д
в о
й
с т
в
е
н н
а
я
з
а
Д
а
ч
а
Е
з
•
Найти
множество
МiпН
з
•
Т
е
о
р
е
м
а
5.
Предnоложи)t,
что
Ь?.
Ощ.
Следующие
утверждения
эnвивалентны;
§
&.4]
ЛИНЕйНЫй
СЛУЧАй
227
1)
Q
=1=
rгJ,
На
=1=
rгJ;
2)
Мах
Q
=1=
rгJ;
3) Min
11
з
=1=
rгJ;
4)
Мах
Q =
Min
Нз
= Q n
п
з
=1=
rгJ.
Д
о
к
а
а
а
т
е
л
ь
с т
в
о.
Легко
понять,
что
Нз
=1=
rгJ
тог
да
и только
тогда,
ногда
Н
J
=1=
rгJ.
Поэтому
утверждение
1)
данной
теоремы
равносильно
утверждению
1)
теоре
мы
4.
Согласно
равенству
(13)
утверждения
3)
данной
теоремы
и
теоремы
4
таЮI\е
равносильны.
Остается
про
в\)
рить
эквивалентность
утверждений
4).
Если
имеет
MeCTt)
4)
теоремы
4,
то
в
силу
(13)
Мах
Q =
lШп
На
и
Q n Н
2
s;
s;
Q n
На.
Но
так
как
Нз
s;
Н
2
,
ТО
Q n
На
s;
Q n Н
2
•
Поэто
му
Q n
Н
2
= Q n
Нз.
Обратно,
если
имеет
место
4)
данной
теоремы,
то
справедливо
Мах
Q
=1=
)о,
ОТI,уда,
согласно
теореме
4.
следует
утверждение
4,)
теоремы
4
.•
Рассмотрим
следующий
иллюстративный
пример.
При
м
е р
5.
Пусть
в
Лllнейной задаче
В
маТРИЦJ,}
С,
А
и
вектор
Ь
такие
iI\e,
как
в
примере
3.
Выпишем
пря
мую
задачу:
найти
мношество
максимальных
векторов'
среди
всех
выпоров
q =
(ql'
q2,
qз,
qJ,
удовлетворпющих
условиям
ql
~
Х,
-
Х5,
q2
~
Х%
-
Х
6
,
qз
~
-Ха,
q.
~
Ха
+
Х.
+
Х"
ХI
-
Х,
-
2Х
6
= 5,
3'2 +
2х,
+
2Х
6
= 3,
Ха
+
2х.
+
5х,
= 5,
X
1
,
Х
2
,
•••
,
Х6
~
О.
Двойственпая
задача
8
а
с
множеством
Нз
вида
(14)
формулируется
СJIедующим
образом:
найти
множе
ство
мишшальных
векторов
среди
всех
векторов
It
=
=
(h
"
h
2
,
h
з
,
h,),
удовлетворяющих
УСЛОВИЯll1
h
,
=
5ив
+
3U
l
2
+
5u
,з
,
h
2
=
5и21
+
ЗU
Z
2
+
5L~2З,
h
з
=
5UЗI
+
ЗUЗ2
+
5U
з
а,
h, =
5ив
+
ЗU.2
+
5u.з,
228
ДВОЙСТВЕННЫЕ
МНОГОНРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ
4
~IUII
+
~2и21
+
~ЗUЗI
+
~~иH
е;
~I,
~IUI2
+
~2и22
+
~ЗUЗ2
+
~.и'2
~
~z,
~IUI3
+
~2и23
+
~зUзз
+
~~Utз
~
-~3
+
~.,
~I(-
ин
+
2n12
+
2n
1з
)
+
~2(-и2!
+
2и2а
+
2
u
z
з
)
+
+
~З(-U31
+
2
u
зz
+
2ll
зз
)
+
~t,(-UH
+
2и'2
+
2u~з)
?
~.,
5~ln13
+
5~2и23
+
5~зuзз
+
5~~иa
;;:;::
-~I
+
~"
~1(-2U1I
+
2Ll12)
+
~2(-2и2I
+
2и22)
+
~з(-2u3I
+
2UЗ2)
+
+
~,(-2uи
+
2иа)
е;;
-
~2,
~I
+
~2
+
~з
+
~,
=
1,
~I, ~2,
~з,
~,
>
О.
Нетрудно
проверuть,
что
значения
~I
=
~2
=
~з
=
~,
=1/4,
и.,
=
1,
i =
1,
2,
3,
4;
j =
1,
2,
3,
удовлетворяют
всем
условиям
в
двойственной
задаче.
Поэтому
Нз
=1=
{О,
а,
значит,
Мах
Q = Min
Нз
= Q n
Нз.
Рассмотрим
допустимое
для
прямой
задачи
решеипе
х
О
=
(5,
3,
О, О,
1,
О),
qO
=
(4,
3,
О,
1).
Для
того
чтобы
представить
вентор
qO
В
виде
qO
=-
иь,
можно
взять
(
1 - 1/3
О)
О
1
О
и=
О О
О'
О
1/3
О
Нетрудно
проверить,
что
для
этих
значений
коэффициен
тов
матрицы
U
и
дЛЯ
~I
=
~2
=
~з
=
~,=
1/4
все
условия
в
двойственной
задаче
выполнены.
Следовательно,
х
О
_
эффективное
решение,
а
qO
-
его
эффеI\тивная
оценна
ис
ходной
прямой
задачи.
Матрица
и,
I\оторая
участвует
в
формулировках
двой
ственных
задач
В
а
ИВа,
ДОПУСI\ает
простую
интерпрета
цию
в
терминах
многокритериального
симплекс-метода.
Однано,
прежде
чем
дать
эту
интерпретацию,
наПОМНИ'1
некоторые
понятия,
связанные
с
обычным
симплекс
методом.
§
Н)
ЛИНЕйНЫй
СЛУЧАй
229
Пусть
система
ограничений
сналярной
задачи
линеii
ного
программирования
(С,
х)
-+
ma"'t',
Ах=Ь,
ХЕЕ;',
танова,
что
rang
А
= k
(т.
е.
«лишние»
уравнения
уже
исключены)
и
Ь
~
О(/<).
Предположим,
что
х
О
-
неноторое
допустимое
базисное
решение
системы
линейных
уравне
пий
Ах
=
Ь.
Без
потери
общности
можно
считать,
что
первые
1
(1
s k)
компонент
вектора
х
О
положительны,
а
остальные
раппы
нулю.
Согласно
определению
базис
ного
решения
первые
1
вектор-столбцов
матрицы
А
ли
нейно
независимы.
Поскольку
rang
А
==
k,
то
найдутся
такие
k
-1
вектор-столбцов
матрицы
А,
которые
вместе
с
1
первыми
образуют
линейно
независимую
систему.
Можно
считать,
что
такую
линейно
независимую
систему
составляют
первые
k
вектор-столбцов.
Обозначим
матрицу,
I\ОТОРУЮ
опи
составляют,
через
Ав,
а
оставшуюся
«часты
матрицы
А
-
через
A
N
•
Введем
также
обозначения
ХВ=
(Xj,
Xz,
•••
,
ХА)'
x
N
=
(XHj,
••.
,
х
п
).
В
этих
обозначениях
систему
линейных
уравнений
Ах
=
=
ь
можно
занисать
в
виде
Авхв+
ANXNi=
Ь.
Умножая
данное
равенство
слева
на
матрицу
Ав!
(заме
тим,
что
в
силу
rang
А
II
==
k
такая
матрица
существует),
получим
систему
линейных
уравнений
ХВ
+
AB
l
A
N
xN
=
А
в
1
Ь,
(15)
раппосильную
исходной.
Теперь
преобразуем
целевую
ФУНIЩИЮ
(С,
Х)
тю:,
чтобы
в
нее
не
входили
базисные
перемепные
Х\,
Xz,
•••
,
X~.
ДЛЯ
этого
равенство
(15)
скаЛЯРНQ
умножим
на
вектор
СВ
=
(cj,
Cz,
••.
,
C~)
и
найдеh1
(Св,
ХВ)
= -
(Св,
AjJ
1
Aj\XN) +
(Св,
ABlb).
Далее,
обозначая
CN
=
(cHI,
••.
,
Сп)
11
учиrывая
найден
ное,
можно
занисать
(С
,
Х)
;;;
(Св,
ХВ)
+ (CNI
XN)
:;;; (CN - c
B
AB
l
A
N1
XN>+
+
с
в
АВ"
l
Ь.
230
ДВОйСТВЕННЫЕ
МНОГОRРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ.
~
Исходя
из
полученного
представления
целевой
фУШЩИJI,
легко
прийти
к
следующему
выводу: если
выполняется
неравепство
(16)
то
переход
от
х
О
к
новому
допустимому
базисному
реше
пию
не
приведет
к
увеличению
значения
целевой
фуш.:
цИИ
<С,
х
О
),
т.
е.
решение
Х
О
будет
оптимальным.
Следо
вательно,
неравенство
(16)
представляет
собой
УСЛОВIIе
оптимальности
допустимого
базисного
решения
Х
О
•
Лепю
понять,
что
(16)
можно
записать
в
следующем
эквива
лентном
виде:
(с
в
А
в
1
А
-
с,
х):>
О
для
всех
хЕ
E~.
(17)
Посмотрим
теперь,
какой
вид
нримет
условие
6пти
мальности
(эффективности)
(17)
в
задаче
с
прежней
си
стемой
ограничений,
но
с
векторной
целевой
фушщией
Сх.
ПО
аналогии
с
вышеприведенным
через
СВ
обозначим
матрицу
из
вектор-столбцов
матрицы
С,
отвеч.ающих
ба
зисным
перемепным,
а
через
C
N
-
матрицу
из
вектор
столбцов,
отвечающих
небазисным
переменным.
Исполь·
зуя
равенство
(15),
находим
Свхв
= -
CвAi
1
A
N
XN
+
С
в
Ав
1
ь,
и
поэтому
можно
записать
Сх
=
Свхв
+
CNXN
=
(C
N
- C
B
A
B
1
A
N
)
XN
+
С
в
А
В
1
ь.
Отсюда,
так
же
как
и
в
случае
одной
целевой
функции,
приходим
к
выводу,
что
базисное
решение
х
О
будет
эф·
фективным,
если
(C
N
- C
B
AB
l
A
N
)
XN
<::
О(т)
ДЛЯ
всех
XN
Е
Er
k
•
Это
эквивалентно
следующему
УСЛОВИЮf
(CbAb1A-С)Ш:>О(т)
для
всех
ШЕЕ~.
Последнее,
согласно
лемме
5,
равносильно
существова·
нию
такого
вектора
~t
Е
М,
что
Полученное
неравенство
есть
Ilе
что
иное,
как
условие