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

Размещено на http://www.allbest.ru/

Минобрнауки России

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Вятский государственный гуманитарный университет"

Факультет информатики, математики и физики

Кафедра прикладной математики и информатики

Курсовая работа

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

Выполнил

студент II курса группы ПМИ-21

Смагин Евгений Дмитриевич

Научный руководитель

заведующая кафедрой прикладной

математики и информатики

Разова Елена Владимировна

Киров

2013



Содержание

Введение

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 г., содержавшая помимо прочих результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, а её публикация прошла незамеченной среди математиков.

http://e-maxx.ru/algo/assignment_hungary

Цель работы:

Исследовать решение задач о назначениях.

Задачи:

Рассмотреть теоретическую часть задач о назначениях.

Проанализировать Венгерский метод решения задач о назначениях.



1. Основы задач о назначениях в теории

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

Транспортная задача - математическая задача о наиболее экономном плане перевозок грузов однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) - имеет обширные практические приложения не только к проблемам транспорта.

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

1. Любая задача транспортного типа, как задача линейного программирования, может быть решена симплекс-методом. Однако специфические особенности задач рассматриваемого класса позволили разработать более эффективные вычислительные методы. А поскольку в реальных задачах транспортного типа число ограничений и переменных, как правило, бывает весьма значительным, то использование эффективных вычислительных алгоритмов становится не только выгодным, но и просто необходимым.

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

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

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

В современных условиях развития каждое предприятие стремится с наименьшими затратами функционировать в сложившихся условиях с целью получения высоких доходов. Экономико-математические задачи о назначениях позволяют найти оптимальный вариант размещения одного кандидата на выполнение одной работы таким образом, чтобы минимизировать суммарные затраты по выполнению комплекса работ группой исполнителей. В некоторых условиях задачи о назначении могут модифицироваться, например: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во-вторых, штатный состав организации может быть представлен большим количеством исполнителей, нежели количество работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику.

Данная задача в такой постановке относится к классу комбинаторных, решение которых путем прямого перебора невозможно при достаточно больших n, так как число вариантов назначений составляет n! Данный программный продукт позволяет за короткий промежуток времени решать описанные модификации задачи о назначениях венгерским методом, с определением оптимального варианта размещения исполнителей по работам, исходя из поставленных условий.

2. Задача о назначениях

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

3. Венгерский метод решения задач о назначениях

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

Структура алгоритма такова: есть последовательные шаги, на каждом из которых делается попытка выбрать назначение при неотрицательной матрице убытков так, чтобы все выбранные элементы матрицы были нулевыми. Если это сделать не удается, матрица изменяется с сохранением свойства неотрицательности. Первоначально подготовка матрицы заключается в том, что от каждого элемента каждой строки матрицы в каждой строке. Вычитание из каждого столбца наименьшего в нем элемента обеспечивает существование нулевых элементов и в столбцах. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.

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

4. Сущность и решение венгерским методом

Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным.

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

1	7	1	3
1	6	4	6
17	1	5	1
1	6	10	4



Нам нужно вычесть самое маленькое значение из первой строчки. И так далее, вычитаем из каждой строчки до тех пор, чтобы в каждой строчке было хотя бы по одному нулю. Можно и более.

Понижаем порядок матрицы на один.

0	6	0	2
0	5	3	5
16	0	4	0
0	5	9	3

Каждый ноль соответствует ребру двудольного графа, напомню, что двудольный граф - это граф, который распадается на два множества, внутри они не соединяются, а соединяются только друг с другом. От I к j вершине. Итак, вершины распадаются на два множества. Первый 0 на месте (1.1) первая вершина соединяется с первой.



Первая с третьим.

Переходим к второй вершине первой доли.

Третья вершина соединяется в двух местах.

И последняя соединяется только с первой.

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

Сначала берем любое, затем максимальное и только затем из максимального находим наибольшее. Так находим наибольшее паросочетания. Мы взяли максимальное паросочетание, теперь нам нужно проверить является ли оно наибольшим.

На отдельном графике найдем наибольшие паросочетания. Если мы будем программировать на компьютере, то он перебирает все возможные варианты. И будет выводить первый попавшийся.

Если есть чередующаяся цепь, то эта чередующаяся цепь состоит из множества X, Y. Состоит из толстых и тонких линий. Тонкие ребра - это все паросочетания полученные из матрицы. Толстые входят в максимальное паросочетание. Из Х прийти в Y по тонким из Y в Х и снова из Х в Y. Потом мы обращаем эту цепь и получаем все наоборот. Из 3 в 2 мы оставим как есть. И добавим тонкие ребра, чтобы посмотреть, есть ли еще чередующаяся цепь.



Есть подозрение, что это максимальное паросочетание.

Но это не единственное максимальное паросочетание. Посмотрим еще один вариант.

Это паросочетание тоже является наибольшим. По черным вперед по красным назад. Их количество должно быть нечетным.

Обозначим вершины, которые не охватываются наибольшим паросочетанием.

Xm=	{X4}
Ym=	{Y4}

По этим множествам создадим еще 2 множества: X' и Y'.

Возьмем Xm и X. Нужно выйти из Xm и вернуться в X. Исходя из той же стратегии: движемся вперед по черным вперед, назад по красным. И смотрим какие при этом мы проходим вершины. Те которые мы проходим вершины помещаем в множества X' Y'. Выходим из X4 в Y1, затем попадаем в X2.

Получаем:

X'=	{x4, x2}
Y'=	{y1}

Теперь по этим номерам строим так называемое альфа-преобразование. Из преобразованной матрицы берем вторую и четвертую строчки и не первый столбец. Из множества Y мы вычитаем Y': Ym/{Y'}

Выделяем в преобразованной матрице строку 2 и 4, и столбцы все, кроме первой. Нас интересует то, что находится в пересечении.

Мы получили шесть элементов.

0	6	0	2
0	5	3	5
16	0	4	0
0	5	9	3

И в этих шести элементах находим минимальное значение. В данном случае получили 3. Далее из этих строк вычитаем тройки и вставляем их в первый столбец. Таким образом, получается:

3	6	0	2
0	2	0	2
19	0	4	0
0	2	6	0

По аналогии строим граф.

В этом двудольном графе ищем вариант, который соответствует максимальному значению. Возьмем первую вершину и исследуем её. Проводим от X1 к Y3. От X2 к Y1. От X3 к Y2. Смотрим на то, чтобы не были заняты вершины графа. ОТ X4 к Y4.



Получилось совершенное паросочетание. Все степени вершин имеют по единице. Возвращаемся в исходную матрицу.

1	7	1	3
1	6	4	6
17	1	5	1
1	6	10	4

Вычисляем сумму выделенных элементов:

1+1+1+4=7

Это и есть ответ решения задачи о назначениях венгерским методом.

5. Реализация задачи о назначениях

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

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

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

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

Основной шаг алгоритма состоит из поиска "нулевого" назначения и преобразования матрицы. Для "нулевого" назначения лучше воспользоваться терминологией простых графов, считать, что Мх -- множество строк матрицы, М2 -- множество столбцов и дуга из i в j идет в том и только в том случае, если a[i, j] = 0. Тогда существование "нулевого" назначения эквивалентно существованию в этом графе полного паросочетания. Будем разыскивать в нашем графе максимальное паросочетание (дающее наибольшее число "независимых" нулей - нулей, расположенных в различных строках и столбцах матрицы). Число дуг в максимальном паросочетании равно наименьшему числу вершин в множестве, которому инцидентны все дуги графа. В терминах теорема звучит следующим образом: наибольшее число независимых нулей равно наименьшему числу вертикальных и горизонтальных линий (столбцов и строк), которыми можно перечеркнуть все нули матрицы.

В данной реализации представлен поиск максимального паросочетания в двудольном графе.

Будем рассчитывать из вводимых данных: рабочие, количество назначаемых задания, количество пар (рабочий-задание).

А в выводе отображается количество заданий, заданных по такой схеме.

const

m = 200;

n = 200;

var

a: array [1..n, 1..m] of boolean; /обозначим переменные

v: array [1..n] of boolean;

p: array [1..m] of word;

c, mm, nn: longint;

procedure init;

var

x, y, k, i: longint;

f: text;

begin

fillchar(a, sizeof(a), 0); / заполняем массивы

fillchar(v, sizeof(v), 0);

fillchar(p, sizeof(p), 0);

c := 0;

assign(f, 'matching.in'); / связываем файловую переменную с именем f

reset(f); / открываем на чтениеread(f, nn, mm, k); / считываем из файла значения

for i := 1 to k do

begin

read(f, x, y);

a[x, y] := true;

end;

close(f);

end;

function findpair(k: integer): boolean; / функция нахождения пар, ставим условия.

var

i: integer;

begin

findpair := false;

if v[k] then

exit;

v[k] := true;

for i := 1 to mm do

if a[k, i] and ((p[i] = 0) or findpair(p[i])) then

begin

findpair := true;

p[i] := k;

exit;

end;

end;

procedure solve; / процедура решения

var

i: longint;

begin

for i := 1 to nn do

begin

fillchar(v, sizeof(v), false); / заполняем массивы, если паросочетание i найдено, то прибавляем 1 к выводимому значению.

if findpair(i) then

inc(c);

end;

end;

procedure done;

var

i: longint;

begin

writeln(c); / выводим количество заданий

for i := 1 to mm do

if p[i] <> 0 then

writeln(p[i], ' ', i); / выводим количество паросочетаний

end;

begin

init;

solve;

done;

readln;

end.



Заключение

Основной принцип работы венгерского метода состоит в следующем: прибавлением определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так именуемых независимых нулей. Набор из нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные - равными 0, тогда получим оптимальный план назначения.

Алгоритм венгерского метода состоит из предварительного шага и не более чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n), задача решена. Оптимальный план назначения определится положением независимых нулей на последней итерации.

задача назначение венгерский полином



Список используемой литературы

1. Асанов М.О., Баранский В.А., Расин В.В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.

2. И.В. Романовский - Алгоритмы решения экстремальных задач.

3. И.К. Волков, Е.А. Загоруйко - Исследования операций.

4. Е.С. Вентцель - Исследование операций: задачи, принципы, методология.

5. Г. Вагнер - Основы исследования операций.

6. А.М. Юрьевич - Исследование операций в экономике: модели, задачи, решения.

7. Информация взята с сайта: http://e-maxx.ru/algo/assignment_hungary.

Размещено на Allbest.ru

...