Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Транспортная задача Теория игр Поток сети
Параметры сетевой модели Задача коммивояжера Метод Гомори
Симплексный метод Графический метод Многоканальные СМО

Венгерский метод

Содержательная постановка задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Qi тонн груза (i = 1,2,…, n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве Rj тонн в месяц (j = 1,2,…, n).
Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составляется матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут.

Венгерский метод решения задач о назначениях

Алгоритм венгерского метода.
Задача о назначениях является частным случаем транспортной задачи, поэтому для ее решения можно воспользоваться любым алгоритмом линейного программирования, однако более эффективным является венгерский метод.
Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.
Следует иметь в виду, что для любого недопустимого назначения соответствующая ему стоимость условно полагается равной достаточно большому числу М в задачах на минимум. Если исходная матрица не является квадратной, то следует ввести дополнительно необходимое количество строк или столбцов, а их элементам присвоить значения, определяемые условиями задачи, возможно после редукции, а доминирующие альтернативы дорогие или дешевые исключить.
Перейти к онлайн решению своей задачи
Пример. В задачах данного раздела найти решение задачи по критерию стоимости любым из известных методов.
Исходная матрица имеет вид:
8 6 0 8
4 3 4 0
7 8 2 2
2 9 9 3

Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (9) так, чтобы матрица не содержала бы отрицательных элементов:
1 3 9 1
5 6 5 9
2 1 7 7
7 0 0 6

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

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

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

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

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

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

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

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

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

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

Cmax = 8 + 4 + 8 + 9 = 29
Перейти к онлайн решению своей задачи
Пример №2. Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей cij. Решить задачу методом потенциалов и венгерским методом.
Решение венгерским методом.
Исходная матрица имеет вид:
3 14 5 6 7
1 9 7 4 3
8 7 4 6 3
5 6 9 13 15
19 14 16 8 12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cmin = 5 + 1 + 3 + 6 + 8 = 23

Задача назначения

Дано m = 5 видов машин и m = 5 видов работ с трудоемкостью aij (маш./ч), представленной в табл. 14.15. Закрепить работы за машинами таким образом, чтобы суммарная трудоемкость работ была бы наименьшей.
Решение. Исходная матрица имеет вид:
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
Скачать решение:xls
Перейти к онлайн решению своей задачи