Имя материала: Теория и методы принятия решений, а также Хроника событий в Волшебных странах

Автор: О.И. Ларичев

5. основные алгоритмы решения многокритериальной задачи о назначениях

 

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

 

5.1. Различные индексы соответствия

 

Подход к решению МЗН основан на поиске ответов на два основных вопроса:

1) как определить ранги всех возможных назначений в матрице назначений М(n´n)?

2) как, зная ранги, найти решение, соответствующее введенному выше критерию оптимальности?

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

1. Формальное соответствие. При этом способе на основе характеристик элементов расчитывается индекс соответствия характеристик объекта и субъекта. Эти индексы используются в качестве ранговых показателей в матрице М(n´n).

2. Относительное соответствие. При этом способе на основе предпочтений ЛПР ранжируются по качеству назначений все субъекты по отношению к каждому из объектов и все объекты по отношению к каждому из субъектов. Суммы соответствующих рангов для пары объект—субъект используются как индексы соответствия и формируют матрицу М(пхп).

3. Абсолютное соответствие. При этом способе на основе предпочтений ЛПР определяется ранг каждого из возможных назначений, т. е. каждой клетке матрицы М(n´n) присваивается ранг, который рассматривается как индекс соответствия.

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

5.2. Поиск решения многокритериальной задачи

        о назначениях

 

В процедуре поиска решения МЗН можно выделить следующие основные этапы.

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

2. Формирование области допустимых решений. На втором этапе реализуются алгоритмы, которые используют преобразованные данные и упрощают исходную задачу для того, чтобы обеспечить ЛПР возможность целостного взгляда на стоящую перед ним проблему. Система поддерживает процедуры интерактивного взаимодействия с ЛПР, который формирует область допустимых решений (ОДР) путем введения логических условий, связанных с запретом определенных назначений или с их принудительным включением в решение МЗН. Результатом работы на этом этапе является новая ОДР и варианты возможных решений МЗН.

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

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

Рассмотрим эти этапы подробнее.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 | 201 |