Задача о назначениях

Задача о назначениях. В процессе управления производством зачастую возникают задачи назначения исполнителей на различные виды работ, например: подбор кадров и назначение кандидатов на вакантные должности, распределение источников капитальных вложении между различными проектами научнотехнического развития, распределение экипажей самолетов между авиалиниями. Задачу о назначениях можно сформулировать следующим образом. Необходимо выполнить N различных работ. Для их выполнения можно привлечь M рабочих. Каждый рабочий за определенную плату готов выполнить любую работу. Выполнение любой работы следует поручить одному рабочему. Требуется так распределить работы между рабочими, чтобы общие затраты на выполнение всех работ были минимальными. Задача о назначениях в стандартной форме. При рассмотрении задачи о назначениях в стандартной форме предполагается, что количество рабочих равно количеству работ. Обозначения: cij — показатель эффективности назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы; xij — переменная модели ( xij = 1, если i-й рабочий используется на j-й работе, и xij = 0 в противном случае). Модель задачи о назначениях: f  x     xij cij  min n n (1) i 1 j 1 n  x  1 j  1, n ( 2)  x  1 i  1, n (3) i 1 n j 1 ij ij xij  0 i  1, n j  1, n ( 4) Здесь (1) — целевая функция (минимум издержек на выполнение всех работ); (2) — система ограничений, отражает условие, что каждая работа должна быть выполнена одним рабочим; (3) — система ограничений, отражает условие, что каждый рабочий может быть привлечен только к одной работе; (4) — условие не отрицательности переменных. При решении задачи о назначениях исходной информацией является таблица (матрица) задачи о назначениях С  сij , элементами которой служат показатели эффективности назначений. Для   задачи о назначениях, записанной в стандартной форме, количество строк этой таблицы совпадает с количеством столбцов: работа … 2 с11 с12 с1 j с1n 2 с21 с22 с2 j с2 n … i сi1 сi 2 сij сin …. n сn 1 сn 2 сnj сnn рабочий 1 j … 1 n Основная идея венгерского метода решения задачи о назначениях состоит в переходе от матрицы С  сij к матрице С *  с*ij .       Матрица С  с ij состоит из неотрицательных элементов и n независимых нулей (никакие два не принадлежат одной и той же строке или одному и тому же столбцу). При переходе используется тот факт, что оптимальность не нарушается при уменьшении или увеличении элементов строки или столбца матрицы на одно и то же число. * * Оптимальный план задачи о назначениях (1)—(4) можно представить в виде квадратной матрицы назначений, в каждой строке и в каждом столбце которой находится ровно одна единица. Такую матрицу иногда называют матрицей назначений ( перестановок). Значение целевой функции (1), соответствующее оптимальному плану, называют эффективностью назначений. Решение считается оптимальным, если все измененные таким образом n набор с*ij  0 и найден такой n x * ij , что  x *ij c *ij  0 . Это означает, что все подлежащие распределению единицы i 1 j 1 должны попасть в клетки с нулевыми затратами. Задача о назначениях в открытой форме. Задача о назначениях в открытой форме возникает тогда, когда количество рабочих не равно количеству работ. В этих случаях задача может быть преобразована в задачу, сформулированную в стандартной форме. Пусть, например, количество рабочих n превышает количество работ m. Введем дополнительные фиктивные работы с индексами j = m + 1,..., n. Коэффициенты таблицы назначений с ij  0, i  1, n, j  m  1, n , получаем задачу, сформулированную в стандартной форме. * Если в оптимальном плане этой задачи х ij  1, при j  m  1,...., n , то исполнитель i назначается на выполнение фиктивной работы, т.е. остается без работы. Заметим, что оптимальное значение целевой функции исходной задачи совпадает с оптимальным значением задачи, приведенной к стандартной форме. Поэтому эффективность назначений в результате такого преобразования не меняется. Замечание 1. Таким образом, если исходная матрица С  сij  не является квадратной, то нужно ввести фиктивные объекты или фиктивные ресурсы, так, чтобы матрица стала квадратной. Замечание 2. Если исходная задача на max , например С  сij - матрица полезности, то все элементы матрицы умножаем на (-1) и к каждому элементу полученной матрицы С  сij  прибавляем число   max cij , далее решаем задачу на min. Алгоритм решения стандартной задачи на min. 1 этап: Получение нулей в каждой строке. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки 2 этап: Получение нулей в каждом столбце. В преобразованной матрице в каждом столбце определяют минимальный элемент и вычитают его из всех элементов данного столбца. 3 этап: Поиск оптимального решения. Найти строку, содержащую наименьшее число нулей. Отмечаем один из нулей, например подчеркиванием или обведением. Зачеркиваем оставшиеся нули этой строки и столбца, в котором находится отмеченный нуль. (Так как одной работе должен соответствовать один человек). Аналогичная операция проводится для всех строк, пока это возможно. Если число отмеченных нулей совпадает с количеством строк, т.е. в каждой строке есть отмеченный нуль, то получено оптимальное решение. В противном случае переход к этапу 4. 4 этап: (Если оптимальное решение не получено) 1. Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в матрице 2. Найти наименьший из элементов, через которые не проходит ни одна прямая 3. Вычесть его из всех элементов, через которые не проходят прямые 4. Прибавить его ко всем элементам, лежащим на пересечении прямых 5. Элементы, через которые проходит только одна прямая, оставить неизменными В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 3. 5 этап. Запись результата. Записать матрицу назначений Х *  xij  и найти значение целевой функции f  Х *  . 3  2 Пример: Распределить все ресурсы по объектам.  4  9 7 4 7 7 5 4 2 3 8  5 8  8  Матрица квадратная, задача на минимум, следовательно, используем алгоритм. Редуцируем матрицу по строкам и столбцам.  0 4 2 5    3 7 5 8 3 2 2 3      2 4 4 5  2 →  2 5 0 6  → Проверяем на оптимальность.  4 7 2 8 2   6 4 5      9 7 3 8 3 2 3 0   0 2  6 2 3 2 2 2 0 Назначение не состоялось. Проводим через нули прямые: 0  0 2  6 2 3 2 2 2 2  0   2 Преобразуем матрицу и проверяем на оптимальность 3  2  0  2 → 2  6 0 1 0 2 4 0 0   0  Получено оптимальное решение, назначение состоялось. 1  0 Записываем матрицу назначений и находим значение целевой функции. 1  Х *  xij*     0 1 1 0  0 0  1  f(x*)=3+4+2+8=17. 1  0 Замечание. Существует ещѐ одно оптимальное решение:   0 f(x*)=3+7+2+5=17. 1 1 0  1 0  0  2  0  3  2 