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

При отсутствии клеток D₁/D₁ наилучшие назна­чения должны определяться на основании информа­ции, получаемой от ЛПР.

Отметим, что этап формального анализа может быть осуществлен на ЭВМ.

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

Очевидно, что кандидатами на возможные наилуч­шие назначения являются клетки вида H₁/H₁ или H₁/D₁ ,D₁/H₁, так как только такие клетки при по­лучении дополнительной информации от ЛПР могут перейти в клетки D₁/D₁ соответствующие наилуч­шим назначениям. В общем случае от ЛПР требуется лишь информация, позволяющая сравнить вершины первых ядер графов подобия T_v, S_m; объем этой ин­формации намного меньше, чем объем информации, необходимой для упорядочения всех вершин этих гра­фов.

Итак, после выделения клеток H₁/H₁ ,H₁/D₁ ,D₁/H₁ для каждой из них проводится анализ первых ядер графов подобия, соответствующих данной строке и столбцу. Определяется, по какому числу критериев отличаются вершины этих ядер, а также количество вершин. Отметим, что данный анализ также может быть осуществлен на ЭВМ.

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

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

Итак, предложенный метод решения имеет челове­ко-машинный характер: этапы формального анализа, реализованные в виде программ для ЭВМ, чередуют­ся с этапами получения дополнительной информации от ЛПР.