Задача  о назначениях. Метод  Мака.

     Задача  о женихах и  невестах:

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

     Алгоритм  Мака.

     Рассмотрим  конкретную задачу «о назначениях» и  алгоритм Мака, реализующий ее решение.

     В начале и при каждом возвращении  к началу считаем А – пустым, а А’ – всем остальным.

1. Выбираем в А столбец, содержащий белее одного подчеркнутого элемента. А={2}.
2. Пусть подчеркнутый элемент множества А в строке i =b_i, а минимальный элемент множества А’ из этой же строки равен a’_i. Пусть min_i(a’_i- b_i)= a’_r- b_r.,    r=3, a’₃- b₃=1.
3. Увеличиваем все элементы множества А на это число (т.е. столбец 2 на это число).

6. Подчеркнем  элемент a’_r полностью. Это новый подчеркнутый элемент.

7. Найдем исходный  подчеркнутый элемент и уберем  старое подчеркивание. И обозначим  столбец, где было старое подчеркивание буквой D.

8. Если D не содержит других подчеркнутых элементов, он должен элемент, отмеченный точками, обозначим его a’_r и вернемся к шагу 6. 

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

     Если  в каждом столбце есть подчеркнутый элемент, то оптимум (элементы, соответствующие  оптимальному выбору) должны быть просуммированы и тем самым вычислена минимальная «стоимость».

     Вернемся  к исходным числам:

     Получаем  минимум: 39 

     Примеры использования задачи о назначениях: Оптимальное использование торговых агентов.