Многокретериальные задачи

Многокритериальные  задачи

В многокритериальной задаче оптимизации сравнение решений  по предпочтительности осуществляется не непосредственно, а при помощи заданных на множестве решений  Х числовых функций f₁, f₂,…f_m, называемых критериями (а также показателями качества или эффективности, критериальными функциями, целевыми функциями и т.п.). Предполагается, что m ≥ 2: при m=1 задача оптимизации является однокритериальной.

Математическая  модель многокритериальной задачи принятия решений представляется в виде <X, f₁,f₂,…,f_m>, где X – множество допустимых исходов, f_j – числовая функция, заданная на множестве X; при этом f_j(α) есть оценка исхода α∈X по j-му критерию (j=1,m).

Критерий называется позитивным, если принимающий решение стремится к его увеличению, и негативным, если он стремится к его уменьшению.

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

Пусть Y_j – множество значений функции f_i, т.е. множество всех оценок по j-му критерию (j=1,n). Тогда множество , состоящее из всевозможных упорядоченных наборов оценок по критериям 1,2,…, m, называется множеством векторных оценок. Любой элемент у∈Y представляет собой вектор y=(y₁,y₂,…,Y_m), где y∈Y_j. Для всякого исхода α∈Х набор его оценок по всем критериям, т.е. набор (f₁(α), f₂(α),…, f_m(α)) есть векторная оценка исхода α. Векторная оценка содержит полную информацию о ценности (полезности) этого исхода для принимающего решение и сравнение любых двух исходов заменяется сравнением их векторных оценок.

Основное отношение, по которому производится сравнение  векторных оценок (значит, и сравнение  исходов), − это отношение доминирования по Парето, которое определяется следующим образом.

Говорят, что  векторная оценка y=(y₁,y₂,…,y_m) доминирует по Парето векторную оценку y`=(y`₁,y`<sub>2</sub>,…,y`_m), (записывается в виде y y'), если для всех j=1,n выполняется неравенство у_j ≥ у`_j, причем по крайней мере для одного индекса j=1,n неравенство должно быть строгим.

Пусть Q ⊆ Y − некоторое множество векторных оценок.

Векторная оценка y*∈Q называется Парето-оптимальной в Q, если она является максимальным элементом множества Q относительно Парето-доминирования (т.е. если в множестве Q не существует такой векторной оценки y, которая доминирует по Парето векторную оценку y*).

Перенесем теперь эти понятия на исходы.

Говорят, что  исход α₁ доминирует по Парето исход α₂ (записывается в виде a₁a₂), если векторная оценка исхода α₁ доминирует по Парето векторную оценку исхода α₂.

Содержательно условие a₁a₂ означает, что исход α₁ не хуже, чем исход α₂ по любому из рассматриваемых критериев, причем по крайней мере, по одному из этих критериев α₁ лучше α₂.

Исход a*∈X называется Парето-оптимальным исходом в множестве Х, если он не доминируется по Парето никаким другим исходом из множества Х (т.е. если векторная оценка исхода α* является Парето-оптимальной в множестве векторных оценок Q.

Парето-оптимальность  исхода а* означает, что он не может быть улучшен ни по одному из критериев без ухудшения по какому-нибудь другому критерию.

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

В случае, когда  множество допустимых исходов является дискретным (конечным), получаем «картинку» типа изображенной на рис. 1.

 
Рис. 1.

Задача отыскания  множества Парето решается следующим  образом. Находим все точки с  наибольшим значением U. Если их несколько, выбираем из них точку с наибольшим значением V. Включаем ее в множество Парето. Отсекаем точки с меньшими либо равными значениями U и V (юго-западный угол с вершиной в выбранной точке). Повторяем процедуру для оставшейся части допустимой области. Таким образом, Парето-оптимальными являются исходы {4,5,7,8}.

Пример.

Фирма по разработке программного обеспечения должна выполнить  проекты 1 и 2 в последовательности 1, 2. Для выполнения каждого проекта  можно привлечь одного, двух или  трех исполнителей. Пусть x₁ и x₂ – число исполнителей, привлеченных для выполнения проектов 1 и 2 соответственно. Время выполнения проекта i равно p_i(x_i) месяцев, а соответствующая стоимость c_i(x_i) млн.рублей. Требуется минимизировать общее время выполнения проектов при минимальной стоимости. Значения функций заданы следующим образом:

Решение.

Общее время  выполнения проектов равно f₁= p₁(x₁)+ p₂(x₂), а стоимость их выполнения равна f₂= c₁(x₁)+ c₂(x₂).

Определим все  возможные значения пар (f₁, f₂) = {(2,6), (2,7), (2,8), (3,5), (3,6), (4,6), (4,7), (5,5)}.

 
Рис. 2

Находим все  точки с наименьшим значением  f₁. Если их несколько, выбираем из них точку с наименьшим значением f₂. Включаем ее в множество Парето. Отсекаем точки с большими либо равными значениями f₁ и f₂ (северо-восточный угол с вершиной в выбранной точке). Повторяем процедуру для оставшейся части допустимой области. Таким образом, Парето-оптимальными являются исходы {(2,6), (3,5)} и соответствующие решения {(2,2), (1,2)}.

В случае, когда  множество допустимых исходов является непрерывным, их векторные оценки «заполняют»  некоторую область Ω на плоскости.

Рассмотрим на плоскости (U,V) множество Ω (рис. 3). Каждая его точка обладает одним из следующих свойств: либо все точки, ближайшие к ней, принадлежат множеству Ω (такая точка называется внутренней точкой множества Ω), либо сколь угодно близко от нее расположены как точки множества Ω, так и точки, множеству Ω не принадлежащие (такие точки называются граничными точками множества Ω). Граничная точка может как принадлежать, так и не принадлежать множеству Ω. Множество всех граничных точек множества называется его границей. Обозначение ∂Ω.

 
Рис. 3

Точки множества  Ω можно разбить на три класса:

к первому классу относятся точки, которые можно  сдвинуть так, чтобы одновременно увеличились  обе координаты и при этом точки  остались в множестве Ω (в этот класс попадают все внутренние точки множества Ω и часть его граничных точек);

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

в третий класс  попадут точки, перемещение которых  по множеству Ω способно лишь уменьшить  хотя бы одну из координат.

Множество точек  третьего класса называется границей (множеством) Парето данного множества  Ω.

Говоря нестрого, граница Парето множества Ω −  это точки, из которых нельзя сдвинуться на «север», «восток» либо «северо-восток», оставаясь в том же множестве  Ω.

На рис. 4 указаны  границы Парето некоторых множеств. 

 
Рис. 4

Замечание. Предположим, что в задаче принятия решений  имеются критерии разного характера. Пусть, например, первый критерий негативный, второй – позитивный. Тогда целью  принимающего решение будет уменьшение первого критерия и увеличение второго, что соответствует движению на координатной плоскости «влево и вверх». В этом случае Парето-оптимальная граница области Ω представляет собой ее «северо-западную» границу (рис. 5).

 
Рис. 5.

Рассмотрим случай, когда множество допустимых исходов  является непрерывным.

Пусть на плоскости (х,y) задано множество ω (рис. 6) и в каждой точке этого множества определены две непрерывные функции:

U = Φ(x,y) и V = Ψ(x,y).

 
Рис. 6

Рассмотрим следующую  задачу.

На множестве  ω найти точку (x₀,y₀), в которой

Φ(x₀,y₀)=max и Ψ(x₀,y₀)=max.

Существует несколько  способов решения поставленной задачи. Среди известных следует отметить два:

1. метод уступок;
2. метод идеальной точки.

Оба метода используют множество Парето, составленное в  данном случае из допустимых точек  задачи, которые не могут быть «сдвинуты» в пределах допустимого множества  с улучшением сразу по обоим критериям.

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

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

Пример.

Пусть на множестве  ω плоскости (x,y), определяемой системой неравенств

заданы две  линейные функции:

Требуется найти  решение задачи

U → max, V → max

Решение.

Рассмотрим решение  данной задачи методом идеальной  точки.

Множество ω  представляет собой пятиугольник (рис. 7), вершины которого имеют следующие  координаты:

A(0;0), B(0;2), C(2;2), D(4;1), E(4;0).

 
Рис. 7.

В силу линейности критериев U и V пятиугольник ABCDE переходит в пятиугольник A*B*C*D*E* (рис. 8), координаты вершин которого вычисляются по формулам (1):

A*(2;6), B*(4;4), C*(6;6), D*(7;9), E*(6;10).

 
Рис. 8.

Находим границу  Парето. Это отрезок D*E*. Точка утопии M*(7;10) считается заданной (ее координаты суть наибольшее значение U и V).

Требуется найти  на множестве Парето точку, ближайшую  к точке утопии M*. Из рисунка видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и E* прямую. Пусть

αU+βV=γ

− ее уравнение. Чтобы отыскать конкретные значения параметров α,β и γ, подставим  в него координаты обеих точек  D* и E*. Получим

6α+10β=γ,

7α+9β=γ.

Вычитая из первого  равенства второе, после простых  преобразований придем к соотношению

− α + β = 0,

откуда

α = β.

Положим α = β = 1. Тогда γ = 16 и

U + V = 16

− искомое уравнение  прямой.