Задача о назначениях. Частным случаем транспортной задачи линейного программирования является задача о назначениях – задача выбора

Частным случаем транспортной задачи линейного программирования является задача о назначениях – задача выбора.

Это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.п.), а каждый ресурс может быть использован на одной и только работе.

То есть, ресурсы не делимы между работами, а работы не делимы между ресурсами.

Задача о назначениях имеет место при назначении людей на должности, водителей на машины, транспортных средств на маршруты, при распределении групп по аудиториям, тем по подразделениям.

Исходные параметры модели

Имеется n работ и n кандидатов для их выполнения (механизмов). Производительность каждого механизма различна. Затраты i -го кандидата на выполнение j -ой работы равны c_ij (i, j = ).

Пусть х_ij – переменная, значение которой равно 1, если i -й кандидат назначен выполнять j -ю работу и 0 – в противном случае.

Математическая модель.

Найти минимум целевой функции

(в целевую функцию входят только те значения c_ij (i, j = ), для которых х_ij отличны от нуля, т.е. входят затраты, соответствующие назначенным работам)

при ограничениях

(каждый кандидат выполняет только одну работу);

(каждая работа может выполняться одним кандидатом);

х_ij Є {0; 1}, (i, j = ).

Решить задачу о назначениях – значит найти х_ij, удовлетворяющие ограничениям и доставляющим минимуму целевой функции.

Это транспортная задача, в которой правые части ограничений равны 1, а переменные могут принимать только два значения (0,1). Простая форма задачи позволила разработать для нее достаточно простые методы решения.