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

Цель работы:

Задача о назначениях является типичным примером оптимального принятия управленческих решений. Эта задача позволяет распределить объекты из некоторого множества по группе субъектов из другого множества и это распределение должно соответствовать оптимальности одного или нескольких итоговых показателей.

Рассмотрим несколько примеров.

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

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

Большая фирма переезжает в новое здание. Возникает необходимость распределить сотрудников по помещениям. С одной стороны, каждый сотрудник выдвигает определенные требования к своим соседям (например, предпочитает некурящих) и к расположению комнаты (например, вблизи от коллег по совместному проекту). С другой стороны, каждое помещение имеет определенные характеристики. Необходимо найти такой вариант распределения, при котором, по меньшей мере, не ухудшился бы психологический климат в коллективе

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

Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1.

Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:

1 этап:

1.Формализация проблемы в виде транспортной таблицы

2.В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки

3. Повторить ту же процедуру для столбцов

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю.

2 этап:

1. Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.

2. Зачеркнуть оставшиеся нулевые значения данного столбца

3. Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным

Если окажется, что имеется несколько нулей, которым не соответствуют назначения, и которые остались не зачёркнутыми, необходимо:

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

5. Зачеркнуть оставшиеся нули в данной строке

6. Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным

Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6

Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.

3 этап: (Если решение является недопустимым)

1. Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице

2. Найти наименьший из элементов, через которые не проходит ни одна прямая

3. Вычесть его из всех элементов, через которые не проходят прямые

4. Прибавить его ко всем элементам, лежащим на пересечении прямых

5. Элементы, через которые проходит только одна прямая, оставить неизменными

В результате в таблице появится как минимум одно новое нулевое значение.

Вернуться к этапу 2 и повторить решение заново.

Пример 9.1.

Компания имеет 4 сбытовых базы и 4 заказа, которые необходимо доставить потребителям. Складские помещения каждой из баз достаточны для размещения любого из этих заказов.

Составим транспортную таблицу.

База	Потребитель 1	Потребитель 2	Потребитель3	Потребитель 4
А
B
C
D

Вычтем минимальные элементы по строкам (выделены полужирным), получим новую таблицу:

База	Потребитель 1	Потребитель 2	Потребитель3	Потребитель 4
А
B
C
D

Повторим ту же процедуру для столбцов:

База	Потребитель 1	Потребитель 2	Потребитель3	Потребитель 4
А
B
C
D

Далее получаем

База	Потребитель 1	Потребитель 2	Потребитель3	Потребитель 4
А
B
C
D

База	Потребитель 1	Потребитель 2	Потребитель3	Потребитель 4
А
B
C
D

В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы (по диагонали – 68+60+35+45=208), это и будет минимальное решение данной задачи. Для решения такой же задачи на максимум, необходимо первоначальные значения умножить на (-1), после чего провести решение по приведенному выше алгоритму.

Пример 9.2. Решить задачу об оптимальном назначении с матрицей эффективностей A.

А=

Решение. Поскольку не указано, будем решать задачу на минимум (стандартная постановка). Решение будем искать венгерским методом.

Составляем исходную таблицу (матрицу):

Этап 1. В каждой строке ищем минимальный элемент (выделяем жирным в таблице) и отнимаем от всех элементов строки.

Теперь проводим аналогичную процедуру для всех столбцов: ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца. Получим:

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью.

Этап 2. Выбираем строку с одним нулем (строка №1), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №3). Выбираем строку с одним нулевым значением (строка №5), выделяем нуль. Выбираем строку с одним нулем (строка №3), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №4). Выбираем строку с одним нулем (строка №4), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №1).

Выбираем строку с одним нулевым значением (строка №2), выделяем нуль.