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

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

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

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

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

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

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

Зададим на пространствеR_n расстояние 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 = {х₁, х₂, х₃, х₄}. Каждый вариант характери­зуется двумя координатами: емкостью оперативной памяти и тактовой частотой х₁=(4 Мб, 16 МГц); х₂=(8 Мб, 16 МГц); х₃=(4 Мб, 32 МГц); х₄ = (16 Мб, 16 МГц). Тогда идеальной точ­кой будет а°=(16 Мб, 32 МГц). Будем упорядочивать варианты, полагая, что 1 Мб памяти эквивалентен 1 МГц тактовой частоты.

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

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

d(х₂, а°)»17,9; d(х₃, а°)=12; d(х₄, а°)=16.

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

Для метрики d₁: х₃ > х₄ > х₂ > х₁.

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

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

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