 |
Особые случаи задачи о назначениях
|
|
|
|
Контрольная работа
Содержание
Задание 1 – Задачи о назначениях, их модификации и особые случаи. 3
Задача о назначениях. 3
Особые случаи задачи о назначениях. 5
Максимизация целевой функции. 5
Недопустимые назначения. 7
Несоответствие числа пунктов производства и назначений. 7
Венгерский метод решения задачи о назначениях. 8
Алгоритм решения задачи о назначениях. 9
Задание 2. 12
Задание 3. 19
Задание 4. 31
Задание 5. 34
Список использованной литературы.. 36
Задание 1 – Задачи о назначениях, их модификации и особые случаи
Задача о назначениях
Задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Наиболее эффективным методом ее решения является венгерский метод. Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д.
Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.
Транспортная задача – задача о наиболее экономном плане перевозок однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) – является важнейшей частной задачей линейного программирования, имеющей обширные практические приложения не только к проблемам транспорта.
Применительно к задаче о назначениях симплексный метод не эффективен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эффективный метод ее решения, известный как венгерский метод.
|
|
|
Эта задача исторически является первой задачей дискретного программирования (опубликована венгерским математиком Е. Эгервари в 1932 г. как транспортная задача).
Имеется n исполнителей, которые могут выполнить n различных работ. Известна полезность cij, связанная с выполнением i-м исполнителем j-ой работы (i, j = 1, 2,..., n). Необходимо так назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.
Для составления математической модели задачи обозначим через xij факт назначения или неназначения i-го исполнителя на j-ую работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то xij должен принимать только два значения: 1 или 0 (такие переменные называются булевыми):
xij = 1, если i-ый исполнитель назначен на j-ую работу;
xij = 1, в противном случае.
Таким образом, приходим к задаче: Найти план назначения (xij), который максимизирует суммарную полезность назначений
при следующих ограничениях:
каждый i исполнитель назначается только на одну работу:
на каждую j работу назначается только на один исполнитель:
на переменные наложены условия неотрицательности и целочисленности:
Легко можно увидеть, что задача о назначении является частным случаем транспортной задачи при ai = 1, bj = 1. С учетом специфики для ее решения разработаны специальные, более эффективные алгоритмы.
Задача о назначении имеет самое широкое применение. Например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали, назначении на должность, о распределении рабочих, бригад, фирм и т.д. В каждом конкретном случае математическая модель задачи имеет свою специфику. Например, в задаче распределения алгоритмов между вычислительными машинами на ВЦ число распределяемых алгоритмов не равно числу машин. При назначении на должность для некоторых исполнителей существуют ограничения.
|
|
|
Точное решение задачи о назначениях находится методом динамического программирования (венгерский метод). Существует также много других приближенных методов. Хорошее приближение дает модификация метода аппроксимации Фогеля для определения опорного плана транспортной задачи.
Особые случаи задачи о назначениях
|
|
|
