Алгоритм решения задачи о назначениях

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

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

ü преобразование строк и столбцов матрицы;

ü определение назначения;

ü модификация преобразованной матрицы.

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

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

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

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

Пример. Фирма, имеющая 4 склада, получила 4 заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы имеют вполне достаточное количество, товара, чтобы выполнить любой один из этих заказов. Расстояние между базой и каждым потребителем приведены в матрице: . Как следует распределить заказы по базам, чтобы общая дальность транспортировки была минимальной?

Решение.

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