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

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

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

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

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

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

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

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

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