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

Задача  о назначении.

    Задача  о назначении - задача об оптимальном распределении ряда работ между исполнителями при условии взаимного соответствия между множествами работ. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д.

    Математически такие задачи — частный случай распределительных задач с той  особенностью, что в них объемы наличных и требующихся для выполнения каждой работы ресурсов равны единице, т. е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях. Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется матрицей оценок, результаты — в матрице назначений.

    Количество  возможных вариантов назначений равно факториалу числа работ  и ресурсов и огромно даже в  небольшой задаче. Поэтому для  нахождения оптимального варианта применяют  специальные алгоритмы.

    Известно  несколько методов решения задач  и назначение, из которых наиболее эффективным методом решения является венгерский метод.

    Венгерский  алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время . Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари). 

    Джеймс  Манкрес в 1957 году заметил, что алгоритм является полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни.

    Алгоритм  основан на двух идеях:

• если из всех элементов некоей строки или столбца вычесть одно и то же число y, общая стоимость уменьшится на y, а оптимальное решение не изменится;
• если есть решение нулевой стоимости, оно оптимально.

Алгоритм  метода включает следующие основные шаги:

Шаг 1. Получение  нулей в каждой строке.

1.1. Находят  наименьший элемент d-, в каждой  строке, который вычитают из всех  ее элементов и получают новую матрицу.

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

Шаг 2. Поиск  оптимального решения.

2.1. Рассматривается одна из строк таблицы , имеющая меньшее число нулей; отмечается звездочкой.

2.2. Аналогичные  операции выполняют последовательно для всех строк.

2.3. Если назначения, которые получены при всех нулях, отмеченных звездочками, являются полными, т. е. число нулей, отмеченных точками, равно л, то решение является оптимальным. В противном случае переходят к шагу 3.

Шаг 3. Поиск  минимального набора строк и столбцов, содержащих нули.

3.1. Отмечают  звездочкой:

3.1.1. все строки, в которых нет ни одного отмеченного звездочкой нуля;

3.1.2. все  столбцы, содержащие перечеркнутый  нуль хотя бы в одной из отмеченных точкой строк;

3.1.3 . все строки, содержащие отмеченные звездочкой нули хотя бы в одном из отмеченных звездочкой столбцов;

3.2. Шаги 3.1.2 и 3.1.3 повторяют поочередно до тех пор, пока есть что отмечать.

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

Шаг 4. Перестановка некоторых нулей.

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

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

В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта  известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в таблице. Как коммерческий директор должен осуществить назначение продавцов  по торговым точкам, чтобы достичь  максимального объема продаж?