Венгерский метод
Содержательная постановка задачи. В объединении находится 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 |
Скачать решение:xls
Перейти к онлайн решению своей задачи