Модели

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

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

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

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

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

т т

AScmin\' (1)

т

1x^=1, j=\\,...,m, (2а)

т

Дху= 1, /=1,..., т, (26)

Ху >0, /=1, ..., т; j = 1, ..., т.

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

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

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

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

— условия неотрицательности переменных.

При решении задачи о назначениях исходной информацией является таблица задачи о назначениях с={су}, элементами которой служат показатели эффективности назначений. Для задачи о

назначениях, записанной в стандартной форме, количество строк этой таблицы совпадает с количеством столбцов:\r\nРабота 1 2 j т\r\nРабочии^^ \r\n1 сп с\\2 CU cim\r\n2 С21 с22 cv е2и\r\n \r\n/ са са са cim\r\n \r\nт Ст\\ ст2 стт\r\n*

x

Результатом решения задачи о назначениях (1)—(3) является вектор х* = { j }, компоненты которого — целые числа.

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