Задача о назначениях — различия между версиями
Материал из ALL
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
[[файл:ЗН01.JPG|thumb|300|[[Математическая модель]] ЗН]] | [[файл:ЗН01.JPG|thumb|300|[[Математическая модель]] ЗН]] | ||
| + | '''Задача о назначениях''' – это задача оптимального назначения работ исполнителям. | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеется '''n''' работ '''(A1,A2,…,An)''' и '''n''' исполнителей '''(B1,B2,…,Bn)'''. Пусть известны доходы '''c<sub>ij</sub>''' от назначения '''i'''-ой работы '''j'''-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. | Пусть имеется '''n''' работ '''(A1,A2,…,An)''' и '''n''' исполнителей '''(B1,B2,…,Bn)'''. Пусть известны доходы '''c<sub>ij</sub>''' от назначения '''i'''-ой работы '''j'''-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. | ||
| Строка 7: | Строка 8: | ||
где '''x<sub>ij</sub>''' – '''1''' если есть назначение '''i'''-ой работы '''j'''-ому исполнителю, '''0''' - если нет назначения. | где '''x<sub>ij</sub>''' – '''1''' если есть назначение '''i'''-ой работы '''j'''-ому исполнителю, '''0''' - если нет назначения. | ||
| − | |||
== Метод решения == | == Метод решения == | ||
Задача о назначениях решается венгерским методом. | Задача о назначениях решается венгерским методом. | ||
| + | == Пример ЗН == | ||
| + | [[файл:ЗН09.JPG]] | ||
| − | |||
[[файл:ЗН10.JPG]] | [[файл:ЗН10.JPG]] | ||
| − | |||
| − | |||
| − | |||
=== Подготовительный этап === | === Подготовительный этап === | ||
[[файл:ЗН12.JPG]] | [[файл:ЗН12.JPG]] | ||
| Строка 22: | Строка 20: | ||
[[файл:ЗН14.JPG]] | [[файл:ЗН14.JPG]] | ||
| − | |||
=== Решение венгерским методом === | === Решение венгерским методом === | ||
[[файл:ЗН21.JPG]] | [[файл:ЗН21.JPG]] | ||
| Строка 29: | Строка 26: | ||
Оптимальное решение равно | Оптимальное решение равно | ||
| − | |||
[[файл:ЗН30.JPG]] | [[файл:ЗН30.JPG]] | ||
| − | |||
== Другие задачи: == | == Другие задачи: == | ||
| − | + | {{Список ЗТТ}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
* Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | * Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | ||
Текущая версия на 10:20, 28 сентября 2016
Задача о назначениях – это задача оптимального назначения работ исполнителям.
Содержание
Постановка задачи
Пусть имеется n работ (A1,A2,…,An) и n исполнителей (B1,B2,…,Bn). Пусть известны доходы cij от назначения i-ой работы j-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. Тогда задача о назначениях (ЗН) формулируется следующим образом:
,
где xij – 1 если есть назначение i-ой работы j-ому исполнителю, 0 - если нет назначения.
Метод решения
Задача о назначениях решается венгерским методом.
Пример ЗН
Подготовительный этап
Решение венгерским методом
Оптимальное решение равно
Другие задачи:
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3;
- Открытая транспортная задача с промежуточными пунктами 4;
- Трёхиндексная транспортная задача.
Ссылки
- Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
- Участник:Logic-samara
