Решение задачи о назначениях в Excel с использованием настройки Поиск решения

Задача о назначениях яляется частным видом линейной оптимизационной задачи. Наиболее часто задача о назначениях представляется следующим образом:

Имеются n рабочих и m видов работ. Стоимость c_ij выполнения i-м рабочим j-той работы приведена в таблице, где под строкой понимается рабочий, а под столбцом - работа. Необходимо составить план работ так чтобы все работы были выполнены, каждый рабочий был занят только на одной работе, а суммарная стоимость выполнения всех работ была бы минимальной.

Решение задачи о назначениях очень похоже на решение транспортной задачи. Особеность лишь в том, что плановые переменные могут принимать только значения 0 или 1 и в каждом столбце и строке может быть только одно ненулевое значение. Для решения задачи о назначениях в Excel с использованием настройки Поиск решения следует выделить ячейки назначений и подсчитать для них суммы по столбцам и по строкам. В ячейку целевой функции следует ввести формулу вычисляющую сумму произведений стоимости работы на план назначений.

После чего следует выбрать в Excel пункт меню Сервис/Поиск решения, в окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения. Как правила используются ограничения следующего вида:

1. Неотрицательность значений изменяемых ячеек;
2. Суммы значений изменяемых ячеек для каждой строки и столбца должны быть равны 1;
3. Иногда бывает необходимо задать целечисленные ограничения на изменяемые ячейки.

Далее следует нажать кнопку Выполнить, после чего будет получено решение задачи о назначениях.

Довольно часто задача о назначениях бывает представлена в так называемом несбалансированном виде (количество работ не равно количеству работников). В этом случае для приведения задачи о назначениях к сбалансированному виду следует добавить в таблицу одну или несколько фиктивных работ или работников.

Скачать детально разобранный пример решения задачи о назначениях в Excel с использованием настройки Поиск решения с depositfiles

Ключевые слова: задача о назначениях, решение задачи о назначениях, Excel, поиск решения.