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

Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по пстанкам. Работа i(i=1,…,т), выполняемая на станке j (j=1, …, п), связана с затратами с_ij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки-«пункты назначения». Предложение в каждом исходном пункте равно 1, т. е. a_i = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т. е. b_j = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна c_ij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость c_ij берётся равной очень большому числу.

Прежде чем решать такую задачу, необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m=n.

Пусть x_ij=0, если j-я работа не выполняется на i-ом станке,

x_ij=1, еслиj-я работа выполняется на i-ом станке.

Таким образом, решение задачи может быть записано в виде двумерного массива X = (x_ij). Допустимое решение называется назначением. Допустимое решение строится путём выбора одного элемента в каждой строке матрицы X = (x_ij) и одного элемента в каждом столбце этой матрицы. Для заданного значения nсуществует n! допустимых решений.

Теперь задача будет формулироваться следующим образом:

Сущность венгерского алгоритма состоит в том, чтобы в исходной матрице c_ijполучить т=п независимых нулей, т. е. чтобы в каждой строке или столбце должен быть только один ноль.

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

Шаг 2. Модификация редуцированной матрицы.

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

б) В полученной сокращённой матрице выбираем минимальный элемент и:

- вычитаем его из всех не вычеркнутых элементов;

- прибавляем его к элементу, расположенному на пересечении двух линий.

Если он не оптимальный, повторяем процедуры шага 2.

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

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

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

Необходимо направить ресурсы на объекты так, чтобы суммарная стоимость была минимальна

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

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

В этой матрице в строке 3 и столбце 1 по два нуля, т. е. необходимо провести дальнейшую модификацию редуцированной матрицы стоимостей (оптимальный план не получен).

Шаг 2. Модификация редуцированной матрицы.

Этот минимум прибавляем к элементам редуцированной матрицы, стоящим на пересечении вычеркнутых строк и столбцов (11, 2). В результате получаем модифицированную матрицу:

Шаг 3. Проверяем полученный план на оптимальность и производим назначения.

Отыскиваем строки с одним нулём и отмечаем его. Это строка 2. Следующая строка-4. Отмечаем нуль в этой строке, одновременно вычёркиваем оставшийся ноль в первом столбце. Следующая строка, содержащая один 0-1, отмечаем этот ноль, одновременно вычёркиваем ноль в 3 столбце. Отмечаем ноль в 4 столбце. Все нули независимы, т. е. получен оптимальный план, накладывая модифицированную матрицу на исходную матрицу стоимости, видим, что все назначения сделали.

Оптимальное назначение: Х₁₃=1; Х₂₂=1; Х₃₄=1;Х₄₁=1

Накладываем модифицированную матрицу на исходную, получим F(x)=9+4+11+4=28

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

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

Таким образом, суть венгерского метода состоит в следующем: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или более) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные х_ij равными 1, а все остальные – равными 0, получим оптимальный план назначения.

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: