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

Введение 3
Глава 1. Теоретические основы задач о назначениях 5
1.1 Задача о назначениях 5
1.2. Особые случаи в задачах о назначениях 5
Глава 2. Венгерский метод решения задачи о назначениях 9
2.1 Сущность Венгерского метода 9
2.2 Венгерский алгоритм решения задачи (на минимум целевой функции) 10
2.3. Пример решения задачи о назначениях Венгерским методом 12
Глава 3. Решение задачи о назначениях на ЭВМ путем использования программного обеспечения Microsoft Exсel 16
Заключение 20
Список использованной литературы 21

Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.
Транспортная задача - это задача о поиске наиболее экономного плана транспортировки однородного или взаимозаменяемого продукта из пунктов производства (станций отправки), в пункты потребления (станции назначения). Она является одной из важнейших частных задач линейного программирования, имеющих широкие практические приложения далеко не только к проблемам транспорта.
Симплексный метод относительно задач о назначениях неэффективен, поскольку каждое ее допустимое базисное решение вырожденное. Благодаря специфическим особенностям задачи о назначениях представилась возможность создать эффективный метод ее решения, именуемый венгерским методом.
В современных эко номических условиях любое предприятие старается с минимальными затратами осуществлять свою деятельность в образовавшихся условиях с намерением получения высокой прибыли. Экономико-математические задачи о назначениях делают возможным нахождение оптимального варианта размещения одного кандидата на выполнение одной работы таким образом, чтобы максимально уменьшить итоговые затраты по реализации комплекса работ группой исполнителей. Также возможны некоторые модификации задачи о назначениях: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во-вторых, штатный состав организации может быть представлен большим количеством исполнителей, количеством работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; и в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику. В такой постановке данная задача относится к классу комбинаторных, решение которых с помощью прямого перебора невозможно при достаточно больших n, поскольку число вариантов назначений составляет n!. Данный программный продукт способен за небольшой промежуток времени решать описанные модификации задачи о назначениях венгерским методом, с определением оптимального варианта размещения исполнителей по работам, исходя из поставленных условий. Смысл метода был высказан венгерским математиком Эйгеном Эгервари и состоит он в следующем. Создается начальный план, не удовлетворяющий в общем случае всем условиям задачи. Затем производится переход к новому плану, который более близок к оптимальному. Дальнейшее использование этого приема за конечное число повторений приводит к решению задачи.
Цель данного курсового проекта - исследовать решение задач о назначениях.
Задачи:
1. Изучить теоретические основы задач о назначениях;
2. Проанализировать Венгерский метод решения задачи о назначениях;
3. Решить задачу о назначениях при помощи ЭВМ.
Предметом нашего курсового проекта является задача о назначениях.
Объектом нашего курсового проекта является максимизация прибыли путем эффективного распределения трудовых ресурсов посредством задачи о назначениях.
Источниками информации послужили учебная литература, пособия и ресурсы всемирной сети Интернет.
Основные методы исследования, применяемые в курсовом проекте - индукция и дедукция, анализ и синтез.
Данная работа состоит из введения, теоретической и практической частей, заключения, списка использованных источников и приложений

Курсовой проект на тему: Задача о назначениях. Ее решение венгерским методом