Практическая работа № 11. Задача о назначениях

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

Рисунок 3.23 – Стоимости работ в задаче о назначениях

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

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

минимизировать: , (3.3)

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

,

,

.

Для решения этой задачи с помощью средства поиска решений отведем под неизвестные диапазон ячеек F2: I5. В ячейку J1 введем целевую функцию:

=СУММПРОИЗВ(F2: I5; A1: D4),

вычисляющую стоимость работ. Введем формулы, задающие левые части ограничений, как показано на рисунке 3.24

Рисунок 3.24 - Левые части ограничений в задаче о назначениях

Затем выберем команду Сервис, Поиск решения и заполним открывшееся диалоговое окно Поиск решения, как показано на рисунке 3.25.

Рисунок 3.25 – Диалоговое окно Поиск решения задачи о назначениях

Не забудьте в диалоговом окне Параметры поиска решения установить флажок Линейная модель. После нажатия кнопки Выполнить средство поиска решений найдет оптимальное решение, которое приведено на рисунке 3.26.

Рисунок 3.26 – Оптимальный план работ в задаче о назначениях