Общие процедуры принятия решений на расширенных множествах и графы структур решений.

Необходимо определить процедуры принятия решений на расширенных множествах.

Стратегия 1

Формирование расширенного множества.

Проверка существования допустимых решений для каждого из подмножеств, принадлежащих расширенному множеству.

Оценка решений для всех допустимых подмножеств по критерию предпочтения (сложности).

Выбор наиболее предпочтительного (наименее сложного).

Стратегия 1 наиболее общая, используется, когда необходимо предварительно решить вопрос о существовании допустимых решений.

Где? - в экстремальных задачах комбинаторного типа; в задачах, решаемых итерационными методами.

Стратегия 2. Если оценки предпочтения сформированы или получить их просто.

Формирование расширенного множества.

Оценка предпочтения выбора подмножеств.

Исключение бесперспективных подмножеств (путём формирования и проверки условия , где - допустимая оценка).

Проверка существования допустимых решений для всех Y, удовлетворяющих условию п.3.

Выбор наиболее предпочтительных вариантов решения.

Стратегия 3. Один из вариантов общей стратегии поиска элемента минимальной сложности.

Формирование подмножества в расширенном множестве.

Оценка предпочтения подмножеств.

Упорядочивание подмножеств по предпочтению Y'>Y'', Y''>Y''' и т.д.

Проверка существования допустимых решений для наиболее предпочтительного подмножества Y' и (если в Y' Допустимых решений не существует) в подмножествах Y'', Y''' и т.д.

Этими стратегиями не покрываются все варианты организации процедур решения задач на расширенных множествах альтернатив. Для формирования таких стратегий удобно использовать специальную конструкцию - граф структур решения (ГСР). Он является ориентированным мультиграфом, как правило, …-параллельной формы, в котором каждая вершина отражает факт решения какой-либо подзадачи (или выполнение определённой операции).

Дуги, входящие в каждую вершину, «нагружены» значениями компонентов оценочной функции, функций допустимости и сложности и характеризуют каждую подзадачу (операцию).

Любой маршрут начинается в вершине О и заканчивается в вершине N, и соответствует одному конкретному варианту решения задачи.

Для задачи, представленной на рисунке 2.1 , ГСР - простая цепь из вершины О в вершину N, в которой каждый уровень (подзадача) изображён одной дугой.

ГСР представляет три стратегии.

Стратегия 1: маршрут О, 2, 3, N

Стратегия 2: O, 1, 4, 5, 3, N

Стратегия 3: O, 1, 4, 6, N

Рис. 33 Граф структур решения

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