Алгоритм решения задачи о назначениях

Этот алгоритм состоит из трех этапов.

Этап 1:

1. Формализация проблемы в виде транспортной таблицы по аналогии с решением

транспортной задачи.

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

3. Повторить ту же самую процедуру для столбцов.

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

486 Ч. 4. Моделирование в бизнесе

Этап 2.

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

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

2. Зачеркнуть оставшиеся нулевые значения данного столбца.

3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным.

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

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

5. Зачеркнуть оставшиеся нули в данной строке.

6. Повторять пункты 4 и 5 до тех пор, пока дальнейшая их реализация окажется невозможной.

Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.

Этап 3-

1. Провести минимальное число прямых через строки и столбцы матрицы (но не по диагоналям) таким образом, чтобы они проходили через все нули, содержа­щиеся в таблице.

2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых.

3. Вычесть его из всех элементов, через которые не проходят прямые.

4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых.

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

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

□ Пример 13.7. Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские поме­щения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В табл. 13.29 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной?

Гл. 13. Транспортная задача и задача о назначениях 487

Таблица 13.29. Расстояние от сбытовых баз до потребителей

Сбытовая база	Расстояние, миль Потребители
I	II	III	IV
А В С D	68 56 38 47	72 60 40 42	75 58 35 40	83 63 45 45

Решение

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

Этап 1 Венгерского метода: В каждой строке находится наименьший элемент. Таблица 13.30. Выявление наименьших элементов по строкам

	Потребители	Наименьший элемент строки
I	II	III	IV
А В С D	68 56 38 47	72 60 40 42	75 58 35 40	83 63 45 45	68 56 35 40

Наименьший элемент вычитается из всех элементов соответствующей строки

Таблица 13.31. Вычитание наименьшего элемента по строкам н выявление наименьшего элемента по столбцам

				Наименьший

Найденный наименьший элемент вычитается из всех элементов соответствую­щего столбца.