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

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

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

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

Алгоритм венгерского метода.
Задача о назначениях является частным случаем транспортной задачи, поэтому для ее решения можно воспользоваться любым алгоритмом линейного программирования, однако более эффективным являетсявенгерский метод.
Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.
Следует иметь в виду, что для любого недопустимого назначения соответствующая ему стоимость условно полагается равной достаточно большому числу М в задачах на минимум. Если исходная матрица не является квадратной, то следует ввести дополнительно необходимое количество строк или столбцов, а их элементам присвоить значения, определяемые условиями задачи, возможно после редукции, а доминирующие альтернативы дорогие или дешевые исключить.
Перейти к онлайн решению своей задачи
Пример. В задачах данного раздела найти решение задачи по критерию стоимости любым из известных методов.
Исходная матрица имеет вид:
8608
4340
7822
2993

Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (9) так, чтобы матрица не содержала бы отрицательных элементов:
1391
5659
2177
7006

Далее решаем с помощью калькулятора.
Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
02801
01045
10661
70060

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
0280
0104
1066
7006
0000

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

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

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

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

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

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

Количество найденных нулей равно k = 4. В результате получаем эквивалентную матрицу Сэ:
0280
0104
1066
7006

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

Cmax = 8 + 4 + 8 + 9 = 29
Перейти к онлайн решению своей задачи
Пример №2. Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей cij. Решить задачу методом потенциалов и венгерским методом.
Решение венгерским методом.
Исходная матрица имеет вид:
314567
19743
87463
5691315
191416812

Решение находим с помощью сервиса Задача о назначениях.
Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0112343
086321
541303
0148105
1168048

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
010134
07532
53030
003810
115704
01100

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

В данной таблице количество нулей равно 3 (должно быть 5).
[0]10134
[-0-]7532
53[0]3[-0-]
[-0-][0]3810
115704

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

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

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]10134
[0]7532
53[0]3[-0-]
[-0-][0]3810
115704

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

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

В данной таблице количество нулей равно 3 (должно быть 5).
[0]10134
[-0-]7532
53[0]3[-0-]
[-0-][0]3810
115704

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

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

В данной таблице количество нулей равно 3 (должно быть 5).
[0]10134
[-0-]7532
53[-0-]3[0]
[-0-][0]3810
115704

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

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

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

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

В данной таблице количество нулей равно 3 (должно быть 5).
[0]10134
[-0-]7532
53[0]3[-0-]
[-0-][0]3810
115704

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

Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 4 и столбце 5 вычеркиваем.
В данной таблице количество нулей равно 2 (должно быть 5).
[0]10134
[-0-]7532
53030
[-0-]03810
1157[0]4

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

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

В итоге получаем следующую матрицу:
[0]10134
[-0-]7532
53[0]3[-0-]
[-0-][0]3810
1157[0]4

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

Минимальный элемент сокращенной матрицы (min(10, 1, 4, 7, 5, 2, 5, 7, 4) = 1) вычитаем из всех ее элементов:
09033
06431
53030
003810
114603

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
09033
06431
63040
103910
114603

Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
090330
064310
630400
1039100
1146030

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
09033
06431
63040
103910
114603
00000

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

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

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

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

В данной таблице количество нулей равно 3 (должно быть 5).
[-0-]9[0]33
[0]6431
63[-0-]4[0]
103910
114603

В данной таблице количество нулей равно 4 (должно быть 5).
[-0-]9[0]33
[0]6431
63[-0-]4[0]
1[0]3910
114603

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

В итоге получаем следующую матрицу:
[-0-]9[0]33
[0]6431
63[-0-]4[0]
1[0]3910
1146[0]3

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:
09033
06431
63040
103910
114603

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

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

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

Дано m = 5 видов машин и m = 5 видов работ с трудоемкостью aij (маш./ч), представленной в табл. 14.15. Закрепить работы за машинами таким образом, чтобы суммарная трудоемкость работ была бы наименьшей.
Решение. Исходная матрица имеет вид:
45746
66999
62468
73697
25637

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

013024
003336
402462
403643
034152

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

01100
00131
40044
40162
03213
00202

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

[0]11[-0-][-0-]
[-0-][0]131
4[-0-]044
4[-0-]162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[0]11[-0-][-0-]
[-0-][0]131
4[-0-][0]44
4[-0-]162
[-0-]3213

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

[-0-]11[0][-0-]
[0][-0-]131
40044
40162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]11[0][-0-]
[0][-0-]131
4[0][-0-]44
4[-0-]162
[-0-]3213

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

[-0-]11[-0-][0]
[0][-0-]131
40044
40162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]11[-0-][0]
[0][-0-]131
4[0][-0-]44
4[-0-]162
[-0-]3213

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

[-0-]11[0][-0-]
[0][-0-]131
40044
40162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]11[0][-0-]
[0][-0-]131
4[0][-0-]44
4[-0-]162
[-0-]3213

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

[0]11[-0-][-0-]
[-0-][0]131
4[-0-]044
4[-0-]162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[0]11[-0-][-0-]
[-0-][0]131
4[-0-][0]44
4[-0-]162
[-0-]3213

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

[0]11[-0-][-0-]
[-0-][-0-]131
4[0][-0-]44
4[-0-]162
[-0-]3213

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

[0]11[-0-][-0-]
[-0-]0131
4[-0-][0]44
40162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[0]11[-0-][-0-]
[-0-][0]131
4[-0-][0]44
4[-0-]162
[-0-]3213

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

[0]11[-0-][-0-]
[-0-][-0-]131
4[-0-]044
4[0]162
[-0-]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[0]11[-0-][-0-]
[-0-][-0-]131
4[-0-][0]44
4[0]162
[-0-]3213

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

[-0-]11[0][-0-]
[-0-]0131
40044
40162
[0]3213

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]11[0][-0-]
[-0-][0]131
4[-0-]044
4[-0-]162
[0]3213

В данной таблице количество нулей равно 4 (должно быть 5).

[-0-]11[0][-0-]
[-0-][0]131
4[-0-][0]44
4[-0-]162
[0]3213

В итоге получаем следующую матрицу:

[-0-]11[0][-0-]
[-0-][0]131
4[-0-][0]44
4[-0-]162
[0]3213

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

01100
00131
40044
40162
03213

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

01100
00131
40044
40051
03102

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

12100
11131
51044
40051
03102

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

121000
000201
510440
400510
031020

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

12100
00020
51044
40051
03102
00000

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

121[0][-0-]
[0][-0-][-0-]2[-0-]
51044
40051
[-0-]31[-0-]2

В данной таблице количество нулей равно 3 (должно быть 5).

121[0][-0-]
[0][-0-][-0-]2[-0-]
51[0]44
40[-0-]51
[-0-]31[-0-]2

В данной таблице количество нулей равно 4 (должно быть 5).

121[0][-0-]
[0][-0-][-0-]2[-0-]
51[0]44
4[0][-0-]51
[-0-]31[-0-]2

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

121[-0-][0]
[0][-0-][-0-]2[-0-]
51044
40051
[-0-]3102

В данной таблице количество нулей равно 3 (должно быть 5).

121[-0-][0]
[0][-0-][-0-]2[-0-]
51[0]44
40[-0-]51
[-0-]3102

В данной таблице количество нулей равно 4 (должно быть 5).

121[-0-][0]
[0][-0-][-0-]2[-0-]
51[0]44
4[0][-0-]51
[-0-]3102

В данной таблице количество нулей равно 5 (должно быть 5).

121[-0-][0]
[0][-0-][-0-]2[-0-]
51[0]44
4[0][-0-]51
[-0-]31[0]2

В итоге получаем следующую матрицу:

121[-0-][0]
[0][-0-][-0-]2[-0-]
51[0]44
4[0][-0-]51
[-0-]31[0]2

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

12100
00020
51044
40051
03102

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

121[-0-][0]
[0][-0-][-0-]2[-0-]
51[0]44
4[0][-0-]51
[-0-]31[0]2

Cmin = 6 + 6 + 4 + 3 + 3 = 22
Альтернативный вариант №2.

121[0][-0-]
[-0-][-0-][-0-]2[0]
51[0]44
4[0][-0-]51
[0]31[-0-]2
Cmin = 9 + 4 + 4 + 3 + 2 = 22
Скачать решение:xls
Перейти к онлайн решению своей задачи
Учебно-методический
  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия
Подробнее
Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Курсовые на заказ