§ 62. Задача о назначении

Эта задача уже была сформулирована в § 54 Здесь мы продолжим ее изучение и покажем ее связь с результатами предыдущего параграфа

Пусть имею работников, должностей и мера ценности (стоимость) работника на должности равна

Рассмотрим булеву матрицу размера такую, что

Матрица называется матрицей назначения.

Имеем

и если

то матрица назначения называется насыщенной.

Рис. 488

Рис. 489.

В этих терминах задача о назначении формулируется следующим образом: найти насыщенную матрицу назначения, для которой

На рис. 488 приведен пример матрицы а на рис. 489 — насыщенная матрица назначения с общей стоимостью

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

опору простого графа. Для иллюстрации приведем пример матрицы на рис. 490.

Предварительно сформулируем одну несложную лемму.

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

Доказательство. Действительно, каждое решение задачи о назначении использует одно и только одно число в каждой строке и каждом столбце. Поэтому единственным следствием уменьшения или увеличения элементов какой-нибудь строки (или столбца) на величину X будет уменьшение или увеличение на X значения каждого решения.

Рис. 490.

Описание алгоритма. Он распадается на семь этапов.

А) Получение нулей. Из каждого элемента столбца вычитаем наименьший элемент этого столбца и образуем матрицу с элементами

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

Матрица имеет нуль в каждой строке и каждом столбце.

Для матрицы на рис. 490 матрица показана на рис. 491, а матрица на рис. 492.

Б) Нахождение полного паросочетания. Ищем решение с нулевым значением для матрицы Если такое решение удается найти, то оно будет оптимальным. В противном случае переходим к В). Для нахождения решения с нулевым значением рассматриваем сначала первую строку матрицы и отмечаем один из ее нулей, а остальные нули, а также другие нули того столбца, где отмечен нуль, зачеркиваем. Затем переходим ко второй строке: если она содержит незачеркнутый нуль, то отмечаем его и вычеркиваем остальные нули этой строки и все другие нули столбца, в котором находится отмеченный нуль. Поступаем аналогично с остальными строками.

В нашем примере (рис, 493) сначала отметили и зачеркнули и Затем отметили зачеркнули и т. д. Насыщенное назначение получить не удалось (строка не содержит отмеченных нулей). Переходим к В),

В) Нахождение максимального паросочетания. Используем алгоритм, изложенный на стр. 390—391, но здесь вместо единиц будем обращать внимание на нули.

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

Рис. 491.

Рис. 492.

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

Рис. 493

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

Если максимальное паросочетание дает насыщенное назначение, то оптимальное решение получено и процесс останавливается. В противном случае переходим к Г).

Г) Нахождение минимальной опоры (минимального множества линий, содержащего все нули). Действуем последовательно:

а) помечаем кружком каждую строку, не содержащую отмеченных нулей;

б) помечаем кружком каждый столбец, содержащий зачеркнутые нули какой-либо из помеченных кружком строк;

в) помечаем кружком каждую строку, содержащую отмеченный нуль в каком-нибудь столбце, помеченном кружком;

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

Можно нумеровать помечаемые строки и столбцы по мере их получения (как это сделано для нашего примера на рис. 494, 495), но необходимости в этом нет.

Рис. 494.

Рис. 495.

Таким образом, приходим к минимальному множеству линий (т. е. строк пли столбцов), содержащих все нули матрицы

Д) Выделение минимальной опоры. Проведем пунктирные линии через все не помеченные кружком строки (в нашем примере и все помеченные кружком столбцы (в нашем примере Эти пунктиры обозначат минимальную опору.

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

В нашем примере единица вычитается из элементов столбцов и прибавляется затем к элементам строк Получаем матрицу на рис. 496.

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

не расположены в одной строке или одном столбце (это решение может не быть единственным). Значение этого решения определяется через числа стоящие на тех же местах в матрице

В нашем примере оптимальное решение получено уже на рис. 495 (легко показать, что оно единственно).

Рис. 496

Рис. 497.

На рис. 497 приведены значения и видно, что значение оптимального решения равно

Случай Если то присоединим к матрице размера строк, состоящих из нулей, и с полученной матрицей поступаем так, как было описано.

Рис. 498.

Пример дается матрицей на рис. 498; процесс вычислений показан на рис. 499—502.

2) Если то присоединяем к матрице размера столбцов, состоящих из нулей, и с полученной матрицей поступаем так, как было описано.

Пример этого дается матрицей на рис. 503; процесс вычислений показан на рис. 504—507.

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

1) Находят число

(очевидно, что матрица не должна содержать символа

(кликните для просмотра скана)

(кликните для просмотра скана)

2) Находят далее минимальное решение задачи о назначении для матрицы с

тогда

Если А — множество насыщенных назначений и , то

Рис. 510.

Рис. 511 Насыщенное назначение.

Рис. 512.

Рис. 513.

Пример. Минимальное назначение для матрицы имеет значение 16. Отсюда значение максимального назначения! есть Процесс вычислений представлен на рис. 508—513.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)