Эвристический алгоритм

Пусть - матрица потерь множества ранжирований.

1-ая интерпретация. Подсчитаем . Найдем

Альтернативу а_i1 ставим на первое место в искомом ранжировании. Полагаем S⁽¹⁾ = s_i1. Вычеркивая в строку и столбец с номером i₁ получаем матрицу множество индексов строк и столбцов

которой, соответственно:

К-ая интерпретация. В матрице потерь подсчитаем найдем ,

альтернативу a_ik ставим на К-ое место в искомом упорядочении. Полагаем .

Вычеркивая в строку и столбец с номером i_k получаем матрицу , множество индексов строк и столбцов которой . Алгоритм завершается после n-ой итерации , искомое упорядочение:

Последовательно проверяем справедливость соотношений . Как только для некоторого к оно нарушено альтернативы a_ik и a_ik+1 в ранжировании меняем местами, а отношение:, проверяем, начиная с альтернативы непосредственно предшествующей альтернативе подвергшейся перестановке.

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

Пример (для вышеприведенного случая)

Найдем ранжирование Р_I :

1-ая итерация.Подсчитаем:

минимум достигается на

на первое место в ранжировании Р_I помещается альтернатива а₂ и из дальнейших рассмотрений исключается.

2-ая итерация. Подсчитаем:

минимум достигается на , на второе место в ранжировании Р_I помещается альтернатива а₃ и из дальнейших рассмотрений исключается.

3-я итерация. Подсчитаем:

минимум достигается на , на третье место в ранжировании Р_I помещается альтернатива а₄ и из дальнейших рассмотрений исключается.

Таким образом, ранжирование Р_I имеет вид:

Найдем теперь ранжирование P_II

Сравниваем r₄₁ и r₁₄, поскольку альтернативы a_n и a₁ стоят, соответственно, на предпоследнем и последнем местах в ранжировании Р_I

Так как r₄₁ < r₁₄, переходим к сравнению r₃₄ и r_43, т.к. r₃₄ < r₄₃, переходим к сравнению r₂₃ и r₃₂ r₂₃ > r₃₂, поэтому альтернативы а₂ и а₃ меняем местами поскольку r₂₄ < r₄₂, найденное ранжирование и является ранжированием P_II, для которого соотношения , выполнено.