ДОКЛАДЫ АКАДЕМИИ НАУК, 2011, том 438, № 4, с. 456-459
= ИНФОРМАТИКА
УДК 519.816
СУЖЕНИЕ МНОЖЕСТВА ПАРЕТО НА ОСНОВЕ УЧЕТА ПРОИЗВОЛЬНОГО КОНЕЧНОГО НАБОРА ЧИСЛОВОЙ ИНФОРМАЦИИ
ОБ ОТНОШЕНИИ ПРЕДПОЧТЕНИЯ © 2011 г. В. Д. Ногин, О. В. Басков
Представлено академиком С.К. Коровиным 21.01.2011 г. Поступило 17.02.2011 г.
Многие прикладные задачи экономического и технического характера могут быть сформулированы в виде задачи многокритериального выбора с несколькими числовыми функциями. Специфика многокритериальных задач заключается в том, что лицо, принимающее решение (ЛПР), приступая к выбору, как правило, не в состоянии четко выразить свои интересы и предпочтения, на основе которых следует сделать этот выбор. Тем самым ЛПР, начиная поиск множества (в частном случае — одноэлементного) "наилучших" элементов, не располагает точным определением этого понятия. Часто эти "наилучшие" элементы выявляются в ходе принятия решения на основе имеющейся информации о предпочтениях ЛПР.
Предложено много процедур и методов решения многокритериальных задач в зависимости от типа и характера информации о предпочтениях ЛПР [1, 2]. Нередко эти процедуры носят эвристический характер и приводят к принципиально различным "наилучшим" решениям. По мнению подавляющего большинства исследователей "наилучшие" решения следует искать в множестве парето-опти-мальных (эффективных, компромиссных) вариантов. Это обстоятельство нашло свое выражение в принципе Эджворта—Парето, сравнительно недавно получившем аксиоматическое обоснование [3]. Тем самым проблема выбора множества "наилучших" вариантов может быть переформулирована как проблема сужения множества Парето.
Рассмотрим модель многокритериального выбора [3], которая содержит множество исходных вариантов X, векторный критерий у = /(х) = /1(х), /2(х), ...,/т(х)) и асимметричное бинарное отношение предпочтения >х, заданное на множестве X. Пусть У=/(X), а >У есть бинарное отношение, заданное на множестве У и индуцированное отношением >х следующим образом:
Санкт-Петербургский государственный университет
х1 >х х2 ^ /(х1) >У >/(х2) для всех х1 е хх, х2 е
е х2; хг, х2 е X, где X — совокупность классов эквивалентности, порожденных отношением эквивалентности х1 ~ х2 /(х1) = /(х2) на множестве X. Множества выбираемых ("наилучших") вариантов и векторов обозначим С(Х) и С(У) = /(С(Х)) соответственно. Это те множества, которые подлежат нахождению в процессе выбора. Множество парето-оптимальных вариантов относительно векторного критерия / на множестве X обозначается Р(Х).
Сузить множество Парето Р/(Х), т.е. удалить из рассмотрения некоторые парето-оптимальные элементы, можно при наличии дополнительной информации о предпочтениях ЛПР. Наиболее надежными и простыми с точки зрения их получения являются сведения о готовности ЛПР идти на определенный компромисс. Этот компромисс нередко заключается в том, что ЛПР соглашается понести некоторые потери по каким-то непринципиальным критериям ради получения определенной выгоды по критериям, которые имеют приоритетное значение для данного ЛПР.
Учет подобной информации об отношении предпочтения ЛПР, которое изначально обычно полностью неизвестно самому ЛПР, положено в основу аксиоматического подхода к решению проблемы сужения множества Парето, развиваемого почти три последних десятилетия [3]. Сначала было установлено, каким образом следует использовать единственное сообщение (один "квант информации") в виде двух наборов чисел, один из которых указывает верхние допустимые пределы потерь для ЛПР по одной группе непринципиальных критериев, а другой — величины выигрышей для принципиально важных критериев, большие или равные которым ЛПР желало бы получить, идя на компромисс. В последующем были исследованы возможности использования тех или иных наборов такого рода сообщений (нескольких "квантов информации") для сужения множества Парето.
На геометрическом языке наличие "кванта информации" об отношении предпочтения ЛПР означает [3] выполнение соотношения и >г0, при некотором и е где Ыт — множество т-мерных векторов, имеющих по крайней мере одну строго положительную и одну строго отрицательную компоненты. Задание же набора "квантов информации" равносильно выполнению соотношений и >г0, ' = 1, 2, ..., к.
В данной работе предлагаются два универсальных алгоритма (два метода), которые базируются на учете произвольного конечного набора "квантов информации" для сужения множества Паре-то. Первый (геометрический) алгоритм, принадлежащий первому автору, заключается в решении задачи выпуклого анализа, сформулированной в [3]. Второй (алгебраический) алгоритм, разработанный вторым автором, предполагает последовательный учет имеющегося набора "квантов" на основе линейного оператора, используемого при учете одного "кванта" в теореме 3.5 из [3]. Далее будут считаться выполненными четыре аксиомы "разумного" выбора, сформулированные в [3].
Упомянутая геометрическая задача выпуклого анализа заключается в следующем. Имеется конечный набор векторов а1, а2, ..., ак е Ит, к > т, который порождает острый выпуклый "-мерный конус М. Требуется построить минимальный (по числу) набор векторов Ь1, Ь2, ..., Ь", порождающих конус {у е Ят | (а', ¿) > 0, ' = 1, 2, ..., к}, двойственный конусу М. Угловые скобки здесь означают скалярное произведение векторов. Следует отметить, что искомые векторы Ь1, Ь2, ..., Ь" всегда существуют и определяются с точностью до положительного множителя.
Для решения этой задачи предлагается следующий алгоритм, на вход которого подается набор векторов а1, а2, ..., ак, а на выходе (в памяти) образуется искомый набор векторов.
Алгоритм 1. Шаг 1 (открытие цикла по перебору векторов). Открыть цикл по перемен-
ной ' от 1 до Ск генерирования всех возможных
поднаборов из т — 1 векторов набора а1, а2, ..., ак.
Шаг 2 (проверка на линейную независимость). Если текущий '-й поднабор а'1, а'2, ..., а'(т-1), выбранный из а1, а2, ..., ак, линейно-зависим, то увеличить номер ' на единицу и вернуться к началу шага 2. Когда увеличение номера ' невозможно,
т.е. ' = С
т - 1
, необходимо перейти к шагу 5. В про-
тивному случае, т.е. когда указанный поднабор линейно-независим, выполнить шаг 3.
Шаг 3 (построение ортогонального вектора). Образовать из вектор-столбцов поднабора а'1, а'2, ..., а'(т-1) квадратную матрицу Б "-го порядка, приписав к указанным столбцам справа лю-
бой вектор из множества I' = {а1, а2, ..., ак}\{а'1, а'2,..., а'(т-1)}, образующий вместе с а'1, а'2, ..., а'(т-1) линейно-независимую систему. Найти последний столбец матрицы (Б7)-1, где Т — символ транспонирования. Найденный вектор-столбец (обозначим его у') следует запомнить.
Ш а г 4 (проверка вектора у' на принадлежность искомому множеству Ь1, Ь2, ..., Ь"). Вычислить скалярные произведения (а>, у) для всех векторов а> е I. Если хотя бы одно такое скалярное произведение окажется отрицательным, то удалить из памяти вектор у'. Увеличить номер ' на единицу и перейти на шаг 2 (когда такое увеличение невозможно, выполнить шаг 5).
Примечание. Для сокращения перебора и исключения в памяти записи одинаковых (с точностью до положительного множителя) искомых векторов для каждого записанного в память вектора у', на шаге 4 следует запоминать соответствующий ему набор У из всех векторов а1, а2, ..., ак, ортогональных вектору у' (т.е. тех а>, для которых (а!, у) = 0). А на шаге 2 всякий раз в случае, когда текущий поднабор а'1, а'2, ..., а'(т —1) оказывается подмножеством хотя бы одного образованного ранее множества У, пропускать такой поднабор, сразу увеличивая номер ' на единицу.
Ш а г 5 (завершение работы алгоритма). В результате выполнения полного цикла по переменной ' в памяти будут записаны искомые вектор-столбцы Ь1, Ь2, ..., Ь" (в ходе выполнения алгоритма они получали обозначение у').
Теорема 1. Векторы Ь1, Ь2, ..., Ь", построенные в результате конечного алгоритма 1, образуют минимальный набор векторов, порождающих конус, двойственный т-мерному острому выпуклому конусу М, порожденному набором векторов а1, а2, ..., ак еЯт, к > т.
Теорема 2. Пусть выполнены четыре аксиомы "разумного" выбора и задан непротиворечивый набор "квантов информации" и' >г0, ' = 1, 2, ..., к [3].
Тогда для любого множества выбираемых вариантов С(Х) имеют место включения
(1)
С(X) с Р&(X) с Р/X).
Здесь Ре(Х — множество парето-оптимальных вариантов на исходном множестве Xотносительно нового "-мерного векторного критерия g(x) =((Ь1,/(л)), (Ь2, /(х)), ..., (Ь",/(х))), " > т, где векторы Ь1, Ь2, ..., Ь" получены в результате применения алгоритма 1 к набору, состоящему из векторов, задающих " кванты информации" и1, и2, ., ик, вместе с т единичными ортами пространства Ит.
Согласно теореме 2, применяя алгоритм 1, следует построить новый векторный критерий g, от-
458
НОГИН, БАСКОВ
носительно которого новое множество Парето дает оценку сверху (1) для неизвестного множества выбираемых вариантов С(Х) с учетом имеющегося набора "квантов информации".
Алгебраический подход максимально использует специфику заданного набора "квантов информации" и' >У0, I = 1, 2, ..., к, и носит последовательный характер, т.е. учет информации производится строго в порядке нумерации имеющихся "квантов".
Пусть имеется вектор и1 = (и1, и2, ..., ит). Введем множества А = {'| и, > 0}, В = {] | ц < 0}, С = {1\ и1 = 0}. Когда множества А и В непустые, вектор и1 порождает "квант информации" об отношении предпочтения, если и1 >г 0. Для его учета в теореме 3.5 из [3] предлагается построить новый векторный критерий g, компоненты которого связаны с компонентами критерия/следующими соотношениями (порядок компонент не существен):
gl = VI 6 А и С,
8и = и^ - и// V(/,]) 6 А х В.
В матричной форме эти соотношения можно переписать в виде g = Т/, где Т — прямоугольная матрица соответствующего размера.
Построенный указанным способом критерий g порождает новое множество векторов Z = g(X). На нем индуцировано новое отношение >г, связанное со "старым" отношением следующим образом: х' >Хх" < g(x') >Z g(x"). В дальнейшем для краткости индекс (символ множества, на котором действует рассматриваемо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.