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

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

Другим основанием классификации служит размерность МЗН. В приведенном примере нетрудно перебрать все возможные назначения, сравнить их между собой и выбрать лучшие. Ясно, что такая возможность существует при небольшом количестве элементов двух множеств и малом числе критериев. Однако в за­дачах о назначениях количество элементов может меняться от десятков до тысяч, а число критериев – от трех–четырех до де­сяти и более, при этом количество оценок на шкалах, как прави­ло, три–пять [1,2,3]. В связи с этим в каждом из классов уни­кальных и повторяющихся задач целесообразно выделить сле­дующие типы МЗН, различающиеся размерностью своих харак­теристик:

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

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

Для задач типа В требуются средства, позволяющие реали­зовать детальные алгоритмы выявления предпочтений ЛПР и построения общего решающего правила.

Для задач типа С необходимы в первую очередь средства анализа данных и средства, реализующие способы решения ло­кальных задач о назначениях, которые возникают при кон­фликтных критериальных оценках.

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

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

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

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

Основные алгоритмы решения многокритериальной задачи о назначениях

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