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

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

Пример 1. Сбалансированная задача о назначениях

Четверо рабочих могут выполнять четыре вида работ. Стоимости Сij выполнения i-м рабочим j-й работы приведены в ячейках A1:D4.

1 4 6 3 рабочий1
9 10 7 9 рабочий2
4 5 11 7 рабочий3
8 7 8 5 рабочий4
работа1 работа2 работа3 работа4  

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

Для решения данной задачи построим её математическую модель. Пусть переменная xij = 1, если i-ым рабочим выполняется j-ая работа, и xij = 0, если i-ым рабочим не выполняется j-ая работа. Тогда модель имеет следующий вид:


Сформируем такую таблицу:


Ячейки A1:D4 - стоимости работ, должны быть >= 0.
Ячейки F2:I5 отведем под неизвестные. Если работник выполняет работу в ячейке 1, иначе 0. Неизвестные должны быть целыми, двоичными.
В ячейке J2 целевая функция  - суммарная стоимость работ.
Левые части ограничений заданы суммами. Например:

СУММ(F2:I2) должна быть равна 1. Это говорит о том, что работник №1 выполняет только одну работу.
СУММ(F2:F5) должна быть равна 1. Это говорит о том, что работу №1 выполняет только один работник.

Найдите оптимальное решение инструментом Поиск решения.
 

Ответ: Стоимость работ = 18.

Пример 2. Несбалансированная задача о назначениях

Четверо рабочих могут выполнять пять видов работ. Эта задача не сбалансирована, т.к. число рабочих не равно числу видов работ. Если задача не сбалансирована, то перед началом решения её надо сбалансировать, введя недостающее число фиктивных строчек или столбцов с достаточно большими штрафными стоимостями работ. В нашей задаче добавлен фиктивный "Рабочий 5". Разберитесь самостоятельно с приведенным ниже решением задачи.

Ответ

  1. Минимальная  стоимость работ = 7.

  2. Из решения видно, что на работу №4 назначен фиктивный рабочий №5, то есть эту работу не выполняет никто.