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

Математическая постановка задачи о назначениях

Целевая функция имеет вид

постановка задачи о назначениях формула

ограничения

постановка задачи о назначениях

при этом матрица должна быть квадратной.


Рассмотрим на примере решение задачи максимизации целевой функции о назначениях венгерским методом

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

матрица

Решение

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

матрица максимальное по строкам

Затем последовательно из найденного максимального значения данной строки отнимаем каждое значение этой строки (поэлементно) при этом получаем нули в ячейках с максимальным значением и получаем матрицу вида

Задача о назначениях матрица

По столбцам матрицы находим минимальные значения

матрица по столбцам

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

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

В нашем случае, наилучшее назначение:

Автомобиль A → Маршрут 4

Автомобиль B → Маршрут 2

Автомобиль C → Маршрут 1

Автомобиль D → Маршрут 3

Но на практике часто бывают ситуации, когда, например, какие-то из столбцов не равны нулю. Рассмотрим, опять же на примере. Пусть дана матрица вида и выполняем те же операции, что и ранее. матрица решение задачи о назначении пример

Также при решении задачи о назначении венгерским методом является необходимым выполнения следующего условия:

число исключений в таблице – минимальное.
в каждой строке и столбце таблицы должен стоять единственный выбранный ноль.

Исключаем столбцы и строки с нулями, получаем таблицу

Матрица вычеркиваем элементы

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

Итак, оптимальное решение найдено, получаем матрицу вида

матрица задача о назначении оптимальное решение

Таким образом, матрица назначений будем иметь вид:
матрица назначений

Leave a Reply

Ваш e-mail не будет опубликован.