Исследование оптимальности по конусу в многокритериальной задаче

ИССЛЕДОВАНИЕ ОПТИМАЛЬНОСТИ ПО КОНУСУ В МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧЕ

1. Многокритериальная задача: оптимальность по конусу

Рассматривается задача принятия решений в некоторой управляемой системе, качество решения в которой оценивается несколькими критериями. Исследуем понятие оптимальности в многокритериальной задаче. В такой постановке проявляется неопределённость в управляемой системе. Фактически в этом случае представлена неопределённость в выборе решения лицом, принимающим решение (ЛПР), относительно итоговой цели выбора. В классификации неопределённостей в исследовании операций она выделена как “неопределённость, отражающая нечёткость знания игроками своих целей” [1, c.17].

Перейдём к математической формализации, при этом используем терминологию и обозначения из [2]. Итак, рассматривается многокритериальная задача

(1)

Здесь имеется один участник, принимающий решение (ЛПР). Задано множество допустимых альтернатив x X Rⁿ, из которых ЛПР делает свой выбор. Выделен конечный набор желаемых свойств, оцениваемых критериями. В рассматриваемой математической модели используются количественные критерии, которые представляются целевыми функциями: каждая функция оценивает одно свойство.

Обычно информацию o всех критериях объединяют в одну, векторную функцию Значения этой векторной функции каждой альтернативе ставят в соответствие количественную оценку для выделенных свойств в критериальном пространстве . Множество всех векторных оценок или множество исходов .

Не уменьшая общности, считаем, что критерии являются позитивными, т.е. ЛПР стремиться к их увеличению [3, с.55]. Тогда, на содержательном уровне, цель ЛПР состоит в выборе такой альтернативы, которая доставляет возможно большие значения одновременно всем компонентам векторной функции выигрыша . Отметим, что в соответствии с [3, c.12-13] множество X и векторная функция f из (1) определяют соответственно реализационную и оценочную структуры задачи принятия решения. Используем обозначения для отношения предпочтения в R^m из [4, с.7]:

;

(2)

В качестве решения многокритериальной задачи (1) часто рассматривают альтернативу, обладающую свойством, что её оценка не поддаётся улучшению по какому-либо критерию, иначе как за счёт ухудшения по какому-то другому критерию. Именно, альтернатива в многокритериальной задачи (1) называется максимальной по Парето (эффективной), если из условия следует, что хотя бы при одном . Множество максимальных по Парето альтернатив обозначается и множество соответствующих исходов - через .

Достаточно общий подход на определение оценочной структуры в (1) предлагают конусные отношения. В многокритериальных задачах такой подход представлен в [4, с.42 - 47; 5; 6; 7]. Будем рассматривать выпуклый, острый конус К [8, с.235-255]. Часто рассматривается многогранный (полиэдральный) конус в конечномерном евклидовом пространстве, который можно задать квадратной матрицей, именно,

K = { f R^m | Af ? 0_m (3)

Полагаем, что элементы матрицы А являются неотрицательными, а сама матрица невырожденной. Это гарантирует то, что соответствующий конус К будет выпуклым, острыми и его размерность совпадает с размерностью критериального пространства . Конус порождает в векторном пространстве бинарное отношение ?_k по правилу

f ?_k g (4)

Известно, что если конус К в (4) является выпуклым, острым и не содержит начало координат, то он определяет отношение строго порядка инвариантное относительно линейного положительного преобразования в . Верно и обратное утверждение [4, с.45].

Такой конус К называют конусом доминирования в . Стандартным образом строгий порядок (4) в при заданном конусе К определяет оптимальное (максимальное, минимальное) по конусу решение в многокритериальной задаче (1).

Определение 1. Альтернатива x* X называется оптимальной по конусу К в задаче векторной оптимизации (1), если x X, x - x* ? K. Если (), то оптимальное решение называется максимальным по конусу К (минимальным по конусу К).

Отметим, что максимальные по Парето альтернативы в многокритериальной задаче (1) являются максимальными по конусу решениями и конус доминирования из (2).

Подход к решению многокритериальной задачи (1) на основании конусных отношений предпочтения широко использовался и результаты представлены в ряде работ. Так, если в многокритериальной задаче (1) множество альтернатив X Rⁿ компактно, векторная функция выигрыша f: X R^m непрерывна, конус доминирования К в критериальном пространстве является выпуклым, острым, то существует альтернатива, оптимальная по конусу К. Далее, для построения процедуры уточнения оптимального по Парето решения, потребуется результат, представленный в [5, с.336]. Пусть в многокритериальной задаче (1) заданы конусы доминирования и множества альтернатив, оптимальных по конусу соответственно. Тогда из следует включение

Пример. Рассматривается двухкритериальная задача

, (5)

в которой множество допустимых исходов представлено на рис.1. Двухкритериальный выигрыш = и область исходов показана на рис. 2. Задан многогранный конус доминирования

K = {x R² | Ax = }. (6)

Этот конус доминирования К в пространстве представлен на рис. 3.

Рассмотрим оценки допустимых исходов, представленные на рис. 2. Расположим конус доминирования в R² так, что его вершина совпадает с оценкой некоторого исхода. Если, в этом случае, множество точек конуса не пересекается с множеством оценок всех допустимых исходов (за исключением общей вершины), то соответствующий исход является оптимальным по конусу К. Тогда оптимальные по конусу исходы расположены на дуге QMPNT (рис. 2), а соответствующие альтернативы на стороне АВ (рис. 1). В этом случае r* = 1. Выделим на дуге оценки, оптимальные по конусу К. Они расположены на участке дуги NM (рис. 2). В пространстве критериев координаты точки N (точки М) находятся из условия

().

В данном примере получены все максимальные по конусу K исходы

Они изображены отрезком СD на рис. 1. Множество оценок

отмечены дугой NM на рис. 2.

Заметим, что в данной многокритериальной задаче (5) максимальные по конусу решения являются уточнением максимальных по Парето решений. Действительно, паретовские альтернативы представляются отрезком АВ на рис.1 и их оценки - всей дугой QMPNT на рис.2. В тоже время оптимальные по конусу К из (6) решения представляются точками отрезка CD на рис.1 и их образы - дугой NM на рис.2.

Рис. 3. Конус доминирования в пространстве

Многокритериальная задача (1) является задачей в условиях неопределённости, именно в условиях неопределённости цели. Для уточнения решения (уменьшения степени неопределённости) можно использовать дополнительную информацию. Это могут быть мнения экспертов. Так в рассмотренном примере два эксперта оценили важность (вес) критериев. Первый эксперт указал отношение важности для критериев, как 3:2, а второй эксперт, как 4:1. Эта информация позволила определить многогранный конус предпочтений K и соответствующую матрицу А в (6). Полученное оптимальное по конуса К решение имеет определённый содержательный смысл..

Пусть - оптимальный по конусу К исход. Тогда, если найдётся другое решение, для которого исход по первому критерию увеличится на , то в этом случае второй критерий уменьшится на или более. Аналогично для второго критерия: его увеличение по второму критерию в новой альтернативе на приведёт к уменьшению по первому критерию на или более единиц. Отметим, что оптимальное по Парето решение обладает аналогичным свойством. Именно, увеличение по одному критерию может быть только за счет уменьшения по другому критерию. Таким образом, оптимальный по конусу исход задаёт некоторый компромисс между критериями, который соответствует мнению экспертов о важности критериев.

Соотношения между критериями определяются параметрами конуса, именно, направляющими векторами рёбер конуса К. Они представлены на рис. 3. Это векторы d₁(2,-3) и d₂(-1,4). Таким образом, конусные решения - это паретовские решения, из числа которых исключены заведомо неприемлемые (по мнению экспертов) решения. Отметим, что ничего не меняется, если информация о важности критериев получена от ЛПР. Такая информация не входит в формулировку многокритериальной задачи (1), но, безусловно, является важной при принятии решения. Использование информации об относительной важности критериев и сужение на её основании множества Парето подробно представлено в [4].

2. Уточнённое по последовательность конусов решение

Оптимальных по конусу решений может быть много. Тогда уточнение по конусу можно применить несколько раз, последовательно уточняя (улучшая) решение. Соответствующий подход можно представить в матричной форме. Рассмотрим следующую последовательность квадратных, невырожденных, неразложимых, стохастических матриц [8, с.352; c.381]

. (7)

Все элементы стохастической матрицы неотрицательны и сумма элементов каждой строки равна 1 [8, с.381]. По последовательности матриц построим новую последовательность

(8)

Каждая матрица из последовательности (8) будет определять многогранный конус аналогично (2). Обозначим конусы этой последовательности, как Полученная последовательность конусов позволит построить уточнённое по конусу решение многокритериальной задачи (1).

Утверждение 1. Пусть матрицы , из последовательности (7) являются неотрицательными, невырожденными, неразложимыми, стохастическими. Тогда для любого натурального n

a) матрица из последовательности (8) является неотрицательной, невырожденной, неразложимой, стохастической;

б) для соответствующих конусов имеет место включение

в) для соответствующих множеств оптимальных по конусу решений задачи (1) имеет место включение

Каждая матрица из последовательности (8) является стохастической и для них верны условия теоремы Фробениуса. У каждой такой матрицы максимальное собственное значение Каждому собственному значению однозначно можно выбрать левый собственный вектор

(9)

Учитывая вышеизложенное, для последовательности матриц (8) верно

Утверждение 2. Пусть матрицы , из последовательности (7) являются неотрицательными, невырожденными, неразложимыми, стохастическими. Тогда существует предел последовательности матриц (8), т.е.

=

Матрица является положительной, вырожденной с рангом равным 1, все строки матрицы равны

,

где левый собственный вектор из (9).

Последнее утверждение является основанием для уточнения оптимального решения в задаче (1).

Определение 2. Рассматривается многокритериальная задача (1) и последовательность неотрицательных, невырожденных, неразложимых, стохастических матриц (7). Пусть набор чисел

представляет строку предельной матрицы из утверждения 2. Тогда альтернативу

(10)

будем называть уточнённым по последовательности конусов (7) оптимальным (максимальным) решением многокритериальной задачи (1).

Утверждение 3. Пусть в многокритериальной задаче (1) множество допустимых альтернатив X Rⁿ компактно, векторная функция выигрыша f: X R^m непрерывна, квадратные матрицы порядка m в последовательности (7) являются неотрицательными, невырожденными, неразложимыми, стохастическими. Тогда в задаче существует оптимальное уточнённое по последовательности конусов (7) оптимальное решение (10).

Существование уточнённого по последовательности конусов решения следует их компактности множества допустимых альтернатив X и непрерывности функции

.

где , есть строка предельной матрицы .

Утверждение 4. Уточнённое по последовательности матриц (7) оптимальное (максимальное) решение в многокритериальной задачи (1) является оптимальным (максимальным) по Парето решением, более того, оно является оптимальным (максимальным) по любому конусу, определённому матрицей из последовательности (8).

Уточнение оптимального по Парето (по конусу) решения многокритериальной задачи (1) определяется последовательностью матриц (7). В частности такая последовательность может состоять из постоянных матриц, т.е. в (7) , где - произвольная неотрицательная, невырожденная, неразложимая, стохастическая матрица. В этом случае последовательность матриц (8) составляют натуральные степени матрицы А. Суммируя результаты для данного частного случая, получаем

Утверждение 5. Пусть квадратная матрица А порядка m является неотрицательной, невырожденной, неразложимой, стохастической. Тогда

a) существует предел последовательности матриц = ;

б) предельная матрица А₀ является неотрицательной, невырожденной, неразложимой, стохастической и все строки этой матрицы равны левому собственному вектору, относящемуся к максимальному собственному значению матрицы А

;

с) для последовательности матриц , соответствующая последовательность многогранных конусов , определённая аналогично (2), удовлетворяет цепочке включений

д) соответствующая последовательность множеств, оптимальных по конусу , решений в многокритериальной задаче (1) удовлетворяет включениям

Если в определении 2 уточнение оптимального по Парето решения в многокритериальной задаче (1) проводится по последовательности многогранных конусов, определённых степенями неотрицательной, невырожденной, неразложимой, стохастической матрицы А, то полученное решение будем называть уточнённым по конусу К решением многокритериальной задачи (1).

Рассмотренные выше методы уточнения оптимального по Парето решения существенно зависят от дополнительной информации, связанной с критериями задачи (1). Если такая информация отсутствует, то решением в (1) может быть только Парето оптимальный исход. Причём все такие решения равноправны, как решения задачи (1). В тоже время информация о важности критериев может возникать из оценок экспертов или из отношения ЛПР к критериям. Такая информация позволяет уточнить оптимальное по Парето решение.

Оценка относительной важности критериев может быть представлена весовыми коэффициентами, т.е. набором положительных (неотрицательных) чисел, отношение между которыми представляет отношение важности соответствующих критериев для эксперта (для ЛПР). Набор положительных чисел можно нормировать так, что сумма коэффициентов равна 1, при этом отношение чисел не изменится. Кроме того, что такое преобразование приводит различные мнения экспертов к единой форме, оно позволяет представить информацию от всех экспертов в форме стохастической матрицы. Последнее допускает построение последовательности уточнений.

Представленный выше алгоритм уточнения решения предполагает использование квадратных матриц порядка m, т.е. использование m экспертных оценок относительной важности критериев. Аналогичный алгоритм уточнения решения можно определить и для k экспертов, k ? m, k ? 2. В этом случае матрица А₁ в последовательности (7) будет иметь размер kЧm и остальные матрицы последовательности - квадратные порядка k. Если же при выработке решения в задаче (1) эксперты выработали однозначный набор весовых коэффициентов для критериев, т.е. k = 1, то многокритериальная задача (1) сводится к задаче математического программирования. В этом случае снимается неопределённость, связанная с многими критериями в задаче (1).

Если процесс выработки решения в задаче (1) развивается во времени, т.е. информация о важности критериев поступает дискретными порциями, то возникает последовательный процесс уточнения решения. Если на очередном шаге новая информация о критериях отсутствует, то последняя матрица уточняет оптимальное по Парето решения. Далее, в условиях отсутствия новой информации, решение уточняется последовательностью конусов, определяемых степенями последней матрицы . Но такую последовательность уточнений, начиная с шага, можно не выполнять, а сразу перейти к предельной матрице, как она определяется в утверждении 5. Таким образом, применив конечное число уточнений (именно ), решение задачи (1) может быть сведено к задаче математического программирования и её решение - уточнённое по конусу решение многокритериальной задачи (1).

Уточнение оптимального по конусу решения позволяет в некоторых случаях выделить в многокритериальной задаче (1) единственную наилучшую альтернативу. Условия существования единственного уточнённого по конусу К решения формулируется с использованием вогнутости векторной функции цели [9, c.169].

Пусть множество допустимых альтернатив X Rⁿ выпукло. Векторная функция векторного аргумента f: X R^m, m?1, называется вогнутой (строго вогнутой) на множестве X, если каждая компонента этой функции является вогнутой (строго вогнутой) на этом множестве, т.е. для любых i = 1,…,m, x y X, выполнено неравенство

( ).

Утверждение 6. Пусть в многокритериальной задаче (1) векторная функция f: X R^m, m?1, будет вогнутой на компактном множестве X Rⁿ и найдётся, по крайней мере, одно , что скалярная функция будет строго вогнутой на этом множестве, многогранный конус определён квадратной матрицей А, которая является неотрицательной, невырожденной, неразложимой, стохастической. Тогда в задаче существует единственная уточнённая по конусу альтернатива.

Согласно определению 2, уточнённым по конусу оптимальным решением многокритериальной задачи (1) является альтернатива

.

По теореме Фробениуса матрица A однозначно определяет левый собственный вектор, относящийся к максимальному собственному значению . Это вектор . Тогда функция является строго вогнутой, т.к. такими же являются и функции и, по крайней мере, одна из них строго вогнута. Тогда последняя линейная комбинация представляет строго вогнутую функцию. Наконец, строго вогнутая функция достигает максимального значения на компактном множестве в единственной точке [9, с.170].

Пример (продолжение). Продолжим рассмотрение двухкритериальной задачи (5). Для неё конус доминирования К представлен в (6). Этот конус можно задать с помощью стохастической матрицы, которую, также как и в (6), обозначим А

K = { x R² | Ax = }.

Найдем предел последовательности матриц = . Наибольшее собственное значение матрицы А есть = 1 Получаем, Тогда по утверждению 5 матрица A₀ = В соответствии с определением 2, уточнённым по конусу К максимальным решением многокритериальной задачи (5) будут решения задачи математического программирования (задача максимизации)

.

Здесь максимальное значение достигается при На рис.1 этому решению соответствует точке ). В пространстве исходов на рис.2 ему соответствует точка . Таким образом, уточнённое по конусу (6) решение многокритериальной задачи (5) будет единственным и векторный выигрыш в этом случае = (0,8944, 0,4472).

Заключение

В работе проведено исследование оптимальности по конусу в многокритериальной задаче. Такая проблема анализируется как оптимизационная задача в условиях неопределённости, именно, в условиях неопределённости цели. Обычно в качестве решения многокритериальной задачи предлагается оптимальное по Парето (эффективное) решение. Но таких решений, как правило, много. Возникает проблема его уточнения .

Оптимальное по Парето решение входит в класс конусных решений. Многогранный конус в векторном критериальном пространстве задаёт векторную упорядоченность, что позволяет определить оптимальное по конусу решения. Такое решение имеет определённый содержательный смысл, связанный с экспертными оценками важности критериев.

Конусное решение указывает приемлемый компромисс между критериями по мнению экспертов при принятии решения. Именно, если исход оптимален по конусу и от него возможен переход к другому исходу, что выигрыш по одному критерию будет большим, тогда найдётся другой критерий, что проигрыш по нему будет недопустимо большим.

Конусные решения в многокритериальной задаче имеют важное свойство: если первый конус включает второй конус как подмножество, то множество оптимальных по первому конусу решений является подмножеством решений, оптимальных по второму конусу. На этом свойстве построена процедура уточнения решения.

Конусные отношения можно задавать в матричной форме, именно в форме стохастических матриц. В этом случае последовательное уточнение конусной упорядоченности соответствует умножению стохастических матриц. Предлагается следующий алгоритм: на основании мнения экспертов строится последовательность расширяющихся конусов, которой соответствует последовательность вложенных множеств конусных решений. Решение по предельному конусу называется уточнённым по последовательности конусов оптимальным решением многокритериальной задачи.

В работе проведено обоснование алгоритма уточнения решения. Указаны свойства последовательности стохастических матриц, которые гарантируют существование предельного конуса. Выявлены условия, при которых уточнённое по последовательности конусов оптимальное решение является единственным. Рассматривается модельный пример.

На основании исследования оптимальности по конусу в многокритериальной задаче предложена концепция уточнения решения, выявлены свойства уточнённого по последовательности конусов решения и указан случай единственности такого решения.

Литература

1. Жуковский В.И. Кооперативные игры при неопределённости и их приложения. М: Эдиториал УРСС, 1999.

2. Подиновский В.В., Ногин В.Д. Парето - оптимальные решения многокритериальных задач. М.: Наука, 1982.

3. Розен В.В. Математические модели принятия решений в экономике. - М.: Книжный дом "Университет", Высшая школа, 2002.

4. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. -М.: Физматлит, 2002.

5. Yu P.L. Cone convexity, cone extreme points and nondominated solutions in decision problems with multiobjectives // Journal of optimization theory and application. -1974. -V. 14, N^o3. - P. 319 - 377.

6. Kuroiwa D., Tanaka T., Truong Xuan Duc Ha. On cone convexity of set - valued maps // Pros. 2^nd World Congress of Nonlinear Analysis - Elsevier Science, 1997. -P. 1487 - 1496.

7.Матвеев В.А. Существование и единственность уточнённого по конусу решения многокритериальной задачи // Труды псковского политехнического института. 10.1. Естествознание и математика. Псков, 2006. -С.24 -27.

7. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983 .

8. Гантмахер Ф.П. Теория матриц. Издание 3. М.: Наука, 1967.

9. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.