Рациональное распределение трудовых ресурсов в строительных сетях

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

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

Обозначения:

сij - показатель эффективности назначения i-го рабочего на j-й работе, например издержки выполнения i-м рабочим j-й работы;

xij - переменная модели (хij = 1, если i-й рабочий используется на j-й работе, и xij = 0 в противном случае).

Модель задачи о назначениях:

Здесь:

(1) - целевая функция (минимум издержек на выполнение всех работ);

(2) - система ограничений, отражающая следующие условия:

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

б) каждый рабочий может быть привлечен к одной работе;

(3) - условия неотрицательности переменных.

Оптимальный план задачи о назначениях (1) - (3) можно представить в виде квадратной матрицы назначений, в каждой строке и в каждом столбце которой находится ровно одна единица. Такую матрицу иногда называют матрицей перестановок. Значение целевой функции (1), соответствующее оптимальному плану, называют эффективностью назначений.

Исходные данные:

На предприятии ООО «Металлист» имеется 5 рабочих каждый из которых может выполнять 5 различных операций по обработке деталей. Известна затраты времени каждого рабочего при выполнении каждой операции, заданная матрицей (табл. 1.1.1):

Таблица 1.1.1