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

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

Содержательная постановка задачи. В объединении находится 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
Перейти к онлайн решению своей задачи
Алгоритм Дейкстры
Поиск кратчайшего пути между указанными вершинами. Решение по шагам
Алгоритм Дейкстры онлайн
Решение онлайн
Множество Парето
Выбор оптимальной стратегии по Парето. Решение по шагам
БыстродействиеЕмкость57182610934
Решение онлайн
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Курсовые на заказ