Модель максимального согласования

Простейшей моделью, относящейся к моделям второй группы, является модель максимального согласования, которая при­меняется для анализа простых структур без равноценных элементов (в матрице только 0 и 1). В данной модели анализируется некоторое упорядочивание I, например упорядочение, определенное порядковыми номерами альтернативных вариантов. Затем это упорядочивание сравнивается с матрицей А, содержащей результаты бинарного сравнения аij. Если в I-м упорядочивании i-й элемент предшествует j-му, а в матрице А аji =1, то такая ситуация называется минимальным несогласием. В этом случае упорядочивание I корректируется.

Задачей согласования является отыскание такого оптимального упорядочивания I*, чтобы число несогласий было минимально. Графически решение задачи представляется штриховкой правого верхнего угла матрицы А, в котором должны содержаться единичные элементы.

Задачи такого класса относятся к сложным задачам. Их решение сопряжено с решением трудных проблем комбинаторной оптимизации.

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

Метод идеаль­ной точки

Положим, что каждый альтернативный вариант хi, описыва­ется вектором в пространстве Rn. Определим в этом пространстве идеальную точку а° = (а1°,..., аn°). Такая точка оптимальна сразу по всем критериям. Как правило, идеальная точка а° не принадлежит множеству W.

Зададим на пространствеRn расстояние d(а°, хi), которое вводится аксиоматически: 1). d(а°, хi) ³ 0; если а°= хi, то d(а°, хi) = 0.

2). d(а°, хi) = d(хi, а°).

3). d(а°, хj) + d(хj, хi) ³ d(а°, хi).

Исходя из этих аксиом, можно ввести различные функции расстояния с общим видом

, где S - целое число.

Если S =2, то получаем евклидово расстояние

Если S =1 имеем .

При S=¥ получим равномерную метрику:

В этом случае лучшей альтернативой является альтернатива, имеющая наименьшее расстояние между значением наихудшего параметра (оценки по критерию) и значением этого параметра для идеальной точки.

Упорядочивание вариантов производится по полученному значению d.

Пусть, например, анализируются четыре альтернативных варианта ЭВМ W = {х1, х2, х3, х4}. Каждый вариант характери­зуется двумя координатами: емкостью оперативной памяти и тактовой частотой х1=(4 Мб, 16 МГц); х2=(8 Мб, 16 МГц); х3=(4 Мб, 32 МГц); х4 = (16 Мб, 16 МГц). Тогда идеальной точ­кой будет а°=(16 Мб, 32 МГц). Будем упорядочивать варианты, полагая, что 1 Мб памяти эквивалентен 1 МГц тактовой частоты.

Используя евклидово расстояние, получим:

d(х1, а°) = =20;

d(х2, а°)»17,9; d(х3, а°)=12; d(х4, а°)=16.

Наилучшим в этом случае будет третий вариант. Если использовать равномерную метрику, то наилучшим будет третий вариант, а остальные варианты имеют одинаковое значение d¥ и не могут быть упорядочены.

Для метрики d1: х3 > х4 > х2 > х1.

Данный пример показывает, что при выборе метрики нужно иметь дополнительную информацию, определяющую важность отстояния критериев от идеальной точки.

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

Метод "идеальной точки" подразумевает предварительное заданиеэтой точки а° =(а1°, ..., аn°). В ряде практических задач определение отдельных координат аi° идеальной точки не может быть осуществлено однозначно иди с достаточной точностью. В этих случаях производится построение других форм интегральных критериев.








Дата добавления: 2018-06-28; просмотров: 241;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.