Введение 4
1 Теоретическая часть 6
1.1 Задача о назначениях 6
1.2 Методы решения задачи о назначениях 8
1.2.1 Метод полного перебора 9
1.2.2 Венгерский метод 9
1.3 Транспортная задача 13
2 Практическая часть 17
2.1 Постановка задачи 17
2.2 Математическая постановка задачи 18
2.3 Преобразование к задаче назначения 20
2.4 Преобразование к транспортной задаче 21
3 Апробация 23
3.1 Программная реализация 23
3.2 Метод полного перебора 26
3.3 Венгерский метод 28
3.4 Метод потенциалов транспортной задачи 32
Заключение 39
Список использованных источников 40
Купить

Исключительные темпы технического прогресса и усложнение хозяйственных связей породили проблему создания систем управления сложными системами, которая, в свою очередь, привела к необходимости построения математических моделей принятия оптимальных решений.
Задача о назначениях - вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации «рабочий — станок» характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности
Актуальность. В современных условиях развития каждое предприятие стремится с наименьшими затратами функционировать в сложившихся условиях с целью получения высоких доходов. Экономико-математические задачи о назначениях позволяют найти оптимальный вариант размещения одного кандидата на выполнение одной работы таким образом, чтобы минимизировать суммарные затраты по выполнению комплекса работ группой исполнителей. Также возможны некоторые модификации задачи о назначениях: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во -вторых, штатный состав организации может быть представлен большим количеством исполнителей, нежели количество работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику [1].
На практике возникают различные вариации задачи о назначениях. Например, известны обобщенная задача о назначениях, задача о назначении минимального количества исполнителей, линейная задача о назначениях в узких местах, квадратичная задача о назначениях, задача о марьяже, задача о соседях по комнате, задача о назначении целей. В данной работе объектом исследования является задача о распределении сотрудников по помещениям. Предприятие набирает рабочий персонал. Каждый рабочий имеет свой уровень адаптированности (предпочтения) к условиям предоставленных помещений. Необходимо найти такой вариант распределения, который бы максимизировал суммарный уровень адаптированности.
Предмет исследования: методы линейного целочисленного математического программирования.
Цель работы: разработка алгоритма решения задачи о распределении сотрудников по помещениям.
Для реализации цели выпускной квалификационной работы были поставлены следующие задачи:
- подбор и анализ литературных источников;
- изучение алгоритмов решения задачи о назначениях;
- формализация задачи о распределении сотрудников по помещениям;
- разработка алгоритма решения задачи;
- программная реализация алгоритма и его апробация.

Купить