7.4. Пример решения задачи о назначениях.
Пусть в виде таблицы дана матрица несоответствия «претендентов» , , , , имеющимся «должностям» , , , , ( ):
Таблица 1.
-
7
2
1
9
4
9
6
9
5
5
3
8
3
1
8
7
9
4
2
2
8
4
7
4
8
Если вначале дана матрица соответствия , то элементы матрицы определим по формулам .
Определим начальные значения потенциалов, положив и . Другими словами, потенциал положим равным наименьшему из тарифов в - том столбце. Нетрудно проверить, что так определенные потенциалы удовлетворяют условиям : , поскольку . Значения потенциалов запишем в добавленный справа к таблице столбец, а потенциалов в добавленную снизу строку. Кроме того, в клетки таблицы, удовлетворяющие условию запишем «потенциальные» единицы.
Таблица 2.
-
7
1 2
1 1
9
4
0
9
6
9
5
5
0
1 3
8
3
1 1
8
0
7
9
4
2
1 2
0
8
4
7
4
8
0
3
2
1
1
2
Очевидно, что в силу определения и равенство будет выполняться в тех клетках - того столбца, в которых значение тарифа является наименьшим в соответствующем столбце (именно в этих клетках мы и поставили единицы). Заметим, что если бы оказалось ровно по одной единице в каждом столбце и в каждой строке, то есть всего 5 допустимых единиц, то согласно п.7.3 мы получили бы оптимальное решение задачи, положив для соответствующих допустимых единиц (а все остальные полагая равными нулю). Выберем теперь из имеющихся 6 потенциальных единиц максимально возможное число единиц так, чтобы в каждом столбце и в каждой строке стояло не более одной (допустимой) единицы. Разумеется, это можно сделать методом полного перебора, но мы хотим указать не метод «тыка», а способ, дающий эффективное решение задачи выбора допустимых единиц, основванный на известном алгоритме Форда-Фалкерсона. Для этого будем считать переменные , , , , и , , , , вершинами некоторой сети. Снабдим эту сеть (фиктивным) входом и (фиктивным) выходом , соединив вход дугами с вершинами , , , , и вершины , , , , с выходом (см. рис. 1). Кроме того, каждой потенциальной единице, стоящей в -той строке и -том столбце таблицы 2, сопоставим дугу с началом и концом . В результате получим следующую сеть.
Рис.1. Сеть для таблицы 2.
Кроме того, в таблицу снизу добавлена строка для определяемой ниже невязки и одна вспомогательная строка, смысл которых прояснится в дальнейшем и
С помощью условия (3) определим заполненные клетки таблицы. В первом столбце ( ) равенство будет иметь место
добавив столбец для переменных , строку для переменных и две специальных строки, назначение которых станет ясно
-
7
2
1
9
4
9
6
9
5
5
7
8
3
1
8
7
9
4
2
2
8
4
7
4
8
невязка
строка
-
α
α1
7
12
11
9
4
0
α2
9
6
9
5
5
0
α3
1 3
8
3
1
8
0
α4
7
9
4
2
12
0
α5
8
4
7
4
8
0
min βj
3
2
1
1
2
невязка
строка