Венгерский метод в excel
Решение задачи о назначениях выполняется в онлайн режиме и оформляется в отчете формата Word (см. пример решения задачи о назначениях).
Инструкция . Выберите размерность матрицы (количество вакансий и количество кандидатов). После ввода данных, создается шаблон решения в Excel (см. задача о назначениях в Excel).
Типичное задание:
В цехе предприятия имеются 5 универсальных станков, которые могут выполнять 4 вида работ. Каждую работу единовременно может выполнять только один станок, и каждый станок можно загружать только одной работой.
В таблице даны затраты времени при выполнении станком определённой работы. Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты времени.
Задача. Служба занятости имеет в наличии четыре вакантных места по разным специальностям, на которые претендуют шесть человек. Проведено тестирование претендентов, результаты которого в виде баллов представлены в матрице
Распределить претендентов на вакантные места таким образом, чтобы на каждое место был назначен человек с наибольшим набранным по тестированию баллом.
Пример решения задачи о назначении с минимальной стоимостью;
Пример решения задачи о назначении с максимальной стоимостью;
Постановка задачи о назначениях
Сделаем содержательную постановку задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Qi тонн груза (i = 1,2,…,n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве Rj тонн в месяц (j = 1,2,…,n).
Распределить автомобили по маршрутам так, чтобы минимизировать суммарную величину неиспользуемой провозной способности. Конкретизируем задачу (рис. 1). Пусть имеется 4 автомобиля и 4 маршрута. Характеристики провозных способностей автомобилей соответственно равны Q1 = 30 т., Q2 = 35 т., Q3 = 5 т., Q4 = 5 т. Характеристики потребностей потребителей соответственно равны R1 = 25 т., R2 = 32 т., R3 = 5 т., R4 = 4 т. Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Понятно, если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составим матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут. Элементы маршрута будут равны:
Ограничения. Каждый автомобиль i должен быть назначен только один раз на любой из маршрутов.
или
при ограничениях: .
Все предполагаемые алгоритмы поиска решения задачи о назначениях базируются на следующем утверждении: оптимальное решение задачи не изменится, если к любой строке или столбцу матрицы издержек прибавить (или вычесть) постоянную величину в силу того, что приоритет назначения не изменится. И весь алгоритм ведется на матрице издержек с соответствующими преобразованиями для получения в ней нулевых элементов, образующих систему так называемых «независимых нулей». Число независимых нулей равно размерности матрицы, а их расположение таково, что каждый из них встречается один раз в строке и один раз в столбце. Если такие независимые нули будут найдены, то в матрице решения в соответствии с их положением будут проставлены единицы. В матрице 1 нулевые элементы получены вычитанием наименьшего элемента в каждой строке. (1)
Как только будут получены нулевые элементы, применяют различные алгоритмы: Мака, венгерский, минимальных линий. Рассмотрим процедуру вычеркивания нулевых элементов минимальным числом прямых линий. В матрице 2 показано, как используется это правило. Могут быть и другие варианты вычеркивания.
Если все нулевые элементы в матрице будут вычеркнуты, а минимальное число линий будет равно размерности матрицы, то независимые нули в матрице существуют, и решение найдено. В противном случае выбирается наименьший элемент из невычеркнутых элементов (он равен 1). Этот элемент вычитается из каждого невычеркнутого элемента и прибавляется к каждому элементу, стоящему на пересечении проведенных прямых.
В результате получается матрица (3), которая указывает на два оптимальных решения (матрицы решений 4 и 5).
Значение целевой Z = 5 + 3 + 0 + 1 = 9 . Оптимальное решение можно было получить и сразу, не применяя процедуру вычеркивания нулей, если в матрице 2 из столбца 4 вычесть минимальный элемент. Сделано было иначе только для демонстрации процедуры вычеркивания.
Следует заметить, что, если на последнем шаге оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.
Модель назначений
Модель назначений часто встречается в задачах управления, где требуется, например, распределить мастеров-ремонтников по вызовам, продавщиц по отделам, аудиторов по фирмам и т. д. В качестве примера рассмотрим возможную постановку задачи назначения.
Пример . Руководство фирмы приняло решение произвести инспекцию своих предприятий в Лейпциге, Нанси, Льеже и Тилбурге, направляя туда своих вице-президентов, каждый из которых в компании возглавляет одно из направлений (финансы, маркетинг, производство и персонал). Хотя может существовать большое число факторов, которые нужно учесть при таком назначении (знание языка, узкая специализация, невозможность оторваться от прямых обязанностей и т. д.), руководство компании решило оптимизировать в качестве первого шага только суммарные затраты на командировку вице-президентов. Таблица командировочных расходов в различные города (тыс. долларов) приведена ниже.
Вице-президенты | Лейпциг | Нанси | Льеж | Тилбург |
По финансам | 24 | 10 | 21 | 11 |
По маркетингу | 14 | 22 | 10 | 15 |
По производству | 15 | 17 | 20 | 19 |
По персоналу | 11 | 19 | 14 |
Требуется составить схему распределения вице-президентов по филиалам, минимизирующую командировочные расходы.
Решение. Табличная модель этой задачи после проведенной оптимизации приведена на рис.
Модель назначений является разновидностью транспортной модели. От последней она отличается только тем, что в ней единица предложения не может распределяться по нескольким местам назначения (ср. рис.).
Таким образом, модель назначений всегда можно построить в виде транспортной модели, в которой предложение в каждой исходной точке и спрос в каждом конечном пункте равны единице.
Точно так же, как и транспортная модель, модель назначений может быть несбалансированной, содержать недопустимые назначения, иметь альтернативные решения при одном и том же значении целевой функции. Эти варианты моделей назначения строятся в полной аналогии с соответствующими транспортными моделями.
Оптимальное распределение продавцов по торговым точкам
Задание. Существует 4 продавца А1, А2, А3, А4 и 4 торговые точки В1, В2, В3, В4. Эффективность работы продавцов на торговых точках задаётся следующей матрицей:9 | 3 | 4 | 8 |
4 | 6 | 7 | 11 |
5 | 8 | 8 | 4 |
6 | 12 | 15 | 9 |
Найти оптимальное распределение продавцов по торговым точкам.
Поскольку задана матрица эффективности, то искать необходимо максимальные значения, следовательно, целевая функция стремится к максимуму. Именно поэтому при решении выбираем вид Максимальная прибыль .
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (15) так, чтобы матрица не содержала бы отрицательных элементов:
6 | 12 | 11 | 7 |
11 | 9 | 8 | 4 |
10 | 7 | 7 | 11 |
9 | 3 | 0 | 6 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0 | 6 | 5 | 1 | 6 |
7 | 5 | 4 | 0 | 4 |
3 | 0 | 0 | 4 | 7 |
9 | 3 | 0 | 6 | 0 |
0 | 6 | 5 | 1 |
7 | 5 | 4 | 0 |
3 | 0 | 0 | 4 |
9 | 3 | 0 | 6 |
0 | 0 | 0 | 0 |
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 3). Другие нули в строке 4 и столбце 3 вычеркиваем.
В итоге получаем следующую матрицу:
[0] | 6 | 5 | 1 |
7 | 5 | 4 | [0] |
3 | [0] | [-0-] | 4 |
9 | 3 | [0] | 6 |
0 | 6 | 5 | 1 |
7 | 5 | 4 | 0 |
3 | 0 | 0 | 4 |
9 | 3 | 0 | 6 |
[0] | 6 | 5 | 1 |
7 | 5 | 4 | [0] |
3 | [0] | [-0-] | 4 |
9 | 3 | [0] | 6 |
Cmax = 9 + 11 + 8 + 15 = 43
Таким образом, распределение продавцов по торговым точкам будет следующее:
1 продавец – торговая точка №1
2 продавец – торговая точка №4
3 продавец – торговая точка №2
4 продавец – торговая точка №3.
При таком назначении, максимальная эффективность составит 43.
С помощю этого онлайн калькулятора можно решить задачу о назначениях (задачу о выборе) венгерским методом. Для решения задачи о назначениях задайте размерность матрицы, выберите из вариантов "максимальная прибыль" и "минимальные расходы". Затем введите данные в ячейки и нажимайте на кнопку "Вычислить". Теоретическую часть смотрите ниже.
Предупреждение
Задача о назначениях − теория
Математическая задача о назначениях или задача о выборе формулируется следующим образом. Требуется выбрать такую последовательность элементов из следующей квадратной матрицы
чтобы достигала своего максимального значения, причем при . Другими словами, нужно выбрать из каждого столбца и каждой строки ровно по одному элементу так, чтобы их сумма была максимальной.
Отметим, что если бы матрица C была устоена так, что максимальные элементы каждой строки лежали бы в разных столбцах, то решение задачи было бы элементарным, т.е. к качестве решения нужно было выбрать эти максимальные элементы. Однако обычно максимальные элементы нескольких строк(столбцов) расположены в одном и том же столбце (строке) и решение проблемы затрудняется.
При решении задачи о назначениях применяется венгерский метод, что существенно упрощает решение задачи.
Венгерский метод
Сделаем несколько определений.
1. Нулевые элементы квадратной матрицы S будем называть независимыми нулями , если столбец и строка, в которых находится данный нулевой элемент не содержат другого нулевого элемента.
2. Две прямоугольные матрицы и порядка mxn называются эквивалентными, если , , .
Решение задачи имеет подголовительную и итерационную части.
Подготовительная часть. Для каждого столбца матрицы C найдем максимальный элемент и из этого элемента вычитаем каждый элемент данного столбца. (Если рассматривается задача на минимум, то находим минимальный элемент каждого столбца и из элементов данного столбца вычитаем этот минимальный элемент. Далее все по нижеизложенному алгоритму). В результате получим матрицу, в каждом столбце которой имеется нулевой элемент . Далее находим минимальный элемент каждой строки и из элементов данной строки вычитаем этот минимальный элемент. В результате получим матрицу, в каждой строке и в каждом столбце имеется по крайней мере один нулевой элемент.
Далее отмечаем звездочкой произвольный нуль в пероом столбце и просматриваем второй столбей и если в нем есть нули и в этой строке нет отмеченного нуля, то отмечаем данный нуль звездочкой. Аналогичным образом поступаем и с остальными столбцами. Отмеченные нули являются независимыми.
Этап 1. Если количество независимых нулей равно размерности матрицы, то задача решена и позиции отмеченных нулей является решением задачи о назначениях. Если же количество независимых нулей меньше n, то продолжаем процедуру. Выделяем столбцы матрицы C содержащие нули со звездочкой. Если среди невыделенных элементов матрицы нет нулевых, то переходим к этапу 3. Если обнаруживается невыделенный нуль, то есть два варианта:
Вариант 1. Строка, содержащая невыделенный нуль содержит также нуль со звездой. В этом случае ставим над найденным нулем знак °, выделяем строку, содержащую этот нуль, снимаем выделение из столбца, на пересечении которой с только что выделенной строкой находится нуль со звездой. Далее, если обнаруживается невыделенный нуль, переходим к этапу 1. Если невыделенных нулей нет, то переходим к этапу 3.
Вариант 2. Строка, содержащая невыделенный нуль не содержит нуль со звездой. В этом случае отмечаем этот нуль знаком ° и переходим к этапу 2.
Этап 2. Исходя из нуля со знаком °, в строке которой нет нуля со звездой (вариант 2) строим следующую цепочку элементов матрицы C: Исходный 0° − 0* (лежащий в одном столбце (если существует)) − 0° (лежащей в одной строке с предшествующим 0* и т.д. Цепочка имеет вид 0°−0*−0°−. и обязательно заканчивается 0°. Там, где 0°, заменяем на 0*, а на четных позициях уничтожаем знак * над нулями. Далее уничтожаем все ° над нулями и снимаем выделения из столбцов и строк. Число независимых нулей увеличился на единицу. Переходим к этапу 1.
Этап 3. К этому этапу переходим после завершения этапа 1, когда независимых нулей нет.
Среди невыделенных элементов находим минимальный q>0. Далее величину q вычитаем из всех элементов матрицы C расположенных на невыделенных строках, и прибавляем ко всем элементам на выделенных столбцах (можно и так: величину q вычитаем из всех невыделенных элементов матрицы C и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов). В полученной матрице появятся невыделенные нули поэтому переходим к этапу 1.
Для рассмотрения численного примера задачи о назначениях (задачи выбора), введите в кальнуляторе в начале страницы элементы матрицы и нажмите на кнопу вычислить. Онлайн калькулятор выдаст подробное рашение задачи.
Привет, друзья! В этой статье хотел бы рассказать про интересный алгоритм из дисциплины «Исследование операций» а именно про Венгерский метод и как с его помощью решать задачи о назначениях. Немного затрону теории про то, в каких случаях и для каких задач применим данный алгоритм, поэтапно разберу его на мною выдуманном примере, и поделюсь своим скромным наброском кода его реализации на языке R. Приступим!
Пару слов о методе
Для того чтобы не расписывать много теории с математическими терминами и определениями, предлагаю рассмотреть пару вариантов построения задачи о назначениях, и я думаю Вы сразу поймете в каких случаях применим Венгерский метод:
- Задача о назначении работников на должности. Необходимо распределить работников на должности так, чтобы достигалась максимальная эффективность, или были минимальные затраты на работу.
- Назначение машин на производственные секции. Распределение машин так, чтобы при их работе производство было максимально прибыльным, или затраты на их содержание минимальны.
- Выбор кандидатов на разные вакансии по оценкам. Этот пример разберем ниже.
В итоге задача должна быть решена так, чтобы один исполнитель (человек, машина, орудие, …) мог выполнять только одну работу, и каждая работа выполнялась только одним исполнителем.
Необходимое и достаточное условие решения задачи – это ее закрытый тип. Т.е. когда количество исполнителей = количеству работ (N=M). Если же это условие не выполняется, то можно добавить вымышленных исполнителей, или вымышленные работы, для которых значения в матрице будут нулевыми. На решение задачи это никак не повлияет, лишь придаст ей тот необходимый закрытый тип.
Step-by-step алгоритм на примере
Постановка задачи: Пусть намечается важная научная конференция. Для ее проведения необходимо настроить звук, свет, изображения, зарегистрировать гостей и подготовиться к перерывам между выступлениями. Для этой задачи есть 5 организаторов. Каждый из них имеет определенные оценки выполнения той, или иной работы (предположим, что эти оценки выставлены как среднее арифметическое по отзывам их сотрудников). Необходимо распределить организаторов так, чтобы суммарная их оценка была максимальной. Задача имеет следующий вид:
Если задача решается на максимум (как в нашем случае), то в каждой строке матрицы необходимо найти максимальный элемент, его же вычесть из каждого элемента соответствующей строки и умножить всю матрицу на -1. Если задача решается на минимум, то этот шаг необходимо пропустить.
В каждой строке и в каждом столбце должен быть только один выбранный ноль. (т.е. когда выбрали ноль, то остальные нули в этой строке или в этом столбце уже не берем в расчет). В этом случае это сделать невозможно:
(Если задача решается на минимум, то необходимо начинать с этого шага). Продолжаем решение далее. Редукция матрицы по строкам (ищем минимальный элемент в каждой строке и вычитаем его из каждого элемента соответственно):
Т.к. все минимальные элементы – нулевые, то матрица не изменилась. Проводим редукцию по столбцам:
Опять же смотрим чтобы в каждом столбце и в каждой строке был только один выбранный ноль. Как видно ниже, в данном случае это сделать невозможно. Представил два варианта как можно выбрать нули, но ни один из них не дал нужный результат:
Продолжаем решение дальше. Вычеркиваем строки и столбцы, которые содержат нулевые элементы (ВАЖНО! Количество вычеркиваний должно быть минимальным). Среди оставшихся элементов ищем минимальный, вычитаем его из оставшихся элементов (которые не зачеркнуты) и прибавляем к элементам, которые расположены на пересечении вычеркнутых строк и столбцов (то, что отмечено зеленым – там вычитаем; то, что отмечено золотистым – там суммируем; то, что не закрашено – не трогаем):
Как теперь видно, в каждом столбце и строке есть только один выбранный ноль. Решение задачи завершаем!
Подставляем в начальную таблицу месторасположения выбранных нулей. Таким образом мы получаем оптимум, или оптимальный план, при котором организаторы распределены по работам и сумма оценок получилась максимальной:
Если же вы решаете задачу и у вас до сих пор невозможно выбрать нули так, чтобы в каждом столбце и строке был только один, тогда повторяем алгоритм с того места где проводилась редукция по строкам (минимальный элемент в каждой строке).
Реализация на языке программирования R
Венгерский алгоритм реализовал с помощью рекурсий. Буду надеяться что мой код не будет вызывать трудностей. Для начала необходимо скомпилировать три функции, а затем начинать расчеты.
Данные для решения задачи берутся из файла example.csv который имеет вид:
Результат выполнения программы:
В завершение
Спасибо большое что потратили время на чтение моей статьи. Все используемые ссылки предоставлю ниже. Надеюсь, Вы узнали что-то для себя новое или обновили старые знания. Всем успехов, добра и удачи!
Задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Наиболее эффективным методом ее решения является венгерский метод. Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д.
1. Задача (формулировка).
Мы будем проще (в терминах). =)
Представим себе задачу: нужно эффективным образом реализовать некоторый относительно большой проект. Для проекта была отобрана команда первоклассных разработчиков, разбирающихся в различных областях. И так уж посчастливилось, что есть сведения (накопленная статистика) о степени (эффективности) владения технологиями для каждого. Но, к сожалению, разработчиков в команде не так уж и много, а точнее – столько же, сколько и технологий будет использовано в проекте.
Необходимо: самым эффективным способом задействовать наибольшее количество технологий, назначив каждому разработчику свою задачу. т.е. оптимально распределить между ними области ответственности за технологии, принимая во внимание их личные способности.
2. Подход к решению
In the end, all business operations can be reduced to three words: people, product, and profits ©. Если мы попробуем изобразить поставленную перед нам и задачу на листе бумаги, то наверняка получим подобную иллюстрацию, как на рисунке (с такими картинками).
Получился — граф. Вершины слева – разработчики, вершины справа – технологии (задачи). Ребра, которые их соединяют – означают то, насколько разработчик в ней разбирается. Эти цифры, т.е. степень владения разработчиком данной технологией, очень важны, но к ним обратимся чуть позже. А пока мы уже верно наметили направление, в котором эффективно решается данная задача:
3. Графы
Самые основы графов были изложены в статье (max cost), поэтому сразу перейду к терминологии, касающейся данной задачи:
Двудольный граф – граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. В нашей задаче тоже есть четкое разделение: одни вершины – это разработчики, другие – задачи, и связи (эффективность владения) есть только между разработчиками и задачами.
Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение», чтобы каждый задействованный разработчик взял на себя отдельную задачу. И не получилось такого, что два разработчика прорабатывают одну проблему, или один «бедняга» отвечал за две задачи.
В теории графов наша проблема, как это ни странно, называется Задачей о Назначениях (ЗН). =) Она является частным случаем задачи нахождения максимального паросочетания. В самом деле, мы ведь стремимся максимально задействовать ресурсы, чтобы одновременно прорабатывалось максимальное число технологий, поэтому в терминах графов — пытаемся найти «максимальное паросочетание», составить максимальное количество пар разработчик-задача.
4. Максимальное паросочетание
Чтобы упростить себе жизнь, мы пока не обращаем внимания на способности людей. Просто хотим каждому подыскать работу. Нескольким первым попавшимся под руку разработчикам предложить работать со знакомой им технологией не составит проблем. Продолжая в том же духе, мы распределим еще несколько задач, но построенное таким образом паросочетание вряд ли будет максимальным. Возможна ситуация как та, что изображена на рисунке:
Как же увеличить паросочетания (назначения)?
- если нашли свободную – поиск завершен
- если задача уже кому-то назначена, то пройдя по этому ребру паросочетания, попытаемся «переназначить» технологию разработчику, участвующему в данном назначении
Добавим еще немного терминологии из теории графов, простыми словами:
Экспонированная вершина – это вершина, которая не участвует в текущем паросочетании. Т.е. либо «незадействованный разработчик», либо «свободная задача».
Альтернирующая цепь – это цепь, ребра которой попеременно лежат или не лежат в паросочетании. (…- владение технологией – назначенная задача – владение технологией – назначенная задача — …)
Альтернирующее дерево – дерево, состоящее из альтернирующих цепей
Аугментальная цепь – это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Вот как называется то, что мы и ищем! =)
Аугментальное дерево – соответственно дерево, в котором хотя бы одна из веток – это аугментальная цепь.
Вот и нашли способ наращивать паросочетание, стремясь получить максимальное. Нужно строить альтенирующее дерево. Когда оно станет аугментальным, искать аугментальные цепи из «незадействованного разработчика» в «свободную задачу» и потом «переназначать» задачи вдоль них. Это выгодно, т.к. увеличивает количество «задач в обработке» на 1:
Теперь мы уже сможем задействовать наибольшее количество технологий в проекте. Самое время принять во внимание еще одно важное условие поставленной перед нами проблемы: эффективность владения технологиями. Мы ведь хотим оптимально назначить всем задачи.
5. Венгерский метод.
Найти решение с максимальной суммарной эффективностью (стоимостью). Звучит, в некотором смысле, похоже на задачу об оптимальной упаковке рюкзака. Наводит на мысль. Вот если бы нам представилась возможность действовать по принципу «жадных алгоритмов».
Мы бы для начала всем разработчикам до упора назначили задачи в соответствии с их максимальными способностями. Если всем разработчикам удалось сразу же распределить задачи — отлично. Но такое происходит не часто. Вдруг два человека, оптимально владеют одной и той же технологией, кому она достанется и что делать в этой ситуации? Одному из разработчиков нужно будет подыскать иную свободную задачу, так же наиболее соответствующую его способностям. Если при текущих (максимальных требованиях) условиях не найдется свободной задачи, то нужно будет попробовать подыскать среди задач, предварительно немного занизив наши требования. Как бы искусственно занизить способности разработчиков в графе. Если в таких условиях обнаружим свободную задачу – получим аугментальное дерево. «Поменяем» по цепочке паросочетания, после чего будет +1. И продолжим назначать таким вот оптимальным образом, пока всем не подыщем работу.
Стратегия ясна.
Мы почти разгадали принцип Венгерского алгоритма. Но как все же построить решение по принципу «жадных алгоритмов»: до упора назначить по max способностям, потом чуть занизить способности и добавив к рассмотрению новые задач, до упора назначить их, занизить… и.т.д.? Как оценить способности и оптимальность текущего назначения?
Вся «фишка» этого алгоритма заключается в следующем. Нам дан всего один параметр в графе – эффективность решения определенной задачи разработчиком, что указано на ребрах. Эта величина присвоена парам разработчик-задача. Мы же «разделим» (отделим от пар) эти величины на две. Искусственно добавим два дополнительных параметра. Одни величины будут приписаны вершинам задач, другие — вершинам разработчиков.
- у разработчиков мы укажем их «способности», допустим в единицах «сил», просто указывающие на то, насколько эффективно мы можем их задействовать или задействовали.
- у задач мы укажем их «изученность», или, если можно так выразиться, «переизбыток внимания». Этот параметр будем так же измерять в «силе». Переизбыток внимания к задаче возникает в следующей ситуации. Если мы какого-то разработчика «недогрузили», т.е. он способен решать задачу на 5, а ему досталась всего на 3. То у него остается еще 2 «силы» которые он, в принципе, может уделить какой-то из знакомых ему задач. Бегать между кабинетов, консультировать по телефону, давать советы тем, кто занимается любимой ему технологией.
Таким образом, величины указанные на ребрах мы «разделим» на 2 значения, приписанных уже вершинам: эффективность решения задачи = способность разработчика + изученность задачи. В принципе, логично. Чем способней разработчик или чем более известна технология, тем лучше будет реализована эта часть в проекте. Эффективней.
В конце, после того как мы найдем решение, мы конечно будем учитывать только величины на ребрах, но сейчас эта «фишка» поможет нам найти решение. =)
6. Описание алгоритма
Инициализируем граф. Будучи «упертыми оптимистами», мы для каждого разработчика рассчитаем его максимальную «способность» по знакомым ему технологиям, и присвоим ему это число. Everyone enjoys doing the kind of work for which he is best suited ©. О задачах пока ничего неизвестно, поэтому их «изученность» инициализируем нулями.
При поиске «свободной задачи» для «незадействованного разработчика» мы ограничимся теперь только (назовем их) оптимальными ребрами графа, т.е. теми, для которых выполняется равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина) .
- Удалось обнаружить свободную задачу. Дерево стало аугментальным. «Переназначаем» задачи, наращиваем паросочетание. Начинаем строить альтернирующее дерево заново, т.к. мало ли как там граф изменился
- Мы не нашли (не достигли) свободную задачу по оптимальным ребрам. А она есть, т.к. начинали ведь мы со свободного разработчика, а в графе у нас одинаковое количество задач и разработчиков. Полученное альтернирующее дерево становится, так называемым, Венгерским (весь метод так же называется). В данном случае нам нужно будет немного понизить наши требования к разработчикам и начать поиски заново. Failure is simply the opportunity to begin again, this time more intelligently (с).
- Незадействованные разработчики, т.к. именно с них мы начинаем стоить дерево
- Разработчики и задачи, до которых можно дотянуться по оптимальным ребрам из незадействованных разработчиков. Т.к. именно через их «переназначение» мы пытаемся трудоустроить последних.
- Разработчики и задачи, находящиеся в паросочетании, но недоступные из свободных вершин (разработчиков). Нашли им работу – нечего их пока трогать.
- Задачи, недостижимые по оптимальным ребрам – до них нам и нужно будет добраться. Поэтому при построении дерева мы будем отмечать вершины, в которые удалось попасть. А эти задачи, соответственно, останутся неотмеченными.
- Понизим способности разработчиков на delta, чтобы «присоединить» наименее безболезненным способом, по крайней мере, одно ребро к альтернирующему дереву, по которому в следующий раз будем продолжать поиски свободной задачи
- Повысим «изученность» задач на delta, чтобы внутри уже сейчас построенного аугментального графа ребра — остались оптимальными. Т.е. чтобы сохранилось равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина)
Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts.
7. Алгоритм словами, очень кратко
- Инициализация. Разработчикам – max способности. Задачи – не изучены.
- Пока не всем разработчикам нашли задачи.
- Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам
- «Переназначаем» задачи, увеличивая паросочетания
- Понижаем способности разработчиков на min величину
8. Листинг
Код, конечно, будет покороче, чем все мое описание. =)
Я взял его здесь. На мой взгляд, очень хорошая реализация. Единственное отличие, у автора приведен код метода минимизации назначений (если, допустим, на ребрах – зарплата), а в статье мы распределяли задачи с целью получения максимальной эффективности. Поэтому, слегка модифицировав код, приведу ниже реализацию максимального метода:
int n;
vector < vector< int >> a; // Матрица эффективности a[разраб][задача]
vector < int >xy, yx; // Паросочетания: xy[разраб], yx[задача]
vector < char >vx, vy; // Альтернирующее дерево vx[разраб], vy[задача]
vector < int >maxrow, mincol; // Способности, изученностьbool dotry ( int i) if (vx[i]) return false ;
vx[i] = true ;
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = true ;
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) xy[i] = j;
yx[j] = i;
return true ;
>
for ( int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) xy[i] = j;
yx[j] = i;
return true ;
>
return false ;
>mincol.assign (n, 0);
minrow.assign (n, 0);
for ( int i=0; i for ( int j=0; j maxrow[i] = max (maxrow[i], a[i][j]);xy.assign (n, -1);
yx.assign (n, -1);
for ( int c=0; c vx.assign (n, 0);
vy.assign (n, 0);
int k = 0;
for ( int i=0; i if (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) int z = INF;
for ( int i=0; i if (vx[i])
for ( int j=0; j if (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for ( int i=0; iif (vy[i]) mincol[i] += z;
>
>
>int ans = 0;
for ( int i=0; i ans += a[i][xy[i]];
printf ( "%d\n" , ans);
for ( int i=0; i printf ( "%d " , xy[i]+1);
>* This source code was highlighted with Source Code Highlighter .
9. Итого
Если кто-то видит Венгерку впервые. И после прочтения описания, а за ним листинга – возникнет уверенное впечатление «да тут по листингу и без этих описаний все понятно, что было распинаться». Буду все же надеяться, что хоть отчасти описание добавило понимания в работу алгоритма. Буду искренне рад за Вас! а мне, в свою очередь, это немного даст почувствовать, что писал, наверное, не зря. =)
Прочие статьи цикла
Задача выбора (назначения). Венгерский метод решения
Понятия и термины в задаче выбора
Общие понятия линейного программирования сохраняют свои значения и в этой задаче, например, план, допустимый план, оптимальный план, целевая функция и др. Новые в сущности сохраняют смысл, но называются с учетом предметной области или особенностями алгоритма. Вместо пунктов отправления и прибытия транспортной задачи рассматриваются множества должностей и претендентов занять их.
Постановка задачи выбора
Пусть каждый из Пi должностных лиц должен быть назначен на одну из Дj должностей (следовательно, i, j = 1(1)n. ). Обозначим через dij производительность труда (эффект исполнения обязанностей) лица Пi в должности Дj. Оптимальное назначение состоит в таком распределении претендентов (личного состава) по должностям, при котором суммарная производительность с эффектом деятельности будет наибольшей. Если xij =1, когда претендент Пi выступает в должности Дj ; xij =0, в остальных случаях, то необходимо максимизировать функцию
Нетрудно видеть, что эту задачу, названную задачей выбора (или задачей о назначениях), легко свести к обычной транспортной задаче, если потребовать минимизации новой линейной формы
Условие баланса в задаче выбора может быть записано в виде равенства m = n. В случае нарушения баланса m ≠ n необходимо добавит либо фиктивных претендентов (если m
m >n). Задачу выбора можно решить одним из методов решения задач транспортного типа, например методом потенциалов, рассмотренным ранее. Однако специфический характер системы ограничений позволяет существенно упростить алгоритм решения задачи выбора. Один из упрощенных алгоритмов, разработанный венгерским математиком Я. Эгервари, получил наибольшее распространение и был назван в честь своего создателя "венгерским" способом. В основе этого способа используются, так называемые "эквивалентные" преобразования матрицы D[m, n]. Две прямоугольные матрицы А[m, n] и D[m, n] одинаковой размерности m× n называются эквивалентными, если аij =dij +pi + rj, где pi и rj - некоторые произвольные действительные числа, [i=1(1)m; j=1(1)n]. Из последней формулы видно, что эквивалентное преобразование сводится к суммированию ко всем элементам любой строки или столбца одного и того же числа. Покажем, что оптимальные планы двух задач выбора, матрицы которых эквивалентны, совпадают. Пусть Х*[m, n] - оптимальный план задачи выбора с матрицей ||aij||, элементы которой вычисляются по формуле суммы. По определению оптимального плана Но суммы для pi и rj не зависят от выбранного плана, поэтому можно заключить, что план Х*[m, n] минимизирует линейную форму задачи, т.е. является оптимальным для задачи выбора с эквивалентной матрицей ||dij||. Переход от одной матрицы к другой, ей эквивалентной, будем обозначать стрелкой ||dij|| → ||аij||. Приведем структурно-логическую схему алгоритма венгерского способа, которая включает предварительный этап и три этапа вычислений. Ниже рассмотрим эти этапы.
Структурно-логическая схема алгоритма венгерского метода решения задачи выбора
1. Предварительный этап состоит из определения начального (исходного) плана и соответствующего ему выбора, а также эквивалентного преобразования матрицы ||dij||. При этом под "выбором" будем понимать множество элементов dij, соответствующих хij = 1. Эти элементы условимся обозначать d*ij.
Пример 1. Пусть заданы матрицы D[3,3], и план Х[3,3] для плана необходимо определить выбор, соответствующий плану.
Решение: Искомый выбор получаем при выписывании элементов матрицы D[3,3], отвечающих хij = 1. Этот выбор получает вид d11 = 0; d23 = 5; d32 = 0. Начальный план задачи выбора может быть построен тем же способом, что и в транспортной задаче общего вида, причем способ северо-западного угла здесь вырождается в диагональный способ, при котором хij = δij = 1 при i = j; хij = δij = 0 при i≠ j; δij - дискретная дельта-функция или символ Кронекера.
После того как построен начальный план, необходимо с помощью эквивалентного преобразования обеспечить в каждых строке и столбце хотя бы по одному нулю при условии отрицательности всех остальных элементов. для этого необходимо:
- из элементов каждого столбца вычесть наибольший элемент этого столбца;
- из элементов каждой строки вычесть наибольший элемент данной строки.
В результате такого эквивалентного преобразования в каждых строке и столбце будет, по крайней мере, по одному нулю, а все ненулевые элементы будут отрицательными. На этом предварительный этап венгерского метода завершается.2. Сущность первого этапа заключается в проверке всех элементов выбора dij эквивалентной матрицы, полученной на предварительном этапе. Если все dij = 0, то план оптимален и ему соответствует наибольшее значение линейной формы Q*= 0 (при любом другом плане это значение будет отрицательным). Если же некоторые dij < 0, то значение функции цели можно увеличить путем перехода на 2-м этапе к новому улучшенному плану.
3. Основным содержанием 2-го этапа. является переход к новому опорному плану, для которого значение линейной формы больше. С этой целью по следующему правилу строится так называемая цепочка пересчета:
- начальным узлом цепочки назначается любой ненулевой элемент выбора d'ij ≠ 0;
- в качестве следующего узла цепочки выбирается нуль в строке d'ij; и т. д.Цепочка пересчета построенная на 2-м этапе, может оказаться либо замкнутой, либо разомкнутой. Если цепочка замкнута, то необходимо перейти к новому выбору (а, следовательно, и к новому плану) путем включения в него нулей и исключения ненулевых элементов замкнутой цепочки. В противном случае, когда цепочка пересчета оказалась незамкнутой, следует перейти к 3-му этапу.
4. Сущность третьего этапа состоит в том, что путем эквивалентного преобразования матрицы число нулей возрастает, но при этом по возможности сохраняются нули незамкнутой цепочки, построенной на предыдущем этапе. Чтобы добиться этого, необходимо из строк, содержащих элементы выбора в граничных клетках незамкнутой цепочки пересчета, вычесть максимальные элементы этих же строк. Затем эти же элементы следует добавить к столбцам, содержащим нули незамкнутой цепочки (тем самым общее число нулей в цепочке останется прежним). После завершения 3-го этапа необходимо (в соответствии со структурно-логической схемой алгоритма) вернуться к 1-му этапу, т.е. снова проверить полученный план на оптимальность.
Пример 2. Рассмотрим методику решения венгерским способом одной из распространенных задач, получившей название "задачи о назначениях". Предположим, что на предприятие возникли 4 вакансии Вj, j =1(1)4 на сходные должности. По объявлению о наборе специалистов подали заявление 4-ро претендентов Сi, i =1(1)4.
Предприятие заинтересовано в наиболее рациональном использовании специалистов, поэтому перед назначением они были проверены компетентной комиссией, определившей (методом экспертных оценок) ту условную прибыль dij, которую предприятие получит, если i-й специалист будет назначен на j-ю должность (i,j = 1(1)4 ).
Значения dij, установленные комиссией, приведены в матрице D[4,4], а вид решения задается матрицей Х*[4,4]
Необходимо найти оптимальный план распределения специалистов, при котором они смогут обеспечить предприятию наибольшую прибыль.
Решение. В соответствии с алгоритмом (см. схему) решение задачи заключается в ряде последовательных эквивалентных преобразований матрицы ||dij||. Будем исходный план выбирать способом северо-западного угла, а числа pi и rj, с помощью которых осуществляются преобразования, записывать около соответствующей строки или столбца матрицы. Тогда цепочка преобразований будет выглядеть следующим образом:
Цепочки в матрицах обозначены пунктиром со стрелками указывающими направление переходов между элементами матриц
Заключение
В статье рассмотрен еще один тип задач линейного программирования. Отличие задач этого типа от задач, решаемых симплексным методом, состоит в том, что элементами плана в задаче выбора являются единицы (целые значения). Существует обширный класс задач, в которых требуется целочисленность решения и не только из единиц. Но условия, накладываемые на переменные, не позволяют из решать в рамках классического линейного программирования. Исследование операций изучает и такие задачи, разрабатывает методы их решения, но часто методы более сложные и не всегда математически строгие.
Читайте также:
- Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам