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

Алгоритм венгерского метода включает в себя 4 этапа.

1. Приведение матрицы.

2. Вычисление максимального числа независимых нулей в приведенной матрице.

3. Получение новых нулей при .

4. Отыскание n независимых нулей при .

Рассмотрим каждый этап подробнее.

Этап 1

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

Таким образом, приведенная матрица удовлетворяет двум условиям:

1. ;

2. и .

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

Пример 1. Пусть

.

Легко проверить, что

,

,

причем матрица является приведенной.

Этап 2

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

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

Пример 2. Пусть имеется приведенная матрица

из примера 1. Все ее нули содержат 1-ая горизонталь и 1-ая вертикаль, следовательно, здесь .

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

Этап 3

Обозначим через элемент приведенной матрицы , зачеркнутый раз на 2-м этапе, и положим , где минимум берется по всем , т.е. ищется наименьший из незачеркнутых элементов матрицы . Если теперь провести пересчет элементов матрицы по формулам

то такие преобразования являются следствием применения Теоремы 1. Пересчитаем элементы матрицы из примера 2 при , в итоге получим приведенную матрицу

.

Все ее нули содержат, например, 1-ая горизонталь и три вертикали: 1-ая, 2-ая, 3-я. Следовательно, здесь и .

Еще один пересчет дает приведенную матрицу

.

Здесь уже

Этап 4

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

1. В результате удается выбрать независимых путей. ОСТАНОВ. Выписать ответ.

2. На некотором шаге все оставшиеся строки и столбцы содержат более одного нулевого элемента. В этом случае выбирается любой нулевой элемент, «помечается» номер строки, из которой выбран 0, и осуществляется переход к выбору следующего нулевого элемента. Если таким образом удается выбрать все независимых нулей, то ОСТАНОВ. Выписать ответ. В противном случае следует возвратиться к помеченной строке и выбрать из нее другой нулевой элемент. По этой схеме надо действовать до тех пор, пока не получим независимых нулей.

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

,

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

,

причем .

Ответ: при или .

УПРАЖНЕНИЯ

1. Укажите количество независимых единиц в матрице

.

2. Является ли матрица приведенной? Укажите количество независимых нулей в ней

a) , b) .

3. Решите задачу о назначениях размера с матрицей вида

a) , b) ,

c) , d) .

Задача 1. Цех металлообработки получил срочный заказ на выпуск партии деталей. Для производства детали необходимо выполнить операции на четырех станках. В Цехе работают четыре слесаря высокой квалификации, каждый из которых может работать на любом станке, но с различным процентом брака (процент известен из документации ОТК):

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

Задача 2. Самолеты компании «Аэрофлот» летают между Москвой и Сочи. Полеты беспосадочные. График движения показан в следующие таблице:

Рейсы могут обслуживаться московским или сочинским экипажами. Любой экипаж выполняет пару рейсов - «туда и обратно». Время, необходимое для подготовки самолета к очередному рейсу, - один час. Требуется определить, какую пару рейсов следует выполнять каждому экипажу, и из какого отряда, московского и ли сочинского, должен быть соответствующий экипаж. Распределение рейсов необходимо осуществить таким образом, чтобы суммарное время ожидания вылета в «чужом» городе было минимальным. Время ожидания не включает тот час, который уходит на подготовку самолета к очередному рейсу.

Каково минимальное общее время пребывания экипажей в «чужих» городах?

Какое количество рейсов должны выполнить московские экипажи?

Задача 3. Рассматривается проблема распределения четырех рабочих по четырем видам станков. Различная квалификация рабочих обусловливает различную стоимость выполнения работ. Стоимость работ (условных единиц) приведена в таблице. Отметим, что первый рабочий не может выполнять работу на 3-м станке, а третий — работу на 4-м станке. Кроме того, не исключается возможность ввода в эксплуатацию нового станка, работу на котором может выполнить любой из четырех рабочих, со стоимостью соответственно 20, 10, 20 и 80 условных единиц. Будет ли ввод новый станка экономически оправдан.

Задача 4. Необходимо распределить 4 сорта топлива, имеющегося в наличии, между четырьмя агрегатами. Задана матрица теплотворной способности, где ккал/кг – теплотворная способность -го сорта топлива при использовании его в -м агрегате.

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