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

Алгоритм нахождения оптимального назначения максимальной стоимости

1 шаг. В каждом столбце выбрать максимальный элемент.

2 шаг. Пересчитать все элементы каждого столбца по правилу: новое значение элемента столбца = максимальный элемент столбца – старое значение элемента столбца.

3 шаг. Если в каждой строке и в каждом столбце имеется нуль, то переходим к шагу 5.

4 шаг. В каждой строке выбрать минимальный элемент и из каждого элемента строки вычесть соответствующие минимальное значение.

5 шаг. В полученной матрице найти строку или столбец с одним нулем.

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

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

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

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

10 шаг. В оставшейся матрице найти минимальный элемент.

11 шаг. К элементам, лежащим на пересечении вертикальных и горизонтальных прямых, найденный минимальный элемент прибавить.

12 шаг. Из всех невычеркнутых элементов матрицы найденный минимальный элемент вычитается.

13 шаг. Повторить шаги 5–8.

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

Задача 1

На автомойку приехали три машины: Ауди, Пежо и ВАЗ. На автомойке есть три поста, на каждом из которых можно обслужить любую из этих трех машин, но за различную плату (см. таблицу).

Стоимость мойки автомобиля

Не нашли, что искали? Воспользуйтесь поиском: