Основы задач о назначениях в теории. Изучение истории создания венгерского метода решения задач о назначениях. Описание алгоритма решения данным методом за время порядка полинома, не зависящего от величины стоимостей. Реализация задачи о назначениях.
Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кенига (Denes Konig) и Эйгена Эгервари (Jeno Egervary). Джеймс Манкрес (James Munkres) показал, что этот алгоритм работает за (строго) полиномиальное время (т.е. за время порядка полинома, не зависящего от величины стоимостей).Транспортная задача - математическая задача о наиболее экономном плане перевозок грузов однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) - имеет обширные практические приложения не только к проблемам транспорта. Интерес к этим задачам обусловлен не только спецификой их формализации и прикладной значимостью, но и рядом других причин, среди которых отметим следующие: 1. Любая задача транспортного типа, как задача линейного программирования, может быть решена симплекс-методом. Это представление в ряде случаев позволяет преобразовывать к задачам транспортного типа даже такие задачи исследования операций, которые на первый взгляд не имеют с ними ничего общего, и использовать для их решения эффективные вычислительные алгоритмы. Задачи транспортного типа тесно связаны с детерминированными динамическими задачами исследования операций, в том числе и с многошаговыми задачами принятия решений в условиях определенности, имеющими большое прикладное значение.При ее решении этой задачи ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей.Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Структура алгоритма такова: есть последовательные шаги, на каждом из которых делается попытка выбрать назначение при неотрицательной матрице убытков так, чтобы все выбранные элементы матрицы были нулевыми.Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. И так далее, вычитаем из каждой строчки до тех пор, чтобы в каждой строчке было хотя бы по одному нулю. Каждый ноль соответствует ребру двудольного графа, напомню, что двудольный граф - это граф, который распадается на два множества, внутри они не соединяются, а соединяются только друг с другом. Первый 0 на месте (1.1) первая вершина соединяется с первой. Паросочетания - это тоже двудольный граф, особенность у него в том, что все степени вершин будут равны единице-это означает что от одной вершины два ребра не пойдет.Для получения "нулевого" назначения нужно таким образом изменить матрицу, чтобы минимальное значение целевой функции равнялось нулю. Таким образом, невозможность получить "нулевое" назначение показывает, что матрица еще недостаточно изменена. Метод изменения матрицы очень прост - он состоит из прибавления ко всем элементам какой-либо строки или столбца матрицы одного и того же числа. Поскольку в любом допустимом решении должен быть ровно один элемент из этой строки (или этого столбца), к значению целевой функции при этом изменении прибавляется то же число. В терминах теорема звучит следующим образом: наибольшее число независимых нулей равно наименьшему числу вертикальных и горизонтальных линий (столбцов и строк), которыми можно перечеркнуть все нули матрицы.Основной принцип работы венгерского метода состоит в следующем: прибавлением определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так именуемых независимых нулей. Набор из нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные - равными 0, тогда получим оптимальный план назначения.
План
Содержание
Введение
1. Основы задач о назначениях в теории
2. Задача о назначениях
3. Венгерский метод решения задач о назначениях
4. Сущность и решение Венгерским методом
5. Реализация задачи о назначениях
Заключение
Список используемой литературы
Введение
Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кенига (Denes Konig) и Эйгена Эгервари (Jeno Egervary).
В 1957 г. Джеймс Манкрес (James Munkres) показал, что этот алгоритм работает за (строго) полиномиальное время (т.е. за время порядка полинома, не зависящего от величины стоимостей).
Поэтому в литературе данный алгоритм известен не только как "венгерский", но и как "алгоритм Куна-Манкреса" или "алгоритм Манкреса".
Впрочем, недавно (в 2006 г.) выяснилось, что точно такой же алгоритм был изобретен за век до Куна немецким математиком Карлом Густавом Якоби (Carl Gustav Jacobi). Дело в том, что его работа "About the research of the order of a system of arbitrary ordinary differential equations", напечатанная посмертно в 1890 г., содержавшая помимо прочих результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, а ее публикация прошла незамеченной среди математиков.
Цель работы: Исследовать решение задач о назначениях.
Задачи: Рассмотреть теоретическую часть задач о назначениях.
Проанализировать Венгерский метод решения задач о назначениях.
Вывод
Основной принцип работы венгерского метода состоит в следующем: прибавлением определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так именуемых независимых нулей. Набор из нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные - равными 0, тогда получим оптимальный план назначения.
Алгоритм венгерского метода состоит из предварительного шага и не более чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n), задача решена. Оптимальный план назначения определится положением независимых нулей на последней итерации. задача назначение венгерский полином
