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

Рассмотрим пример решения задачи о назначениях. Четверо рабочих могут выполнять 4 вида работ. Стоимости с_{i, j} выполнения i-м рабоим j-й работы приведены в ячейках диапазона А1: D4:

Рис. 3.4. Задача о назначениях. Ввод данных

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

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

-минимизировать

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

, j [1, 4],

, i [1, 4],

х_{i, j} {0, 1}, i [1, 4], j [1, 4]

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

=СУММПРОИЗВ(F2: I5; A1: D4), вычисляющую стоимость работ. В ячейки F6: I6, а также J2: J5 введем формулы, задающие левые части ограничений.

Рис. 3.5. Задача о назначениях. Ввод формул.

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

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

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