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

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

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

Кроме того, в задаче о назначениях от каждого постав­щика к каждому потребителю поставляется только одна единица «груза» (например, только одного рабочего мож­но назначить для выполнения данной работы) или ни од­ной. Поэтому все «запасы» и все «заказы» равны 1.

Понятно, что все переменные решения в задаче о на­значениях могут принимать только значения 1 или 0. На первый взгляд, это похоже на задачи целочисленного ли­нейного программирования. Однако в силу особенностей структуры ограничений транспортной задачи явно требо­вать целочисленность переменных решения (как их ра­венства только нулю или единице) не требуется. Такие значения получаются при решении автоматически.

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

В заключение данного учебного вопроса еще раз отметим, что транспорт­ная задача обязательно должна обладать свойством сбалансированности: сумма запасов производителей должна быть равна сумме заказов потребителей. Если это условие в реальности не выполняется, необходимо сбалансировать задачу, а именно:

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

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

При решении транспортной задачи с помощью проце­дуры MS-Excel Поиск решения она автоматически выберет специальные эффективные алгоритмы решения и обеспе­чит целочисленность решения (без специального требова­ния целочисленности), если организация данных и введен­ные ограничения соответствуют транспортной задаче.

Задача о назначениях представляет собой частный слу­чай транспортной задачи с числом строк (поставщиков), равным числу столбцов (потребителей). Каждый «постав­щик» (это может быть рабочий) предлагает самого себя одному из «потребителей» (это может быть операция, ста­нок или напарник). Поэтому все «запасы» и «заказы» в задаче о назначениях равны 1.