ЗАДАЧА О НАЗНАЧЕНИЯХ
— задача о наилучшем распределении
работ между
исполнителями в предположении, что каждый исполнитель назначается только на одну работу и каждая работа предназначается только для одного исполнителя. Исполнители различаются по своим способностям выполнять ту или иную работу. Пусть
производительность
исполнителя на
работе. Наилучшим считается распределение работ, максимизирующее эффективность, измеряемую суммой производительностей всех
исполнителей. Обозначим через
переменную, равную единице, если
исполнитель назначен на
работу, и нулю, если для
работы выбран другой исполнитель. Задача сводится к задаче программирования линейного, заключающейся в нахождении
, которые максимизируют
при условиях
Задача максимизации линейной формы (1) при условиях (2—4) всегда имеет целочисленное решение, поэтому в силу условий (2—3) каждое будет нулем или единицей. 3. о н. представляет собой частный случай транспортной задачи. Наиболее эффективным методом для решения 3. о н. является венгерский метод. Другими примерами могут служить задачи распределения работ по механизмам, распределение целей между огневыми средствами и т. п.
Лит. см. и ст. Программирование линейное.
Л. Н. Комзанова.
