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

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

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

Имеется исполнителей, которые могут выполнить различных работ. Известна стоимость (затраты, издержки) от выполнения -м исполнителем -й работы (). Необходимо так назначить исполнителей на работы, чтобы добиться минимальной суммарной стоимости такого назначения при условии, что каждый исполнитель может быть назначен только на одну работу и каждую работу может выполнять только один исполнитель.

Для построения математической модели обозначим через факт назначения или неназначения -го исполнителя на -ю работу, а именно:

С учетом обозначений математическая модель задачи о назначениях имеет вид:

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

1. В исходной матрице стоимостей для каждой строки определяется минимальный элемент и вычитается из всех элементов строки.

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

3. Так как мы рассматриваем задачу на минимум, то оптимальному назначению соответствуют нулевые элементы матрицы, полученной на предыдущем шаге.

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

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

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

4.3. Произвести назначение на нулевые элементы матрицы стоимостей. Если это невозможно — повторить шаг 4.

Дата добавления: 2014-12-29