Решение задачи о назначении венгерским методом. Пример
Методы принятия управленческих решений
РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ
Задачу о назначениях можно сформулировать следующим образом: имеется n исполнителей и n работ, задана - эффективность выполнения каждой работы каждым исполнителем (таблица, в которой содержатсяn 2 чисел, характеризующих эффективность, называется n xn - или n 2 -матрицей). Задача заключается в том, чтобы назначить каждому исполнителю одну и только одну работу таким образом, чтобы оптимизировать заданную функцию эффективности. Математическая модель выглядит следующим образом:
Алгоритм решения задачи о назначениях
(венгерский метод)
,
(
,
что
.
Шаг 1 . Получение нулей в каждой строке
Выберем в каждой строке минимальный элемент и запишем его значение в правом столбце. Вычтем минимальные элементы из соответствующих строк. Переход к шагу 2.
Шаг 2. Получение нулей в каждом столбце.
В преобразованной таблице найдем минимальные значения в каждом столбце (графе) и запишем их в нижней строке. Вычтем минимальные элементы из соответствующих столбцов. Переход к шагу 3.
Шаг 3 . Поиск оптимального решения
Сделаем назначения. Для этого просматривают строку, содержащую наименьшее число нулей. Отмечают один из нулей этой строки и зачеркивают все остальные нули этой строки и того столбца, в котором находится отмеченный нуль. Аналогичные операции последовательно проводят для всех строк. Если назначение, которое получено при всех отмеченных нулях, является полным (число отмеченных нулей равно n ), то решение является оптимальным. В противном случае переходят к шагу 4.
Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.
Для этого необходимо отметить:
Все строки, в которых не имеется ни одного отмеченного нуля;
Все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных строк;
Все строки, содержащие отмеченные нули хотя бы в одном из отмеченных столбцов.
Действия 2) и 3) повторяются поочередно до тех пор, пока есть что отмечать. После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец.
Цель этого шага – провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.
Шаг 5 . Перестановка некоторых нулей.
Взять наименьшее число из тех клеток, через которые не проведены прямые. Вычесть его из каждого числа, стоящего в невычеркнутых столбцах и прибавить к каждому числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета повторить, начиная с шага 3.
ПРИМЕР
руководитель, |
Время выполнения i -м научным руководителем j |
|||
В венгерском методе используется следующий принцип: оптимальность решения задачи о назначениях не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину.
Решение считается
оптимальным
,
если все измененные таким образом
затраты
,
(
)
и можно отыскать такой набор,
что
.
Выберем в каждой строке минимальный элемент и запишем его значение в правом столбце.
руководитель, |
Время выполнения i -м научным руководителем j -го исследовательского проекта |
Минимальное |
|||
Вычтем минимальные элементы из соответствующих строк, перейдем к новой таблице, в которой найдем минимальные значения в каждом столбце (графе) и запишем их в нижней строке.
руководитель, |
а ij |
|||
Минимальное время по графе |
Вычтем минимальные элементы из соответствующих столбцов.
Сделаем назначения
руководитель, |
а ij |
|||
руководитель, |
а ij |
|||
руководитель, |
а ij |
|||
Число отмеченных (желтым цветом) нулей равно 3, т.е. назначение не является полным (3<4).
Найдем минимальный набор строк и столбцов, содержащий все нули.
руководитель, |
а ij |
|||
руководитель, |
а ij |
|||
руководитель, |
а ij |
|||
В оставшихся клетках минимальный элемент равен 2.
руководитель, |
а ij |
|||
Вычтем минимальный элемент равный 2 из каждого числа (каждой клетки) невычеркнутых (1,2,4) столбцов. Получим таблицу.
руководитель, |
а ij |
|||
Прибавим минимальный элемент равный 2 к каждому числу вычеркнутых строк в преобразованной таблице. Получим таблицу.
руководитель, |
а ij |
|||
Вновь сделаем назначение, отметив по порядку нули в таблице.
руководитель, |
а ij |
|||
Это назначение является полным, так как число отмеченных (желтым цветом) нулей равно 4.
Время выполнения всех (четырех) проектов:
Т =3х1+4х1+2х1+8х1=17.
Данное назначение не единственное. Если во второй строке сначала отметить не второй, а четвертый нуль, получим следующее назначение.
руководитель, |
а ij |
|||
Время на выполнение всех проектов не изменилось:
Т =3х1+5х1+2х1+7х1=17.
Таким образом, получены два оптимальных назначения, которым соответствует минимальное время выполнения проектов равное 17 месяцам.
Предположим, что у нас имеются $4$ склада $A_1,\ A_2,\ A_3,\ A_4$ и $4$ магазина $B_1,\ B_2,\ B_3,\ B_4$. Расстояния от каждого склада до каждого магазина заданы с помощью следующей матрицы:
Например, расстояние от $A_1$ до $B_1$ равно элементу $a_{11}=10$, расстояние от $A_2$ до $B_2$ равно элементу $a_{12}=20$, и т.д.
Требуется так прикрепить склады к магазинам, чтобы суммарное расстояние получилось минимальным. Такая задача называется задачей о назначениях. Решать ее можно с помощью так называемого венгерского алгоритма.
Венгерский алгоритм
- В каждой строке матрицы назначения находим минимальный элемент и вычитаем его из всех элементов строки.
- В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.
- Находим строку с одним нулем. Этот ноль заключаем в квадрат и называем отмеченным. В столбце, где стоит отмеченный ноль, все остальные нули зачеркиваем и в дальнейшем не рассматриваем. Этот шаг продолжаем, пока возможно.
- Находим столбец с одним нулем и этот ноль отмечаем. В строке, где стоит отмеченный ноль, все остальные нули зачеркиваются. Этот шаг продолжаем, пока возможно.
- Если после выполнения шагов $3$ и $4$ еще остаются неотмеченные нули, то отмечаем любой их них, а в строке и столбце, где стоит отмеченный ноль, все остальные нули зачеркиваются.
- Если каждая строка и каждый столбец матрицы содержит ровно один отмеченный ноль, то получено оптимальное решение. Каждый из отмеченных нулей прикрепляет поставщика к потребителю. В противном случаем проводим минимальное количество пересекающихся вертикальных и горизонтальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел ищем минимум. Этот минимум вычитаем их всех не зачеркнутых чисел и прибавляем ко всем числам на пересечении прямых. К полученной матрице применяем вышеприведенный алгоритм, начиная с шага $3$.
Пример решения
Находим минимальный элемент в каждой строке матрицы и вычитаем его из всех элементов строки.
В полученной матрице проделываем тоже самое со столбцами, то есть находим в каждом столбце минимальный элемент и вычитаем его из всех элементов столбца.
В первой строке полученной матрицы находится ровно один ноль. Отмечаем его, а в столбце, где стоит этот ноль все остальные нули зачеркиваем. Получим матрицу:
Следующая строка, в который находится ровно один ноль, это $4$-я. С ней поступаем точно так же. Больше нет строк, содержащих ровно один ноль, но имеются столбцы с одним нулем. Второй столбец содержит ровно один ноль, который мы и отметим. Поскольку этот ноль находится в $3$-й строке, то вычеркиваем все нули, находящиеся в $3$-й строке. Получим матрицу:
Видим, что в матрице больше нет нулей. Полученное распределение не является оптимальным, поскольку во второй строке нет отмеченных нулей. Проводим минимальное количество пересекающихся вертикальных и горизонтальных прямых через все нули.
Находим минимальный элемент среди не зачеркнутых этими прямыми чисел: ${\min \left(5,\ 13,\ 7,\ 2,\ 11,\ 8\right)\ }=2$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:
Полученное распределение не является оптимальным, поскольку в $4$-й строке нет отмеченных нулей. Проводим прямые:
${\min \left(11,\ 5,\ 9,\ 6,\ 6,\ 1\right)\ }=1$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:
К полученной матрицы применяем вышеописанный алгоритм:
Видим, что в каждой строке и в каждом столбце матрицы находится ровно один отмеченный ноль. Получено оптимальное распределение. $A_1$ прикрепляем к $B_4$, $A_2$ - к $B_1$, $A_3$ - к $B_2$, $A_4$ - к $B_3$. Для того, чтобы найти суммарное распределение, нужно сложить числа, расположенные в исходной матрице на месте отмеченных нулей. Получим: $5+3+8+8=24$.
Стоит отметить, что задача о назначениях может решаться и на максимум (чтобы суммарное расстояние было максимальным). В этом случае каждый элемент матрицы умножается на $-1$ и к полученной матрице применяется вышеописанный алгоритм.
При обсуждении постановки задачи о назначениях было отмечено, что эта задача является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа. Применительно к задаче о назначениях симплексный метод не эффективен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод.
Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях 2может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.
Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.
Рассмотрим основные идеи венгерского метода на примере решения задачи выбора (задачи о назначениях), которая является частным случаем Т-задачи, а затем обобщим этот метод для произвольной Т-задачи.
Постановка задачи. Предположим, что имеется различных работ и механизмов, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим, и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.
Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы
чтобы сумма была максимальна и при этом из каждой строки и столбца С был выбран только один элемент.
Введем следующие понятия.
Нулевые элементы матрицы С называются независимыми нулями, если для любого строка и столбец, на пересечении которых расположен элемент, не содержат другие такие элементы.
Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).
Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.
Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij)m,n, элементы которой неотрицательны и удовлетворяют неравенствам:
Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij)m,n. Близость этой матрицы к решению задачи характеризует число Dk - суммарная невязка матрицы Хk:
В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.
Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).
Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности.
Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.
Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.
И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.
Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.
Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.
Задача о назначениях
Алгоритм решения задачи о назначении на узкие места
Задача о назначении на узкие места
ЛЕКЦИЯ 13. Задачи о назначении. Венгерский алгоритм
Эта задача решается описанным выше алгоритмом. Вот ее постановка.
Имеется n рабочих мест на некотором конвейере и n рабочих, которых нужно на эти рабочие места расставить; известна производительность c ij рабочего i на рабочем месте j . Тот факт, что при некотором распределении на рабочие места рабочий i k попадает на рабочее место j k можно описать следующей таблицей:
Имея способ s назначения на рабочие места, можно найти конкретную для этого способа минимальную производительность и заметить, что именно эта минимальная производительность и определяет скорость и производительность конвейера. То рабочее место, на котором реализуется минимальная производительность и называют узким местом в назначении.
Задача состоит в том, чтобы максимизировать
Шаг 0. Фиксируем матрицу производительностей и любое назначение на рабочие места. Пусть s - минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C ; в клетку с номером (ij ) в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.
Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n , то имеющееся назначение на рабочие места уже оптимально.
Постановки задачи:
Пример 13.1 . Требуется распределить m работ (или исполнителей) по n станкам. Работа i (i =1,...,m ), выполняемая на станке j (j=1,...,n ), связана с затратами. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат c ij .
Пример 13.2. C= (c ij ) – стоимость производства детали i на станке j нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.
Пример 13.3. Транспортная задача. Заданы пункты производства товара, пункты потребления товара. Требуется определить оптимальное взаимно-однозначное соответствие между пунктами производства и пунктами потребления, исходя из матрицы стоимостей перевозок C между соответствующими пунктами (т.е. минимизировать суммарную стоимость перевозки).
Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) работы i к станку j равна c ij . Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу.
Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n .
Пусть = 0, если j -я работа не выполняется на i -м станке, = 1, если j -я работа выполняется на i -м станке. Таким образом, решение задачи может быть записано в виде двумерного массива . Допустимое решение называется назначением . Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в каждом столбце этой матрицы.
Замечание 1. Для заданного значения n существует n ! допустимых решений.
Математическая модель задачи:
Минимизировать функцию , при ограничениях:
, (12.1)
, (12.2)
Ограничения (12.1) необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения (12.2) гарантируют, что каждому станку будет приписана ровно одна работа.
Пример 13.4. Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками. Стоимость производства детали i на станке j :
Нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.
Специфическая структура задачи о назначениях позволяет использовать эффективный метод для ее решения.
Замечание 2 . Оптимальное решение задачи не изменится, если из любой строки или столбца матрицы стоимостей вычесть произвольную постоянную величину.
Приведенное замечание 2 показывает, что если можно построить новую матрицу с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным.
.
Оптимальное назначение: , , , остальные , .
К сожалению, не всегда удается определить решение так просто. Для таких случаев рассмотрим следующий алгоритм.
Шаг 1. (Редукция строк и столбцов). Цель данного шага состоит в получении максимально возможного числа нулевых элементов в матрице стоимостей. Для этого из всех элементов каждой строки вычитают минимальный элемент соответствующей строки, а затем из всех элементов каждого столбца полученной матрицы вычитают минимальный элемент соответствующего столбца. В результате получают редуцированную матрицу стоимостей и переходят к поиску назначений.
Шаг 2. (Определение назначений). На этом шаге можно использовать алгоритм поиска «наибольшего паросочетания с матрицей двудольного графа (существуют и другие возможности), если все =0 матрицы заменить на «1», а >0 на «0».
Если нельзя найти полного назначения, то необходима дальнейшая модификация матрицы стоимостей, т.е. перейти к шагу 3.
Шаг 3 . (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:
а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.
б) Вычеркнуть строку или столбец с максимальным числом нулей.
в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.
г) Из всех невычеркнутых элементов вычесть минимальный невычеркнутый элемент и прибавить его к каждому элементу, расположенному на пересечении двух линий.
Перейти к шагу 2.
Замечание 3 .Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.
Пример 13.5. Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей:
.
Итерация 1
Шаг 1 . Редукция строк и столбцов.
Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:
.
Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.