Задачи о назначениях. Теоретические основы

Задача о назначениях – это модель для количественного анализа ситуаций, когда менеджер должен назначить рабочих для выполнения различных производственных операций, распределить ряд производственных заданий по различным машинам (которые могут эти задания выполнить с различной эффективностью), или решить какого торгового агента в какую область послать для продвижения продукции фирмы. Это распределение или назначение должно быть сделано либо из соображений наибольшей эффективности, либо из соображений наименьших затрат.

С математической точки зрения, задача о назначениях – это частный случай транспортной задачи, в которой число поставщиков (например, число рабочих или, иначе, поставщиков рабочей силы) в точности равно числу потребителей (“работ”, различных технологических операций). Поэтому таблица “транспортных издержек” (аналогом которых может выступать любая мера эффективности выполнения той или иной операции данным работником) должна быть квадратной.

Переменные x_ij в задаче о назначениях принимают два значения: , если i-ый претендент (Pi) не принимается на j-ую вакансию (Vj), , если i-ый претендент (P_i) принимается на j-ую вакансию (Vj). Все переменные задачи неотрицательные и целые числа. Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:

Если обозначить через c_ij количественную меру эффективности назначения i-ого претендента на j-ую вакансию, целевая функция задачи о назначения будет выглядеть следующим образом

Итак, формализованное описание задачи о назначениях совпадает с описанием транспортной задачи.