Задача о назначениях кратко
Обновлено: 07.07.2024
Основы задач о назначениях в теории. Изучение истории создания венгерского метода решения задач о назначениях. Описание алгоритма решения данным методом за время порядка полинома, не зависящего от величины стоимостей. Реализация задачи о назначениях.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 15.05.2014 |
| Размер файла | 294,2 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
"Вятский государственный гуманитарный университет"
Факультет информатики, математики и физики
Кафедра прикладной математики и информатики
Задача о назначениях
студент II курса группы ПМИ-21
Смагин Евгений Дмитриевич
заведующая кафедрой прикладной
математики и информатики
Разова Елена Владимировна
1. Основы задач о назначениях в теории
2. Задача о назначениях
3. Венгерский метод решения задач о назначениях
4. Сущность и решение Венгерским методом
5. Реализация задачи о назначениях
Список используемой литературы
Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кёнига (Dйnes Kхnig) и Эйгена Эгервари (Jenх Egervбry).
В 1957 г. Джеймс Манкрес (James Munkres) показал, что этот алгоритм работает за (строго) полиномиальное время (т.е. за время порядка полинома, не зависящего от величины стоимостей).
Поэтому в литературе данный алгоритм известен не только как "венгерский", но и как "алгоритм Куна-Манкреса" или "алгоритм Манкреса".
Впрочем, недавно (в 2006 г.) выяснилось, что точно такой же алгоритм был изобретён за век до Куна немецким математиком Карлом Густавом Якоби (Carl Gustav Jacobi). Дело в том, что его работа "About the research of the order of a system of arbitrary ordinary differential equations", напечатанная посмертно в 1890 г., содержавшая помимо прочих результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, а её публикация прошла незамеченной среди математиков.
Исследовать решение задач о назначениях.
Рассмотреть теоретическую часть задач о назначениях.
Проанализировать Венгерский метод решения задач о назначениях.
1. Основы задач о назначениях в теории
Задача о назначениях является частным случаем классической транспортной задачи и, тем самым, является задачей транспортного типа.
Транспортная задача - математическая задача о наиболее экономном плане перевозок грузов однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) - имеет обширные практические приложения не только к проблемам транспорта.
Интерес к этим задачам обусловлен не только спецификой их формализации и прикладной значимостью, но и рядом других причин, среди которых отметим следующие:
1. Любая задача транспортного типа, как задача линейного программирования, может быть решена симплекс-методом. Однако специфические особенности задач рассматриваемого класса позволили разработать более эффективные вычислительные методы. А поскольку в реальных задачах транспортного типа число ограничений и переменных, как правило, бывает весьма значительным, то использование эффективных вычислительных алгоритмов становится не только выгодным, но и просто необходимым.
2. Для задач транспортного типа естественным и удобным является их геометрическое представление в виде графа специального вида. Это представление в ряде случаев позволяет преобразовывать к задачам транспортного типа даже такие задачи исследования операций, которые на первый взгляд не имеют с ними ничего общего, и использовать для их решения эффективные вычислительные алгоритмы.
3. Задачи транспортного типа тесно связаны с детерминированными динамическими задачами исследования операций , в том числе и с многошаговыми задачами принятия решений в условиях определенности, имеющими большое прикладное значение .
Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод.
В современных условиях развития каждое предприятие стремится с наименьшими затратами функционировать в сложившихся условиях с целью получения высоких доходов. Экономико-математические задачи о назначениях позволяют найти оптимальный вариант размещения одного кандидата на выполнение одной работы таким образом, чтобы минимизировать суммарные затраты по выполнению комплекса работ группой исполнителей. В некоторых условиях задачи о назначении могут модифицироваться, например: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во-вторых, штатный состав организации может быть представлен большим количеством исполнителей, нежели количество работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику.
Данная задача в такой постановке относится к классу комбинаторных, решение которых путем прямого перебора невозможно при достаточно больших n, так как число вариантов назначений составляет n! Данный программный продукт позволяет за короткий промежуток времени решать описанные модификации задачи о назначениях венгерским методом, с определением оптимального варианта размещения исполнителей по работам, исходя из поставленных условий.
2. Задача о назначениях
Задача о назначениях - это задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей. При её решении этой задачи ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. К задаче о назначении можно отнести множество интерпретаций: распределение работников на предприятии в соответствии их работоспособности и навыкам, распределение работы различных механизмов и их энергозатрат и т.д. Наиболее эффективным методом ее решения является венгерский метод.
3. Венгерский метод решения задач о назначениях
Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу.
Структура алгоритма такова: есть последовательные шаги, на каждом из которых делается попытка выбрать назначение при неотрицательной матрице убытков так, чтобы все выбранные элементы матрицы были нулевыми. Если это сделать не удается, матрица изменяется с сохранением свойства неотрицательности. Первоначально подготовка матрицы заключается в том, что от каждого элемента каждой строки матрицы в каждой строке. Вычитание из каждого столбца наименьшего в нем элемента обеспечивает существование нулевых элементов и в столбцах. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.
Следует иметь в виду, что для любого недопустимого назначения соответствующая ему стоимость условно полагается равной достаточно большому числу М в задачах на минимум. Если исходная матрица не является квадратной, то следует ввести дополнительно необходимое количество строк или столбцов, а их элементам присвоить значения, определяемые условиями задачи, возможно после редукции, а доминирующие альтернативы дорогие или дешевые исключить.
4. Сущность и решение венгерским методом
Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным.
Приведем пример: имеется определенное число работников и определенное число мест. На каждом месте работник имеет определенную заработную плату. Расставить оптимально работников так, чтобы заработная плата была меньше всего. Будем рассматривать с точки зрения руководителя. Работа будет производиться на минимум. В каждой строчке матрицы мы будем выбирать по одному элементу, нельзя чтобы работник работал сразу на двух местах. На каждой строчке и на каждом столбце должно быть по одному выделенному элементу. Распишем сущность алгоритма венгерским методом. Имеем исходную матрицу:
Еще одна из выделенных задач линейного программирования, о которой важно упомянуть - это задача о назначениях. Вообще говоря, можно считать, что это частный случай транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность). Если на примерах, это может быть задача назначения работников на должности (с достижением максимальной эффективности, или, может, минимальных затрат на зарплату), назначение машин на производственные линии и т.п., при этом один исполнитель (человек, машина, орудие и т.п.) может выполнять только одну работу.
Так же как для решения транспортной задачи был модифицирован симплекс-метод и разработан метод потенциалов, так и для задачи о назначениях был создан более подходящий (более краткий) метод решения. Чаще всего используется так называемый венгерский метод (см. решение примера 1 ниже).
Ниже выложены примеры задач о назначениях, решенные разными способами - изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Решение задач линейного программирования для студентов.
Задача о назначениях: примеры решений онлайн
Задача 1. Решить задачу об оптимальном назначении с матрицей эффективностей A.
Задача 2. Решить задачу о назначениях.
Задача 3. Четыре работника должны выполнять четыре вида работ. Назначить работников на работы методами динамического программирования и ветвей и границ таким образом, чтобы затраты труда были минимальны.
Задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Наиболее эффективным методом ее решения является венгерский метод. Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д.
1. Задача (формулировка).
Мы будем проще (в терминах). =)
Представим себе задачу: нужно эффективным образом реализовать некоторый относительно большой проект. Для проекта была отобрана команда первоклассных разработчиков, разбирающихся в различных областях. И так уж посчастливилось, что есть сведения (накопленная статистика) о степени (эффективности) владения технологиями для каждого. Но, к сожалению, разработчиков в команде не так уж и много, а точнее – столько же, сколько и технологий будет использовано в проекте.
Необходимо: самым эффективным способом задействовать наибольшее количество технологий, назначив каждому разработчику свою задачу. т.е. оптимально распределить между ними области ответственности за технологии, принимая во внимание их личные способности.
2. Подход к решению
In the end, all business operations can be reduced to three words: people, product, and profits ©. Если мы попробуем изобразить поставленную перед нам и задачу на листе бумаги, то наверняка получим подобную иллюстрацию, как на рисунке (с такими картинками).
Получился — граф. Вершины слева – разработчики, вершины справа – технологии (задачи). Ребра, которые их соединяют – означают то, насколько разработчик в ней разбирается. Эти цифры, т.е. степень владения разработчиком данной технологией, очень важны, но к ним обратимся чуть позже. А пока мы уже верно наметили направление, в котором эффективно решается данная задача:
3. Графы
Самые основы графов были изложены в статье (max cost), поэтому сразу перейду к терминологии, касающейся данной задачи:
4. Максимальное паросочетание
Чтобы упростить себе жизнь, мы пока не обращаем внимания на способности людей. Просто хотим каждому подыскать работу. Нескольким первым попавшимся под руку разработчикам предложить работать со знакомой им технологией не составит проблем. Продолжая в том же духе, мы распределим еще несколько задач, но построенное таким образом паросочетание вряд ли будет максимальным. Возможна ситуация как та, что изображена на рисунке:
Как же увеличить паросочетания (назначения)?
Добавим еще немного терминологии из теории графов, простыми словами:
Теперь мы уже сможем задействовать наибольшее количество технологий в проекте. Самое время принять во внимание еще одно важное условие поставленной перед нами проблемы: эффективность владения технологиями. Мы ведь хотим оптимально назначить всем задачи.
5. Венгерский метод.
Стратегия ясна.
6. Описание алгоритма
Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts.
7. Алгоритм словами, очень кратко
8. Листинг
Код, конечно, будет покороче, чем все мое описание. =)
Я взял его здесь. На мой взгляд, очень хорошая реализация. Единственное отличие, у автора приведен код метода минимизации назначений (если, допустим, на ребрах – зарплата), а в статье мы распределяли задачи с целью получения максимальной эффективности. Поэтому, слегка модифицировав код, приведу ниже реализацию максимального метода:
int n;
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 for ( int c=0; c 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; i if (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
>
>
>
int ans = 0;
for ( int i=0; i "%d\n" , ans);
for ( int i=0; i "%d " , xy[i]+1);
>
* This source code was highlighted with Source Code Highlighter .
9. Итого
С помощю этого онлайн калькулятора можно решить задачу о назначениях (задачу о выборе) венгерским методом. Для решения задачи о назначениях задайте размерность матрицы, выберите из вариантов "максимальная прибыль" и "минимальные расходы". Затем введите данные в ячейки и нажимайте на кнопку "Вычислить". Теоретическую часть смотрите ниже.
Предупреждение
Задача о назначениях − теория
Математическая задача о назначениях или задача о выборе формулируется следующим образом. Требуется выбрать такую последовательность элементов из следующей квадратной матрицы
 |
чтобы достигала своего максимального значения, причем при . Другими словами, нужно выбрать из каждого столбца и каждой строки ровно по одному элементу так, чтобы их сумма была максимальной.
Отметим, что если бы матрица 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.
Для рассмотрения численного примера задачи о назначениях (задачи выбора), введите в кальнуляторе в начале страницы элементы матрицы и нажмите на кнопу вычислить. Онлайн калькулятор выдаст подробное рашение задачи.
Читайте также: