Решение многокритериальной задачи о назначениях, страница 18

Строки - С₁,  С₂   ,.., С_n       Столбцы – O₁ , O₂  ,.., O_n

Столбцы матрицы сходства соответствуют объек­там, а строки —субъектам. Клетка, находящаяся на пересечении v-ro столбца и m-й строки, должна ха­рактеризовать оценку v-ro объекта со стороны m-го субъекта и оценку m-го субъекта со стороны v-ro объ­екта.

В клетку матрицы M, находящуюся на пересече­нии v-ro столбца и m-й строки, занесены два индекса. В правой верхней части клетки находится индекс, от­носящийся к графу подобия T_v, a r левой нижней ча­сти— индекс, относящийся к графу подобия S_m. При помощи матрицы сходства М можно формально опре­делить введенное выше понятие очевидного назначе­ния. Очевидному назначению соответствует клетка мат­рицы сходства с индексами D₁/D₁. Наилучшему ре­шению (n очевидных назначений) соответствует слу­чай, когда после перестановки столбцов и строк мож­но получить матрицу сходства, на главной диагонали которой находятся все клетки с элементами D₁\D₁.

При заполнении матрицы сходства возможны сле­дующие три случая:

а)  есть хотя бы одна клетка D₁/D₁;

б) в каком-либо столбце пли строке имеется не­сколько клеток D₁/D₁;

в)   нет клеток D₁/D₁.

В случае а) можно сразу же сделать идеальные назначения и понизить размерность рассматриваемой задачи. После понижения размерности необходимо вернуться к графам подобия T_v, S_m. Выделяемые ядра будут также совсем иными. Далее возникает новая матрица М сходства, выделяются (если они сущест­вуют) новые очевидные назначения и т. д. Результа­ты, приведенные выше, позволяют предположить, что при небольшом числе (3—4) оценок на шкалах кри­териев вероятность появления клеток D₁/D₁ является достаточно высокой.

В случае б) появляется возможность сделать сра­зу несколько назначений. Для получения их возмож­но большего количества следует использовать алго­ритм определения максимального числа паросочетаний [8].