Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач
Подождите немного. Документ загружается.
ЭКОНОМИКО.
МАТЕМАТИЧЕСКАЯ
БИБЛИОТЕКА
В.
В.
подиновекий,
в.
д.
НОГИН
ПАРЕТО-ОПТИМАЛЬНЫЕ
РЕШЕНИЯ
МНОГОI\РИТЕРИА,JIЬНЫХ
ЗАДАЧ
МОСНВА
«НАУНА»
ГЛАВНАЯ
РЕДАНЦИЯ
ФИ3ИНО-МАТЕМАТИЧЕСl\Ой
ЛИТЕРАТУРЫ
1982
22.18
П
44
УДК
519.6
Парето-оптимальные
решения
многокритериальных
задач.
П
о
Д и
н
о
в
с
к и
й
В.
В.,
Н
о
г
и
н
В.
Д.-
М.:
Наука.
Главная
редакция
физико-математической
литературы,
1982.-
256
с.
Монография
посвящена
оптимумам
(по)
Парето,
играющим
важную
роль
при
анализе
многокритериальных
задач
принятия
решений.
В
ней
разбирается
содержательный
смысл,
теоретиче
ское
и
практическое
значения
понятия
оптимального
по
Парето
(эффективного)
решения, подробно
рассматриваются
различного
рода
условия
оптимальности,
исследуются
структура
и
свойства
множеСТВа
Парето,
излагается
теория
двойственности
многокрите
риальных
задач.
Кратко
обсуждаются
вопросы
построения
мно
жества
Парето
и
проверки
оптимальности
решений.
Книга
рассчитана
на
широкий
круг
читателей
-математиков,
специалистов
по
экономической
кибернетике,
автоматизации
управ
ления
и
проектирования,
а
также
студентов
и
аспирантов
соответ
ствующих
специальностей.
Рис.
35.
Библ.
291
назв.
П
1502000000 - 06763_82
053(02)-82
©
Издательство
«Наука,).
Главная
редакции
фИЗИlю-математичеСRОЙ
Il
ите
ратуры.
1982
ОГЛАВЛЕНИЕ
Предисловие
. • .
Основные
обозначения
5
7
г
л
а в
а
1.
Основные
понятия
и
определенпя
9
§
1.1.
Общне
сведения
о
многокритериальных
задаqах
оптимизации
. . . . . . • • • . •
1.2.
Отношения
предпочтения,
функции
ценности
и
вы-
бора
. . . . . . . . . . . . .
§
1.3.
Независимость
критериев
по
предпочтению.
Много-
критериальные
задачи
максимизации
. . . .
§
1.4.
Эффективные
и
слабо
эффективные
oцeНI\!!
и
ре-
шения
....
..
§
1.5.
Теоретическое
и
практическое
значения
понятия
эфФективного
решения
. . . . . . . .
§
1.6.
Сооственно
и
подлинно
эффективные
решения
.
§
1.7.
Эффективные
последовательности
оценок и
реше-
ний
. . . . . .
1.8.
Эквивалентные
векторные
критерии
9
15
24
29
38
49
57
60
г
л
а в
а
2.
Условия
оптимальности
65
§
2.1.
Общие
условия
оптимальностн.
.
..
66
§
2.2.
Условия
оптимальности
для
ВОГНУТЫХ
п
линейных
задач
97
§
2.3.
Условия
оптимальности
для
двухкритериальных
задач
. . .
.,
117
2.4.
Условия
оптимальности
для
дифференцируемых
функций
. . . . . . . . 124
§
2.5.
Условия
ОПТIlмальности
второго
порядка.
128
§
2.6.
Условия
оптимальности
для
негладких
задач
131
§
2.7.
Свойства
эффективных
последовательност~й
136
г л
а
в
а
3.
Структура
и
свойства
множества
эффективных
решений
141
§
3.1.
Топологические
свойства
множеств
эффективных
оценок
и
решений
. . . . . . . • •
141
§
3.2.
Условия
существования
эффективных
решений
. 155
§
3.3.
Структура
множества
эффективных
решений
в
ли-
нейных
задачах
162
1'"
ОГЛАВЛЕНИЕ
§
3.4.
ОцеНRа
числа
эффективных
точек
в
ДIIснретных
задачах
. . • . . . . . . . . .
170
§
3.Ч.
О
построении
множества
эффективных
решений
и
про
верке
эффективности
выделенного
решения
182
r
л
а в
а
4.
Двойственные
мвогокритериальные
задачи
189
§
4.1.
Седповые
пары,
максимины
и
мини:максы
BeRTOp-
ных
функций
. . . . . . . .
190
§
4.2.
Общая
конструкция
двойственных
задач
198
§
4.3.
Вогнутый
случай
202
§
4.4.
Линейный
случай
212
Послесловие
• . . . . . . . .
233
Дополнительные
библиографические
ссылки
234
Литература
. . •
236
Предметный
указатель·
252
ПРЕДИСЛОВИЕ
Почти
ВСЯI<ая
сложная
праI<тичеСI<ая
задача
принятия
решения
(и
индивидуалыюго,
и тем
более
группового)
является
МНОГОI<ритериальноЙ.
В
связи
с
этим
особое
зна
чение
в
настоящее
время
-приобретает
бурно
развиваю
щаяся
теория
принятия
решений
при
наличии
многих
I;ритериев.
Одним
из
основных,
фундаментальных
ПОНЯТИЙ
ЭТОЙ
теории
является
понятие оптимального
по
Парето,
или
эффеитивного
решения.
Оно
представляет
собой
обобще
нпе
понятия
ТОЧI<И
маI<симума
числовой
фУНI<ЦИИ
на
слу
чай
неснолы<хx
фУНI<ЦИЙ:
решение
Парето-оптимально,
если
значение
любого
из
нритериев
можно
улучшить
лишь
за
счет
ухудшения
значений
остальных
I<ритериев.
Наименование
уназанного
понятия
связано
с
именем
птальянсного
ЭI<ономиста
II
социолога
В.
Парето
(1848-
1923),
IЮТОРЫЙ
одним
из
первых
начал
его
использовать
при
математичеСI<ИХ
исследованиях
процесс
а
рыночного
обмена
товаров.
Свойствам
II
методам
ОТЫСI<ания
Парето-оптимальных
решений
посвящена
достаточно
обширная
журнальная
лптература,
насчитывающая
уже
несI<олы<o
сотен
наиме
нований.
Эти
вопросы
затрагиваются
таI<же
во
МНОГИХ
ра
ботах
по
теории
игр,·
математичесной
:ШОНОМИI<е,
теории
статистичеСI<ИХ
решений,
исследованию
операций,
теории
оптимального
управления
и
по
другим
научным
дисцип
лпнам,
в
ноторых
изучаются
различные
МНОГОI<ритериаль
ные
модели
принятия рациональных
решений.
Однано
си
стематичеСI<ое
и
достаточно
полное
изложение
современ
ного
состояния
теории
оптимумов
Парето
возможно
лишь
в
рамнах
нниги,
специально
посвященной
этому
вопросу.
Таная
ннига
и предлагается
вниманию
читателей.
В
ней
наряду
с
известными
приведены
и
новые
результаты,
по
лученные
авторами.
lIPЕДIrСЛОlш-е
Отметим,
что
всюду
D
юшге
используется
Rлассиче
cRoe
понятие
числовой
фуНIЩИИ:
опа
не
должна
прини
мать беСRонечные
значения
(+00
или
':""00)
*).
TaRoe
огра
ничение,
неСRОЛЬRО
сузив
Rpyr
рассмотренных
задач,
по
зволило
в
целом
ряде
случаев
существенно
упростить
изложение
материала.
УRазанное
обстоятельство
авторы
считают
немаловажным,
ПОСI{ОЛЬRУ
целью
IШИГИ
являетсн
систематизация
современного
состояния
теории
Парето
оптимальных
решений
**).
Этим
же
соображением
про
ДИRтовано
и
еще
одно
ограничение
-
в
RIIиге
рассматри
ваются
многокритериальные
задачи
в
осповпом
лишь
В
Rонечномерном
еВRЛИДОВОМ
пространстве
Еn.
Рассчитывая
на
ШИРОRИЙ
круг
читателей,
ках,
матемаТИIi.ОD,
тан
и
не
математинов,
авторы
по
возможности
стремились
приво
дить
в
соответствующих
местах
необходимые
определения
п
фанты,
не
встречающиеся
в
распространенных
курсах
по
теории
оптимизации.
В
книге
формулы,
теоремы,
примеры
и
т.
д.
нумеруют
ся
в
пределах
наждого
параграфа.
При
ссылнах
на
мате
риалы
из
других
параграфов
той
же
главы
используется
двойная
нумерация,
а
ссыЛl\И
на
другие
главы
сопровож
даются
тройной
нумерацией.
Рисунни
нумеруются
по
главам.
Несмотря
на
внушительпые
размеры,
списон
литерату
ры,
приведеНllЫЙ
в
нонце
IШИГИ,
не
может
считаться
ис
черпывающим.
Тем
не
менее
желающие
более
подробно
ознаномиться
с
вопросами,
за
тронутыми
в
нниге
лишь
вснользь,
смогут
извлечь
из
него
полезную
информацию.
Глава
1
книги
(нроме
п.
6
из
§ 1.4), §
2.1
(пп.
5,
6),
§ 2.7, § 3.4
{По
О;
§ 3.5
и
§ 4.1
написаны
В.
В.
Подинов
сним;
§
2.2
(пп.
4-6,
8),
§
2.3
(п.
3), §
2.4-§
2.6, § 3.2,
§ 3.3, § 3.4
(п.
2), § 4.3
и
§ 4.4 -
В.
Д.
Ногиным;
осталь
ной
материал написан
авторами
совместно.
Авторы
признательны
В.
В.
Федорову,
взявшему
на
себя
труд
по
рецензированию
IШИГП.
*)
Это
нужно
учитывать
при
разборе
неноторых
формулиро
вон
и
доназательств,
особенно
при
наличии
ССЫЛОR
на
монографию
Р.
РонафеЛJlара
Г931,
в
RОТОРОЙ
фуннции
могут
принимать
бес
Rонечпые
значения.
**)
Первой
монографией,
посвященной
систематичеСRОМУ
Н3-
ложению
теории
оптимумов
Парето,
ЯIJплась
113дапная
в
1971
г.
книга
В.
В.
Подиповского
[77].
ОСНОВНЫЕ
ОБО3НА
ЧЕНИЯ
{х
Е
А
I
n(х)}
-
совокупность
элементов
х
ыножества
А,
для
которых
выполнено
n
(х)
{о
-
пустое
множество
I
А
I -
число
элементов конечного
множества
А
... ,
А
Х
В
-
декартово
нроизведение
множеств
А
и
В
h:
А
--
В
-
отображение
h
множества
А
во
множество
В
Е
-
множество
вещественных
чисел
Ent[q]
-
целая
часть
числа
q
Еm
-
евклидово
т-мерное
пространство
О(m)
=
(О, О,
•••
,
О)
-
нулевой
вектор
пространства
Еm
Для
векторов
у,
z
из
Еm:
т
<у,
Z>
=
~
YiZi -
скалярное
произведение
у
и
z
i=1
I\уl\
=
"'I(У,
у)
-
норма
у
у
~
Z
++
У!
~
Zj,
i =
1,
2,
••.
,
т
у
~
z
++
у
;;:::
Z,
но
у
=1=
z
у
:>
Z
++
У;
>
Zi,
i =
1,
2,
...
,
т
у
:>
Z
++
у
= Z
или
У;
>
Zj
хотя
бы
нри
одном
т
В';
=
(У
Е
вт
I
У>
O(m)j-
положительный
ортант
i = 1,2,
..•
простран-
ства
Ет
B~
=
!У
Е
вт
I
у;:::
О(т)}
-
неотрицательный
ортант
простран-
ства
Ет
Для
МIIО'нества
А
s;
Еm:
А
-
вамыRниеe
множества
А
int
А
-
внутренность
:множества
А
Fr
А
-
граница
множества
А
l'i
А
-
относительная
внутренность
выпуклого
множества
А
conv
А
-
выпуклая
оболочка
множества
А
conv
А
-
вамыкание
выпуклой
оболочки
А
А
Q -
поляра
выпуклого
конуса
А
О+(А)
-
рецессивный
конус
выпуклого
Множества
А
Т(А;
У*)
-
касательный
конус
ко
множеству
Ав
точке
у*
Мах
А
(Min
А)
-
множество
максимальных
(минимальных)
Элементов
множества
А,
упорядоченного
отношением
.:::
Для
множеств
А,
В
s;
Ет:
А
+
В
=
{у
Е
Ет
I
у
=
а
+
Ь,
а
Е
А,
Ь
Е
В}
А
-
В
=
{v
Е
Еm
у
=
а
-
Ь,
а
Е
А,
Ь
Е
В}
8
ОСНОВНЫЕ
ОБО3НА
ЧЕНИJI
х
-
ыпжествоo
(допустимых)
решений
/1,
/2,
...
,
1т
-
критерии
(целевые
фУНlЩИИ)
М
=
{1,
2,
.•.
,
т}
-
множество
номеров
критериев
t
=.
(fl,
/2,
...
,
1т)
-
векторный
критерий
g = (gl,
g2,
•••
,
gя)
-
вектор-фушщия
ограничений
(задана
на
множестве
D
s;
Еn)
l(х
О
)
=
{j
Е
{1,
2,
...
, k} I g j
(х
О
)
=
О}
-
множество
номеров
активных
ограничений
в х
О
У
;
-
шкала
критерия
'!
УХ
==
Y1X
У
2
Х
...
Х
У
т
у
-
множество
(векто,Рных)
оценок
У
=
'(Х)
=
{у
Е
Ет
I
у
=
!(х),'
х
Е
Х}
-
множество
достижи
иых
(векторных)
оценок
У.
=
у
-
Е';=
U
{:
Е
вт
I
у
>z}
=
УЕ:У
-
;;1'
!::!'
~"
""'1-
отношеНlIЛ
в
Х,
индуцированные
с
по-
мощью
f
отношениями
~,
2:,
>,
=
соответственно
(х'
>-
,х"
при
!(х')
~
!(х")
и
т.
д.)
Р
(У)
=
Мах У
(Р
f
(Х»
-
множество
эффективных,
оптималь
ных
по
Парето
оценок
(решений)
8(У)
(8
t
(X»
-множестпо
слабо
эффеКТIIВПЫХ,
оптимальных
110
Слейтеру
оценок
(решений)
G
(У)
(G
t
(Х»
-
множество
собственно
эффективных,
ОПТII
мальных
по
Джоффриону
оценок
(решений)
В(У)
(Bj(X»
-мпожество
подлинно
эффективных,
оптимаJIЬ
ных
по
Борвейну
оценок
(решений)
М
=
{~t
Е
В';
I
i~11Li
=
1}
КI
=
{fl
Е
B;;.I.~
~ti
=
1}
-
1=1
8-
конец
доказательства
ГЛАВА
f
ОСНОВНЫЕ
ПОНЯТИЯ
И
ОПРЕДЕЛЕНИЯ
§ 1.1.
Общие
сведения
о
многокритериальных
задачах
оптимизации
1.
I\онцепция
принят
ия
(выработки)
решения
в
каче
стве
первичного
элемента
деятельности
рассматривает
решение
как
сознательный
выбор
одной
из
ряда
альтер
натив,
называемых,
в
зависимости
от
их
конкретного
со
держания,
стратегиями,
планами,
вариантами
и
т.
п.
Этот
выбор
про
изводит
лицо,
принимающее
решение
и
стремящееся
к
достижению
определенных
целей.
В
роли
TaRoro
лица
выступают
отдельные
люди
или группы
лю
дей,
обладающие
правами
выбора
решения
и
несущие
ответственноеть
за
его
последствия.
Применение
математических
методов
при
принят
ии
решепий
предполагает
построение
подходящей
математи
чеСRОЙ
модели,
формализованно
представляющей
про
блемную
ситуацию,
т.
е.
ситуацию
выбора
решения.
Для
задач
принят
ия
решений
(задач
оптимизации)
в
условиях
определенности,
когда
случайные
и
неопределенные
фак
торы
отсутствуют,
компонентами
такой
модели
являются
множество
Х
всех
(альтернативных)
решенuй,
из
которых
II
надлежит
про
извести
выбор
одного
наилучшего,
или
оnтuмального
решения,
и
описание
предпочтений
лица,
принимающего
решение.
Для
того
чтобы
была
обеспече
на
возможность
(свобода)
выбора,
множество
Х
должно
содержать
не
менее
двух
решений.
2.
В
много~рuтериальной
аадаче
оnтимиаации
сравне
ние
решений
по
предпочтительности
осуществляется
не
непосредственно,
а
при
помощи
заданных
на
Х
число
вых
фУНКЦИЙ
111
1:
•...
,
1т.
называемых
~ритериями
(а
также
показателями
качества
или
эффективности,
кри
териальными
функциями,
целевыми
функциями
и
т.
п,).
Предполагается,
что
т ~
2:
при
т
= 1
задача
оптимиза
ции
является
о{}ноnритериалъноЙ
..
Для
каждого
критерия
fj
на
числовой
прямой
Е
уна
зывается
подмножество
У/,
из
которого
он
принимает
10
ОСНОВНЫЕ
понятия
И
ОПРЕДЕЛЕНИIl
[ГЛ.
r
свои
значения.
Практически
мпожество
У,
(которое,
до·
пуская
вольность
речи,
часто
называют
шкалой
*)
крите·
рия
j;)
определяется
в
соответствии
с
содержательным
смыслом
этого
критерия.
Например,
если
заведомо
IIЗ
вестно,
что
критерий
/1
положителен
или
неотрицателен
(характеризует
массу,
стопмость
и
Т.
пJ
..
то
можно
при
нять
У
1
=
(О,
+00)
или
11
=
[О,
+00).
Если
значения
/2
ограничены
снизу
и
сверху
некоторыми
естественным\{
границами
а
и
Ь,
то
У
2
=
[а,
bJ
(так,
если
/2
-
израсхо
дованная
доля
запаса
ресурсов,
то
У
2
=
[О,
1]).
Если
3Нi:l.
чениями
/з
могут
служить
лишь
нуль и
натуральные
чис
ла (скажем,
если
/з
определяется
в
результате
подсчета
количества
некоторых
объеI\ТОВ),
то Уз
=
Ю,
1,
2,
..
J.
Ес
ли
на
значения
/~
нет
НИI\аI\ИХ
смысловых
ограничений,
то У,
=
(-00,
+00)
=Е
н
т.
п.
Критерии
/;,
называемые
частnымu
(а
также
ЛОI\аЛЬ
ными),
образуют
веnторnый
nритерий
/ =
(/1,
/2'
...
,
/т).
Считается,
что
I\аждое
решение
х
полпостью
харю\теризу
ется
соответствующей
(веnторnой)
оцеппой,
Т.
е.
BeI\TOp0!l1
!(х).
ПОЭТОJ\ry
выбор
оптимального
решения из
множества
всех
решений
Х
сводится
к
выбору
оптимальной
оцешш
И3
множества
достижимых
оценок
Y=f(X)=
(УЕЕт/у=нх),
XEXJ~
где
Еm
-
т-мерное
числовое
пространство,
называемое
критериальпым.
При
необходимостп
это
пространство
бу
дет
СЧIIтаться
евклидовым,
Т.
е.
снабженным
метрикой
Ily
-
у'"
=
(У
-
у',
У
- y')1/2 =
[i~
(Yi
_
y~)2
]1/2.
В
реальных
задачах
множество
У
часто
построить
весьма
сложно,
а
то
и
невозможно.
Поэтому
в
рассмот
рение
вводится
неноторое
более
ШИРОI\ое
множество
у
s=
Ет,
векторам
из
ноторого
можно
придать
содержа
тельный
смысл.
Чаще
всего
это
множество
У
~
у
всех
(достижимых,
т. е.
И3
у,
и
гипотетических)
оценон
явля
ется
многомерпым
параллелепипеДОllf
ух
=
У.
Х
У
2
Х
•.•
• )
в
математической
теории
измерений
понятие
шкалы
непо
средственно
связывается
с
понлтием
допустимого
преобразованил
критерия
(см.
п.
2).