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

Полученное выше противоречие означает, что при
переходе от матрицы М к матрице `М одна часть ин­
формации позволила определить, что субъект Сi ближе к объекту Oj, чем субъект С1 а другая часть ин­
формации определяла прямо противоположное. По
условию теоремы линейные порядки непротиворечивы,
 что позволяет сделать вывод о  наличии хотя бы
одной клетки D1/D1 на пересечениях строк С1i и
столбцов Ov, Oj.                  

В общем случае в графе `Tj индекс D1 может иметь иная вершина, чем С1j.

Тогда такое же противоречие возникнет позже, когда вершина графа `Tk с индексом D1 окажется в уже встречавшейся р строке или вер­шина графа `Sp окажется в уже встречавшемся k-м столбце. Так как общее число строк и столбцов мат­рицы  ` `M`(с чертой) равно 2n, тоуказанноепротиворечие встре­тится не позднее чем через 2п шагов. Очевидно, что противоречие устраняется при наличии хотя бы одной клетки D1/D1 на пересечениях встречавшихся строк и столбцов, что и требовалось доказать.

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

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

 

 


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