Сведение многокритериальной задачи к однокритериальной

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

q₀(x) = q₀(q₁(x), q₂(x), ..., q_p(x)). (2)

Суперкритерий позволяет упорядочить альтернативы по величине q₀, выделив тем самым наилучшую (в смысле этого критерия). Вид функции q₀ определяется тем, как мы представляем себе вклад каждого критерия в суперкритерий; обычно используют аддитивные или мультипликативные функции:

; (3)

. (4)

Коэффициенты s_i обеспечивают, во-первых, безразмерность числа q_i/s_i (частные критерии могут иметь разную размерность, и тогда некоторые арифметические операции над ними, например сложение, не имеют смысла) и, во-вторых, в необходимых случаях (как в формуле (4)) выполнение условия β _iq_i/s_i £ 1. Коэффициенты α _i и β _i отражают относительный вклад частных критериев в суперкритерий.

Итак, при данном способе задача сводится к максимизации суперкритерия:

(5)

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

Суперкритерий играет роль этой упорядочивающей функции, и его даже “небольшое” изменение может привести к тому, что оптимальная в новом смысле альтернатива окажется очень сильно отличающейся от старой. На рис. 1, а видно, как изменяется выбор наилучшей альтернативы при простой смене коэффициентов в линейной упорядочивающей функции (3), что отражается в изменении наклона соответствующей прямой: q₀₁(x₁*) > q₀₁(x₂*), но q₀₂(x₁*) < q₀₂(x₂*). Заметим, что линейные комбинации частных критериев придают упорядочению следующий смысл: “чем дальше от нуля в заданном направлении, тем лучше”. На рис. 1, а направления, соответствующие суперкритериям q₀₁ и q₀₂, изображены стрелками. Идея такого упорядочивания в многомерном пространстве заложена в некоторых балльных системах оценки вариантов.

Другой вариант поиска альтернативы, самой удаленной от нуля в заданном направлении, дает максимизация минимального критерия [23]:

(6)

что означает поиск вокруг направления α _iq_i/s_i = const методом “подтягивания самого отстающего”.

 

Условная максимизация

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

(7)

при условии, что дополнительные критерии остаются на заданных им уровнях. На рис. 1, б приведено решение задачи

В некоторых задачах оказывается возможным или даже необходимым задавать ограничения на сопутствующие критерии не столь жестко, как в задаче (7). Например, если сопутствующий критерий характеризует стоимость затрат, то вместо фиксации затрат разумнее задавать их верхний уровень, т.е. формулировать задачу с ограничениями типа неравенств:

(8)

На рис. 1, б приведено решение задачи . Отметим, что такое, казалось бы, незначительное изменение постановки задачи требует принципиально иных методов ее решения.

 

Варианты оптимизации при разноважных критериях

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

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

Пусть частные критерии могут быть пронумерованы в порядке убывания их важности. Возьмем первый из них и найдем наилучшую по этому критерию альтернативу (на рис. 1, б это x₂*, если самым важным критерием является q₂, и x₄*, если им является q₁). Затем определим “уступку” Δ q_i, т.е. величину, на которую мы согласны уменьшить достигнутое значение самого важного критерия, чтобы в пределах этой уступки попытаться увеличить, насколько возможно, значение следующего по важности критерия (на рис. 1, б полученные таким образом альтернативы изображены точками x₃* и x₅*). Далее (если число критериев более двух) определяется уступка по только что максимизированному критерию и максимизируется следующий; процедура повторяется до тех пор, пока перечень критериев не закончится.

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

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

Выбор между упорядочениями

Для рассматриваемых методов многокритериальной оптимизации существенным является исходное упорядочение критериев. Иногда их порядок очевиден или общепризнан (как порядок букв в алфавите), но бывает, что этот вопрос не тривиален, а привлекаемые для его решения эксперты дают несовпадающие упорядочения критериев. Выход состоит в том, чтобы установить, какое из предложенных экспертами упорядочений является “средним”, “типичным” для данной группы. Это опять-таки можно делать по-разному. Среди специалистов пользуется признанием упорядочение, называемое медианой Кемени.

Обозначим через R_i упорядочение критериев, предложенное i-м экспертом. Введем некоторую меру расхождения между двумя (i-й и j-й) ранжировками: d(R_i, R_j). Медианой Кемени R* среди n предложенных упорядочений R₁, R₂, ..., R_n называется то из них, которое отвечает условию

,

т.е. то, сумма “расстояний” до которого от всех остальных минимальна. Ясно, что многое зависит от того, как определить расстояние d. Например, если R_i = q₁⁽ⁱ⁾, ..., q_p⁽ⁱ⁾, то d_p(R_i, R_j) можно определить как d(h_i, R_j1) = = p – , где? (x⁽ⁱ⁾, x^{( j)}) – символ Кронекера.

Однако следует отметить, что с медианой Кемени связано несколько трудностей. Во-первых, оптимизационная задача по нахождению R* решается методами дискретной оптимизации (динамического программирования, ветвей и границ, и др.), трудоемкость которых экспоненциально растет с увеличением размерности задачи. Во-вторых, иногда решение задачи не единственно, и в этом случае возникают трудности: в литературе приводится пример, когда в одной из оптимальных ранжировок конкретная альтернатива стоит на первом месте, а в другой – на последнем). Поэтому используют и другие способы упорядочения, наиболее известным из которых является метод строчных сумм. Пусть критерии сравниваются попарно: a_ij= 1, если k-й эксперт считает, что q_i важнее q_j; 0, если наоборот; 1/2, если он считает их равноценными. Для каждого критерия вычисляют величины , i = I, n, и критерии упорядочивают по этой “сумме очков” – совсем как по турнирной таблице в спорте. Однако и этот метод может давать сбои, как и всякое голосование (см. § 7.5).

⇐ Предыдущая12345Следующая ⇒

Поделиться: