Задача о назначениях

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

Так, например, всегда актуальной является проблема формирования трудового коллектива, обеспечивающего желаемую эффективность.

Известно, что один и тот же работник может выполнять различные функции с разной производительностью в зависимости от опыта работы, квалификации, индивидуальных особенностей. Поэтому возникает задача о назначениях, предполагающая такое распределение работников, но должностям, при котором производительность труда в коллективе была бы максимальной. Очевидно, здесь следует соблюдать золотое правило экономики, заключающееся в найме таких работников, которые дают дополнительный доход, превышающий назначенную им заработную плату.

Построение экономико-математической модели задачи. На коммерческом предприятии имеется т работников.

каждый из которых должен выполнять одну й, из имеющихся п видов работ:

Для каждого работника Л, на рабочем месте й_; рассчитывается производительность труда Су. Необходимо определить, кого и на какую работу следует назначить, чтобы добиться максимальной суммарной производительности или минимальной стоимости назначения при условии, что каждый работник может быть назначен только на одну работу.

Обозначим Ху назначение i-го работника на7−10 работу. Количество работников т равно количеству работ, поэтому Ху может принимать только два целочисленных значения: 1, если i-й работник назначен на выполнение у-й работы; 0, если не назначен. При назначении i-го работника на j-ю работу производительность или стоимость назначения равна СуХу. Необходимо построить квадратную матрицу распределения, но должностям X, которая обеспечивает максимальное или минимальное значение линейной функции цели.

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

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