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

Задача о назначениях является частным случаем транспо­ртной задачи, в которой Ai = Bj = 1. Поэтому ее можно решать алгоритмами транспортной задачи. Рассмотрим другой метод, который является более эффективным, учитывающим специ­фику математической модели. Этот метод называется венгер­ским алгоритмом. Он состоит из следующих шагов:

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

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

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

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

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

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

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

Пример.

Распределить ресурсы по объектам.

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

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

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

3-й шаг. Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого эле­мента равно 2:

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

Ответ. Первый ресурс направляем на 3-й объект, вто­рой — на 2-й объект, четвертый — на 1-й объект, третий ре­сурс — на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квад­ратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на ка­кой-то объект, то соответствующая стоимость полагается рав­ной достаточно большому числу М.

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

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

< Предыдущая		Следующая >