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

Шаг 1. Редукция строк и столбцов.

Цель данного шага состоит в получении максимально возможного числа нулевых элементов в матрице стоимостей. Для этого из всех элементов каждой строки вычитают минимальный элемент соответствующей строки, а затем из всех элементов каждого столбца полученной матрицы вычитают минимальный элемент соответствующего столбца. В результате получают редуцированную матрицу стоимостей и переходят к поиску назначений.

Шаг 2. Определение назначений.

а) Найти строки, содержащие ровно один невычеркнутый нулевой элемент. В каждой такой строке произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждом столбце, в котором было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Строки рассматриваются в порядке возрастания их номеров.

б) Найти столбцы, содержащие ровно один невычеркнутый нулевой элемент. В каждом таком столбце произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждой строке, в которой было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Столбцы рассматриваются в порядке возрастания их номеров.

в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов. Если построенное назначение полное, то оно является оптимальным.

Если некоторые нули остались невычеркнутыми, то можно попытаться найти полное назначение.

Если нельзя найти полного назначения, то необходимо провести дальнейшую модификацию матрицы стоимостей, т.е. перейти к шагу 3.

Шаг 3. Модификация редуцированной матрицы.

Для редуцированной матрицы стоимостей:

а) вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце;

б) вычеркнуть строку или столбец с максимальным числом нулей;

в) выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули;

г) из всех невычеркнутых элементов вычесть минимальный невычеркнутый элемент и прибавить его к каждому элементу, расположенному на пересечении двух линий.

Перейти к шагу 2.

Примечания

1) Если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк (столбцов), то существует полное назначение.

2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (–1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следует решать как задачу минимизации.

Пример 6.7. Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей:

Итерация 1.

Шаг 1. Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

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

=

Шаг 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

а) Строки 1, 2 и 4 содержат по одному невычеркнутому нулю. Рассматривая эти строки в порядке возрастания их номеров, произведем вначале назначение, соответствующее элементу (1,1), и вычеркнем нулевой элемент (4,1). Затем произведем назначение, соответствующее элементу (2,2). Строка 4 не может быть использована, поскольку нулевой элемент (4,1) был вычеркнут.

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

Таким образом, ни одно полное назначение не может быть получено, и необходимо провести дальнейшую модификацию редуцированной матрицы стоимостей.

Шаг 3. Модификация редуцированной матрицы.

=

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией.

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

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

Итерация 2.

Шаг 2. Выполняя вновь процедуру построения допустимого решения нулевой стоимости, получаем следующее оптимальное решение:

Оптимальное назначение:

остальные ,

9 + 4 + 11 + 4 = 28.

Пример 6.8 Задача размещения производства.

Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции – по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции.

1. Издержки производства единицы продукции (руб.):

2. Издержки сбыта единицы продукции (руб.):

Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукции каждого вида следующие:

Общие издержки на единицу продукции складываются из издержек производства и издержек сбыта. Поскольку продажная цена единицы каждого вида продукции известна, то можно вычислить прибыль на единицу продукции:

Умножая прибыль, приходящуюся на единицу продукции, на годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции – предприятие. Данные величины (в тыс. руб.) приведены в следующей таблице:

Если прибыль рассматривать как отрицательные затраты, то исходная задача максимизации может быть сведена к минимизационной задаче о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с числом 5760 и введем два вида фиктивной продукции (4 и 5), которой соответствует нулевая прибыль. В результате будет получена следующая матрица:

Итерация 1.

Шаг 1.

=

Шаг 2.

Шаг 3.

Итерация 2.

Шаг 2. Воспользуемся замечанием 1. Тогда получим:

Оптимальное решение данной задачи следующее: производство первого вида продукции назначается предприятию 4, второго вида – предприятию 1, третьего вида – предприятию 3, четвертого вида – предприятию 2, пятого вида – предприятию 5. Очевидно, что 2 последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна 1050 + 5600 + 1242 = 7892 (тыс. руб).