Лабораторная работа № 5 Постановка и решения задачи о назначении

Цель: Научиться составлять модели и решать задачи о назначении. Решение задачи о назначении (Венгерский алгоритм). Проверка решения с помощью Excel.

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

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

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

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

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

1. Неотрицательность значений изменяемых ячеек;

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

3. Иногда бывает необходимо задать целечисленные ограничения на изменяемые ячейки.

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

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