VIII Международная студенческая научная конференция Студенческий научный форум - 2016

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

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

Рассмотрим алгоритм решения на конкретном примере:

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

Матрица эффективности имеет вид

С =

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

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

Находим произвольный 0 в первом столбце и обозначаем его со звездочкой рассматриваем второй столбец и если есть ноль, расположенный в строке, не содержащий ноль со звездочкой, то обозначаем его со звездочкой и т.д. по всем столбцам. Столбцы, содержащие нули со звездочками обозначаем +

Имеем матрицу

Первый этап

Из невыделенных столбцов ( в третьем столбце), находим ноль и отмечаем его со штрихом, если в строке есть 0 со звездочкой , то второй столбец становится не выделенным, а вторая строка выделенной

В оставшихся невыделенных столбцах ищем 0, в данной матрице его нет.

Выбираем наименьший элемент из невыделенных строк и столбцов, он равен 1

Из элементов строк вычитаем, а к выделенным столбцам прибавляем

Проводя аналогичные рассуждения приходим к матрице

Из последней матрицы видим, что распределение должностей следующее:

За первым работником закрепить 4 работу, за вторым - 3 работу, за третьим -2,

за четвертым -1,за пятым - 4. Оптимальный эффект равен 49.

Данная задача имеет второе решение : соответствие следующее 1 -4; 2- 5 ; 3- 2; 4 -1 ; 5-4 . Следовательно, учитывая дополнительные условия можно выбрать одно из полученных решений.

Литература

1. Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с

2. R.E. Burkard, M. Dell’Amico, S. Martello: Assignment Problems. SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4

Код для цитирования: Скопировать