Задача о назначениях — различия между версиями
Материал из ALL
| Строка 36: | Строка 36: | ||
*[[Общая прямая задача линейного программирования]]; | *[[Общая прямая задача линейного программирования]]; | ||
*[[Общая двойственная задача линейного программирования]]; | *[[Общая двойственная задача линейного программирования]]; | ||
| − | *[[ | + | *[[Транспортная задача]]; |
*[[Распределительная задача]]; | *[[Распределительная задача]]; | ||
*[[Транспортная задача с промежуточными пунктами]]; | *[[Транспортная задача с промежуточными пунктами]]; | ||
Версия 05:50, 16 ноября 2015
Содержание
Постановка задачи
Пусть имеется n работ (A1,A2,…,An) и n исполнителей (B1,B2,…,Bn). Пусть известны доходы cij от назначения i-ой работы j-ому исполнителю и необходимо определить назначения с наибольшей суммой доходов, при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу. Тогда задача о назначениях (ЗН) формулируется следующим образом:
,
где xij – 1 если есть назначение i-ой работы j-ому исполнителю, 0 - если нет назначения.
Метод решения
Задача о назначениях решается венгерским методом.
Пример ЗН
Подготовительный этап
Решение венгерским методом
Оптимальное решение равно
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Транспортная задача;
- Распределительная задача;
- Транспортная задача с промежуточными пунктами;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
- Участник:Logic-samara
