4.4. Задача «о назначениях»

Задача представляет собой частный случай Т-задачи, когда p_i = = d_j = 1. Отсюда и вид ее модели ЛП.

Модель ЛП

при ограничениях на х_ij:

где х_ij = 0 и 1.

Такие ограничения означают, что в каждой строке и каждом столбце матрицы ||х_ij|| содержится ровно по одной единице. Поэтому уравнение баланса превращается в условиеm = n.

Однако число уравнений остается равным m + n = m + m = 2m. Столько же и переменных х_ij, не равных тождественно 0. Из них m переменных равны 1, поскольку каждая единица содержится в строке и столбце одновременно. Остальные переменные равны 0 (так называемая нулевая поставка в распределительном методе).

Отсюда ясно, что алгоритм задачи может быть значительно упрощен.

Решение задачи «О назначениях»

(венгерский метод)

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

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

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

Шаг 1. Замена минимальных значений с_ij в строках и столбцах матрицы ||с_ij|| нулями с помощью преобразований:

– в строках фиксировано,

– в столбцах фиксировано.

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

Шаг 2. Пробное max назначение. Метятся нули в строках с единственным нулем. Остальные нули в столбцах с помеченным нулем зачеркиваются. Если такие строки исчерпаны, то переходят к столбцам с единственным нулем. В результате все нули в матрице ||с_ij|| оказываются либо помеченными, либо зачеркнутыми. Если назначение полное, то КОНЕЦ. Иначе – переход на шаг 3.

Шаг 3. Построение min опоры (по операциям):

а) помечаем строку без назначения (такая строка найдется, иначе назначение было бы полным);

б) помечаем столбец с зачеркнутым нулем в помеченной строке (такой ноль найдется, иначе строка имела бы назначение);

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

г) повторяем операции б и в пока возможно.

Шаг 4. В матрице ||с_ij|| вычеркиваем помеченные столбцы и непомеченные строки. При этом гарантируется, что вычеркнутые столбцы и строки содержат все нули матрицы ||с_ij|| и их число минимально.

Шаг 5. Среди оставшихся элементов матрицы ||с_ij|| находим минимальный и вычитаем его из них (появляются новые нули), а к элементам на пересечении вычеркнутых строк и столбцов прибавляем его. Остальные элементы остаются без изменения. Переход на шаг 2.

Выводы:

1)

2) теперь можно вычислить F_ц:

где с_ij являются элементами исходной матрицы стоимостей ||с_ij||.

Замечания к решению задачи

1. Если условие баланса нарушено (m ≠ n), то матрица ||с_ij|| дополняется фиктивной строкой или столбцом с нулевыми элементами.

2. Если исходная задача на max F_ц, то она сводится к задаче на min F_ц преобразованием матрицы ||с_ij||:

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

Иллюстративный пример

Пусть требуется решить задачу о назначениях на max F_ц с матрицей стоимостей, представленной ниже. Преобразовав ее в соответствии с замечаниями 1 и 2, последовательно получим матрицы 1 и 2.

Задача свелась к задаче на minF_ц, а матрица стоимостей стала квадратной. Теперь к ней можно применить алгоритм. Сделаем замену минимумов в строках и столбцах нулями = шаг 1 (матр. 2–4).

Матрица 3Матрица 4 Матрица 5

Делаем пробное назначение: помечаем и зачеркиваем соответствующие нули = шаг 2 (матр. 5). Назначение неполное – переходим к шагу 3. На этой же таблице помечаем соответствующие строки и столбцы (см. алгоритм). Вычеркиваем помеченные столбцы и непомеченные строки = шаг 4.

Получаем матрицу 6.

Матрица 6 Матрица 7

Из оставшихся элементов находим min c_ij и выполняем шаг 5. Получаем матрицу 7 и переходим к шагу 2: снова делаем пробное назначение на этой же матрице. Получаем полное назначение, следовательно, задача решена. Матрица ||x_ij||, являющаяся решением задачи, выписывается очевидным образом из матрицы 7. После этого можно вычислить целевую функцию в исходных стоимостях: