Общая задача назначения п работников на п работ представлена в табл. 5.31. Таблица 5.31
Коэффициент сц равен стоимости назначения работника i на работу j (i,j= 1, 2, n). То, что количество работников равно количеству работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.
Задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы - пунктам назначения. В данном случае все величины спроса и предложения равны 1. Стоимость "транспортировки" рабочего i на работу равна cv. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу. Вместе с тем тот факт, что все величины спроса и предложения равны 1, привел к разработке упрощенного алгоритма решения, названного венгерским методом. Хотя этот метод не имеет никакого отношения к транспортной задаче, он, как и метод потенциалов, все равно основан на симплекс-методе.
5.4.1. Венгерский метод7
Для представления этого метода используем два примера. Интерпретация венгерского метода как симплекс-метода будет рассмотрена в следующем разделе.
Пример 5.4.1
Трое детей Джоя Клини - Джон, Карен и Терри - желают подзаработать немного денег на школьную экскурсию в местный зоопарк. М-р Клини выбрал три вида работ, которые дети выполнить могут за определенную плату: стрижка газона, уборка гаража и мойка семейного автомобиля. Чтобы избежать ненужных споров между детьми, он опросил каждого (конечно, по секрету), сколько за каждый вид работ они хотят получить. Результаты опроса (в долл.) представлены в табл. 5.32.
Таблица 5.32
| Стрижка газона | Уборка гаража | Мойка машины |
Джон | | | |
Карен | | | |
Терри | | | |
Классический венгерский метод, как и методы решения транспортной задачи, первоначально разрабатывался для ручных вычислений и сегодня, в основном, представляет только исторический интерес. В настоящее время нет необходимости в таких "быстрых" ручных вычислительных алгоритмах, поскольку задачи этого класса эффективно решаются как обычные задачи ЛП с помощью мощной современной вычислительной техники.
Основываясь на этой информации, как распределить работы между детьми с минимальными (денежными) потерями для м-ра Клини?
Решим эту задачу о назначениях венгерским методом.
Этап 1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.
Этап 2. В матрице, полученной на первом этапе, найдем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.
Этап 3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем этапе.
Обозначим через pt и qt минимальные стоимости соответственно в строке / и столбце у, определенные на первом и втором этапах описанного выше алгоритма. Минимальные стоимости по строкам находятся по исходной матрице стоимостей, как показано в табл. 5.33.
Таблица 5.33
Стрижка газона Уборка гаража Мойка машины Минимумы по строкам
Джон | | | | Pi =9 |
Карен | | | | Д2 = 9 |
Терри | | | | Рз = 8 |
Теперь вычтем минимальные стоимости из элементов соответствующих строк, и в результате получим следующую матрицу.
Таблица 5.34
| Стрижка газона | Уборка гаража | Мойка машины |
Джон | | | |
Карен | | | |
Терри | | | |
Минимумы по столбцам | Oi =0 | 02=1 | 9з = 0 |
На втором этапе алгоритма находим минимальные значения по столбцам и вычитаем их из элементов соответствующих столбцов. В результате получим матрицу, представленную в виде табл. 5.35.
Таблица 5.35
| Стрижка газона | Уборка гаража | Мойка машины |
Джон | | | |
Карен | | | |
Терри | | | |
В последней матрице подчеркнутые нулевые элементы определяют оптимальное решение: Джон будет убирать в гараже, Карен подстригать газон, а Терри достанется мойка машины. Эти работы обойдутся м-ру Клини в 9 + 10 + 8 = 27 долл. Отметим, что эта сумма всегда равна (р, + р2 + р3) + (<?, + q2 + q3) = (9 + 9 + 8) + + (0 + 1 + 0) = 27 долл. (Доказательство этого приведено в следующем разделе.)
Алгоритм венгерского метода в предыдущем примере завершен успешно, поскольку нулевые элементы в конечной матрице соответствуют допустимому решению (в том смысле, что каждому ребенку назначена в точности одна работа). В некоторых случаях нулевые элементы, полученные на первом и втором этапах венгерского метода, не позволяют непосредственно получить допустимое решение. Тогда необходимы дополнительные действия. Следующий пример демонстрирует это.
Пример 5.4.2
Предположим, что в примере 5.4.1 представлено четыре ребенка и четыре вида работ. Таблица 5.36 соответствует матрице стоимостей для этой задачи (данные представлены в долл.).
Таблица 5.36
Применение первого и второго этапов алгоритма к исходной матрице (при этом рх =1, рг = 7, р3 = 4, р4 = 5, <?, = 0, q2 = 0, <?3 = 3 и <?4 = 0) приводит к следующей матрице (проверьте!).
Таблица 5.37
Виды работ 2 3
Дети
В последней матрице расположение нулевых элементов не позволяет назначить каждому ребенку одну работу. Например, если мы назначим первому ребенку работу 1, из дальнейшего рассмотрения исключается первый столбец, и тогда в строке третьего ребенка не окажется нулевых элементов. Подобные проблемы можно разрешить, добавив к описанной в примере 5.4.1 процедуре следующий этап.
Этап 2.1. Если после выполнения первого и второго этапов описанного алгоритма не получено допустимое решение, выполните следующие действия.
i) В последней матрице проведите минимальное число горизонтальных и вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все нулевые элементы.