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

↑

⇐ ПредыдущаяСтр 127 из 159Следующая ⇒

Чтобы привести формальную постановку МЗН, введем следующие понятия, термины и обозначения. Имеются два исходных множества по n элементов: С{n} и O{n}. Обозначим: C{C₁, C₂, ..., C_i, ..., C_n} — первое множество, элементы которого назовем субъектами; О{О₁, О2, ..., O_j, ..., О_n} - второе множество, элементы которого назовем объектами.

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

Часть критериев отражает требования субъектов и возможности объектов, другая часть — требования объектов и возможности субъектов. Введем следующие обозначения: S_k(S₁, S₂, ..., S_m, ..., S_w} — множество оценок на шкале k-ro критерия; Sk_m — m-я по порядку оценка на шкале k-ro критерия; Tik_p — р-я по порядку оценка на шкале требований i-го элемента по k-му критерию; Vju_t — t-я оценка на шкале возможностей j-ro элемента по u-му критерию.

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

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

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

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

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

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

Дано: два множества: C_i (I = 1,2, ..., n) и O_j (j = l,2, ..., n); оценка каждого элемента двух множеств по N критериям (k₁, k₂, ..., k_N).

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

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

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

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США