ПОИСК Статьи Чертежи Таблицы Принципиальная возможность решения многокритериальной задачи о назначениях из "Объективные модели и субъективные решения " Информация, содержащаяс я в порядках fv, S , может быть занесена в матрицу М, аналогичную по своему построению ма ице М. На пересечении строки и столбца матрицы М находится клетка Д Д, показывающая -й ранг объекта в линейном порядке, построенном для субъекта, и /-й ранг субъекта в порядке, построенном для объекта. После заполнения матрицы М возникает вопрос принципиального характера всегда ли имеется возможность сделать очевидные назначения, всегда ли встречаются клетки Di Di Ответ на этот вопрос дают приведенные ниже результаты. [c.60] Теорема 1. Если в каком-либо из графов подобия Ту, S . имеется вершина с нулевыми оценками по всем критериям, то в матрице М имеется клетка D) D,. [c.60] Доказательство. Согласно (3), (5), вершины с нулевыми оценками по всем критериям являются доминирующими на графах подобия Ту, S . Согласно (1), (2), такая доминирующая вершина имеется как в графе Ту, так и в графе S, , причем вектору Qv соответствует вектор Оу,-. Следовательно, на пересечении v-ro столбца и 1-й строки матрицы М возникает клетка D, Z) что и требовалось доказать. [c.60] В общем случае необходимый результат устанавливает следующая теорема. [c.60] Из (22) — (24) следует, что в линейном порядке, построенном для С), объект О, находится выше объекта в линейном порядке, построенном для Оу, субъект С,- находится выше, чем в порядке, построенном для С,-, объект Оз находится выше, чем 0 Отсюда можно сделать вывод, что в порядке, построенном для О,, субъект С( должен быть выше, чем С1. Однако из (25) следует противоположное. Легко увидеть, что противоречие исчезает, если допустить существование клетки хотя бы на одном из пересечений строк С), i и столбцов Оу, О,-. [c.61] В общем случае графе Г,- индекс D может иметь иная вершина, чем С -. Тогда такое же JIpoтивopeчиe возникнет позже, когда вершина графа с индексом D окажется в уже встречавшейся р-й строке или вершина графа окажется в уже встречавшемся -м столбцу. Так как общее число строк и столбцов матрицы М равно 2 , то указанное противоречие встретится не позднее чем через 2п шагов. Очевидно, что противоречие устраняется при наличии хотя бы одной клетки 01 0, на пересечениях встречавшихся строк и столбцов, что и требовалось доказать. [c.61] Вернуться к основной статье