Задача о назначениях (о женихах)

Пусть имеется пять человек с номерами М₁,М₂,М₃,М₄,М₅. Каждый из них способен выполнять разные работы Т₁,Т₂,Т₃,Т₄,Т₅. Время, которое они затрачивают на выполнение этих работ, указано в матрице стоимости

     Оценки в матрице стоимости выставляются на основании экспертных оценок. Это время в в минутах для выполнения задания. Как распределить людей по заданиям, чтобы  суммарное время выполнения работ было минимальным.

Пусть x_ij-участие (1) или неучастие (0) i-го человека в выполнении j-го задания.

       x_ij>=0, x_ij=0,1

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

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅=1-в каком-то из заданий каждый человек будет

........                             участвовать

x₅₁+x₅₂+x₅₃+x₅₄+x₅₅=1

и ограничений

x₁₁+x₂₁+...+x₅₁=1 -ограничения

.....

x₁₅+x₂₅+... x₅₅=1

Условие на минимальное время запишется в виде

min T=10x₁₁+5x₁₂+...+19x₅₄+10x₅₅

Задача является частным случаем транспортной задачи, люди представляют исходные пункты, а работа -пункты назначения. Предложения в каждом исходном пункте равны 1, т.е. a_i=1 для всех i, спрос b_j=1 тоже. Стоимость перевозки (прикрепления человека i за работой j) равна c_ij. Если какого-то человека нельзя назначить на работу , то c_ij=M-большое число.

Задачу о назначениях можно представить следующим образом:

Пусть x_ij=0, если j-е задание не выполняется i-м человеком и x_ij=1, если выполняется. Тогда задача сводится к минимизации Z=S_j=1ⁿS_j=1ⁿc_ijx_ij при ограничениях

S_j=1ⁿx_ij=1, i=1,...n  ,  S_i=1ⁿx_ij=n    j=1,..n      x_ij=0 или 1

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

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

Мeтод Мака является итерационным процессом и основан на выборе в каждой строке min элемента.

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

Программы, реализующие алгоритм Мака, приведены в книге /10/.