2. Постановка многокритериальной задачи о назначениях

2.1. Содержательная постановка задачи

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

Предъявляя требования к качеству назначений, т.е. к сте­пени соответствия характеристик элементов двух множеств, до­пустимой при образовании пар, ЛПР формирует область допус­тимых решений (ОДР), определяя обязательные назначения или исключая недопустимые, с его точки зрения, пары. Формируя назначения в ОДР, ЛПР стремится к одному из возможных ре­шений, при котором нельзя улучшить качество назначения для какой-либо пары элементов, не ухудшив при этом качество на­значений для других пар. Назовем эти решения эффективны­ми. Среди эффективных решений ЛПР стремится отыскать та­кое, которое позволяет получить максимальное количество наилучших возможных назначений. Учитывая описанные выше особенности, сформулируем содержательную постановку МЗН в следующем виде.

Дано: элементы двух множеств, n субъектов и n объектов, каждый из которых характеризуется совокупностью оценок по N критериям.

Требуется: на основе предпочтений ЛПР сформировать об­ласть допустимых решений и найти в этой области эффективное решение с максимально возможным числом наилучших, с точ­ки зрения ЛПР, назначений.

2.2. Критерий оптимальности решения мзн

В качестве критерия наилучшего решения МЗН выбрано максимально возможное число наилучших назначений. Отме­тим, что это не единственно возможный критерий. Понятие наилучшего, с точки зрения ЛПР, решения МЗН заслуживает обсуждения. Существуют различные подходы к определению и выбору критерия. Рассмотрим некоторые из них.

Первый подход соответствует принципу: «всем поровну». Ставится задача найти среди эффективных решений такое, при котором назначения для пар элементов в равной по возможно­сти степени отличались бы от идеальных. Иначе говоря, инте­ресы членов коллектива (субъектов и объектов) были бы в рав­ной степени удовлетворены в каждой паре.

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

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

2.3. Формальная постановка задачи

Чтобы привести формальную постановку МЗН, введем сле­дующие понятия, термины и обозначения. Имеются два исход­ных множества по n элементов: С{ n } и O { n }. Обозначим: C { C 1 , C 2 , …, C i , …, C n } – первое множество, элементы которого назовем субъектами; O { O 1 , O 2 , …, O j , …, O n } – второе множество, элементы которого назовем объектами.

Имеется множество из N критериев оценки субъектов и объектов. Каждая оценка на шкале критерия имеет две форму­лировки, отражая взаимные требования и возможности элемен­тов двух множеств (см. пример далее). Шкалы критериев – по­рядковые, с небольшим, как правило, числом оценок, упоря­доченных от лучшей к худшей. Лучшая оценка имеет ранг, равный единице. Оценки могут быть как словесные, так и чис­ленные. (Заметим, что шкалы словесных оценок наиболее ха­рактерны для МЗН. Иллюстрацией могут служить приведенные выше примеры.)

Часть критериев отражает требования субъектов и возмож­ности объектов, другая часть – требования объектов и возмож­ности субъектов. Введем следующие обозначения: S k { S 1 , S 2 , …, S m , …, S w } – множество оценок на шкале k -го критерия; – m -я по порядку оценка на шкале k -го критерия; – р-я по порядку оценка на шкале требований i -г o элемента по k -му критерию; – t -я оценка на шкале возможностей j -г o эле­мента по u -му критерию.

Назовем критериальным соответствием (КС) различие по одному из критериев между требованиями субъекта (объекта) и возможностями объекта (субъекта). Требования i -г o элемента по k -му критерию ( ) удовлетворены возможностями j -г o эле­мента по k -му критерию ( ), если р > t . При этом критери­альное соответствие идеально.

Назовем назначением любую пару { C i , O j }, образованную дву­мя элементами, принадлежащими разным исходным множествам. Имеется множество из ( n ? n ) назначений { C i , O j }, i , j = 1, 2, ..., n , для двух исходных множеств по n элементов: C { n } и O { n }.

Идеальным назначением назовем пару { C i , O j }, для которой взаимные требования полностью удовлетворены по всем крите­риям, т.е. все КС идеальны.

Назовем решением многокритериальной задачи о назначе­ниях единичную диагональную матрицу MS ( n ? n ), диагональные элементы которой соответствуют назначениям, формирующим решение. Заметим, что количество возможных решений для размерности исходных множеств С{ n } и O { n } равно n !, что и вы­зывает (в общем случае) существенные трудности при решении МЗН большой размерности.

Идеальным решением назовем решение МЗН, все назначе­ния которого идеальны.

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

Дано: два множества: C i ( i =1,2, ..., п) и O j ( j =1, 2, ..., n ); оценка каждого элемента двух множеств по N критериям ( k 1 , k 2 , …, k N ) .

Требуется: на основе предпочтения ЛПР определить и вы­брать из множества эффективных решений такое, для которого сумма рангов лучших S назначений ( S ? n ) минимальна.

В исследовании операций известна задача о назначениях с одним критерием качества решения [4]. В однокритериальной задаче о назначениях задана стоимость образования той или иной пары, например исполнения каждой из работ каждым из исполнителей. Задан также критерий – минимум стоимости вы­полнения всей совокупности работ. Для решения однокритери­альной задачи применяются различные методы, как правило, ос­нованные на алгоритмах дискретного программирования. Далее мы будем использовать однокритериальную задачу о назначени­ях как вспомогательное средство при решении существенно более сложной многокритериальной задачи. МЗН занимает промежу­точное положение между задачами принятия индивидуальных и коллективных решений. Действительно, ЛПР стремится най­ти наибольшее число максимально удовлетворенных субъектов и объектов, основываясь на характеристиках, отражающих ин­тересы и индивидуальные предпочтения субъектов и объектов. Но в ситуациях, требующих выбора, ЛПР руководствуется своими предпочтениями.

Впервые близкая по постановке задача была сформулиро­вана в [5]. В ней используется тот же критерий оптимальности и дан алгоритм решения задач малой размерности. Его приме­нение позволило решить практическую задачу [2].