Найти оптимальный вариант назначений, если матрица эффективностей такова: (венгерский метод)

Решение. Предварительный этап.

Шаг 1. наибольший элемент первого столбца матрицы равен 26.

Поэтому для получения элементов первого столбца матрицы необходимо из 26 вычесть последовательно элементы первого столбца матрицы и поместить полученные результаты в соответствующие позиции первого столбца искомой матрицы. Аналогично для образования столбцов 2, 3, 4, 5 и 6 матрицы вычесть из величин 23, 26, 30, 27 и 27. Получим матрицу:

Шаг 2. Наименьший элемент первой строки матрицы равен 3. Для получения элементов первой строки матрицы необходимо число 3 вычесть последовательно из каждого элемента первой строки матрицы и поместить полученные результаты на прежние места. Во второй строке из каждого элемента вычитаем число 2, в третьей — число 9. Строки 4, 5 и 6 не изменятся, так как минимальные элементы этих строк равны нулю.

После второго шага предварительного этапа получим матрицу:

+ + + +.

П. 1. В первом столбце матрицы помечаем звездочкой нуль, расположенный в шестой строке; во втором столбце помечаем звездочкой нуль, расположенный в пятой строке. В 3, 4 и 5 столбцах помечаем звездочкой нули, расположенные соответственно в первой, второй и четвертой строках. В шестом столбце единственный нуль расположен в пятой строке, в которой уже есть и поэтому не может быть помечен звездочкой.

Число нулей со звездочкой меньше 6, переходим к пункту 2.

П. 2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4 и 5 и считаем эти столбцы занятыми. Незанятый нуль находится в пятой строке шестого столбца. Помечаем его штрихом. В пятой строке есть, переходим к пункту 3.

П. 3. Знак «+» у второго столбца снимаем и вновь считаем его незанятым столбцом, а пятую строку считаем занятой и помечаем знаком «+» справа. Снятие любого значка, в дальнейшем, условимся обводить в рамочку. Возвращаемся к третьему абзацу пункт 2. Незанятых нулей нет. Переходим к пункту 5.

П. 5. Среди незанятых элементов выбираем минимальный:. Сначала вычитаем из всех незанятых строк, а затем прибавляем ко всем занятым столбцам. Получаем матрицу эквивалентная предыдущей, и содержащая незанятые нули.

+ +.

Возвращаемся к четвертому абзацу пункта 2.

П. 2. Незанятые нули находятся в первой строке второго и шестого столбцов: Первый из них помечаем штрихом. В третьем столбце первой строки находится нуль со звездочкой. Третий столбец вновь считаем незанятым и знак «+» сверху снимаем, а первую строку объявляем занятой и помечаем знаком «+» справа. Незанятый нуль находится в освободившемся 3 столбце в позиции (6,3). Помечаем штрихом и считаем незанятым первый столбец, а 6 — ю строку объявляем занятой. Незанятых нулей нет. Переходим вновь к пятому пункту.

П. 5. Теперь. Вычитаем из незанятых строк: второй, третий и четвертый, а затем прибавляем к занятым столбцам: четвертому и пятому. Получим матрицу, в которой образовалось два незанятых нуля: и .

Переходим к пункту 2. Помечаем штрихом. Имеем два незанятых нуля: и. Первый из них помечаем штрихом. В третьей строке нет, следовательно, переходим к пункту 4.

П. 4. Строим цепочку из нулей. Начинаем от, идем по столбцу до, по строке — до, по столбцу — до, по строке — до, по столбцу — до, по строке — до, по столбцу — до, и наконец, по строке — до. Цепочка имеет вид:

.

Вносим изменения в цепочке: звездочки у нулей в цепочке снимаем, а вместо штрихов у нулей в цепочке ставим звездочки:

.

Все пометки, кроме звездочек, убираем. Получим новый набор, который содержит на один больше, чем предыдущий набор.

Процесс окончен, так как число нулей со звездочкой равно 6, что соответствует размерности матрицы эффективностей (n=6). Оптимальный вариант назначения имеет вид:. Остальные, т. е. первый механизм назначается на вторую работу, второй — на первую, третий — на четвертую, четвертый — на пятую, пятый — на шестую, шестой — на третью. При этом варианте назначения получим максимальную эффективность:

19+22+21+27+27+26=142 единиц эффективности.

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

Кроме того, из оптимального варианта, полученного методом потенциалов, можно получить оптимальный вариант, полученный методом Эгервари, если в качестве разрешающей коммуникации выбрать коммуникацию (1,2).