Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
§ 4.3]
ВОГНУТЫй
СЛУЧАй
211
гнутости
И
дифференцируемости
gj
имеем
(V
gkxO) ,
х
-
хО)
ii:
gj(x)
-
gj(XO)
>
О,
что
означает
выполнение
условия
регулярности
из
усло
вий
теоремы
2.4.1.
Применяя
эту
теорему
при
т=:"
1
к
точке
максимума
хО
функции
(J.I..,
f(x»,
для
некоторого
л
Е3
E~
получаем
V",,2'(J.I.·,
хО,
л)
=
О(n),
(Л,
g(XO»
==
О.
Кроме
того,
в
силу
(8)
и
(15)
имеем
(J.I."',
h)
>
(J.I.'",
f(x()))
=
,2'(J.I.",
хО,
л).
Это
вместе
с
(14)
влечет
heH
t
••
(14)
(15)
При
м
е
ч
а
н
и
е
1.
В
теореме
4
условие
регулярно
сти
нужно
было
'Для
того,
чтобы
из
равенства
(J.I.
6J
1 f
(х
О
)
>
==
=
тах
(J.l.O)l
f
(х»
с
помощью
теоремы
2.4.1
получить
lteX
(14)
и
(15).
в
линейном
случае,
т. е.
когда
D =
Е",
/.-
линейные,
а
gj
-
аффинные
функции,
равенства
(14)
и
(15)
можно
получить,
используя
теорему
2.2.7
(при
т
.....
= 1),
в
которой
условие
регулярности
отсутствует.
Кроме
того,
в
линейной
задаче
множество
Q
полиэДралъно, так
как
представляет
собой
раЗRОСТЬ
двух
поJiиэдральных
множеств
(см.
представление
(2.7),
теорему
19.3
и
след
ствие
19.3.2
из
[93]).
Если
оно
полиэдрально,
значит
зам
кнуто.
Следовательно,
в
линейной
задаче
равенство
(13)
справедливо
лишь
в
предположении
Q
=1=
0
и Н.
+
0.
Ранее
было
установлено
включение
Н
!
s;;;
Н. Следова
теЛЬRО,
intH
I
S=intH.
Если
же
heintH,
то
благодаряте
ореме
1.1 h
Ф.
Q.
Отсюда
в
силу
(1З)
следУет
h
е
Н
!
и,
бо
лее
того,
так
как
Q
замкнуто,
то
h
е
int
Н
I
•
Таким
обра
зом,
если
выполнено
условие
регулярности
Слейтера
и
Н
I
+0,
то
int
Н
I
..... int
Н.
СледУет
отметить,
что
здесь
(а
также
в
Формулиров
l\e
теорв.:иы
4)
условие
Н
I
+ 0
существенно.
Об
<lТОМ
го
ворит
следУЮЩИЙ
При
м
е
р
2.
т'"
2,
n = k
==
1,
/1
(х)
!':'
Х,
[а(х)
-
О,
g\(x)=x.
3десь
Q={qeE
2
Iq2::5:
О}
и
H-{hеЕ
\hj>O},
14-
212
ДВОйСТВЕННЫЕ
МНОГОИРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ.
6
а
равенство
(10)
имеет
вид
/.11
+
ЛI
=
О.
Но
чисел
/.11>
О
и
1.1
~
О,
которые
удовлетворяли
бы
последпеМl
равепству,
не
существует.
Поэтому
Н
1
=
О,
так
что
<!
u
Н.
=1=
Е2
И
int
Н
1
+
int
Н.
Соотношение
между
собственно
эффективными
точ
ками
множества
Q
(тем
самым,
и
точками
множества
G
(У»
и
точками
множества
Min
Н
1
устанавливает
Т
е о
р
е
м
а
5.
Пусть
выполнено
условие
регулярности
Слейтера
и
множество
Q
аамlШУТО.
Тогда:
1)
nаждая
собственно
эффеnтивная
точnа
ltt1l0жества
Q
принадлежит
множеству
Min H
1
;
2)
nаждая
точnа
,м,ножества
Min
Н
1
является
собствен
но
эффеnтивной
для
ltt1tожества
Q.
Д
о
к
а
з
а
т
е
л
ь
с т в
о.
1)
Пусть
q -
собстгенно
эффе
нтивная
точка
множества
Q.
Тогда
q =
j(x)
для
некото
рого
х
е
Gt(X).
В
доказательстве
теоремы
4
было
устано
влено,
что
из
выполнения
условия
регулярности
Слейте
ра
следует
выполнение
условия
регулярности
теоремы
2.4.1.
В
соответствии
с
этой
теоремой
для
точки
х
спра
ведливо
(10)
при
неноторых
J.1
Е
М,
Л
Е
Е;
и
равенство
<1..,
g(x» =
О.
Благодаря
последнему
paB~CTBY
можно
написать
</.1,
q>
= 2(/.1,
х,
л).
Следовательно,
q
Е
H
1
•
Со
гласно
следствию
1
отсюда
BblTeI{aeT
q
Е
Min
1I1'
2)
Пусть
h
Е
Min H
1
•
Ясно,
что
h!jf:
int
lll.
Поэтому
В
силу
(13)
и
замкнутости
Q
получаем
h
Е
Q
()
H
1
,
что
со
гласно
следствию
1
влечет
собственную
эффективность
точки
h
для
множества
Q
.•
Выпишем
вид
двойственной
задачи
Min
Н
I
в
скаляр
ном
случае:
-
минимизиропать
скалярную
функцию
Лаг-
ранжа
L
(х,
л)
по
х
Е
D
и
л
Е
E~,
свяэанным
равенством
V:.L(x,
1..)
=
О(n).
-=
Отметим,
что
полученные
в
данном
пункте
результа
ты
в
идейном
отношении
близки
н
результатам
работы
П.
Шёнфельда
[218].
§ 4.4.
Линейный
случай
В
этом
параграфе
рассматриваются
.1IИнеЙные
много
критериальные
задачи
и
покаэывается,
что
равенство
множеств
решений
прямой
и
двойственной
задач
выпол
няется
при
более
широких
предположениях, чем
в
вогну
том
случае.
§
•.
4)
ЛИНЕйНЫй
СЛУЧАй
213
Поскольку
в
линейном
случае
согласно
следствию
2.2.3
р(у)
-
а(у),
то,
учитывая
теорему
3.5,
двойственное
множество
Н
можно
заменить
на
«ночти
совпадающее»
с
ним
множество
Н"
введенное
в
предыдущем
параграфе.
Это
приводит
к
формулироnке
двойственной
задачи
Min
Н"
нринадлежащей
Гейлу
-
:Н:уну
-
Таккеру
[ 154].
Результаты,
полученные
для
исходной
двойственной
за
дачи
Min
Н,
используются
для
установления
двойствен
ного
соответствия
между
прямой
задачей
Мах
Q
и
двой
ственной
задачей
Min
Н,.
В
свою
очередь,
для
линейной
задачи
с
ограничения
ми
в
форме
'равенств,
множество
Н.
также
можно
заме
пить
па
«почти
совпадающее»
с
ним
множество
H~,
что
ведет
н
двойственной
задаче
Min
Н
2
•
Результаты,
относя
щиеся
н
этой
двойственной
задаче,
кан
следствие
выте
l,aIOT
из результатов,
полученных
для
задачи
Min
Н!.
Нанонец,
оказывается
возможным
в
множестве
Н
2
выде
лить
таное
подмножество
Нз,
что
Min
Нз
=
Min
Н!.
Двой
ствениая
задача
Min
Н
а
была
введена
Г.
Изерманом
[173,
175].
Двойственные
соотношения,
относящиеся
к
задаче
Min
На,
непосредственно
вытекают
из
результатов,
полу
ченных
для
задачи
Min
Н
2
•
:Н:роме
этого,
в
параграфе
рассмотрено
двойственное
соответствие
между
линейными
параметрическими
зада
чами,
введенное
Дж.
:Н:орнблютом
[185].
Это
соответствие,
в
частности,
дает
возможность
получить
Rритерий
су
ществования
эффективных
решений
в
линейной
задаче
без
предположения
о
существовании
допустимых
решений
(т.
е.
без
предположения
Х
r/=
0).
1.
Будем
рассматривать
линейную
МНОГОI{ритериаль
ную
задачу,
в
которой
f(x)
=
Сх,
g(x) =
Ь
-Ах,
D
==
Ei:f
где
С
и
А
-
числовые
матрицы
размера
т
Х
n
и
k
Х
n
соответственно,
а
Ь
-
k-мерный
вектор.
В
соответствии
с
;:ним
прямая
задача
принимает
следующий
вид.
П
р
я
м
а
я
з
а
Д
а
ч
а
А
(линейный
случай).
Найти
мн{)жество
Мах
Q,
где
Q
=<
U
(q
Е
Е,а
I q
~
с
х)
2 (1)
хех
X={xEE:iJAx~b}.
(2)
214
ДВОйСТВЕННЫЕ
МНОГОRРИТЕРИАЛЬНЫЕ
ЗАДАЧИ
[ГЛ.,
Исходя
из
общей
конструIЩИИ
двойственности
вто
рого
параграфа,
двойственная
линейная
задача
формули
руется
следующим
образом.
Двойственная
задача
А
(линейный
случай).
Найти
множество
Min
Н,
где
/
Н
= U n
[h
Е
Е
т
I h:>
Сх
+
<1..1
Ь
-
Ах)
1(т)}"
1t
n
lеЕ>
ХЕЕ>
= -
1(т)=
(1, 1,
..
','
1)
Е
Е
т
•
Множество
Н
допускает
также
представление
(см.
(2.8»
Н
= U n U
{h
I
<f.t,
h)?:
f.tCX
+
<1..1
Ь
-
Ах)}.
"E
1t
Еn
J.lEM
Е
>ХЕ
;;:;
Наряду
с
прямой
задачей
А
приведем
формулировку
линейной
задачи
с
ограничениями
в
форме
равенств.
П
р
я
м
а
я
з
а
Д
а
ч
а
В.
Найти
множество
Мах
Q,
где
Q
имеет вид
(1)
и
х=
{xE~IAx=b}.
(3)
Для
того
чтобы
сформулировать
двойственную
задачу
В
введем
2k-мерную
линейную
функцию
с(х)
=
li
-
Ах,
где
Ь
=
(_
:),
А
=
(_
~).Очевидно,
множество
(3)
сов
падает
с
множеством
{х
Е
~
I g
(х):>
O(2k)}.
Выписывая
применительно
к
этому
множеству
двойственную
задачу
А,
получим
Н=
U n
{hlh5Cx+<;::.t
g(x»1(ffl)}'
-
2k
n
)"ЕЕ>
ХЕЕ>
"'" -
А
обозначая
1:==(1..',
л"),
где
л',
л"
Е
E~,
придем
к
ра-
-=
nенству
Н-
U n
{hlh5Сх+<Л'-Л"l
Ь
-
Ах
)1(т)}.
A'.A"EE~
XEE~
"'"
..
Pait!lOCTb
л'
-
л"
есть
не
который
вектор
из
E~.
Обратно,
lIюбоii
вектор
из
E~
можно
представить
в
виде
разности
.nиgЕЙНЫЙ
СЛУЧАЙ
215
двух
неотрицателъных
векторов.
Поэтому
справедливо
равенство
Н
= U n
{h
I h
>=
Сх
+
<1.,1
Ь
-
Ах)
1(m)}'
(4)
I.EEkxEE~
в
соответствии
с
этим
получаем
следующую
двойствен.
ную
гадачу
для
прямой
задачи
В.
Д
в о
й
с т в
е
н н
а
11
г
а
Д
а
ч
а В.
Найти
множество
Min
Н,
где
Н
имеет
вид
(4).
Для
определенности
в
этом
пункте
мы
будем
рассмат·
риватъ
пару
задач
типа
А.
Резулъта~ы,
полученные
ДЛК
этого
типа
га
дач,
можно
легко
перенести
на
задачи
типа
В.
Л
е
м м
а
1.
В
Аuнейной
аадаче
для
nа:нсдого
qO
е
Мах
Q
существуют
таnuе
веnторы
~
Е
М.1
Л
Е
E~,
что
-
лА
~
~C,
(5)
<J..I.,
qO)
=
<л,
Ь)·.
(6)
Д
о
R
а з
а т е
л
ь с
т
в
о.
Поскольку
qO
е
Мах
Q,
то
qO_
=СхО
при
неIЮТОРОМ
х
О
е
Р,(Х).
Применяя
к
точке
х'
теорему
2.2.7,
получим
существование
таких
векторов
/1
Е
М.1
Л
Е
E~
и
л'
Е
Е;.,
что
-.
=
J..I.С=ЛА
-л',
<л,
Ь
-
Ах
О
)
+
<л',
хО)
=
О.
Из
первого
равенства
вытекает
неравенство
(5).
А
учи·
тыая
оба
этих
равенства,
приходим к
(6):
</1,
qO)
==
J..I.CX
O
-
J..I.CX
O
+
<л,
Ь
-
Ах
О
)
+
<л',
хО)
..,.
<л,
Ь)
••
В
соответствии
с
леммой
1
если
qO
е
Мах
Q,
то
су·
ществуют
~
Е
М
)
л
Е
E~
такие,
что
<~~
qO):>
~Cx
+
<л,
Ь
-
Ах)
для
всех
х
Е
Бi.
Это
влечет
qO
е
Н(л}
s=
Н.
Поэтому
qO
е
Q n
н,
а
значит
согласно
(2.9)
qO
е
Min
Н.
Следовательно,
в
линейной
за
даче
из
неравенства
Мах
Q
=1=
$2f
всегда
следует
Min
Н
=1=
$2f
п
Мах
Q
siii
Min
Н.
Заметим,
что
в
приведенных
рассужде·
ниях
выполнение
условия
регулярности
Слейтера
не
по·
требовалось.
216
ДВОйСТВЕННЫЕ
МНОГОRРIIТЕРИАЛЬНЫЕ
ЗАДАЧИ
[!'Л.4
Линейный
образ
полиэдрального
множества
является
ПОЛIIэдральным
множеством
(см.
теорему
19.3
из
[9З]);
сумма
двух
полиэдральных
множеств
также
полиэдраль
ное
множество
(см.
следствие
19.3.2
из
[93]).
Поэто
му
из
представления
(2.7)
заключаем,
что
множество
Q
полиэдрально,
а
значит
замкнуто.
Нроме
того,
в
линеЙНО~1
случае
в
доказательстве
теоремы
3.2
можно
использовать
теорему
2.2.7,
в
которой
отсутствует
предпо
ложепие
о
выполнении
условия
регулярности.
Это
озна
чает,
что
теоремы
3.2
и
3.3,
доказапные
для
вогнутого
случая,
в
линейном
случае
верны
без
условия
размерно
сти
Слейтера
(требуется
лишь
Q
=/:
0)
11
имеет
место
включение
Min
Н
s=
Мах
Q,
если
Min
Н=/:
0.
Суммируем
полученное
в
следующей
теореме.
т
е
о
р
е
м
а
1.
В
линеUUО,}t
случае
справедливы
сле-
дующие
утверждения:
1)
если
Q
=/:
ro,
то
Q u
н
=
Ет;
2)
если
Мах
Q
=/:
0,
то
Min
Н=/:
0
и
Мах
Q
s=
Min
П;
3)
если
Q
=/:
0
и
Min
Н
=/:
ro,
то
Мах
Q
=/:
ro
и
Min
II
s=
s=MaxQ.
Когда
условие
Q
=/:
0
не
выполнено,
то
утвержденпе
1)
теоремы
1
может
оказаться
неверным.
Об
этом
СВII
детельствует
При
м
е
р
1.
Пусть
n =
2,
т
=
2,
k =
2,
С
=
(~
~),
(
1
-1)
(-1)
.
А=
-1
l'
Ь=
-1
.
Здесь
Q=ro
(так
как
Х=0)
и
функция
Лагранжа
имеет
вид
(
W-Л
-Л)
L
(Ш
1
л)
= L((w,
ш),
1.,)= w _
л:
_
л:
.
Возьмем
произвольныii
вектор
q
Е
Е
2
•
Из
вида
функции
L(w,
л)
следует,
что
для
любых
1.,1'
1.2
:2:
О
найдется
число
w :2:
О,
дЛЯ
которого
L(w,
л)
~
q.
Это
указывает
на
то,
что
НИ
один
вектор
из
Е
2
не
принадлежит
множеству
Н,
т. е.
Н=0,
а
значит
QUH=/:E~.
ЛИНЕйНЫй
СЛУЧАй
217
Пр
Jl
М
е
р,
2.
Для
линейной
задачи
из
примера
3.2
Q
=1=
О
и
Н
=1=
О,
однаRО
Мах
Q =
Min
Н
=
О,
т.
е.
из
вы
полнения
неравенств
Q
=1=
О
и
Н
=1=
О
не
обязательно
сле
дует
Мах
Q"#:
о
или
Min Н
=1=
О.
Из
теоремы
1
и
теоремы
2.2
очевидным
образом
вы
TeRaeT
Следствие
1.
Если
Q4=0,
то
следующие
утвер-
ждеnия
э~вивалеnтnы:
1)
Мах
Q
=1=
)о
или
Min
Н
=1=
О;
2)
Мах
Q
<1:
О,
MinH<l:0
и
MaxQ=Minll=QnH.
2.
Рассмотрим
следующую
линейную
параметричеСRУЮ
r
задачу
*)
при
BeRTopHoM
параметре
t
Е
Е;
~
t
i
=
1:
"
i=l
найти
множество
Мах
Q(t),
где
Q(t) =
{q
=
CXIXE
E~,
Ax<:Bt}
п
В
-
числовая
матрица
размера
k
Х
r.
3афИRсируем
допуСТIIмый
beRtop-параметр
t.
Сформу
лированная
задача
имеет
решение
тогда
и
то.лЬRО
тогда,
Rогда
существует
по
Rрайпей
мере одна
собствепно
эф
феRтивная
ТОЧRа
по
beRTOP-фушщип
Сх
относительно
со
ответствующего
множества
ограничениII.
Это
имеет
место
в
том
и
ТОЛЬRО
том
случае
(см.
теорему
2.2.4),
если
для
некоторого
/.1.
Е
М
имеет
решение
скалярпая
задача
шах
{~LCX
I
Х
Е
E~,
Ах
<:
Bt}.
Согласно
теореме
двойственности
СI\а.
1
ЩРНОГО
линеiiного
программирования
[105]
эта
задача
имеет
решение
тогда
1I
ТОЛЬRО
тогда,
Rогда
имеет
решение
двойственная
задача
шiп
{лВt
I
л
Е
E~,
).,А
>
~LC}.
В
силу
t >
O(f)'
'I'еоремы
2.2.4
и
равенства
Gj(X)
=
Pj(X)
в
линейном
случае
последняя
задача
имеет
решение
в
том
и
ТОЛЬRО
В
том
случае,
если
имеет
решенпе
следующая
МНОГОRритериальная
задача
(/.1.
Е
М):
найти
множество
Min
Н
(/.1.),
где
Н(~)={h=ЛВIЛЕЕ~,
ЛА>~С}.
"')
Вводимая
здесь
двойственная
I\ОНСТРУI\ЦПЯ
параметрuче
СIШХ
JIинейных
задач
принадлежит
Дж.
Rорнблюту
[185].
218
ДВОйСТВЕННЫЕ
многонритЕриАльныЕ
ЗАдАЧИ
[ГЛ.,
Итак,
задача
Мах
Q(t)
разрешима при
векотором
t>
r
>
0(r)1
~
t{
= 1
J
В
том
и только
том
случае,
если
при
веко-
{=1
тором
J,L
е
М
разрешима
задача
Min
П(J,L>.
В
соответствии
с
этим
задача
Min
П(J,L)
является
двойственной
(в
смы
сле
существования
решений
по
отношению
к
исходной
задаче
Мах
Q(t)
)*).
Заметим,
что
исходная
(прямая)
зада
ча
содержит
т
критериев
и
k
ограничений,
а
двойствеН4
ная
-]'
-критериев
и
n
ограничениЙ.-
В
изложенной
конструкции
двойственности
существеН4
ным
является
то,
что
здесь
заранее
не
предполагается
выполненным
условие
Q(t)
=1=
~.
Это
позволяет
проводить
исследование
существования
исходной
пара
метрической
задачи
с
помощью
соответствующей
двойственной
задачи,
заранее
не
зная,
совместна
система
ограничений
Ах
~ Bt,
r
х
~
0(,,),
t>
0(,),
~
t
j
=1,
или
нет.
Так,
например,
при
i=1
r = 1
вектор-параметр
t
исчезает
и
исходная
параметри
ческая
задача
превращается
в
прямую
задачу
А.
Соответ
ствующая
двойственная
задача
будет
иметь
вид
(J,L
е
М)
min
{<л,
Ь)
I
л
Е
E~,
лА
>
J,LC}.
(7)
В
соответствпи
с
этим
можно
сформулировать
слеДУЮ
4
щий
критерий
существования
эффективных
реmепий
в
ли
нейной
задаче
А.
Т
е
о
р
е
м
а
2.
Прямая
sадача
А
имеет
решенuе
(Т. е.
Мах
Q
rI=
~
или
Р/(Х)
=I=~)
тогда
и
толыи
тогда,
-погда
при
nе"оторо.м
J,L
Е
М
имеет
решеnие
с-палярnая
га
дача
(7).
Еще
раз
заметим,
что
в
условиях
теоремы
2
не
пред
полагается
выполненным
условие
Q +
~
(Х
>1=
~).
Нетрудно
понять,
что
для
прямой
задачи
В
(с
ограни
чениями
в
форме
равенств)
задача
(7)
будет
иметь
.)
Пусть
t'
и
/1'
-
векторы
соответствующей
размерности
с
по
ложительными
компонентами,
сумма
которых
есть
единица.
Обра
щаем
внимание
на
то,
что
неравенство
Мах
Q(t')
>1=
~
не
обяза
тельно
влечет
Min
Н
(J.t')
>I=~,
и
наоборот,
из
Min
Н
(/1')
>1=
~
не
всегда
следует
Мах
Q(t')
>I=~.
Кроме
того,
если
Мах
Q(t')
=~,
то
ие
обязательно
MinH(J.t) =
~
для
всех
(допустимых)
/1.
А
так
же,
если
Min
н
(J-I.')
=
~,
ТО из
этого,
вообще
ГОВО'ря,
ие
следует
Мах
Q(t)
=t
~
для
всех
(допустимых)
t.
В
работе
Дж.
Корнблюта
[185]
в
этом
отношении
имеются
некоторые
ветоЧJIОСТП,
которые
справедливо
отмечены
в
f2431.
!I
4
4)
лиНЕйНЫй
СЛУЧАЙ
219
такой
же
вид
d
той
лишь
разнnцей,
что
на
вектор
л
не
будет
наложено никаких
ограничений
(т.
е.
л
Е Е
А
).
3.
В
п.
1
была
сформулирована
двойственная
задача,
в
I<ОТОРОЙ
участвовало
MHoa~eCTBO
Н.
Если
вместо
Н
ис~
полыювать
введенное
в
предыдущем
параграфе
множество
H
1
,
которое
«почти
совпадает»
с
Н,
то
получим
двой,
ственную
задачу,
имеющую
определенные
преимущества
перед
задачей
Min
-Н.
Выпишем
ttонкретный
вид
множества
Н 1
В
случае,
ногда
исходной
является
прямая
задача
А.
ДЛЯ
этого
по
ложим
D =
Еn
и
введем
функцию
г(х)
=
Б
-
Ах,
гдо
ь
=
(~
)
А
=
(_
~
\
и
Е
..
-
единичная
матрица
n
Х
n.
(n)
, nJ
Очевидно,
допустимое
множество
Х
вида
(2)
совпадает
Q
{х
е
Е"!й(х)
~O(A+")}.
Поэтому
согласно
опредеJlению
мно
жества
Н
1
(п.
4
в
§ 3)
получаем
~
/tCX
+
<л,
Ь
-
Ах)
+
(А',
x)}t
где').
Е
E~I
л'
Е
Ет;.
и
1:
=
(л,
л').
А
условие
(3.10),
свя
зывающеё
перемен;ые
л,
х
и
J.I.,
в
данном
случце
при
нимает
вид
J1C
-
лА
+
л'
....
0(11)'
что
равносильно
неравенству
(5):
лА;;;
J.l.C.
Ясно,
что
используя
последнее
равенство,
можно
записать
Итак,
для
прямой
задачи
А
двойственное
множество
Н
1
имеет
вид
(8),
где
векторы
л
и
J.I.
удовлетворяют
не
равенству
(5).
В
§ 3
было
установлено
включение
Н
1
-
Н.
Выясним,
при
каких
условиях
в
линейном
случае
имеет
место
обрат
ное
включение.
Если
h
е
Н
и
h
е
Q,
то,
в
соответствии
с
теоремой
2.2 h
е
Мах
Q.
Отсюда
по
лемме
1
получаем
h
е
H
1
•
Если
же
h
е
Н
и
h
~
Q,
то
согласно
примечанию
3.1
также
имеем
h
е
Н
1
(при
условии,
что
Q.p
>гJ,
Н,
+-
>гJ).
220
~войствЕнныЕ
МНОГО}{РИТЕРИАЛЬИЫЕ
ЗАдАЧИ
[гл.
4
Таким
образом,
справедлива
Л
е
м м
а
2.
Верны
сдедующие
утверждения:
1)
H
i
!::
Н;
2)
если
Q
0:1=
fO
и
Н
!
0:1=
fO,
ТО
Н
!
=
Н.
Заметим,
что
условие
Н
!
o:I=fO
в
утверждепии
2)
этой
леммы
является
существенным
(см.
при
мер
3.2).
Введем
в
рассмотрение
новую
двойственuую
задачу,
которая
впервые
была
сформулирована
Д.
Гейлом,
х.
КУ4
НОм
И
А.
Таккером
[154].
Двойствепная
задача
A
t
•
Найти
MinТl
t
•
Л
е
1\1
м
а
3.
Сnраведдивы
сдедующие
утвержденищ
1)
если
Min
Н
!
0:1=
fO,
то
Мах
Q
0:1=
fO;
2)
если
Q
0:1=
fO
и
Н
!
0:1=
fO,
то
Мах
Q
o:I=fO.
Д
о
к
а
з
а
т е
л
Ь
с т
в
о.
1)
Пусть
hO
Е
Min H
t
,
Т.
е.
<JL
O
,
hO>
~
<').0,
Ь>
и
').ОА
i$:
J.l.°C
при
некоторых
J.l.0
Е
М,
').0
Е
EE~.
Поскольку
hO
-
минимальный
элемент,
то
<JL\
hO)
=
= h
=
<').0,
Ь
>.
Поэтому
если
для
некоторого
').
Е
Е>,
удовлетво-
ряющего
неравенству
').А
~
J.l.°C,
справедл;во
<').,
Ь)
~
<
<').0,
Ь>,
то
hO
не
является
минимальным
элементом.
Это
означает,
что
для
JL
=
JL
o
задача
(7)
разрешима.
Отсюда
в
соответствии
с
теоремой
2
следует
Мах
Q
0:1=
fO.
2)
Если
Н
!
0:1=
fO,
то
для
некоторых
JL
Е
М,
').
Е
E~
сира
..
веДЛIlВО
неравенство
(5).
Значит,
так
как
Q
0:1=
fO;=ТО
со
гласно
теореме
3.2.6
имеем
Мах
Q
0:1=
fO
••
Соотношение
между
прямой
задачей
А
II
двойствен-
ной
задачей
А
!
описывает
Т
е
о
р
е
м
а
3.
Следующие
утвержденuя
эnвuвалenтны:
1)
Q
0:1=
fO,
Н
!
0:1=
fO;
2)
Мах
Q
0:1=
fO;
3)
Min
Н
!
0:1=
fO;
4)
Мах
Q = Min
Н
!
= Q n
Н
!
0:1=
fO.
(Если
Q
0:1=
fO
II
Н
!
0:1=
fO,
то
Н
!
=
Н
(лемма
2),)
Д
о
к
а
з
а
т
е
л
ь
с т
в
о.
Следовапие
4)
-+
3)
очевидно.
Благодаря
утверждению
1)
леммы
3,
имеет
место
3)
-+
2).
Если
Мах
Q
0:1=
fO,
то
в
силу
теоремы
2
задача
(7)
имеет
допустимое
решение.
Следовательно,
Hi..p
fO,
и
поэтому
2)
-+
1).
Докажем
следование
1)
-+
4).
Согласно
утвержде
нию
2)
леммы
3
из
неравенств
Q
0:1=
fO,
Н
!
+
fO
вытекает
Мах
Q
0:1=
fO,
а
в
силу
леммы
2
Н
!
=
Н.
В
этих
условиях,
применяя
следствие
1,
получаем
Мах
Q = Min
Н
!
=
=QnH
t
••