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

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

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

Запишем исходные данные в таблицу.

 

Bj Аi			…	n	ai
	c11	c12	…	c1n
	c21	c22	…	c2n
…	…	…	…	…	…
n	cm1	cm2	…	cmn
bj			…

 

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

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

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

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

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

x_ij

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

Станки

1 2 3

Виды работ 2

3

 

 

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

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

Приведённое замечание показывает, что если можно построить новую матрицу с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным:

5 7 9 5 0 2 4 0 2 2

С = 14 10 12 10 4 0 2 4 0 0

15 13 16 13 2 0 3 2 0 1

0 0 2

 

Оптимальное назначение:

x₁₁^*= 1, x₂₃^* = 1, x₃₂^* = 1, остальные х_ij^* = 0,

F(x^*) = 5+12+13 = 30.

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

 

Венгерский алгоритм.

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

Шаг 1. Редукция строк и столбцов.

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

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

Для редуцированной матрицы стоимостей:

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

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

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

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

Шаг 3. Проверяем план на оптимальность.

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

Примечания

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

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

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

min

С = (c_ij) =

 

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

Итерация 1.

Шаг 1. Редукция строк и столбцов.

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

 

min 0 0 5 0

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

 

=

 

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

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

 

 

Получим сокращённую матрицу стоимостей:

 

- min = 2 =

 

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

 

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

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

 

 

 

0 0 1 0

 

0 1 0 0

 

0 0 0 1

 

1 0 0 0

 

Оптимальное назначение: Х₁₃=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, получим оптимальный план назначения.

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: