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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Часть критериев отражает требования субъектов и возможности объектов, другая часть — требования объектов и возможности субъектов. Введем следующие обозначения: Sk(S1, S2, ..., Sm, ..., Sw} — множество оценок на шкале k-ro критерия; Skm — m-я по порядку оценка на шкале k-ro критерия; Tikp — р-я по порядку оценка на шкале требований i-го элемента по k-му критерию; Vjut — t-я оценка на шкале возможностей j-ro элемента по u-му критерию.

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

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

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

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

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

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

Дано: два множества: Ci (I = 1,2, ..., n) и Oj (j = l,2, ..., n); оценка каждого элемента двух множеств по N критериям (k1, k2, ..., kN).

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

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

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