Исходная матрица имеет вид:
4	5	7	4	6	
6	6	9	9	9	
6	2	4	6	8	
7	3	6	9	7	
2	5	6	3	7	

Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0	1	3	0	2	4	
0	0	3	3	3	6	
4	0	2	4	6	2	
4	0	3	6	4	3	
0	3	4	1	5	2	

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
0	1	1	0	0	
0	0	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
0	3	2	1	3	
0	0	2	0	2	

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (5; 1), (1; 4), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	0	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	[0]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 4 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[0]	[-0-]	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[0]	[-0-]	1	3	1	
4	[0]	[-0-]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 5 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (1; 4).
В данной таблице количество нулей равно 2 (должно быть 5).
[-0-]	1	1	[-0-]	[0]	
[0]	[-0-]	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]	1	1	[-0-]	[0]	
[0]	[-0-]	1	3	1	
4	[0]	[-0-]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (5; 1), (2; 2).
В данной таблице количество нулей равно 2 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[0]	[-0-]	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[0]	[-0-]	1	3	1	
4	[0]	[-0-]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 2), (4; 2), (2; 1).
В данной таблице количество нулей равно 2 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	0	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	[0]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (4; 2), (3; 3).
В данной таблице количество нулей равно 2 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[-0-]	1	3	1	
4	[0]	[-0-]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 2).
В данной таблице количество нулей равно 2 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	0	1	3	1	
4	[-0-]	[0]	4	4	
4	0	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	[0]	4	4	
4	[-0-]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (3; 2)
В данной таблице количество нулей равно 2 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[-0-]	1	3	1	
4	[-0-]	0	4	4	
4	[0]	1	6	2	
[-0-]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[0]	1	1	[-0-]	[-0-]	
[-0-]	[-0-]	1	3	1	
4	[-0-]	[0]	4	4	
4	[0]	1	6	2	
[-0-]	3	2	1	3	

Фиксируем нулевое значение в клетке (5, 1). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (2; 1)
В данной таблице количество нулей равно 2 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[-0-]	0	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
[0]	3	2	1	3	

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	0	4	4	
4	[-0-]	1	6	2	
[0]	3	2	1	3	

В данной таблице количество нулей равно 4 (должно быть 5).
[-0-]	1	1	[0]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	[0]	4	4	
4	[-0-]	1	6	2	
[0]	3	2	1	3	

В итоге получаем следующую матрицу:
[-0-]	1	1	[0]	[-0-]	
[-0-]	[0]	1	3	1	
4	[-0-]	[0]	4	4	
4	[-0-]	1	6	2	
[0]	3	2	1	3	

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 4), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
строку 1,
столбец 2,
строку 2,
столбец 1,
строку 3,
Получаем сокращенную матрицу (элементы выделены):
0	1	1	0	0	
0	0	1	3	1	
4	0	0	4	4	
4	0	1	6	2	
0	3	2	1	3	

Минимальный элемент сокращенной матрицы (min(1, 6, 2, 2, 1, 3) = 1) вычитаем из всех ее элементов:
0	1	1	0	0	
0	0	1	3	1	
4	0	0	4	4	
4	0	0	5	1	
0	3	1	0	2	

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
1	2	1	0	0	
1	1	1	3	1	
5	1	0	4	4	
4	0	0	5	1	
0	3	1	0	2	

Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
1	2	1	0	0	0	
0	0	0	2	0	1	
5	1	0	4	4	0	
4	0	0	5	1	0	
0	3	1	0	2	0	

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
1	2	1	0	0	
0	0	0	2	0	
5	1	0	4	4	
4	0	0	5	1	
0	3	1	0	2	
0	0	0	0	0	

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 4 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 4), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).
1	2	1	[0]	[-0-]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	0	4	4	
4	0	0	5	1	
[-0-]	3	1	[-0-]	2	

В данной таблице количество нулей равно 3 (должно быть 5).
1	2	1	[0]	[-0-]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	0	[-0-]	5	1	
[-0-]	3	1	[-0-]	2	

В данной таблице количество нулей равно 4 (должно быть 5).
1	2	1	[0]	[-0-]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[-0-]	3	1	[-0-]	2	

Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 5 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 5), (1; 4).
В данной таблице количество нулей равно 2 (должно быть 5).
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	0	4	4	
4	0	0	5	1	
[-0-]	3	1	0	2	

В данной таблице количество нулей равно 3 (должно быть 5).
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	0	[-0-]	5	1	
[-0-]	3	1	0	2	

В данной таблице количество нулей равно 4 (должно быть 5).
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[-0-]	3	1	0	2	

В данной таблице количество нулей равно 5 (должно быть 5).
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[-0-]	3	1	[0]	2	

В итоге получаем следующую матрицу:
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[-0-]	3	1	[0]	2	

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:
1	2	1	0	0	
0	0	0	2	0	
5	1	0	4	4	
4	0	0	5	1	
0	3	1	0	2	

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
1	2	1	[-0-]	[0]	
[0]	[-0-]	[-0-]	2	[-0-]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[-0-]	3	1	[0]	2	

Cmin = 6 + 6 + 4 + 3 + 3 = 22
Альтернативный вариант №2.
1	2	1	[0]	[-0-]	
[-0-]	[-0-]	[-0-]	2	[0]	
5	1	[0]	4	4	
4	[0]	[-0-]	5	1	
[0]	3	1	[-0-]	2	

Cmin = 9 + 4 + 4 + 3 + 2 = 22

Решение было получено и оформлено с помощью сервиса:
Задача о назначениях
С этой задачей решают также:
Задача коммивояжера
Copyright © Semestr.RU