ПОИСК Статьи Чертежи Таблицы СОГЛАСОВАНИЕ ГРУППОВЫХ РЕШЕНИЙ НА ОСНОВЕ ПРЕДПОЧТЕНИЙ ЛПР В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ из "Компьютерная поддержка принятия решений " Применение скалярного критерия и методов свертки позволяет линейно упорядочивать сравниваемые объекты, т.е. выстроить их по старшинству оценок. Ранжирование по Парето (это понятие объясняется ниже) позволяет упорядочивать объекты не линейно, а по группам, считая, что все объекты внутри группы равноценны, т.е. перейти от линейного упорядочивания к групповому. При этом очередность устанавливается не между отдельными объектами, а между их равноценными группами. Такой подход не дает никаких преимуществ, если упорядочивание производится по одному показателю, но открывает новые возможности, если таких показателей несколько. Например, показателями, характеризующими задачу или процесс, решаемые на ЭВМ, могут являться объем оперативной памяти, занимаемой программой, время ее решения, время занятости каналов связи для передачи данных и т.д. В многопроцессорных системах групповой подход при организации очередей задач может оказаться достаточно эффективным, так как на многопроцессорной системе можно одновременно выполнять группу задач или процессов. [c.234] Выше уже приводилось определение правила выбора по Парето. Повторим его. Будем считать, что объект Ь строго предпочтительнее объекта 1к, если оценка объекта Ь превосходит оценку объекта (к, хотя бы по одному показателю, а по всем остальным показателям не хуже нее. [c.234] Например, пусть программа Ь характеризуется следующими показателями требуемый объем оперативной памяти 10 кбайт, время решения - 7 сопрограмма Ь - 10 Кбайт и 5 с соответственно. Для краткости запишем это в виде 1 = 10,7 , Ь = 10,5 . И пусть лучшей считается та программа, у которой требуемый объем памяти и время решения меньше. Тогда программа Ь будет строго предпочтительнее программы 1 , так как по второму показателю она лучше, а первый показатель у обеих одинаков. Если бы лучшей считалась та оценка, у которой показатели имеют большие значения, то это была бы оценка Ь. [c.234] Отсутствие требования линейного упорядочивания оценок позволяет объединить некоторые несравнимые и эквивалентные по оценкам объекты в одну группу и этой группе присваивать номер, определяющий ранг группы. Будем считать, что чем меньше номер, тем выше ранг группы объектов. [c.235] Разбиение объектов на группы будем осуществлять следующим образом отберем такие объекты, для каждого из которых в очереди не существует оценок строго их предпочтительнее. Такие оценки называются оптимальными по Парето. Таким объектам присвоим ранг 1. Аналогично для оставшейся группы объектов (т.е. для тех, которые не вошли в первоочередные) выделим оптимальные и им присвоим ранг 2. [c.235] Изложенный принцип разбиения на классы поясним на следующем примере. Пусть предпочтение в обслуживании отдается наиболее коротким (по времени) и требующим наименьшего объема оперативной памяти задачам, решаемым на вычислительной машине. Естественно, что для наиболее коротких задач не обязательно требуются наименьшие объемы оперативной памяти. [c.235] Необходимо подчеркнуть, что это единственная информация, которая требуется от эксперта или ЛПР. ЛПР должен сказать системе поддержки принятия решений, что значит лучшие когда чего-то больше, что-то легче, быстрее, надежнее, объемнее, меньше и т.д. Затем в систему вводятся характеристики сравниваемых объектов и по приведенным ниже алгоритмам (или каким-нибудь другим) СПР выдает результаты ранжирования. [c.235] Число задач каждого ранга определяется оценками задач, ожидающих в очереди. Возможны следующие случаи все задачи имеют одинаковый ранг, все задачи имеют различный ранг, существуют задачи как с одинаковыми, так и с различными рангами. [c.236] Оценка возможных решений... [c.237] На рис. 3.23.Ь показан другой крайний случай, когда все задачи имеют различные ранги. Это значит, что на основе рассмотренного принципа все задачи могут быть строго линейно упорядочены. При этом каждая задача высшего ранга превосходит все задачи более низкого ранга по всей совокупности показателей. [c.237] Наконец, уже был рассмотрен промежуточный, наиболее типичный и практически важный случай, когда задачи имеют как одинаковые, так и различные ранги (см. рис. 3.22). [c.237] Метод определения рангов объектов, оцениваемых по Парето, рассмотрим на примере. [c.237] Рассмотренные свойства объектов и метод построения матрицы позволяют осуществлять ранжирование объектов. Продемонстрируем это на следующем примере, считая, что задача предпочтительнее, если ее требования на ресурсы больше. [c.238] Пусть в очереди операционной системы имеется девять задач, решаемых на ЭВМ. Каждая задача характеризуется тремя показателями временем использования канала ввода-вывода, временем решения, объемом занимаемой оперативной памяти. Характеристики задач приведены в табл. 3.41. [c.238] Например, сравним задачу Ь с задачей Ь (см. табл. 3.41). Значения первых показателей у них равны (1). Значение второго показателя задачи г больше значения соответствующих показателей задачи Ь (19 и 7). Значение третьего показателя задачи Ь также больше значения третьего показателя задачи Ь (20 и 19). Условие выполнено, и а21 = 1 (см. табл. 3.42). [c.238] Оценка возможных решений... [c.239] Сравним задачи Ь и 1з. Значения первого и второго показателей задачЬиЬ равны (1 и 19), а значение третьего показателя задачи Ь больше значения соответствующего показателя задачи Ь (20 и 19). Следовательно, 325 =1. [c.239] Например, значение второго показателя задачи 1 меньше значения соответствующего показателя задачи 1б (7 и 17), а остальные значения показателей больше. Тем не менее а =0. [c.239] В табл. 3.42 приведена матрица, у которой значения ау вычислены для данных табл. 3.41 в соответствии с рассмотренными выше условиями. Цифры первого столбца и первой строки обозначают номера задач. Для того чтобы определить группу задач ранга I, достаточно найти столбцы, в которых стоят только нули. Такими столбцами будут 2,6,8 и 9-й. Задачи с этими номерами получат ранг 1. Эти задачи и должны быть выбраны на решение. Какая из этих четырех задач должна идти раньше других без дополнительной информации, определить нельзя. С точки зрения выбранного нами упорядочивания они равноценны. В многопроцессорной системе при наличии четырех процессоров на решение могут быть выбраны они все. Если число процессоров меньше 4, то некоторые из них будут решаться во вторую очередь. Если число процессоров больше 4, то на решение могут быть выбраны некоторые задачи из группы ранга 2. Определим эту группу. Вычеркнем из матрицы столбцы 2,6,8,9 и соответствующие им строки. [c.239] Получим матрицу (табл. 3.43). Опять найдем столбцы, содержащие только нули. Такими столбцами будут 4, 5 и 7-й. Задачам с этими номерами присвоим ранг 2. И снова вычеркнем из матрицы эти столбцы и соответствующие им строки. Получим матрицу (табл. 3.44), состоящую только из нулей. Задачам Ь и Ь присвоим ранг 3. Ранжировка задач закончена. [c.240] Вернуться к основной статье